Программисты всегда были склонны мериться... ммм.... производительностью. На удовлетворение как раз этой насущной потребности и направлен проект 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++).

Здравствуйте, remark, Вы писали:

R>Не последнюю роль в этой сыграл мягко говоря странный интерфейс Linux для получения топологии системы в виде парсинга текстового файла (при использовании Windows этот код был бы не нужен, так же как и функции cache_aligned_malloc()/cache_aligned_free() — они уже встроены в ран-тайм MS Visual C++).

А почему бы не использовать posix_memalign ?

The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr. The address of the allocated memory will be a multiple of alignment, which must be a power of two and a multiple of sizeof(void *).

Ей уже 10 лет как-никак, должна быть в том линуксе.

The posix_memalign() function is added for alignment with IEEE Std 1003.1d-1999.

R>

Здравствуйте, remark, Вы писали:

R>мягко говоря странный интерфейс Linux для получения топологии системы в виде парсинга текстового файла

Можно еще посмотреть в /sys/devices/system/cpu/cpuN/topology, там парсить не нужно. Странности, наверное, оттого, что надо поддерживать системы с тысячами процессоров, NUMA и т. п., где топология может быть очень сложной.

R>при использовании Windows этот код был бы не нужен

А как бы это там выглядело?

Здравствуйте, Roman Odaisky, Вы писали:

R>>при использовании Windows этот код был бы не нужен

RO>А как бы это там выглядело?

http://msdn.microsoft.com/en-us/library/ms683213(VS.85).aspx
http://msdn.microsoft.com/en-us/library/ms686253(VS.85).aspx

Здравствуйте, Roman Odaisky, Вы писали:

R>>при использовании Windows этот код был бы не нужен

RO>А как бы это там выглядело?

плюс еще http://msdn.microsoft.com/en-us/library/ms683194(VS.85).aspx

Важна ли такая задача на практике? много ли бывает ситуаций когда требуется паралелить задачи не требующие выч. ресурсов ?

Можгно я скажу?
Мы и так знаем что C\C++ это самые производительные языки. Сию статью надо в другие форумы укладывать

Можгно я скажу?
Мы и так знаем что C\C++ это самые производительные языки. Сию статью надо в другие форумы укладывать

Здравствуйте, minorlogic, Вы писали:

M>Важна ли такая задача на практике? много ли бывает ситуаций когда требуется паралелить задачи не требующие выч. ресурсов ?

Дофига, обычно как бывает: n потоков что-то считают, k — что-то рисуют, j — общаются по сети, m — пишут на диск, p — делают что-то еще очень важное. При этом большая часть потоков немалую часть времени тупо ждет и тем не менее необходимо максимизировать общий throughput системы. Это ИМХО гораздо более распространенная ситуация, чем когда нужно просто распараллелить вычислительную задачу.

Здравствуйте, Sheridan, Вы писали:

S>Можгно я скажу?
S>Мы и так знаем что C\C++ это самые производительные языки. Сию статью надо в другие форумы укладывать
Ой таки не надо. Тут как раз сидят люди, которые информацию из статьи способны применить на благо.
А не дай б-г, эту статью увидят завсегдатаи КСВ — это ж какой шуфель говна в вентилятор будет заброшен...

Здравствуйте, Sheridan, Вы писали:

S>Мы и так знаем что C\C++ это самые производительные языки. Сию статью надо в другие форумы укладывать

А точно не C/C++ ?

Здравствуйте, hexamino, Вы писали:

H>Здравствуйте, Sheridan, Вы писали:

S>>Мы и так знаем что C\C++ это самые производительные языки. Сию статью надо в другие форумы укладывать

H>А точно не C/C++ ?

С:\С++

Здравствуйте, hexamino, Вы писали:


S>>Мы и так знаем что C\C++ это самые производительные языки. Сию статью надо в другие форумы укладывать
H>А точно не C/C++ ?

C\\C++

Здравствуйте, Sergey Chadov, Вы писали:

M>>Важна ли такая задача на практике? много ли бывает ситуаций когда требуется паралелить задачи не требующие выч. ресурсов ?
SC>Дофига, обычно как бывает:
Правда? Давай прикиним:

SC>n потоков что-то считают,
Вычисления.

SC>k — что-то рисуют,
А рисуют это что по твоему?
Правильно. Вычисления.

SC>j — общаются по сети, m — пишут на диск,
Ожидание IO. Те шедуллер усыпляет поток пока не придет прерывание от железки.

SC>p — делают что-то еще очень важное.
Что именно что не сводится к вычислениям или IO?

SC>При этом большая часть потоков немалую часть времени тупо ждет и тем не менее необходимо максимизировать общий throughput системы. Это ИМХО гораздо более распространенная ситуация, чем когда нужно просто распараллелить вычислительную задачу.
Ага. Только к этому тесту отношения не имеет.
Ибо в реальных задачах такой дикой конкуренции за общий ресурс не встречается. Тк нормальные люди всеми силами стараются такого избежать.
А если задача совсем реальная то там кластер вырисовывается со всеми вытекающими.

Здравствуйте, Sergey Chadov, Вы писали:

SC>Здравствуйте, minorlogic, Вы писали:

M>>Важна ли такая задача на практике? много ли бывает ситуаций когда требуется паралелить задачи не требующие выч. ресурсов ?

