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

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

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

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

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

E>>Здравствуйте, minorlogic, Вы писали:
M>>>Кстати , какие причины столь тормознутой реализации на Erlang? который вроде и был задуман для таких задач ?
E>>Re[2]: Хамелеоны быстрые и очень быстрые

Автор: remark
Дата: 19.09.09

тут написано почему Erlang столь медленный на этой задаче, если я правильно понял, Erlang создает легковесные потоки, которые прекрасно подходят для распараллелевания вычислений, а здесь ботлнек в доступе к разделяемым ресурсам.

M>Так это и поражает, легковесные потоки в Эрланге не являются потоками системы, точнее не обязаны ими быть. Поэтому казалось бы что на подобных задачах Эрланг должен как минимум быть удовлетворительным.

Случай, когда легковесные потоки не являются ядерными, можно видеть здесь:
http://shootout.alioth.debian.org/u32/benchmark.php?test=chameneosredux&lang=all
и тут Эрланг действительно показывает "удовлетворительный" результат в 8.3 секунды

А вот когда легковесные потоки становятся ядерными:
http://shootout.alioth.debian.org/u32q/benchmark.php?test=chameneosredux&lang=all
время уже становится 111 секунд.

Т.е. проблема не в легковесных потоках, проблема в том, что взаимодействие между действительно параллельными потоками очень дорого в Эрланг. Этому будет подвержена любая программа на Эрланг, в которой процессы более-менее часто взаимодействуют между собой. А это как раз то, к чему призывает философия Эрланг — дескать процессы и обмен сообщениями легковесные, так что используйте их по полной.

Кстати, по поводу "удовлетворительного" результата с легковесными потоками. Моя реализация показывает в такой ситуации 10.4 секунды, но каждое взаимодействие есть честное переключение ядерного потока ОС (при ожидании я всегда делаю sched_yield()). Т.е. "легковесные" Эрланг потоки легче честных ядерных потоков всего на 25%, вот и судите несколько они "легковесные", и насколько разница в 25% может порождать другой стиль программирования.

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

M>Ок, тогда я могу представить этот бенчмарк как очень синтетический расчитанный на взаимодействие потоков.

