Lock-free структуры данных. Concurrent map: разминка

[maksqwe]

Кстати, тем временем один из разработчиков Boost у себя по немногу пилит свой вариант concurrent_set(map).
github.com/ned14/boost.spinlock/blob/master/include/boost/spinlock/concurrent_unordered_map.hpp
Используется сейчас в другой разрабатываемой им библиотеки boost.afio.

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

Развитие под предводительством Niall Douglas данной реализации предложено на GSoC2015
svn.boost.org/trac/boost/wiki/SoC2015

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

[tagir_valeev]

Спасибо за интересную статью. Претензию издателям передал ph_piter.

[khizmax]

Претензию издателям передал

Супер! Спасибо!

[evnuh]

Вы в своих первых статьях давали книгу www.ozon.ru/context/detail/id/17636939/, чем она хуже M.Herlihy Nir Shavit?

[khizmax]

Она не хуже и не лучше, — эти книги совершенно о разном.
Уильямс — о C++, Herlihy и Shavit — об алгоритмах для multi-threaded programming. У Herlihy и Shavit все примеры — на Java; книга ценна тем, что дает системное видение различных подходов, порою неожиданных, и написана очень просто.

[leventov]

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

Что значит «помешать сделать rehashing»?

Можно и без «глобальной» блокировки, см. java.util.concurrent.ConcurrentHashMap.

Там же, в качестве блокировок цепочек используются блокировки, встроенные в объект Entry, которые меняются при rehashing, т. е. в координатах вашей статьи и языка C++ это соответствует расширению массива блокировок.

Есть и разработки rehashing в бекграунде, без единовременной «долгой» работы вообще, см. проект PauselessHashMap.

[khizmax]

Помешать сделать rehashing — это значит, что во время rehashing'а нельзя делать insert/erase, find — в принципе, можно, с приседаниями.
Насчет Java я не силен, но о Doug Lea и java.util.concurrent.ConcurrentHashMap кое-что читал. Если мне не изменяет память, там внутри блокировки и довольно изощренный механизм их применения, а желаемый уровень конкуренции задается в конструкторе. Насчет расширния массива блокировок — см. ремарку о refinable hash map.
PauselessHashMap — прочитал анонс, не понял, в чем там конкурентность. В том, что мы должны сами блокировать извне, если она необходима?.. Автор, как я понял, не заявляет о том, что его класс является concurrent hash map.
Вообще, я уже не раз отмечал, что Java-алгоритмы иногда трудно переносить на C++ «с листа» — многое, чего нет в C++, в Java встроено, — например, GC, synchronized.

[leventov]

Если мне не изменяет память, там внутри блокировки и довольно изощренный механизм их применения, а желаемый уровень конкуренции задается в конструкторе. Насчет расширения массива блокировок — см. ремарку о refinable hash map.

Задание concurrencyLevel = читай, количество локов (striping factor если хотите) было в версиях JDK5-7, и алгоритм был как раз прост. Вот начиная с JDK 8, он стал гораздо сложнее и лучше, а concurrencyLevel, хотя остался как параметр для совместимости, теперь фактически игнорируется.

Исходник: grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/concurrent/ConcurrentHashMap.java

PauselessHashMap — прочитал анонс, не понял, в чем там конкурентность. В том, что мы должны сами блокировать извне, если она необходима?.. Автор, как я понял, не заявляет о том, что его класс является concurrent hash map.

Да, не конкурентный, я хотел заметить, что есть некие идеи, которые наверняка можно совместить и с concurrentMap на локах, и lock-free.

Вообще, я уже не раз отмечал, что Java-алгоритмы иногда трудно переносить на C++ «с листа» — многое, чего нет в C++, в Java встроено, — например, GC, synchronized.

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

[khizmax]

Да, не конкурентный, я хотел заметить, что есть некие идеи, которые наверняка можно совместить и с concurrentMap на локах, и lock-free.

Действтельно, есть. Довольно известная работа об open addressing hash map. Стоит у меня в списке todo уже несколько лет, каждый раз читаю её и думаю — нет, попозже, есть более интересные алгоритмы с более предсказуемым результатом.

[leventov]

Спасибо за ссылочку. (Тоже добавил в закладки, а в итоге так никто и не прочитает, ха-ха).

[leventov]

По результатам моих экспериментов, хорошим значением load factor является 2 – 4, то есть каждый lock-free список коллизий в среднем содержит 2 – 4 элемента. При load factor = 1 (список коллизий состоит из одного элемента в среднем) результаты чуть лучше, но больше накладные расходы по памяти на фактически вырожденные списки коллизий.

