Lock-free структуры данных. Concurrent maps: skip list

[hack2root]

по-моему,

>при вставке мы сначала ищем позиции в списках на всех уровнях и формируем массивы prev[]

как раз для конкурентной записи/чтения и нужны эти самые lock-free структуры данных.

Ещё бы анализ размерностей, для которых этот алгоритм «оптимален», или «достаточно эффективен» и вот ещё-бы сравенение с другими решениями… а то верить на слово очень непросто, всё-таки…

[khizmax]

Чтобы не верить на слово, нужно попробовать самому для свое задачи. У меня цель несколько другая — показать, что решения lock-free существуют и как они выглядят изнутри.
О размерностях. Думаю, здесь больше зависимость от числа писателей/читателей, то есть от степени конкурентности, чем от числа элементов. Конкретно skip-list разрабатывался для больших map'ов — от сотен тысяч элементов, ИМХО.

[alexeibs]

Цитата из второго комментария к статье habrahabr.ru/post/230413/

Представить себе корректный lock-free алгоритм вообще невозможно.

[khizmax]

Спасибо :-)

[Monnoroch]

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

[khizmax]

В следующей статье будет график производительности для сферического коня в вакууме (то есть синтетического теста) для всех рассмотренных concurrent map по сравнению с std::map/std::unordered_map с блокировкой std::mutex'ом.
На статью это не тянет, ну разве что на статью только с графиками.

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

Оно и работает медленнее для одного потока, — кодильник-то нехилый. Но для множества потоков, то есть при большой конкуренции, возможен выигрыш, — на это и делается ставка в такого типа контейнерах.

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

Если я правильно понял, то это обычное заблуждение: блокировка на уровне ячеек структуры данных (fine-grained locking) не освобождает от необходимости поддерживать структуру данных в консистентном состоянии, то есть применять те же атомарные инструкции, схему управления памятью и пр. методы. Более того, описанные мною lock-free структуры не дают каких-либо гарантий по поводу данных в элементах контейнера, а только гарантируют корректное состояние контейнера в любое время. Это значит, что если вы хотите изменить какое-то неключевое поле в данных map'а, то во избежание гонок доступ к этому полю вы должны обеспечивать сами — атомиками, спин-локом, мьютексом, монитором и т.п. Конкурентный map обеспечит только поиск по ключу и гарантию, что, пока вы изменяете это поле в данных найденного элемента, этот элемент не будет физически удален (delete).

[Monnoroch]

Разумеется!
Но все-таки, например, если сделать хеш-таблицу, в которой будет глобальный лок на рехэшинг и поячеечный лок (возможно, RW) на вставку-удаление-поиск, то не нужно никогда ничего откатывать и уж тем более не нужен геморрой со схемами вроде HP или RCU, которые обладают какими-то просто ужасающими ограничениями, на мой вкус. Из за этого такая структура данных может быть по факту лучше, ведь ваш lock-free алгоритм абсолютно не wait-free при достаточно высоком контеншне (особенно, если активно вставлять-удалять элементы).
Или я не прав?

[khizmax]

Или я не прав?

В общем — нет, не правы.
Во-первых, рассуждения «по факту» неявно подразумевают наличие этого самого «факта» — то есть железа и задачи. Для своего железа и своей задачи вы вольны выбирать то, что будет наиболее оптимальным.
Во-вторых, wait-free — более сильное требование, чем lock-free, следовательно, более тяжелое, в том числе по производительности, как это ни странно. И уж тем более странно рассуждать о wait-free для глобального и поячеечных локов.
В третьих, про геморрой с HP/RCU. Я, видимо, был недостаточно точен в своих статьях. Повторюсь: с точки зрения использования lock-free алгоритмов, «геморрой» с HP и RCU начинается с инициализации, на ней же и заканчивается, то есть речь идет о нескольких строках кода в начале программы/потока. С точки зрения разработки lock-free структуры, — да, геморроя много, но он весь спрятан внутри методов lock-free контейнера.
Кроме того, как я теперь понимаю, порог входа в мир lock-free достаточно высок, нужно не только знать, как оно работает внутри, но и иметь готовые инструменты, — HP, uRCU, transactional memory, схемы версионности и пр. Создать их с нуля — действительно геморрой. Хотелось бы найти готовые, чтобы поиграться. Поэтому я и начал писать про это и про libcds, — вот инструменты, вот реализация, берите, пробуйте, рапортуйте об ошибках, предлагайте более оптимальные решения.