Я думаю, что да, такой взгляд вполне законен. Языки соревнуются в возможностях низкоуровневого взаимодействия.
С одной стороны можно сказать, что это и так понятно, что С/C++ обладает самыми развитыми возможностями, а языки типа Ruby вообще не предназначены для этого (никто не будет писать на них ран-таймы других серьёзных языков). Но с другой стороны всё равно полезно увидеть конкретные цифры, а не оперировать эпитетами. По-крайней мере можно дать ответы на 2 вопроса. Первый — некоторые языки предоставляют меньше возможностей (Java/С#), а другие совсем мало (Python), насколько конкретно они медленнее за счёт этого? Второй — некоторые языки предоставляют совсем другие модели программирования и примитивы (Haskell, Erlang), как они (эти другие модели и примитивы) сопоставляются по производительности с С/C++?


M>Меня настораживает опасность того что этот бенчмарк будет быстрее работать реализованным однопоточно на десктопной машине, я ошибаюсь?

Я думаю, что да. Я думаю, что самый быстрый вариант будет реализовать хамелеонов в стиле легковесных потоков, и применить кооперативное планирование, когда поток сам указывает на какой поток переключиться (в стиле fibers Windows), и запустить их на 1 ядерном потоке. Когда первый хамелеон приходит на место встречи, он переключается на произворльного другого; когда второй хамелеон приходит на место встречи, он переключается на первого, что бы завершить встречу. Соотв. никакой синхронизации тут не надо будет вообще.
Но хотя 2 встречи всё равно можно проводить параллельно на 2 ядерных потоках.


M>Оченья тяжело следить за гранью когда бенчмарк остается корректным.

Да, это общая проблема. Бенчмарк сам-то всегда остаётся корректным, проблема в том на сколько, в какой степени и каких ещё задач можно обобщить его результаты.
Но честно говоря, в данном случае меня это не сильно волновало. Я просто ставил цель реализовать задачу так как она поставлена.

M>P.S. Как насчет тестов с процем с боольшим к-вом ядер , от 8 и более ?

Ну на мою реализацию (так же как и на реализацию на Haskell) это никак не повлияет, т.к. она жёстко использует только 2 ядра. Большинство остальных реализаций, которые [пытаются] использовать все ядры будут работать ещё медленнее.
Резонный вопрос — как же для этой задачи получить выгоду от большего числа ядер? Ответ — никак.

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

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

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

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

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

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

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

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

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

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

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

Здравствуйте, 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».

Здравствуйте, 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>

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

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

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

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

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

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

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

YSS>Если верить манам, то начиная с версии 2.1.91 glibc, т.е. 2000-2001 года.

Спасибо. Может в ближайшем будущем портирую программу на С++, там попробую использовать эти функции.


YSS>Кстати респект за реализацию, и вопрос вдогонку: сильно ли будут отличаться результаты при другой привязке нитей к ядрам,

Изначально моя реализация проводила 2 встречи последовательно, т.е. использовались только 2 ядра. Когда я привязывал потоки к ядрам 0 и 1, время выполнения было 4.8 сек. Когда я привязал потоки к ядрам 0 и 2, время выполнения стало 1.2 сек. Т.е. разница в 4 раза, много это или мало — судите сами.


YSS>и если так — почему тогда эти две группы ядер не объедены в numa-ноды, для выяснения их структуры есть удобный интерфейс в линуксе.

В NUMA узлы они не объединены, т.к. это не NUMA узлы. NUMA узла характеризуются различным временем доступа к памяти, для ядер в составе Q6600 это не так, т.е. время доступа к любой памяти с любого ядра одинакового. Зато отличается стоимость взаимодействия между ядрами. На последних процессорах Intel в составе ядра так же имеются 2 HT потока, это совсем другая песня. Мешать всё это в одну кучу нельзя, т.к. структура системы/связей не однородная. Допустим есть программа, в которой потоки мало взаимодействуют между собой, но зато постоянно работают с различными объектами в памяти; для такой программы необходимо определить структру NUMA узлов, а ядра и HT потоки не интересны. В другой программе потоки постоянно взаимодействуют между собой, и этой программе уже нужно различать ядра. Другая программа производит вычисления и с фиксированной точкой и с плавающей, ей было бы полезно знать какие логические процессоры являются HT потоками-близнецами, а ядра и NUMA узлы ей не нужны.
Почему будет не достаточно введение лишь одной метрики (абстрактной «удалённости» между логическими процессорами)? Традиционная оптимизация для NUMA машин — это создание пулов памяти для каждого NUMA узла. Если мы будем знать только абстрактную удалённость между процессорами, то нам придётся создавать больше пулов, чем это необходимо. Соответственно будет больше потребление памяти и больше издержки на передачу блоков памяти между пулами. Другой пример — программа производит вычисления и с фиксированной точкой и с плавающей, для неё целесообразно проводить разнотипные вычисления на HT потоках-близнецах; если же HT потоков нет в системе, то наоборот сгруппировать вычисления по типу, т.к. однотипные вычисления работают с одними данными (допустим на одном многоядерном процессоре — целочисленные, а на другом — с плавающей точкой). Очевидно, что это не укладывается в модель лишь с одной метрикой удалённости.


YSS>Просто как-то логично привязываться к структуре памяти, а вот к структуре кэшей — imho перебор.

Это зависит.
Во-первых, различие при неправильной привязке я уже озвучил.
Во-вторых, кто-то может вам совершенно законно сказать — просто как-то логично оптимизировать IO, а вот привязываться к структуре памяти — перебор.
С т.з. производительности систему можно представить иерархически (в смысле издержек) следующим образом:
IO (disk/network) ↔ Memory ↔ Cache ↔ Processor
Первая задача при оптимизации — выявить наивысший уровень, который является слабым звеном. Почему наивысший? Потому что там можно получить наибольший выигрыш, или даже правильнее сказать — потому что только там и можно получить хоть какой-то выигрыш. Бессмысленно оптимизировать под процессор (распределение регистров, спец. команды), когда есть проблемы с IO. Бессмысленно оптимизировать требования по пропускной способности кэш↔процессор, когда требования по пропускной способности память↔кэш слишком высоки. Зато для каких-то функций обработки массивов данных самый подходящий уровень оптимизации может быть даже не кэш, а процессор.
В общем, нет такого, что всегда надо оптимизировать Х. Оптимизировать надо то, что является узким местом и за счёт чего можно получить выигрыш. Для данной задачи — это латентность взаимодействия между ядрами.
В-третьих, для некоторых задач/программ привязка к структуре памяти не даст вообще ничего, а привязка к кэшам даст. Т.е. строго говоря тут даже нет строгого отношения "превосходства" между ними, в смысле что вначале надо оптимизировать привязку к памяти и только потом — кэши.

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

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

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

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

С:\С++

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

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

А мы с Шериданом кто? Но мы лучше поругаем MS Windows за кривые способы получения топологии процессоров на очень многопроцессорных системах. ;-)

