Хамелеоны быстрые и очень быстрые

Программисты всегда были склонны мериться... ммм.... производительностью. На удовлетворение как раз этой насущной потребности и направлен проект 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 – она пытается распределять хамелеонов по различным потокам ОС, рассчитывая, что они будут совершать какую-то локальную работу). Но, к сожалению, использование кооперативных потоков и собственных планировщиков запрещено правилами, а постоянное переключение ядерных потоков слишком дорого. Поэтому лучшее, что мы можем сделать, - это привязать потоки хамелеонов к двум (из четырёх) ядрам, это даёт нам возможность устраивать встречи без переключений ядерных потоков (один хамелеон работает на одном ядре, и параллельно второй хамелеон — на втором), и при этом свести конкуренцию за разделяемые ресурсы к минимуму.

Итак, основные моменты реализации.

1. Оптимальное распределение потоков по ядрам.

По условию задачи необходимо провести две независимых серии встреч: первая — для 3 хамелеонов, вторая — для 10 хамелеонов. Т.к. было решено привязать все потоки хамелеонов, участвующих во встрече, только к двум ядрам, вырисовывается достаточно логичная схема: на двух ядрах проходит первая серия встреч, и параллельно на оставшихся двух ядрах — вторая серия встреч. Альтернативный вариант — последовательно провести первую и вторую серию встреч на всех четырёх ядрах; так поступили практически все реализации, которые используют физический параллелизм, однако при этом время выполнения увеличивается примерно в 5 раз.

К каким парам ядер привязывать потоки, относящиеся к одной встрече? Всё равно? Далеко не всё равно! Процессор Q6600 уникален тем, что это фактически 2 независимых двух-ядерных процессора, объединенных на одной подложке, и соединённых между собой шиной. Соответственно и стоимость взаимодействия между разными парами ядер существенно различается. Потоки, относящиеся к одной встрече, должны быть привязаны к одному «подпроцессору» в составе Q6600.

ОС Linux тут преподносит свои сюрпризы. Наивное предположение, что смежные ядра являются логическими процессорами 0 и 1 (2 и 3) было сразу развеяно временем выполнения в 3 секунды. Беглый просмотр кода ядра показал, что загрузочный код вычитывает порядок ядер откуда-то из BIOS'а, и потом остальная часть ядра сама слабо представляет топологию процессора. На тестовой машине смежные ядра оказались логическими процессорами 0 и 2 (1 и 3). Однако единственный интерфейс, через который можно получить эту информацию от ядра, есть парсинг текстового файла /proc/cpuinfo (см. функцию get_affinity()).

2. Минимально необходимое количество максимально лёгких взаимодействий.

Условие задачи требует как минимум 3 взаимодействий между потоками (читай — модификаций разделяемых данных) для проведения одной встречи: (1) первый хамелеон сообщает, что он пришёл первый, (2) второй хамелеон сообщает первому, что тоже пришёл (и обмениваются цветами), (3) хамелеоны освобождают место встречи. Так же необходимо вести подсчёт общего числа прошедших встречь, т.к. необходимо завершить работу после совершения N встреч.

Я закодировал место встречи одним машинным словом:

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. Устранение ложного разделения данных.

На уровне процессора разделение данных происходит не на уровне отдельных байт или слов памяти, а на уровне кэш-линий. Кэш-линия обычно содержит несколько машинных слов, на современных процессорах кэш-линии обычно бывают в диапазоне 16-512 байт, на современных процессорах Intel x86 (IA-32/Intel64) кэш-линия равна 64 байтам. Т.о. если какие-либо две переменные оказываются расположенными в одной кэш-линии (ложное разделение, false sharing), доступы к ним из разных потоков будут приводить к физической передаче данных между ядрами, что является очень медленным - порядка 100-500 таков в зависимости от модели процессоров, характеристик соединителя и топологии. Одним словом - этого допускать нельзя.

Для устранения любой возможности ложного разделения данных я реализовал простую обёртку над функциями управления динамической памятью, и выделяю все структуры данных (хамелеонов и место встречи) с помощью них. Идея очень проста - функция выделения памяти округляет адрес блока памяти вверх до ближайшей границы кэш-линии:

#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, они связаны с исконным для С предоставлением доступа к низлежащему аппаратному обеспечению и ОС, а так же с возможностью точно контролировать раскладку и размещение объектов. С++ не уступает С в этих аспектах.

Ничто не бесплатно в нашем мире, вместе с возросшей производительностью увеличился и объём исходного кода. Моя реализация примерно в 4 раза больше реализаций на Haskell и Erlang, и примерно в 1.5 раза больше других реализаций на С/С++. Не последнюю роль в этой сыграл мягко говоря странный интерфейс Linux для получения топологии системы в виде парсинга текстового файла (при использовании Windows этот код был бы не нужен, так же как и функции cache_aligned_malloc()/cache_aligned_free() - они уже встроены в ран-тайм MS Visual C++).