Comments 13
UFO just landed and posted this here
Попробовали ли вы ThreadSanitizer для отладки (вы когда-то упоминали, что собираетесь)? Как он вам?
К сожалению, в полной мере — нет, но вот уже собираюсь ;-)
Почему до сих пор нет:
Причина 1 — банальная: надо перестраивать билд-систему тестов, чтобы было удобно добавлять всякие инструменты (= флаги компиляции). Для этой задачи я уже созрел.
Причина 2: очень большая работа. Собирал отзывы тех, кто пробовал tsan именно для проверки race/memory ordering. Боюсь погрязнуть в false positive (или false negative? в общем, в сообщениях об ошибках там, где их нет). На C++ 2015 Russia говорил с одним из разработчиков санитайзеров, Дмитрием Вьюковым. Он подтвердил, что tsan — инструмент более тупой (не в смысле «тупой», а в смысле особо не заточенный под memory ordering), чем его же relacy race detector, и может давать false positive. Применять relacy, — это перелопатить весь код libcds, над этим я думаю…
Причина 3 — всепобеждающая: всегда находится более интересная задача
Почему до сих пор нет:
Причина 1 — банальная: надо перестраивать билд-систему тестов, чтобы было удобно добавлять всякие инструменты (= флаги компиляции). Для этой задачи я уже созрел.
Причина 2: очень большая работа. Собирал отзывы тех, кто пробовал tsan именно для проверки race/memory ordering. Боюсь погрязнуть в false positive (или false negative? в общем, в сообщениях об ошибках там, где их нет). На C++ 2015 Russia говорил с одним из разработчиков санитайзеров, Дмитрием Вьюковым. Он подтвердил, что tsan — инструмент более тупой (не в смысле «тупой», а в смысле особо не заточенный под memory ordering), чем его же relacy race detector, и может давать false positive. Применять relacy, — это перелопатить весь код libcds, над этим я думаю…
Причина 3 — всепобеждающая: всегда находится более интересная задача
Tsan более тупой, но он не дает false positive. Он может пропустить ошибки, это да.
Если билд систему сложно менять, то можно сделать «compiler script»:
$ cat /xxx/g++
#!/usr/bin/env bash
clang++ -fsanitize=thread $@
$ export PATH=/xxx:$PATH
Если билд систему сложно менять, то можно сделать «compiler script»:
$ cat /xxx/g++
#!/usr/bin/env bash
clang++ -fsanitize=thread $@
$ export PATH=/xxx:$PATH
Решил задействовать библиотеку в своем проекте. В моем случае очень неплохо показал себя CuckooMap — производительность при одном потоке по сравнению с unordered_map: 50%-100% для insert/erase и 30-40% для find. Скейлинг на разное количество потоков не пробовал. Зато хорошо скейлится при большом (~10^8) количестве элементов (в отличии от SplitListMap). Очень неплохая thread-safe stl-style unordered_map получается, по крайней мере если код не очень «состязательный», но без конкурентной структуры обойтись нельзя.
Для меня это несколько неожиданно.
Хотя это подтверждает тезис о том, что не существует единого «хорошего для всех» map'а. Каждой задаче — свой map.
Хотя это подтверждает тезис о том, что не существует единого «хорошего для всех» map'а. Каждой задаче — свой map.
И разобраться в том, для каких юз-кейсов какой map больше подходит — задача не из простых, похоже. Обзорная статья по сильным-слабым сторонам разных деревьев была очень полезна, но я такой ни на русском, ни на английском не нашел. Даже review articles в научных публикациях такой не отыскалось :(.
Для себя пока выделил три hash-map структуры:
MichaelMap — для данных, которые не требуется перестраивать.
SplitListMap — для небольших (до 10^6) структур
CuckooMap — для низкосостязательного (low-contention) кода, особенно если предполагается большое количество элементов в структуре.
Для себя пока выделил три hash-map структуры:
MichaelMap — для данных, которые не требуется перестраивать.
SplitListMap — для небольших (до 10^6) структур
CuckooMap — для низкосостязательного (low-contention) кода, особенно если предполагается большое количество элементов в структуре.
Спасибо за ссылки!
Протестировал libcuckoo — супер круто. Привожу производительность при 6 потоках (в операциях/микросекунду). CH=CityHash. При одном потоке производительность libcuckoo и std::unordered_map примерно одинакова.
Хотя по функциональности, конечно, libcds несравнимо шире.
map_type find add/rem
cds::CuckooMap: 6.45 6.09672
cds::SplitListMap: 26.5 20.5555
libcuckoo::hashmap: 63.7 52.871
libcuckoo::hashmapCH: 55.5 47.0
Хотя по функциональности, конечно, libcds несравнимо шире.
Прочитал вышеприведенную статью — отличнейший пример оптимизации известного алгоритма! В результате перформанс алгоритма преобразился до неузнаваемости.
Рекомендуется студентам старших курсов профильных вузов и инженерам/исследователям в области оптимизации структур данных, а также всем, кто не ленится применять что-то более чем std::unordered_map
Sign up to leave a comment.
Lock-free структуры данных. Concurrent maps: деревья