Программисты всегда были склонны мериться... ммм.... производительностью. На удовлетворение как раз этой насущной потребности и направлен проект The Computer Language Benchmarks Game. Идея проекта очень простая - имеется ряд задач различного плана, каждый желающий может предложить свою реализацию какой-либо задачи на своём любимом языке; далее эти реализации оцениваются на предмет производительности, читай — времени исполнения (а так же потребляемой памяти и объёма исходного кода). Текущая аппаратная платформа для тестирования — это Intel Core2Quad Q6600, в качестве ОС используется 32/64 битный Linux. Все результаты аккуратно складируются в базу данных, и посетитель сайта имеет возможность посмотреть различные «срезы» информации. Так же имеются такие занятные внешние исследования, как например это. Несколько дней назад я предложил свою реализацию задачи chameneos-redux для GCC C. Если кратко, то суть задачи сводится к следующему. Имеется «место встречи» и несколько одновременно работающих «хамелеонов». Каждый хамелеон «приходит» на место встречи и смотрит, первый ли он пришёл или его уже ждёт другой хамелеон. Если он пришёл первый, то он ждёт второго хамелеона. Если он пришёл второй, то оба хамелеона изменяют свои цвета (в зависимости от их текущих цветов) и уходят. И так по-кругу. Все остальные скучные детали задания можно видеть тут. На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды. Так же можно отметить: самая быстрая реализация на Java – 7 сек.; Scala – 15 сек.; Erlang – 111 сек.; Ruby — 131 сек.; Python — 221 сек. Полную таблицу можно видеть здесь. Результат моей реализации — 0.72 секунды. Кстати, на первый взгляд моя реализация очень похожа вот на эту реализацию на С++ - основной код реализации "встречи" практически идентичен. Однако, реализация на С++ выполняется 8.74 секунд, т.е. более чем в 12 раз медленнее. Что же позволило добиться столь высокого результата и обойти ближайшего соперника более чем в 6 раз? Задача достаточна интересна с точки зрения параллелизма (или точнее сказать concurrency, но для concurrency я не могу подобрать хорошего русского термина), т.к. фактически она требует не добавления как можно большего параллелизма, а наоборот сведения параллелизма к минимуму. Задача по своей сути требует постоянного взаимодействия потоков практически без какой-либо локальной работы потоков; а специфика современных многоядерных процессоров Intel такова, что взаимодействия потоков очень дороги. Поэтому оптимальная реализация будет использовать лишь один поток ОС и кооперативное планирование легковесных потоков поверх (именно поэтому реализация на Haskell [была] столь быстра — она использует кооперативное планирование легковесных потоков языка для реализации параллелизма; и именно поэтому же столь медленна реализация на Erlang – она пытается распределять хамелеонов по различным потокам ОС, рассчитывая, что они будут совершать какую-то локальную работу). Но, к сожалению, использование кооперативных потоков и собственных планировщиков запрещено правилами, а постоянное переключение ядерных потоков слишком дорого. Поэтому лучшее, что мы можем сделать, - это привязать потоки хамелеонов к двум (из четырёх) ядрам, это даёт нам возможность устраивать встречи без переключений ядерных потоков (один хамелеон работает на одном ядре, и параллельно второй хамелеон — на втором), и при этом свести конкуренцию за разделяемые ресурсы к минимуму. Итак, основные моменты реализации. 2. Минимально необходимое количество максимально лёгких взаимодействий. struct meeting_place_t { uintptr_t volatile state; }; При этом младшие 8 бит отводятся под индекс хамелеона, который ожидает на месте встречи; а оставшиеся биты используются для подсчёта кол-ва прошедших встреч. Вот (слегка упрощённый) код основной функции chameneos_func() (обратите внимание на использование интринсика компилятора GCC __sync_val_compare_and_swap()): state = place->state; for (;;) { peer_idx = state & CHAMENEOS_IDX_MASK; if (peer_idx) // уже кто-то ждёт? xchg = state - peer_idx - (1 << MEET_COUNT_SHIFT); else if (state) // нужно проводить встречи дальше? xchg = state | my_id; else // N встречь уже проведено break; prev = __sync_val_compare_and_swap(&place->state, state, xchg); if (prev == state) // CAS удался? { if (peer_idx == 0) { // сюда попадает "первый" хамелеон, пришедший на место встречи // ожидаем второго хамелеона (упрощено) while (chameneos->meeting_completed == 0) {} state = place->state; } else { // сюда попадает "второй" хамелеон, пришедший на место встречи // обмениваемся цветами с хамелеоном peer_idx (не показано) // и уведомляем его о завершении встречи peer->meeting_completed = 1; } } else { // CAS провалился, обновляем текущее состояние и пробудем повторить state = prev; } } 3. Эффективная реализация ожидания.
Поскольку мы отводим под потоки, участвующие во встрече, 2 ядра, и не
хотим постоянных переключений ядерных потоков, необходимо использовать
активное спин ожидание. Однако чисто активное спин ожидание будет плохо
работать в следующих случаях. Первый случай - допустим второй хамелеон
успешно приходит на место встречи, т.е. успешно выполняет
__sync_val_compare_and_swap(); но далее его поток вытесняется до того,
как он успевает уведомить первого. Первый хамелеон будет ждать в
активном спин-ожидании до конца своего кванта (~10мс), пока ОС не
вытеснит и его. Второй случай - допустим на машине периодически работают
какие-то сторонние процессы. Если сторонний процесс будет выполняться
на одном из наших ядер, то при каждой встрече первый хамелеон будет
ждать в активном спин-ожидании до конца своего кванта. spin_count = 20000; while (chameneos->meeting_completed == 0) { if (spin_count) spin_count -= 1; else sched_yield(); } Это даёт одновременно и минимальную латентность активного спин
ожидания и защиту от бесцельного съедания потоком всего кванта времени,
если что-то "пошло не так". На практике эта модификация дала прирост
производительности от 10% до 200% (в зависимости от загрузки машины
другими потоками), а так же существенно снизила дисперсию. 4. Устранение ложного разделения данных. #define CL_SIZE 64 void* cache_aligned_malloc(size_t sz) { char* mem; char* res; void** pos; mem = (char*)malloc(sz + 2 * CL_SIZE); if (mem == 0) exit(1); res = (char*)((uintptr_t)(mem + CL_SIZE) & ~(CL_SIZE - 1)); pos = (void**)(res - sizeof(void*)); pos[0] = mem; return res; } void cache_aligned_free(void* res) { void* mem; void** pos; assert(((uintptr_t)res & (CL_SIZE - 1)) == 0); pos = (void**)((char*)res - sizeof(void*)); mem = pos[0]; free(mem); } Вот, наверное, и всё. Вышеперечисленные 4 аспекта и позволили
получить более чем 12-ти кратное ускорение по-сравнению с "аналогичной"
программой на С++. Справедливости ради стоит заметить, что эти аспекты
никоим образом не связаны с С как таковым или компилятором GCC, они
связаны с исконным для С предоставлением доступа к низлежащему
аппаратному обеспечению и ОС, а так же с возможностью точно
контролировать раскладку и размещение объектов. С++ не уступает С в этих
аспектах. |
Home > In Russian >