Алгоритмы для доработки в libcds

Развитие подхода Flat Combining. Алгоритм DECStack интересен тем, что со стороны работы с центральным стеком он является non-blocking и поэтому требует применения safe memory reclamation (SMR) типа Hazard Pointer (HP), а со стороны фазы collide — блокируемый. Требуется решить следующие задачи:

Еще одна разновидность open-addressing hash table. Алгоритм не описывает расширение таблицы, предлагается использовать метод из предыдущей работы ([2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf).

Ещё одна реализация skip-list. Алгоритм интересен тем, что на нулевом уровне узлы связаны в double-linked list. Авторы не говорят, применим ли HP к их алгоритму, вместо этого они предлагают использовать reference counting или кратко описанный ими epoch-based подход. Требуется понять, можно ли применить HP и/или RCU.

Развитие подхода [2010] Ellen,Fatourou,Ruppert,vanBreugel Non-blocking Binary Search Trees.pdf на k-арные деревья. Сделать без helping'а, оценить, во что выливается реализация helping'а и стоит ли его вообще делать.

[2012] Korenfeld CBTree - A Practical Concurrent Self-Adjusting Search Tree.pdf Разновидность самобалансирующегося дерева, построенного с использованием техники hand-over-hand locking. Проанализировать, какой SMR подходит (HP, RCU, оба), либо же алгоритм не требует никакой SMR схемы.

[2011] Prokopec,Bagwell,Odersky Lock-Free Resizable Concurrent Tries.pdf [2011] Prokopec,Bronson,Bagwell,Odersky Concurrent Tries with Efficient Non-Blocking Snapshots.pdf Реализация конкурентного trie. No comments.

Требующие доработки

Skip-list, основанный на fine-grained locks (блокировка на уровне элементов — именно для такого класса алгоритмов интересно реализовать различные mutex'ы). Интересная и относительно простая реализация skip-list. Node сделать аналогично тому, как сделано в libcds SkipListSet. Можно подумать над оптимизацией для «невысоких» узлов: для узла высотой 1 не выделяется никакой памяти под башню (у него нет башни), 50% узлов в skip-list имеют высоту 1; хотелось бы для узлов высотой ⇐ 4 не распределять память под башни, а использовать какой-то pre-allocated storage. Тем самым для 50 + 25 + 12,5 + 6,25 = 93.75% узлов не будет аллокаций, что хорошо должно сказаться на масштабируемости. Можно попробовать все узлы распределять высотой 4:

Мне этот алгоритм очень хочется попробовать. Единственный минус — авторы не показали, как использовать технику HP, только намекнули в нескольких предложениях. Требуется адаптировать алгоритм под Hazard Pointer и/или связаться с авторами, запросив пояснений.

Эта работа, несмотря на свою «старость», интересна тем, что позволяет сделать полноценные итераторы по lock-free структуре. На основе описанного алгоритма списка можно построить hash-map (MichaelHashSet/Map, SplitListSet/Map – эти структуры в libcds как параметр принимают реализацию списка) или даже SkipList с возможностью безопасной итерации, что очень ценно. Не забывать, что в данном алгоритме есть ошибка — см. [1995] Michael, Scott Correction of a Memory Management Method for Lock-Free Data Structures.pdf.

Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds.

В libcds уже есть HP- и RCU-based реализации (без helping'а), требуется сделать append-only версию (без GC – cds::gc::nogc), то есть версию без возможности удаления элементов. Попробовать реализовать helping (будет хорошо, если helping будет включаться отдельным флагом в traits).

Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, можно ли создать intrusive-версию.

Алгоритм и его подробный анализ есть в книге. Требуется создать стек на C++11, используя оба алгоритма, описанных в книге: на shared_ptr и split reference counting. Оценить, можно ли создать intrusive-версию.

Перспективный алгоритм построения lock-free стека, очереди, deque. Должен обеспечивать очень хорошую производительность для push-операций, так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting.

Интересный алгоритм open-addressing hash table. Следует сделать intrusive-вариант: храним указатели на данные, считаем, что распределять память под данные не нужно. Алгоритм описан достаточно хорошо, но непривычно. Замечания:

Развитие: если можно выделить алгоритм расширения hash-таблицы в отдельную программную сущность (класс), то его в принципе можно применить к любым алгоритмам open-addressing, например, к cuckoo hashing.

Также: А также: [2010] Gidenstam,Sundell,Tsigas Efficient Lock-Free Queues that Mind the Cache.pdf. Алгоритм интересен тем, что память выделяется под блок элементов, как в std::deque, что может значительно увеличить производительность stl-like очереди. Оценить, можно ли реализовать этот алгоритм на Hazard Pointer. Алгоритм существенно полагается на разработанную авторами SMR схему — помесь HP и reference counting – в части управления списком блоков. Попробовать использовать для блоков shared_ptr + HP. Создать intrusive и stl-like версии.

Сегментированный стек. В статье приводится псевдокод для tagged pointers (указатель + версия). Следует реализовать его на Hazard Pointer, intrusive и stl-like версию. Размер сегмента — степень двойки, задается в конструкторе. Оценить, возможно ли сделать оптимизацию — не удалять сегмент, а вести некоторый free-list нескольких удаленных сегментов.

Реализованные

Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется, так как deque основана на массиве.