Плохо параллелится код с std::unordered_map

Через неделю попробую.

Предлагаю заменить вектор на std::deque.

Практически не помогло, разница по сравнению с вектором в десятки процентов, максимальный профит с распараллеливания - стало быстрее на 20% на 4х тредах.

Ну он не соберёт, если не умеет программировать сам, там надо исходники править. Банально некоторые стандартные функции не совпадают.

Он умеет программировать;-)

Но да, он говорит что у него не собралось, я поправляю.

Нет, колизии повышают сложность. В вырожденном случае (у всех элементов один хеш) сложность хеш таблицы O(N). В идеальном случае, где у всех элементов разные хеши O(1). В реальности где-то посередине в зависимости от данных. При этом надо учитывать, что используется не хеш целиком, а последние N бит, потому что хештаблица не будет содержать SIZE_MAX элементов, а всегда меньше. Так что коллизии случаются чаще, чем кажется. Конечно, с этим борятся авторы хешфункций и сама хештаблица (load factor), но это не панацея.

Если упираешься в перф, бенчить хештаблица vs std::map (и аналоги) стандартная практика. Потому что хештаблица не всегда быстрее и не серебряная пуля. Зависит от конкретной задачи и только бенчи знают правду наверняка.

Ну и само собой бенчить хеш таблицы с открытой адресацией и обычные тоже надо между собой, потому что они тоже по-разному ведут себя на разных наборах данных. Хотя на бумаге обе обещают сложность где-то между O(1) и O(N).

Ну так можно установить заведомо бОльший чем требуется размер хэш таблицы и низкий max_load_factor, коллизии будут редки, перехэширования не будет, константное время будет не в среднем случае, а в большинстве.

Можно. А можно сравнить с std::map. Непонятно как большая хештаблица на кеши ляжет и т. д.

Непонятно как большая хештаблица на кеши ляжет и т. д.

Вы так говорите будто std::map более cache-friendly, с чего бы?

Он может кушать меньше ОЗУ, чем хештаблица с низким load factor.

Он может кушать меньше ОЗУ, чем хештаблица с низким load factor.

Это абсолютно irrelevant. А вот то что при любом поиске в std::map Вы всегда будете трогать log(N) нод разбросанных по памяти случайным образом - это медицинский факт. И я ещё не видел чтобы хеш табличка с «хорошей» хеш функцией и малым числом коллизий была медленней.

Если мы равномерно запрашиваем все элементы, то в обоих случаях лучше, чтобы в кеше была вся структура целиком. std::map будет дольше влезать в кеш целиком, чем хештаблица с низким load factor.

Так что опять же, зависит от данных (в том числе их размера) и алгоритма.

Я бы рискнул предположить что это зависит от того как память для map аллоцирована. Если там ноды по отдельности, то фигово будет.

а, я понял. Это тема, в которой всякие чудики блистают своими школьными познаниями про кэши и O(n), которые явно никак не относятся к проблеме :)

std::map будет дольше влезать в кеш целиком, чем хештаблица с низким load factor.

С точки зрения кеширования нас будут интересовать только непустые buckets, я думаю при прочих равных «рабочий» dataset у хеш таблички всё равно будет меньше. Ну, или я совсем чего-то не понимаю.

Я не говорю что std::map - абсолютное зло, и есть целый класс задач / алгоритмов где она просто незаменима. Но утверждать «std::map более cache-friendly» - так себе идея.

Я бы рискнул предположить что это зависит от того как память для map аллоцирована. Если там ноды по отдельности, то фигово будет.

Это не так важно: ни в одном из случаев говорить о последовательном доступе не приходится - никакие «prefetch» не помогут. В этом контексте роль играет исключительно уместились мы хотя бы в L3, или нет.

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

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

Я про то, что в кэш оно же приходит строками

На последних x86 cacheline - 64 bytes. Это «ни о чём».

Я сварщик не настоящий, но тем не менее спрошу: а оно (std::vector, std::map, кто угодно) там вообще в принципе параллелизуется от OpenMP? А то озвученные ускорения в десятки процентов никак на это не похожи. Я в основном с массивами (и, будете смеяться, на фортране), тем не менее ускорение было кратное; top при этом показывал использование процессора в 1000% процентов.

В интырнетах пишут что с векторы очень даже параллелизуется, тем не менее…

Смотря в каком смысле параллелизуется. На чтение должно параллелиться все (ну вектор так точно), на запись с переаалокацией не параллелится ничего:-)

Ускорение зависит от задачи тащем то, на него много факторов влияет. Есть например такая roofline model…

А может его можно переделать в массив, поперезаписывать и назад в map? Если озвученные в начале тайминги я понял правильно - 4 млн элементов х 20 мс = 1.3e+3 min (~20 часов), и могут быть ускорены, то как бы может стоит выделки.

Я переделывал, не помогает.

А, я мс с мкс перепутал:-(

Если переделывание в массив и OpenMP массива не помогает, то, очевидно проблема в алгоритме и переделывание мап в хэш или в любые другие структуры тоже не помогут. Тогда вопрос что ж происходит в цикле, раз он не параллелится? Какие-то хитрые перекрестные ссылки?

у вас число элементов как-то сверху ограничено?

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

вообще все зависит от числа элементов, стратегии добавления/ удаления элементов, обьема памяти.

как реализован unordered_map не знаю, но наверняка там общее решение, которое будет хуже заточенного под задачу.

короче, если стоит задача максимальной производительности, вряд ли стоит пользовать стандартные классы.

Я переделывал, не помогает.

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

Много чего может быть. Сейчас основное подозрение что задача memory bound.

Сабж. Есть плюсовый код, цикл параллелится при помощи OpenMP…

А есть смысл ускорять вычисления? Для проверки работоспособности модели можно и подождать 80 секунд.

Если это «боевая» прошивка блока управления сверхзвукового снаряда, то тут кодогенератор в чистый Си использовать следует ради скорости исполнения расчета и чтобы исключить человеческие ошибки программирования.

Если же просто маяться ерундой в ВУЗе и нет огромной базы унаследованного исходного кода промышленного ПО, то зачем использовать Си++? Фортран считает гораздо быстрее и писать на нем проще.

А есть смысл ускорять вычисления?

Есть.

кодогенератор в чистый Си использовать следует

Не следует.

Фортран считает гораздо быстрее и писать на нем проще.

Не считает быстрее и писать на нем не проще.

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

Все оказалось банально:

sizeof(std::unordered_map<K, V>) == 56

(грррррр! 8 байт сэкономили, молодцы че). Дальше вот такая конструкция

std::vector<std::unordered_map<K, V> > table(omp_get_num_threads());

при совместном доступе из разных потоков встает колом потому что разные потоки ломятся в одну строку кэша.

bugfixer, спасибо!;-)