Differences

This shows you the differences between two versions of the page.

--- projects:libcds:tasks [2017/02/25 14:59] – kel
+++ projects:libcds:tasks [2019/02/04 20:12] (current) – kel
@@ Line 1: / Line 1: @@
 ====== Алгоритмы для доработки в libcds ======
-===== Профилирование и поиск ошибок =====
+===== Требования к реализации =====
-Найти, обосновать и исправить не менее 3 ошибок || пограммирвания (возможные dead lock, data race...). Предполагается использование автоматизированных стредств поиска, таких как:
+//К следующему семестру более явно написать формулировки пп. 4 и 9//
-  - Valgrind //helgrind//
+  - Pull Request должен быть сливаем с текущей master-веткой репозитория
-  - Intel Parallel Studio
+  - Отсутствие закомментированных кусков кода
-  - Google Thread Sanitizer...
+  - Код написан в стиле и стандарте кодирования библиотеки
+  - Написан набор модульных и стресс-тестов (если структура данных стандартная, то тесты используются сущетвующие с регистрацией своей структуры данных)
+  - Поддерживается интерфейс сбора статистики по контейнеру, если таковой есть в библиотеке для реализуемого типа контейнеров
+  - Сборка и прогон тестов с активированными Address и Undefined Behavior Sanitizers не выдаёт никаких ошибок ("-fsanitize=address,undefined")
+  - Тесты прогнаны с активированным Thread Sanitizer и по каждому предупреждению есть уверенность, что это не ошибка
+  - Тесты проанализированы сторонним средством поиска ошибок (например, Intel Parallel Studio) и также по каждому предупреждению есть уверенность, что это не ошибка
+  - После выполнения вышеуказанных пунктов ветка добавляется в CI и на всех поддерживаемых платформах все тесты проходят успешно
-===== Алгоритмы =====
+===== Нереализованные =====
 ==== [2011] Bar-Nissan, Hendler, Suissa. A dynamic elimination-combining stack algorithm.pdf ====
 //Сложность://3\\
@@ Line 15: / Line 21: @@
   - Центральный стек — алгоритм Трейбера. Будет здорово, если в реализации класс стека будет вынесен в опции (traits) класса DECStack.
