В общем, просмотрел статью по диагонали, по-моему, это развитие Multi-level array первого анонса 2013 года. Подход весьма многообещающий, но опять я вижу perfect hashing и fixed-sized keys! О май гот (facepalm)!..
Им бы чуть-чуть ещё подумать за два года — и они бы получили полноценный map для ключей переменной длины (например, для std::string) без всякого perfect hashing.
Хотя это пока только мои задумки без доказательства в виде кода.

DaylightIsBurning Dec 13 2016 at 16:56

Не нашел имплементации lock-free vector в libcds. Есть какие-то сложности с его имплементацией? В других lock-free библиотеках тоже массивов нет обычно.

khizmax Dec 13 2016 at 17:02

Да, есть, мягко говоря, сложности…
Первая из них — а что такое lock-free vector? Каков его интерфейс?.. Если std::vector, — сложности экспоненциально увеличиваются.
Если lock-free vector — это push_back() / pop_back() + итераторы — это чуть проще. Но что-то это стек напоминает…
Напишите, pls, что Вы ожидаете от lock-free vector!

DaylightIsBurning Dec 13 2016 at 17:28

В идеале, конечно std::vector. Если по-минимуму — random-access assign/get, push_back, pop_back, size(). Resize() тоже не помешал бы. Итераторы очень желательно, но ещё неплохо бы что бы get/assign невалидных индексов не крашил, а установливал флаг ошибки. Мб в виде отдельных try_get/try_assign. Последнее было бы здорово т.к. на size() положиться нельзя будет же…

khizmax Dec 13 2016 at 17:40

Я бы тоже хотел lock-free std::vector… Пока не представляю, как его сделать.
random-access assign/get — это позволяет сделать Multi-level array «из коробки» (у меня пока такой коробки нет).
push_back() / pop_back() — с этим сложнее, как я писал: пока вижу решение только с 2-CAS, иначе возможны кратковременные дыры в векторе. Алгоритм 2-CAS (MCAS) сам по себе довольно тяжел и требует довольно нетривиальной инфраструктуры (внутренних дескрипторов), непонятно, будет ли выигрыш по сравнению с std::vector под мьютексом.
Resize()/reserve() — не покатит, это все же lock-free vector, единой непрерывной области памяти там не будет (кстати, часто это основное требование к вектору, — чтобы его данные можно было бы взять как непрерывный буфер и передать куда-нибудь в сишную либу).
В общем, запрос я услышал, тем более что сам периодически подумываю о векторах, но пока… увы