Здравствуйте, 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

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

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

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

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

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


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

C\\C++

Здравствуйте, 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 на этом тесте самый быстрый, и С/С++ не могли его перебить, хотя множество апологетов языков постоянно улучшают реализации на своих любимых языках.

RO>Майкрософт предпочитает создавать дополнительные вызовы — наверное потому, что у них нет специальных файловых систем.

впрочем, могли бы и задействовать \\.\ для этой цели.

Приветствую, remark, вы писали:
r>

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

R>На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды.

Если в твоей программе заменить #include <stdlib.h> на #include <cstdlib>, то C++ тоже обгонит Haskell.

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

R>На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды. Так же можно отметить: самая быстрая реализация на Java – 7 сек.; Scala – 15 сек.; Erlang – 111 сек.; Ruby — 131 сек.; Python — 221 сек. Полную таблицу можно видеть здесь.

Кстати , какие причины столь тормознутой реализации на Erlang? который вроде и был задуман для таких задач ?

Ок, тогда я могу представить этот бенчмарк как очень синтетический расчитанный на взаимодействие потоков.

Меня настораживает опасность того что этот бенчмарк будет быстрее работать реализованным однопоточно на десктопной машине, я ошибаюсь?
Оченья тяжело следить за гранью когда бенчмарк остается корректным.

P.S. Как насчет тестов с процем с боольшим к-вом ядер , от 8 и более ?

Здравствуйте, minorlogic, Вы писали:
M>Кстати , какие причины столь тормознутой реализации на Erlang? который вроде и был задуман для таких задач ?
Re[2]: Хамелеоны быстрые и очень быстрые

Автор: remark
Дата: 19.09.09

тут написано почему Erlang столь медленный на этой задаче, если я правильно понял, Erlang создает легковесные потоки, которые прекрасно подходят для распараллелевания вычислений, а здесь ботлнек в доступе к разделяемым ресурсам.

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

E>Здравствуйте, minorlogic, Вы писали:
M>>Кстати , какие причины столь тормознутой реализации на Erlang? который вроде и был задуман для таких задач ?
E>Re[2]: Хамелеоны быстрые и очень быстрые

Автор: remark
Дата: 19.09.09

тут написано почему Erlang столь медленный на этой задаче, если я правильно понял, Erlang создает легковесные потоки, которые прекрасно подходят для распараллелевания вычислений, а здесь ботлнек в доступе к разделяемым ресурсам.

