Комментарии 22
Сорри, статью не читал, но с хабром надо что-то делать, поэтому апвоут.
П.С. Не читал, потому что нихрена не понятно бедному практикующему маркетологу.
П.С. Не читал, потому что нихрена не понятно бедному практикующему маркетологу.
Хотели бы вы видеть алгоритмы разобранные в статье в доработанном виде в составе библиотеки boost?Конечно!
Если у вас высокая конкуренция потоков за один и тот же контейнер, т.е. в один момент времени к контейнеру в среднем обращаются более 8 потоков, то лучшим решением будет использовать контейнеры из библиотеки CDSlib: github.com/khizmax/libcds
Ну есть ещё другие реализации конкурентных контейнеров. Мне известны две, которые по производительности превосходят libCDS: libcuckoo и Junction.
При libcuckoo этом ещё и также легко использовать, как std::unordered_map: можно хранить любые объекты, не нужно вручную заботится о выделении под них памяти, а также запускать сборщик мусора в каждом потоке или инициализировать библиотеку. У libcuckoo также оверхед по памяти не слишком большой, по сравнению с другими, которые я пробовал.
Я взял наиболее функциональный контейнер — упорядоченный std::map, который позволяет атомарно искать по диапазону ключей, чтобы показать, что вы можете делать потокобезопасным класс любой сложности. И сравнивал его так же с упорядоченными lock-free map. Было бы странно, если бы я сравнивал упорядоченные map с неупорядоченным hash_map.
Более простые контейнеры легче реализовать lock-free и добиться высокой производительности: hash_map, list, stack, queue. А делать более сложные lock-free контейнеры займет уйму времени, чтобы без ошибок и с высокой производительностью.
Более простые контейнеры легче реализовать lock-free и добиться высокой производительности: hash_map, list, stack, queue. А делать более сложные lock-free контейнеры займет уйму времени, чтобы без ошибок и с высокой производительностью.
Какие из перечисленных реализаций будут стабильно работать в разделяемой памяти (в частности, Boost shared memory)?
Замечательные статьи, автору респект!
У меня вопрос: почему вы выбрали BronsonAVLTree и SkipList для сравнения? Только потому, что это стандартные map, не-hash map?..
Я спрашиваю потому, что ваша техника прямо ложится на простой hash-map: хеш-таблица, доступ к каждому элементу таблицы — под вашим легким shared mutex; у Shavit & Herlihy подобная техника называется striping. Не пробовали?..
ИМХО, подход надо развивать, попробовать на каких-то lock-based конкурентных алгоритмах — тот же cuckoo-hashing, hopscotch hashing и пр.
У меня вопрос: почему вы выбрали BronsonAVLTree и SkipList для сравнения? Только потому, что это стандартные map, не-hash map?..
Я спрашиваю потому, что ваша техника прямо ложится на простой hash-map: хеш-таблица, доступ к каждому элементу таблицы — под вашим легким shared mutex; у Shavit & Herlihy подобная техника называется striping. Не пробовали?..
ИМХО, подход надо развивать, попробовать на каких-то lock-based конкурентных алгоритмах — тот же cuckoo-hashing, hopscotch hashing и пр.
Спасибо!
Да, именно потому, что это упорядоченный map с возможностью поиска по диапазону ключей. Полученный мною потокобезопасный упорядоченный контейнер contfree_safe_ptr<std::map> позволяет искать по диапазону ключей и атомарно читать полученную выборку с высокой производительностью, и написать такой lock-free контейнер — это нетривиальная задача. Т.е. чтобы можно было сравнить, не только во сколько раз мы ускоряем стандартные блокировки, но и во сколько раз упрощаем решение по сравнению с lock-free.
Изначально полностью write-contention-free алгоритмы, я разрабатывал для низко-латентного обмена данными между устройствами и серверами кластера по кэш-некогерентному интерфейсу PCI Express.
Да, подобный подход позволяет оптимизировать части многих алгоритмов и контейнеров, например, mp-mc queue или hash-map.
В данном случае я постарался создать именно максимально быстрый из максимально универсальных подходов для обеспечения потокобезопасности любого объекта с высокой производительностью.
Да, именно потому, что это упорядоченный map с возможностью поиска по диапазону ключей. Полученный мною потокобезопасный упорядоченный контейнер contfree_safe_ptr<std::map> позволяет искать по диапазону ключей и атомарно читать полученную выборку с высокой производительностью, и написать такой lock-free контейнер — это нетривиальная задача. Т.е. чтобы можно было сравнить, не только во сколько раз мы ускоряем стандартные блокировки, но и во сколько раз упрощаем решение по сравнению с lock-free.
Изначально полностью write-contention-free алгоритмы, я разрабатывал для низко-латентного обмена данными между устройствами и серверами кластера по кэш-некогерентному интерфейсу PCI Express.
Да, подобный подход позволяет оптимизировать части многих алгоритмов и контейнеров, например, mp-mc queue или hash-map.
В данном случае я постарался создать именно максимально быстрый из максимально универсальных подходов для обеспечения потокобезопасности любого объекта с высокой производительностью.
на что люди не идут лишь бы не писать на Rust
Универсальный подход это здорово, но стоит помнить, что во многих случаях можно вообще отказаться от блокировок применяя шардинг (равномерно распределить задания по рабочим потокам используя фиксированную нарезку по интервалам на основании какого либо ключа). Тогда каждый поток обрабатывает только свои задания и обращается только к своим локальным данным. Локализация данных по ядрам дает дополнительный выигрыш.
Автор упомянул схожую технику, но почему то как «Just for fun».
Автор упомянул схожую технику, но почему то как «Just for fun».
А если допустима некая погрешность в вычислениях, то даже «общими» данными можно оперировать в разных потоках, да хоть на разных машинах…
Из «just for fun» можно еще добавить, что если у вас супер-критичное по скорости приложение, много памяти и ключи умещаются в относительно небольшой диапазон (например, все возможные значения влазят в ushort), то лучше простого массива ничего нет :)
Ато часто map-ы создают даже для словарей из пары десятков значений.
Из «just for fun» можно еще добавить, что если у вас супер-критичное по скорости приложение, много памяти и ключи умещаются в относительно небольшой диапазон (например, все возможные значения влазят в ushort), то лучше простого массива ничего нет :)
Ато часто map-ы создают даже для словарей из пары десятков значений.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Потокобезопасный std::map с производительностью lock-free map