SC>Дофига, обычно как бывает: n потоков что-то считают, k — что-то рисуют, j — общаются по сети, m — пишут на диск, p — делают что-то еще очень важное. При этом большая часть потоков немалую часть времени тупо ждет и тем не менее необходимо максимизировать общий throughput системы.

Это и есть вычисления или ожидания некого события. В описанный выше сценарий не вписывется.

SC>Это ИМХО гораздо более распространенная ситуация, чем когда нужно просто распараллелить вычислительную задачу.
Опишите тогда что есть вычислительная задача?

Здравствуйте, IID, Вы писали:

IID>А почему бы не использовать posix_memalign ?

Спасибо, попробую использовать, если буду делать какие-то патчи.
Кто-нибудь в курсе, она во всех линуксах по-умолчанию? А то про тестовую машину я узнаю только после попытки сабмита.

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, remark, Вы писали:

R>>мягко говоря странный интерфейс Linux для получения топологии системы в виде парсинга текстового файла

RO>Можно еще посмотреть в /sys/devices/system/cpu/cpuN/topology, там парсить не нужно. Странности, наверное, оттого, что надо поддерживать системы с тысячами процессоров, NUMA и т. п., где топология может быть очень сложной.

Для этого требуется маунт sysfs, которая по-умолчанию незамаунчена на линуксах.
Я не думаю, что это связано с требованием поддержки сложных топологий, скорее просто идеология. В Windows это решено достаточно элегантно и практично, функция GetLogicalProcessorInformation (к сожалению она доступна только начиная с Vista).

R>>при использовании Windows этот код был бы не нужен

RO>А как бы это там выглядело?

Насколько я знаю, Windows при нумерации логических процессоров всегда следует топологии. Поэтому там просто можно привязывать потоки к процессорам 0 и 1.

Здравствуйте, Sheridan, Вы писали:

S>Можгно я скажу?
S>Мы и так знаем что C\C++ это самые производительные языки. Сию статью надо в другие форумы укладывать

Я положил сюда просто потому что моя реализация на С.
А по поводу производительности сложно сказать. Длтельное время считалось, что Haskell на этом тесте самый быстрый, и С/С++ не могли его перебить, хотя множество апологетов языков постоянно улучшают реализации на своих любимых языках.

Здравствуйте, minorlogic, Вы писали:

M>Важна ли такая задача на практике? много ли бывает ситуаций когда требуется паралелить задачи не требующие выч. ресурсов ?

Такие задачи определенно есть.
В идеале, конечно, задача разбивается на очень много больших независимых кусков, и тогда характеристики системы поддержки параллелизма практически не влияют на свойства системы (просто так как она задействуется крайне редко). Но этого не всегда удаётся добиться.
Самый показательный пример — ран-таймы языков и библиотек поддержки параллелизма. Свойства ран-тайма напрямую влияют на стиль кодирования. Допустим у нас есть агентно-ориентированная система (типа Эрланг). Производим *естественную* декомпозицию прикладной задачи. Далее вопрос — обеспечит ли наш ран-тайм приемлемое функционирование системы при такой декомпозиции? В смыле, что оверхед вносимый ран-таймом будет допустимым. Если обеспечит — замечательно. Не обеспечит — у нас проблемы, нам придётся перепроектировать систему уже не столь естественным образом, а каким-то искуственным, что бы побороть оверхеды ран-тайма.
Например, это свойственно для многих систем моделирования. Если проводить естественную декомпозицию системы (1 элемент предметной области — 1 агент), зачастую оверхеды оказываются неприемлемыми. За примером далеко ходить не надо — допустим мы хотим смоделировать эту задачу о хамелеонах с помощью Эрланг, результат такой попытки можно видеть в таблице.
Речь естественно идёт не о полном отсутствии полезной локальной работы, а о том какой минимальный размер локальной работы позволяет иметь система.

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

Сюда же такие вещи как базы данных и middlewre. При наличии, допустим, 16/32 физических процессоров (что уже практически сегодняшний день), конкуренция за центральные структуры данных может быть очень высокой (читай — отсутствие локальной работы).

В целом, это, конечно, не удел прикладного программирования. Но в системном программировании область применения значительна.

Здравствуйте, remark, Вы писали:

R>Для этого требуется маунт sysfs, которая по-умолчанию незамаунчена на линуксах.

Странно, еще не видел ни одного линукса без /sys, разве что embedded.

R>Я не думаю, что это связано с требованием поддержки сложных топологий, скорее просто идеология. В Windows это решено достаточно элегантно и практично, функция GetLogicalProcessorInformation (к сожалению она доступна только начиная с Vista).

Я так понимаю, это еще одна иллюстрация разных подходов к выдаче ядерных данных в пространство пользователя: Юниксы используют специальные файловые системы, потому что это проще в расширении, а Майкрософт предпочитает создавать дополнительные вызовы — наверное потому, что у них нет специальных файловых систем. Они ведь уже успели создать GetLogicalProcessorInformationEx, интересно, как они назовут следующую версию этой функции?

R>Насколько я знаю, Windows при нумерации логических процессоров всегда следует топологии. Поэтому там просто можно привязывать потоки к процессорам 0 и 1.

Интел: «Affinity mask is a construct of the OS. Within the Microsoft Windows® XP code base, each different OS release may have an internal implementation that tries to optimize thread scheduling by the OS scheduler according to certain hardware configurations that the OS understands as that particular release was designed. To say this simply, the numerical mapping can vary even within an OS family. There is no guarantee, for example, „AffinityMask = 1; Initial APIC = 0“ must be true».