Так это и поражает, легковесные потоки в Эрланге не являются потоками системы, точнее не обязаны ими быть. Поэтому казалось бы что на подобных задачах Эрланг должен как минимум быть удовлетворительным.

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

CC>>А не дай б-г, эту статью увидят завсегдатаи КСВ
RO>А мы с Шериданом кто?
Я про других завсегдатаев. Про тех, у которых любое не негативное упоминание С++ вызывает острую дисфункцию настроения мыслей и обильное разлитие желчи.

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

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

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

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

R>

Если верить манам, то начиная с версии 2.1.91 glibc, т.е. 2000-2001 года.

Кстати респект за реализацию, и вопрос вдогонку: сильно ли будут отличаться результаты при другой привязке нитей к ядрам, и если так — почему тогда эти две группы ядер не объедены в numa-ноды, для выяснения их структуры есть удобный интерфейс в линуксе. Просто как-то логично привязываться к структуре памяти, а вот к структуре кэшей — imho перебор.

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

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

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

Вот набираю у себя:

[user home]$ cd /sys
[user sys]$ ls
class
[user sys]$

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

RO>Интел: «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».


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

Хотя там же выше человек приводит:

Windows CPU #0 -> AffinityMask = 1; Initial APIC = 0 ...
Windows CPU #1 -> AffinityMask = 2; Initial APIC = 4 ...
Windows CPU #2 -> AffinityMask = 4; Initial APIC = 12 ...
Windows CPU #3 -> AffinityMask = 8; Initial APIC = 8 ...
Windows CPU #4 -> AffinityMask = 16; Initial APIC = 2 ...

Что видимо есть реальный вывод утилиты на его компьютере...

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

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

Значит, всё же подмонтирована, раз class есть. Посмотри еще вывод mount(1), там точно будет sysfs.

Судя по всему, речь о виртуальной машине, вот почему в /sys только class (хотя там обычно 10 поддиректорий). Так обычно бывает в Virtuozzo/OpenVZ, в то время как Xen предоставляет полномасштабную sysfs.

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

А если там 256 процессоров, то как они нумеруются? Тем более, ты сам сказал, что никаких гарантий нет, может, на экзотических платформах нумерация и иная.

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

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

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

RO>Значит, всё же подмонтирована, раз class есть. Посмотри еще вывод mount(1), там точно будет sysfs.

RO>Судя по всему, речь о виртуальной машине, вот почему в /sys только class (хотя там обычно 10 поддиректорий). Так обычно бывает в Virtuozzo/OpenVZ, в то время как Xen предоставляет полномасштабную sysfs.

Да, речь об одной из этих виртуальных машин. Уже повод, что бы пользоваться /proc/cpuinfo.


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

RO>А если там 256 процессоров, то как они нумеруются?

А в чём проблема? От 0 до 255.

RO>Тем более, ты сам сказал, что никаких гарантий нет, может, на экзотических платформах нумерация и иная.

Может.

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

R>Да, речь об одной из этих виртуальных машин. Уже повод, что бы пользоваться /proc/cpuinfo.

В виртуальных машинах как-то не ставится цель выжать еще пару процентов производительности :-)

RO>>А если там 256 процессоров, то как они нумеруются?
R>А в чём проблема? От 0 до 255.

Это-то понятно (разве что маску будет сложно уминать в 64-битное битовое поле), а вот в каком порядке пронумеруются — уже другой вопрос.

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

RO>>>А если там 256 процессоров, то как они нумеруются?
R>>А в чём проблема? От 0 до 255.

RO>Это-то понятно (разве что маску будет сложно уминать в 64-битное битовое поле), а вот в каком порядке пронумеруются — уже другой вопрос.

