Concurrent data structures
February 25, 2019 · View on GitHub
This repository contains a compilation of the available concurrent data structures on the web that support at least lock-free or wait-free properties. Some lock-based fine-grained synchronization approaches, that are competitive with lock-free approaches, are also considered. If you know or own an implementation of a concurrent data structure, feel free to add it to the list.
| Category | Name | Properties | Language | Source |
|---|---|---|---|---|
| Stack | Stack | lock-free | C | Liblfds |
| Stack | Stack | lock-free | C++ | Boost |
| Stack | Stack | lock-free | Ada | NBAda |
| Stack | Trieber Stack | lock-free (based on Treiber's stack algorithm) | C++ | cds |
| Stack | FCStack | lock-free, based on paper [2010] "Flat Combining and the Synchronization-Parallelism Tradeoff" | C++ | cds |
| Queue | Queue | lock-free | C | Liblfds |
| Queue | Queue | lock-free multi-produced/multi-consumer queue | C++ | Boost |
| Queue | Queue | lock-free queue of bounded and dynamic size | Ada | NBAda |
| Queue | Deques | lock-free deques of dynamic size | Ada | NBAda |
| Queue | Bounded Queue | lock-free | C | Liblfds |
| Queue | Priority Queue | lock-free priority queues of dynamic size | Ada | NBAda |
| Queue | Basket Queue | basket lock-free queue (non-intrusive variant) | C++ | cds |
| Queue | MSQueue | Michael & Scott lock-free queue | C++ | cds |
| Queue | RWQueue | Michael & Scott blocking queue with fine-grained synchronization schema | C++ | cds |
| Queue | MoirQueue | variation of Michael & Scott's lock-free queue | C++ | cds |
| Queue | Optimistic Queue | lock-free, based on paper [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues" | C++ | cds |
| Queue | Segmented Queue | based on paper [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency" | C++ | cds |
| Queue | FCQueue | Flat combining queue based on paper by Hendler, Incze, Shavit and Tzafrir [2010] "Flat Combining and the Synchronization-Parallelism Tradeoff" | C++ | cds |
| Queue | Tsigas Cycle Queue | non-intrusive implementation of Tsigas & Zhang cyclic queue based | C++ | cds |
| Queue | Vyukov MPMC Cycle Queue | multi-producer multi-consumer (MPMC), array-based, fails on overflow, does not require GC, w/o priorities, causal FIFO, blocking producers and consumers queue. The algorithm is pretty simple and fast. It's not lock-free in the official meaning, just implemented by means of atomic RMW operations w/o mutexes. | C++ | cds |
| Queue | Ringbuffer (circular queue) | lock-free | C | Liblfds |
| Queue | Ringbuffer (circular queue) | lock-free multi-produced/multi-consumer queue | C++ | Boost |
| List | LinkedList | lock-free | C++ | Lawrence Bush |
| List | Free List | lock-free | C | Liblfds |
| List | Single LinkedList (ordered) | lock-free | C | Liblfds |
| List | Lazy List, Single LinkedList (ordered) | based on an optimistic locking scheme for inserts and removes, eliminating the need to use the equivalent of an atomically markable reference. Based on paper [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit "A Lazy Concurrent List-Based Set Algorithm" | C++ | cds |
| List | Michael List, Single LinkedList (ordered) | based on paper [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets" | C++ | cds |
| List | Single LinkedList (unordered) | lock-free | C | Liblfds |
| Map | HashMap | lock-free | C | Liblfds |
| Map | Spllited Ordered List Map | based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables" and [2008] Nir Shavit "The Art of Multiprocessor Programming" | C++ | cds |
| Map | Stripped Map | striped hash map based on lock striping technique by [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming" | C++ | cds |
| Map | Michael HashMap | based on lock'free ordered list by [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets" | C++ | cds |
| Map | Skip List Map | lock-free variant of skip-list implemented according to book [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming", chapter 14.4 "A Lock-Free Concurrent Skiplist" | C++ | cds |
| Map | Feldman Hashmap | hash map based on multi-level array. Based on paper [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: Wait-free Extensible Hash Maps" | C++ | cds |
| Map | HashMap | Java | Oracle | |
| Map | Map | Scala | Root package | |
| Map | Cuckoo Map | C++ | cds | |
| Map | Fast Concurrent Memoization Map | Fast Concurrent Memoization Map (fcmm) is an almost lock-free concurrent hashmap written in C++11 to be used for memoization in concurrent environments. | C++ | fcmm |
| Map | Junction | Junction is a library of concurrent data structures in C++. It contains several hash map implementations. | C++ | junction |
| Tree | Binary Tree | lock-free | C | Liblfds |
| Tree | Binary Tree | non-blocking BST (external) | [paper (2010)] (http://dl.acm.org/citation.cfm?id=1835736) | |
| Tree | Ellen's Binary Tree | C++ | cds | |
| Tree | Natarajan's Binary Search Tree | lock-free BST (external) | paper (2014) | |
| Tree | Howley's Binary Search Tree | non-blocking internal BST | paper (2012) | |
| Tree | Ramachandran's Binary Search Tree | lock-free internal BST | C++ | paper (2015) |
| Tree | Suffix Tree | Lookups are lock-free. Write operations are blocking | Java | Concurrent Suffix Trees |
| Tree | Radix Tree | Lookups are lock-free. Write operations are blocking | Java | Concurrent Suffix Trees |
| Tree | B Tree | C | B-tree project | |
| Tree | Red Black Tree | C | University of Cambridge | |
| Tree | Red Black Tree | Wait-free red black tree | paper | |
| Tree | Bronson AVL Tree | C++ | cds | |
| Tree | Trie | Scala | Root package | |
| Tree | Heap | C++ | cds | |
| Set | Cuckoo Set | Cuckoo hash map based on papers [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report" and [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming" | C++ | cds |
| Set | Stripped Set | Striped hash set based on approach proposed in [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming" | C++ | cds |
| Set | Feldman Hash Set | hash set based on multi-level array. Based on approached proposed in [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: Wait-free Extensible Hash Maps" | C++ | cds |
| Set | Skip List Set | lock-free variant of skip-list implemented according to book [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming", chapter 14.4 "A Lock-Free Concurrent Skiplist" | C++ | cds |
| Set | Sets | lock-free sets of dynamic size | Ada | NBAda |
| Ring Buffer | Ring Buffer | Lock-free multi-producer single-consumer (MPSC) ring buffer | C++ | rmind/ringbuf |
| Container library | Tervel | Wait-free | C++ | Tervel |
Contributors
- Joel Fuentes
- Chien-Hao Chen
- Matías Bustos
- Simon Giesecke