-==== [2014] Henzinger, Kirsch, Payer, Sezgin, Sokolova Quantitative Relaxation of Concurrent Data Structures.pdf ====
+==== [2005] Purcell, Harris Non-blocking Hashtables with open addressing.pdf ====
-//Сложность://3\\
+//Сложность://5+\\
-Сегментированный стек. В статье приводится псевдокод для tagged pointers (указатель + версия). Следует реализовать его на Hazard Pointer, intrusive и stl-like версию. Размер сегмента — степень двойки, задается в конструкторе. Оценить, возможно ли сделать оптимизацию — не удалять сегмент, а вести некоторый free-list нескольких удаленных сегментов.
+Еще одна разновидность open-addressing hash table. Алгоритм не описывает расширение таблицы, предлагается использовать метод из предыдущей работы ([2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf).
-==== [2010] Gidenstam,Sundell,Tsigas Cache-Aware Lock-free Queues for Multiple Producers-Consumers and Weak Memory Consistency.pdf ====
+==== [2012] Crain,Gramoli,Raynal A Contention-Friendly, Non-Blocking Skip List.pdf ====
-//Сложность://4\\
+//Сложность://6\\
-Также: А также: [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 версии.
+Ещё одна реализация skip-list. Алгоритм интересен тем, что на нулевом уровне узлы связаны в double-linked list. Авторы не говорят, применим ли HP к их алгоритму, вместо этого они предлагают использовать reference counting или кратко описанный ими epoch-based подход. Требуется понять, можно ли применить HP и/или RCU.
-==== [2013] Henzinger,Payer,Sezgin Replacing competition with cooperation to achieve scalable lock-free FIFO queues.pdf ====
+==== [2011] Brown,Helga Non-blocking k-ary Search Trees.pdf ====
-//Сложность://4\\
+//Сложность://7\\
-Мне этот алгоритм очень хочется попробовать. Единственный минус — авторы не показали, как использовать технику HP, только намекнули в нескольких предложениях. Требуется адаптировать алгоритм под Hazard Pointer и/или связаться с авторами, запросив пояснений.
+Развитие подхода [2010] Ellen,Fatourou,Ruppert,vanBreugel Non-blocking Binary Search Trees.pdf на k-арные деревья. Сделать без helping'а, оценить, во что выливается реализация helping'а и стоит ли его вообще делать.
-==== [1995] Valois Lock-Free Linked Lists Using Compare-and_Swap.pdf ====
+==== [2012] Afek,Kaplan,Korenfeld,Morrison,Tarjan CBTree - A Practical Concurrent Self-adusting Search Tree.pdf ====
-//Сложность://3+\\
+//Сложность://7+\\
-Эта работа, несмотря на свою «старость», интересна тем, что позволяет сделать полноценные итераторы по 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.
+[2012] Korenfeld CBTree - A Practical Concurrent Self-Adjusting Search Tree.pdf
+Разновидность самобалансирующегося дерева, построенного с использованием техники hand-over-hand locking. Проанализировать, какой SMR подходит (HP, RCU, оба), либо же алгоритм не требует никакой SMR схемы.
-==== [2003] Michael CAS-Based Lock-Free Algorithm for Shared Deques.pdf ====
+==== [2011] Prokopec,Bagwell,Odersky Cache-Aware Lock-Free Concurrent Hash Tries.pdf ====
-//Сложность://3\\
+//Сложность://8\\
-Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется, так как deque основана на массиве.
+[2011] Prokopec,Bagwell,Odersky Lock-Free Resizable Concurrent Tries.pdf
+[2011] Prokopec,Bronson,Bagwell,Odersky Concurrent Tries with Efficient Non-Blocking Snapshots.pdf
-==== [2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf ====
+Реализация конкурентного trie. No comments.
-//Сложность://5\\
-Интересный алгоритм open-addressing hash table. Следует сделать intrusive-вариант: храним указатели на данные, считаем, что распределять память под данные не нужно.
-Алгоритм описан достаточно хорошо, но непривычно.
-Замечания:
-  - Понять, где следует применять атомарные операции. В псевдокоде это отмечено скобками < >:
-    * < a := b > => atomic load, atomic store
-    * < if a == 0 then a := b > => a.CAS( 0, b )
-  - Псевдокод описан в предположении, что имеется P потоков (процессов), работающих с hash  set. Попробовать избавиться от P. Если не получится — P должен быть параметром конструктора. Для thread-local data использовать TLS. Реализация должна учитывать, что P может быть достигнуто — в этом случае либо выбрасывать исключение (плохо), либо каким-то образом дожидаться освобождения слота (лучше).
-  - К данным, хранимым в hash table, следует применять Hazard Pointer. Для управления внутренними структурами алгоритм использует разновидность refCount.
-Развитие: если можно выделить алгоритм расширения hash-таблицы в отдельную программную сущность (класс), то его в принципе можно применить к любым алгоритмам open-addressing, например, к cuckoo hashing.
-==== [2005] Purcell, Harris Non-blocking Hashtables with open addressing.pdf ====
-//Сложность://5+\\
-Еще одна разновидность open-addressing hash table. Алгоритм не описывает расширение таблицы, предлагается использовать метод из предыдущей работы ([2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf).
+===== Требующие доработки =====
 ==== [2007] Herlihy, Lev, Luchangco, Shavit A Provably Correct Scalable Concurrent Skip List .pdf ====
+> //Сложность://4+
-//Сложность://4+\\
+> [[https://github.com/khizmax/libcds/pull/109|Pull request]]
 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:
@@ Line 86: / Line 75: @@
 </code>
-==== [2008] Herlihy,Shavit,Tzafrir Hopscotch Hashing.pdf ====
+==== [2013] Henzinger,Payer,Sezgin Replacing competition with cooperation to achieve scalable lock-free FIFO queues.pdf ====
+> //Сложность://4
+> [[https://github.com/khizmax/libcds/pull/108|Pull request]]
-//Сложность://5+\\
+Мне этот алгоритм очень хочется попробовать. Единственный минус — авторы не показали, как использовать технику HP, только намекнули в нескольких предложениях. Требуется адаптировать алгоритм под Hazard Pointer и/или связаться с авторами, запросив пояснений.
-Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds.
+==== [1995] Valois Lock-Free Linked Lists Using Compare-and_Swap.pdf ====
+> //Сложность://3+
+> [[https://github.com/khizmax/libcds/pull/107|Pull request]]
-==== [2012] Crain,Gramoli,Raynal A Contention-Friendly, Non-Blocking Skip List.pdf ====
+Эта работа, несмотря на свою «старость», интересна тем, что позволяет сделать полноценные итераторы по 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.
-//Сложность://6\\
+==== [2008] Herlihy,Shavit,Tzafrir Hopscotch Hashing.pdf ====
+> //Сложность://5+
+> [[https://github.com/khizmax/libcds/pull/106|Pull request]]
-Ещё одна реализация skip-list. Алгоритм интересен тем, что на нулевом уровне узлы связаны в double-linked list. Авторы не говорят, применим ли HP к их алгоритму, вместо этого они предлагают использовать reference counting или кратко описанный ими epoch-based подход. Требуется понять, можно ли применить HP и/или RCU.
+Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds.
 ==== [2010] Ellen,Fatourou,Ruppert,vanBreugel Non-blocking Binary Search Trees.pdf ====
+> //Сложность://2+
-//Сложность://2+\\
+> [[https://github.com/khizmax/libcds/pull/104|Pull request]]
 В libcds уже есть HP- и RCU-based реализации (без helping'а), требуется сделать append-only версию (без GC – cds::gc::nogc), то есть версию без возможности удаления элементов. Попробовать реализовать helping (будет хорошо, если helping будет включаться отдельным флагом в traits).
-==== [2010] Bronson,Casper,Chafi,Olukotun A Practical Concurrent Binary Search Tree.pdf ====
+==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ====
+> //Сложность://2
+> [[https://github.com/khizmax/libcds/pull/72|Pull request]]
-//Сложность://7\\
+Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, можно ли создать intrusive-версию.
-Реализация конкурентного AVL-tree, новый метод optimistic hand-over-hand locking. Проанализировать, какой SMR подходит (HP, RCU, оба), либо же алгоритм не требует никакой SMR схемы.
+==== A.Williams “C++ Concurrency in Action” - lock-free стек на shared_ptr ====
+> //Сложность://1+
+> [[https://github.com/khizmax/libcds/pull/73|Pull request]]
-==== [2011] Brown,Helga Non-blocking k-ary Search Trees.pdf ====
+Алгоритм и его подробный анализ есть в книге. Требуется создать стек на C++11, используя оба алгоритма, описанных в книге: на shared_ptr и split reference counting. Оценить, можно ли создать intrusive-версию.
-//Сложность://7\\
+==== [2014] Dodds,Haas,Kirsch Fast Concurrent Data-Structures Through Explicit Timestamping.pdf ====
+> //Сложность://4\\
+> [[https://github.com/khizmax/libcds/pull/55|Pull request]]
-Развитие подхода [2010] Ellen,Fatourou,Ruppert,vanBreugel Non-blocking Binary Search Trees.pdf на k-арные деревья. Сделать без helping'а, оценить, во что выливается реализация helping'а и стоит ли его вообще делать.
+Перспективный алгоритм построения lock-free стека, очереди, deque. Должен обеспечивать очень хорошую производительность для push-операций, так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting.
-==== [2012] Afek,Kaplan,Korenfeld,Morrison,Tarjan CBTree - A Practical Concurrent Self-adusting Search Tree.pdf ====
+==== [2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf ====
+> //Сложность://5\\
+> [[https://github.com/khizmax/libcds/pull/102|Pull request]]
-//Сложность://7+\\
+Интересный алгоритм open-addressing hash table. Следует сделать intrusive-вариант: храним указатели на данные, считаем, что распределять память под данные не нужно.
+Алгоритм описан достаточно хорошо, но непривычно.
+Замечания:
+  - Понять, где следует применять атомарные операции. В псевдокоде это отмечено скобками < >:
+    * < a := b > => atomic load, atomic store
+    * < if a == 0 then a := b > => a.CAS( 0, b )
+  - Псевдокод описан в предположении, что имеется P потоков (процессов), работающих с hash  set. Попробовать избавиться от P. Если не получится — P должен быть параметром конструктора. Для thread-local data использовать TLS. Реализация должна учитывать, что P может быть достигнуто — в этом случае либо выбрасывать исключение (плохо), либо каким-то образом дожидаться освобождения слота (лучше).
+  - К данным, хранимым в hash table, следует применять Hazard Pointer. Для управления внутренними структурами алгоритм использует разновидность refCount.
-[2012] Korenfeld CBTree - A Practical Concurrent Self-Adjusting Search Tree.pdf
+Развитие: если можно выделить алгоритм расширения hash-таблицы в отдельную программную сущность (класс), то его в принципе можно применить к любым алгоритмам open-addressing, например, к cuckoo hashing.
-Разновидность самобалансирующегося дерева, построенного с использованием техники hand-over-hand locking. Проанализировать, какой SMR подходит (HP, RCU, оба), либо же алгоритм не требует никакой SMR схемы.
-==== [2011] Prokopec,Bagwell,Odersky Cache-Aware Lock-Free Concurrent Hash Tries.pdf ====
+==== [2010] Gidenstam,Sundell,Tsigas Cache-Aware Lock-free Queues for Multiple Producers-Consumers and Weak Memory Consistency.pdf ====
+> //Сложность://4\\
+> [[https://github.com/khizmax/libcds/pull/100|Pull request]]
-//Сложность://8\\
+Также: А также: [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 версии.
-[2011] Prokopec,Bagwell,Odersky Lock-Free Resizable Concurrent Tries.pdf
+==== [2014] Henzinger, Kirsch, Payer, Sezgin, Sokolova Quantitative Relaxation of Concurrent Data Structures.pdf ====
-[2011] Prokopec,Bronson,Bagwell,Odersky Concurrent Tries with Efficient Non-Blocking Snapshots.pdf
+> //Сложность://3\\
-Реализация конкурентного trie. No comments.
+> [[https://github.com/khizmax/libcds/pull/98|Pull request]]
+Сегментированный стек. В статье приводится псевдокод для tagged pointers (указатель + версия). Следует реализовать его на Hazard Pointer, intrusive и stl-like версию. Размер сегмента — степень двойки, задается в конструкторе. Оценить, возможно ли сделать оптимизацию — не удалять сегмент, а вести некоторый free-list нескольких удаленных сегментов.
 ===== Реализованные =====
-==== A.Williams “C++ Concurrency in Action” - lock-free стек на shared_ptr ====
+==== [2003] Michael CAS-Based Lock-Free Algorithm for Shared Deques.pdf ====
-> //Сложность://1+
+> //Сложность://3\\
-> [[https://github.com/khizmax/libcds/pull/54|Pull request]]
+> [[https://github.com/khizmax/libcds/pull/88|Pull request]]
-Алгоритм и его подробный анализ есть в книге. Требуется создать стек на C++11, используя оба алгоритма, описанных в книге: на shared_ptr и split reference counting. Оценить, можно ли создать intrusive-версию.
+Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется, так как deque основана на массиве.
-==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ====
-> //Сложность://2
-> [[https://github.com/khizmax/libcds/pull/72|Pull request]]
-Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, можно ли создать intrusive-версию.
-==== [2014] Dodds,Haas,Kirsch Fast Concurrent Data-Structures Through Explicit Timestamping.pdf ====
-> //Сложность://4\\
-> [[https://github.com/khizmax/libcds/pull/55|Pull request]]
-Перспективный алгоритм построения lock-free стека, очереди, deque. Должен обеспечивать очень хорошую производительность для push-операций, так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting.