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

А используемый std::unrodered_map аллокатор не синхронизирует за кулисами потоки при вставке/удалении элементов?

Вот я чего то такого боюсь, да;-( Как бы теперь это победить оставаясь в рамках C++-03 (требование Заказчика).

Откуда у тебя взялся std::unordered_map в c++03?

А какая используется стандартная библиотека? libstdc++ использует один и тотже шаблонный аллокатор, в случае в std::unordered_map это std::allocator<std::pair<>>. Если влияет количество «бакетов», то возможно дело в переодическом вызове rehash при модификации данных. Помнится у Полухина было интересное видео на тему std::unordered_map с названием аля «Делаем контейнер чуточку быстрее» или чтото похожее

upd. видео нашел, но целиком пересматривать не буду) возможно подкинет идей

А блин, еще и это… Ладно, придется видимо на std::map уходить, но все равно интересно.

Спасибо.

Дефолтная?

Хотя Закачик это будет собрать MVS2008 под оффтопик, так что я вообще ХЗ че там у них и как;-(

Вот за что я не люблю STL, так это за такие подводные камни.

Дефолтный у них интерфес)) а реализации разные, кстати никогда не пробовал искать исходники реализации от MS, надо будет глянуть

Меня от MS тошнит. Мне пришлось свой генератор случайных чисел например копипастить, потому что у них не нашлось генератора принимающего сид.

$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/12/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 12.3.0-1ubuntu1~23.04' --with-bugurl=file:///usr/share/doc/gcc-12/README.Bugs --enable-languages=c,ada,c++,go,d,fortran,objc,obj-c++,m2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-12 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=release --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --enable-cet --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-12-DAPbBt/gcc-12-12.3.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-12-DAPbBt/gcc-12-12.3.0/debian/tmp-gcn/usr --enable-offload-defaulted --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.3.0 (Ubuntu 12.3.0-1ubuntu1~23.04) 

оно?;-)

Несовсем понятно что именно «оно»)) g++ использует libstdc++ исходники реализации std::unordered_map, а MSVC будет использовть их имплементацию исходники реализации std::unordered_map <- эту я впервые смотрю)) если честно, имхо код майкрософт выглядит чище

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

Судя по всему с unordered_map я погорячился - придется на map уходить (C++03 все таки) или вообще свой велосипед с дихотомией велосипедить;-(

как именно openmp всё это дело оборачивает своими щупальцами

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

Правда на 100% за корректность работы в таком случае не поручусь;-(

Основная разница в том что тут юзается std::unordered_map c которым я толком дела не имел в параллельных задачах.

Любые STD containers требуют внешней синхронизации. Я вообще удивлён что оно не развалилось как карточный домик ещё….

Еще один вопрос - есть ли какие то рекомендации по выбору числа бакетов? Я выбрал порядка числа элементов (на два порядка ниже чем диапазон ключей), стало лучше чем по умолчанию. Сейчас еще поиграюсь конечно, но боюсь дело совсем не в этом…

Нужно собирать статистику. Например у меня на одном очень легко нагруженном инстансе в проде:

stats: count=2053 load=0.140283 maxSize=2 avg=1.08271 avg2=1.15278
index: [0:1787, 1:244, 2:22]

А вот пример с одного из наиболее нагруженных:

stats: count=467341 load=0.297126 maxSize=6 avg=1.16456 avg2=1.31482
index: [0:1171565, 1:342145, 2:52883, 3:5718, 4:516, 5:40, 6:2]

Задача - добиться чтобы «хвост» (число collisions) не был длинным.

P.S. У нас что gcc что boost довольно старенькие - на них boost::hash_map более «агрессивен» чем std::unordered_map, и при прочих равных выигрывает. Хозяйке на заметку.

Что бы исключить гонку данных каждый тред работает со своей таблицей.

Это я упустил. Посмотри в сторону tcmalloc - возможно спасёт отца Русской демократии.

Любые STD containers требуют внешней синхронизации

Ну вектор все таки не требует, или ты о чем?;-)

Cтарушка hash_map оказалась ВДВОЕ(!!!) быстрее unordered_map. Обычный std::map в полтора раза медленнее unordered_map. Но ни то ни то не параллелится.

Тыкать палочкой в аллокаторы не хочется, tcmalloc я не уверен что смогу втащить в проект. Попробую наколхозить че то на основе вектора…

Ну вектор все таки не требует

std:vector<bool>, который хранит значения в битах и поэтому доступ на запись из разных потоков в соседние элементы вектора приведёт к поломке.

Что просиходит вообще?

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

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

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

Оно на самом деле с любым вектором сломается - достаточно первого resize().

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

std::unordered_map<int, T>, sizeof(T)=16

У тебя точно нельзя массивом обойтись?

Попробуйте попрофилировать без параллелизма:

• hash_map
• map
• vector-based (может даже не надо делать «правильную» реализацию, пусть результат будет не корректный, но похожий по затратам процессорного времени)
• vector-based с зарезервированным заранее размером, чтобы влазило без resize

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

Ничего не понял, причём тут std::unordered_map и плохо паралелится? Плохо или хорошо параллелиться могут конкурентные структуры, где есть синхронизация. И какие операции измеряются – чтения, вставка?

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

Хотя Закачик это будет собрать MVS2008 под оффтопик

Нет, собирать под MVS2008 будете сначала вы, потому что иначе вы получите миллион несовместимого по вызовам говна, залоченного на реализацию в виндовом рантайме. А потом вой от заказчика, мол 50 errors, 231 warnings.

У меня этой шни нет, максимум могу собрать mingw:-)

Попробуйте попрофилировать без параллелизма

разумеется я с этого начинаю. Удивительно, но все реализации +/- примерно одного порядка по времени оказываются.

А почему это должна быть проблема заказчика? mingw предоставляет интерфейсы максимально похожие на g++/gcc а не msvc.

В свою очередь msvc - это набор windows-специфичных костылей с неполной поддержкой стандарта. А в 2008й версии даже с99 получил разве что long long, на остальное забили.

https://learn.microsoft.com/en-us/previous-versions/visualstudio/visual-studio-2008/x84h5b78(v=vs.90)?redirectedfrom=MSDN

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

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

Я тоже так думал, но…

ya-betmen, bugfixer

переписал через вектор - примерно аналогичная производительность и такая же никакущая эффективность распараллелеливания;-(

В реализации через вектор в векторе число элементов на порядок больше чем в хэш-таблице, это обьясняет низкую скорость в один поток - но не объясняет плохое распараллеливание.

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

А почему это должна быть проблема заказчика?

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

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

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

Сколько у тебя элементов там и сколько чтений/вставок?

Чтений нет, только вставки в конец. Каждый поток накидывает данные в свой вектор.

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

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

Я скорее про то нет ли там каких синхронизаций внутренних, которые могут мешать.

только вставки в конец

Я не понял, если у тебя только вставки и только в конец, для чего нужна была мапа?

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

А у тебя точно оно не на создании твоего Т тормозит?

нет ли там каких синхронизаций внутренних, которые могут мешать.

Я не вижу, но это же stl… уже ничему не удивлюсь:-(

если у тебя только вставки и только в конец, для чего нужна была мапа?

Там идёт накопление данных, некоторые данные перекрывают друг друга (имеют одинаковый целочисленный ключ). Можно это перекрытие сразу отрабатывать мапой, можно все накапливать, потом сортировать по ключу и выкидывать повторы.

А у тебя точно оно не на создании твоего Т тормозит?

Там POD тип 16 байт. Вектор их аллоцирует большими кусками.

Std::map - это бинарное дерево, оно кэши шатать будет, а l2-l3 в процессорах общие между потоками. Попробуй заменить, если элементов немного и верхний предел размера гарантирован, на массивы простые, а если нет - на хэш-таблицу с открытой адресацией, например по алгоритму Робина Гуда. В интернете полно реализаций.

нет ли там каких синхронизаций внутренних, которые могут мешать.

Я не вижу, но это же stl… уже ничему не удивлюсь:-(

Явных абсолютно точно нет, есть неявные в недрах аллокатора.

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

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

Но я не понимаю что гарантирует отсутствие совпадений ключей между разными потоками? В какой-то момент эти таблички наверняка же мерджить приходится?

есть неявные в недрах аллокатора.

Для вектора? Если и да, по моим представлениям это крайне редкое событие.

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

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

что гарантирует отсутствие совпадений ключей между разными потоками?

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

Уговорить заказчика на C++11 + https://github.com/greg7mdp/parallel-hashmap.

Перепиши на Сишечку и не мучайся =)

что гарантирует отсутствие совпадений ключей между разными потоками?

Ничто не гарантирует

при дубликате ключей все равно приходится считать все варианты

У меня есть глубокое подозрение что одно и то же зазря считается в нескольких потоках, и именно из-за этого scalability никакая. Я очень серьёзно сомневаюсь что затык именно на thread-private хеш табличке, я бы на «вычисления» смотрел в первую очередь.

А вообще, гадать не надо - profiler в помощь…

Чтений нет, только вставки в конец. Каждый поток накидывает данные в свой вектор.

Предлагаю заменить вектор на std::deque. Он очень хорош для добавлений в конец т.к. аллоцирует кусками. И почти также быстр как вектор при рандомном чтении.

одно и то же зазря считается в нескольких потоках

Нет:-)

Не надо гадать, кто ест процессор. Надо прогнать под perf, построить флеймграф, и все станет ясно.

Не надо гадать, кто ест процессор.

Дык, я так понимаю в том и проблема что никто не ест, а (предположительно) - «дерётся» за что-то.

Нет:-)

Ну, мои телепатические способности - на исходе :) А может стоит от openmp отказаться (хотя бы в качестве эксперимента), и написать свой thread pool manager? Это не так сложно, на самом деле - не так страшен чёрт как его малютка ;)

P.S. Да даже не полновесный thread pool - я так понимаю что именно считать известно заранее? Просто форкнуть N thread‘ов, и пусть они себе «блоками» вычислительные задачи забирают. На первый взгляд по сравнению с тем что уже делается - это просто лишний atomic index в вектор задач.

Не используй std::unordered_map, он медленный шо пипец. Используй abseil flat_hash_map. Я гонял тесты, на некоторых конфигурациях разница достигала 3-5 раз. И это без всякого параллелизма. Ощущение, что его засунули в STL просто для галочки, чтобы был. Или чтобы можно было учить студентов программированию «знакомьтесь, это хештаблица» без подключения либ.

А ещё бывает, что std::map быстрее (в 2-3 раза), чем хештаблица (любая), но зависит от данных, конечно. Так то O(1) у хештаблицы это «в среднем», а O(logN) у std::map во всех случаях.

Я бы в первую очередь побенчил std::map, во вторую подключил abseil flat_hash_map, если можно подключать либы, и только в последнюю очередь тыкался бы с std::unordered_map.

Так то O(1) у хештаблицы это «в среднем»,

Если не произошло перехеширование, то всегда константная сложность ведь. Нет?

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

Почему бы не предположить самый простой вариант, автор просто неправильно использует openmp.

Оно не настолько сложное вроде чтобы не суметь в нем несколько потоков запустить.

Но вообще идея выше про ручной запуск тредов мне нравится.

Ещё может быть мемори баунд задача, но это надо оценки делать.

Не, никаких хитрых железных ресурсов там нет.

Я наверное возьму таймаут на неделю, тут сейчас другими задачами придавило.