Я бы с большой осторожностью давал такие оценки. Средняя длина цепочек в std::unordered_map — 0.75 элементов, java.util.HashMap, java.util.concurrent.ConcurrentHashMap — 0.5625. 2-4 элемента — это хорошо, если каждый байт на счету, потому что система тупо не влазит в оперативку, или это какая-то встроенная штука. Но в целом, в подавляющем большинстве случаев у людей дохренища памяти, и нужна только скорость.

[midday]

Ну-ну. Вы случаем не разрабатываете некий браузер?

[leventov]

Вот интересно, а на что браузеры отжирают память в основном? Неужели на хранение JavaScript-рантаймов (=куча JavaScript объектов, =куча хеш-таблиц). А не на рендеры страниц?

[khizmax]

Я бы с большой осторожностью давал такие оценки

Именно поэтому и пишу — «по результатам моих экспериментов».

[leventov]

Имхо, этого мало. Народ прочитает и кинется всюду лепить load factor 2-4, получая в разы худшую скорость. Имхо, надо писать так:

Если однозначный приоритет это память — делайте load factor 2-4, больше — не разумно даже в этом случае.

Если однозначный приоритет это скорость — делайте load factor 0.5, меньше — не разумно даже в этом случае.

Далее — ищем компромисс где-то посередине, в зависимости от задач.

Еще — обе оценки для chaining, который лучше поддается распараллеливанию и даже приспособлению lock-free. И с точки зрения памяти, и скорости — open addressing предпочтительнее в большинстве случаев. Но в open adressing посложнее с конкуретностью, только striping можно сделать вполне адекватный.

[khizmax]

Поднял сырые результаты тестов для статьи.
Пожалуй, я с вами соглашусь:
MichaelHashMap (это как раз hash map без rehashing'а) на HP, 16 потоков, 90% find, 5% insert, 5% erase:
Load factor=1: Total ops=2131203280, speed=71040109 ops/sec
Load factor=2: Total ops=1983375842, speed=66112528 ops/sec
Load factor=4: Total ops=1582585813, speed=52752860 ops/sec

Не разы, как видно, но десяток-другой процентов.
Load factor меньше 1, как принято в цивилизованном мире, в libcds не поддерживается (пробовал — много жрет оценка, так что load factor у меня — unsigned int)

[leventov]

Разы — не в разы, должно зависеть от общего размера таблицы и характера программы «вокруг» обращений к ней, так сказать. Потому что есть большая разница, если большинство entries находятся в L1, или нет.

[ZyXI]

Так можно же и на целочисленном типе сделать load factor меньше 1. Вам же не нужна вся точность float, наверняка минимальный load factor = 1/16 или 1/8 достаточен? Вроде разбирательство с переполнениями при откусывании трёх‐четырёх бит должно быть менее затратным, не проверяли?

Кстати, в исходниках у вас вроде size_t load factor, не unsigned int.

[khizmax]

Нет, рациональные дроби не проверял. Видимо, надо подумать и внедрить ещё одну стратегию в traits — стратегию оценки load factor. Тогда можно будет довольно легко проверять различные подходы.

Кстати, в исходниках у вас вроде size_t load factor, не unsigned int.

Да, size_t. В комменте я хотел отметить, что load factor в libcds — это целое число (точнее говоря — натуральное).

[nikitadanilov]

> и, наконец, разблокируем все мьютексы в обратном порядке — справа налево. Не забываем, что основная причина deadlock – несоблюдение порядка блокировки/разблокировки нескольких мьютексов.

Разве порядок разблокировки может быть причиной deadlock? «Неправильная» разблокировка (слева направо, в данном случае) может привести к образованию конвоя или thundering herd, но никак не к deadlock-у.

[khizmax]

Конечно может, когда доступ к некому ресурсу требует более одного мьютекса. Такое часто случается в fine-grained blocking схемах, например, в алгоритмах конкурентных деревьев. Правильно выбранная стратегия блокирования нескольких мьютексов/спинлоков (например, для дерева — сверху вниз) гарантирует отсутствие дедлоков.

[nikitadanilov]

Вы можете описать ситуацию, когда неправильный порядок *разблокировки*, т.е. отпускания мьютексов, приводит к проблемам? Ситуации, когда { unlock(A); unlock(B); } корректно, а { unlock(B); unlock(A); } ведет к deadlock-y?

[khizmax]

Теперь понял, — речь именно про разблокировку. Вы правы, сразу вот так пример дедлока на разблокировке привести не смогу (на ум приходят рекурсивные мьютексы).
Но, сугубо ИМХО, нарушение порядка разблокировки без веских на то оснований говорит, по крайней мере, о некой неряшливости кода. Для меня такое было бы сигналом «внимание, возможны мины».

[nikitadanilov]

Да, при прочих равных лучше в каноническом порядке отпускать локи. Меня просто смутила формулировка в статье. Статьи отличные, кстати. Спасибо.