Lock-free структуры данных. Concurrent maps: деревья

[@khizmax]

Спасибо! Значит, цель достигнута :-)

[@encyclopedist]

Попробовали ли вы ThreadSanitizer для отладки (вы когда-то упоминали, что собираетесь)? Как он вам?

[@khizmax]

К сожалению, в полной мере — нет, но вот уже собираюсь ;-)
Почему до сих пор нет:
Причина 1 — банальная: надо перестраивать билд-систему тестов, чтобы было удобно добавлять всякие инструменты (= флаги компиляции). Для этой задачи я уже созрел.
Причина 2: очень большая работа. Собирал отзывы тех, кто пробовал tsan именно для проверки race/memory ordering. Боюсь погрязнуть в false positive (или false negative? в общем, в сообщениях об ошибках там, где их нет). На C++ 2015 Russia говорил с одним из разработчиков санитайзеров, Дмитрием Вьюковым. Он подтвердил, что tsan — инструмент более тупой (не в смысле «тупой», а в смысле особо не заточенный под memory ordering), чем его же relacy race detector, и может давать false positive. Применять relacy, — это перелопатить весь код libcds, над этим я думаю…
Причина 3 — всепобеждающая: всегда находится более интересная задача

[@dvyukov]

Tsan более тупой, но он не дает false positive. Он может пропустить ошибки, это да.
Если билд систему сложно менять, то можно сделать «compiler script»:
$ cat /xxx/g++
#!/usr/bin/env bash
clang++ -fsanitize=thread $@
$ export PATH=/xxx:$PATH

[@DaylightIsBurning]

Решил задействовать библиотеку в своем проекте. В моем случае очень неплохо показал себя CuckooMap — производительность при одном потоке по сравнению с unordered_map: 50%-100% для insert/erase и 30-40% для find. Скейлинг на разное количество потоков не пробовал. Зато хорошо скейлится при большом (~10^8) количестве элементов (в отличии от SplitListMap). Очень неплохая thread-safe stl-style unordered_map получается, по крайней мере если код не очень «состязательный», но без конкурентной структуры обойтись нельзя.

[@khizmax]

Для меня это несколько неожиданно.
Хотя это подтверждает тезис о том, что не существует единого «хорошего для всех» map'а. Каждой задаче — свой map.

[@DaylightIsBurning]

И разобраться в том, для каких юз-кейсов какой map больше подходит — задача не из простых, похоже. Обзорная статья по сильным-слабым сторонам разных деревьев была очень полезна, но я такой ни на русском, ни на английском не нашел. Даже review articles в научных публикациях такой не отыскалось :(.
Для себя пока выделил три hash-map структуры:
MichaelMap — для данных, которые не требуется перестраивать.
SplitListMap — для небольших (до 10^6) структур
CuckooMap — для низкосостязательного (low-contention) кода, особенно если предполагается большое количество элементов в структуре.

[@DaylightIsBurning]

Нашел еще одну конкурентную реализацию CuckooMap — libcuckoo, вышел на нее через статью.

[@khizmax]

Спасибо за ссылки!

[@DaylightIsBurning]

Протестировал libcuckoo — супер круто. Привожу производительность при 6 потоках (в операциях/микросекунду). CH=CityHash. При одном потоке производительность libcuckoo и std::unordered_map примерно одинакова.

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 несравнимо шире.

[@khizmax]

Прочитал вышеприведенную статью — отличнейший пример оптимизации известного алгоритма! В результате перформанс алгоритма преобразился до неузнаваемости.

Рекомендуется студентам старших курсов профильных вузов и инженерам/исследователям в области оптимизации структур данных, а также всем, кто не ленится применять что-то более чем std::unordered_map

[@DaylightIsBurning]

Ну, принстон не зря такую репутацию имеет :)