Версии до Windows7 не поддерживают больше 32/64 процессоров. В Windows7 используются т.н. группы процессоров для обхода этого ограничения. Все легаси приложения будут назначены на группу 0, т.е. не будут использовать более 32/64 процессоров. А новые приложения могут использовать все процессоры путём использования пары (группа, маска внутри группы). Как следствие нельзя задать аффинити маску, которая содержит процессоры из разных групп; т.е. процесс/поток можно привязать только к каким-то процессорам внутри одной группы. Количество групп будет минимальным, т.е. если в системе не больше 32/64 процессоров, то группа будет только одна. В Windows7 количество групп ограничено 4-мя, т.е. максимальное кол-во процессоров 256, в следующих версиях максимальное кол-во групп будет увеличено.

Ну а по поводу нумерации, наверное всё же более корректно использовать API для установления топологии, а не зашивать её жёстко. Просто хотелось бы хоть одним глазком поглядеть на такую Windows машину, где нумерация идёт не согласно топологии.

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

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

R>>На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды.

I>Если в твоей программе заменить #include <stdlib.h> на #include <cstdlib>, то C++ тоже обгонит Haskell.

Я наверное её портирую на С++ в скором времени.

Любопытно , 8 секнд это конечно не 111 и я бы назвал такой результат удовлетворительным.

Вполне возмможно, что его можно улучшить хорошо поработав над реализацией.

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

M>Любопытно , 8 секнд это конечно не 111 и я бы назвал такой результат удовлетворительным.

Но это только если запускать на одноядерной машине. Вероятность этого мала и уменьшается с каждым днём.

M>Вполне возмможно, что его можно улучшить хорошо поработав над реализацией.

Я честно говоря не знаю, можно ли там что-то существенно улучшить. Но я уверен, что над реализацией трудился не один человек, и что они определенно имели целью показать высокую производительность.

Здравствуйте, remark, Вы писали:
R>Я думаю, что самый быстрый вариант будет реализовать хамелеонов в стиле легковесных потоков, и применить кооперативное планирование...
Я тут, кcтати, наборосал прототипчик оного для scheme (plt). Не выводит всякой сервисной информации по заданию, довольно криво обыгран момент смены цветов и нет случайности в шедулинге, но вот как-то так:
http://paste.lisp.org/+1VLE

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


WH>Ибо в реальных задачах такой дикой конкуренции за общий ресурс не встречается. Тк нормальные люди всеми силами стараются такого избежать.
Возражения непонятны. Модельная задача на то и модельная, что берет один аспект взаимодействия и доводит его до абсурда. Я вроде нигде и не утверждал, что система, плохо показавшая себя на этом тесте непригодна, я собственно отвечал на вопрос "много ли бывает ситуаций когда требуется паралелить задачи не требующие выч. ресурсов", на мой взгляд сотни потоков, ожидающие на IO — вполне пример такой ситуации. Да и кстати многие сугубо вычислительные задачи могут создавать подобные ситуации — например ресурсом, за который конкурируют, может оказаться память.

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

SC>Возражения непонятны. Модельная задача на то и модельная, что берет один аспект взаимодействия и доводит его до абсурда. Я вроде нигде и не утверждал, что система, плохо показавшая себя на этом тесте непригодна,
Дело в том что как только появляются хоть какие то заметные вычисления или ожидание IO то все описанные remark'ом эффекты становятся не видимыми даже в микроскоп.

SC>я собственно отвечал на вопрос "много ли бывает ситуаций когда требуется паралелить задачи не требующие выч. ресурсов", на мой взгляд сотни потоков, ожидающие на IO — вполне пример такой ситуации.
Ни разу не такая.

SC>Да и кстати многие сугубо вычислительные задачи могут создавать подобные ситуации — например ресурсом, за который конкурируют, может оказаться память.
Назови хоть одну вычислительную задачу при грамотной реализации которой будет большая конкуренция при записи в память. Конкуренция на чтение не проблема.

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


SC>>Возражения непонятны. Модельная задача на то и модельная, что берет один аспект взаимодействия и доводит его до абсурда. Я вроде нигде и не утверждал, что система, плохо показавшая себя на этом тесте непригодна,
WH>Дело в том что как только появляются хоть какие то заметные вычисления или ожидание IO то все описанные remark'ом эффекты становятся не видимыми даже в микроскоп.
Я еще раз говорю, мое сообщение относится к сообщению remark'а только косвенно, я отвечал на фразу "много ли бывает ситуаций когда требуется паралелить задачи не требующие выч. ресурсов"

SC>>Да и кстати многие сугубо вычислительные задачи могут создавать подобные ситуации — например ресурсом, за который конкурируют, может оказаться память.
WH>Назови хоть одну вычислительную задачу при грамотной реализации которой будет большая конкуренция при записи в память.
Нормальная реализация это я так понимаю такая, которая не создает большой нагрузки на память?
А если серьезно — разреженная линейная алгебра, какой-нибудь swarm intelligence и прочее, где потоков теоретически может быть много, но действия, которые выполняются каждым потоком — относительно простые. Стоит вспомнить, что вычислительные устройства тоже бывают разные.

WH> Конкуренция на чтение не проблема.
интересно, почему.

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

SC>Я еще раз говорю, мое сообщение относится к сообщению remark'а только косвенно, я отвечал на фразу "много ли бывает ситуаций когда требуется паралелить задачи не требующие выч. ресурсов"
Вот я тебе и говорю что таких задач не бывает.
Ожидание IO это совершенно другая история.

SC>Нормальная реализация это я так понимаю такая, которая не создает большой нагрузки на память?
Это та которая сводит запись в одно и тоже место памяти и нескольких потоков к мнимому.

SC>А если серьезно — разреженная линейная алгебра, какой-нибудь swarm intelligence и прочее, где потоков теоретически может быть много, но действия, которые выполняются каждым потоком — относительно простые. Стоит вспомнить, что вычислительные устройства тоже бывают разные.
Все опять мимо. Этим задачам не нужно писать из нескольких потоков в одно место памяти.
А если объемы действительно большие то там вырисовывается кластер и алгоритмы типа map reduce
Если же появляется что-то на подобии сабжевой задачки то это значит что решение нихрена не масштабируется.

WH>> Конкуренция на чтение не проблема.
SC>интересно, почему.
По тому что если память только читают то одна и та же линейка кеша может лежать в кеше нескольких ядер.
А если появляется запись ядро должно захватить линейку кеша эксклюзивно.

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

SC>>Нормальная реализация это я так понимаю такая, которая не создает большой нагрузки на память?
WH>Это та которая сводит запись в одно и тоже место памяти и нескольких потоков к мнимому.
Так кто бы спорил

SC>>А если серьезно — разреженная линейная алгебра, какой-нибудь swarm intelligence и прочее, где потоков теоретически может быть много, но действия, которые выполняются каждым потоком — относительно простые. Стоит вспомнить, что вычислительные устройства тоже бывают разные.
WH>Все опять мимо. Этим задачам не нужно писать из нескольких потоков в одно место памяти.
Зачем в одно, в разные, но например попадающие в одну линейку кэша. Или кэша вообще может не быть. Или все прекрасно, но шина не резиновая и из-за этого часть процессоров получает некислую задержку выполнения. В любом вычислительном устройстве рано или поздно что-то кончается, а это и есть ситуация конкуренции за ресурс.

WH>А если объемы действительно большие то там вырисовывается кластер и алгоритмы типа map reduce
WH>Если же появляется что-то на подобии сабжевой задачки то это значит что решение нихрена не масштабируется.
Да, значит, но не значит, что оно не существует.

WH>>> Конкуренция на чтение не проблема.
SC>>интересно, почему.
WH>По тому что если память только читают то одна и та же линейка кеша может лежать в кеше нескольких ядер.
WH>А если появляется запись ядро должно захватить линейку кеша эксклюзивно.
Верно только если все потоки читают ограниченный, хорошо распределенный по линейкам кэша набор адресов.