ASCYLIB
ASCYLIB (with OPTIK) is a concurrent-search data-structure library with over 40 implementantions of linked lists, hash tables, skip lists, binary search trees, queues, and stacks.
Install / Use
/learn @LPD-EPFL/ASCYLIBREADME
ASCYLIB + OPTIK
ASCYLIB (with OPTIK) is a concurrent data-structure library. It contains over 40 implementations of linked lists, hash tables, skip lists, binary search trees (BSTs), queues, priority queues, and stacks. ASCYLIB contains sequential, lock-based, and lock-free implementations for each data structure.
ASCYLIB works on x86, SPARC, and Tilera architectures and contains tests to evaluate the throughput, latency, latency distribution, and energy efficiency of the included data structures.
OPTIK is a new design pattern for easily implementing fast and scalable concurrent data structures. We have merged several concurrent data structures developed with OPTIK in ASCYLIB. More details can be found here: http://lpd.epfl.ch/site/optik.
- Website : http://lpd.epfl.ch/site/ascylib - http://lpd.epfl.ch/site/optik
- Authors : Vasileios Trigonakis github@trigonakis.com, Tudor David repos@tudordavid.com
- Related Publications:
- Optimistic Concurrency with OPTIK,
Rachid Guerraoui, Vasileios Trigonakis (alphabetical order),
PPoPP 2016 - Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures,
Tudor David, Rachid Guerraoui, Vasileios Trigonakis (alphabetical order),
ASPLOS 2015
- Optimistic Concurrency with OPTIK,
Algorithms
The following table contains the algorithms (and various implementations of some algorithms) included in ASCYLIB:
| # | Name | Progress | Year | Referece | |:-:|-----------|:-----:|:-----:|:-----:| || Array Maps |||| |1| Java's CopyOnWrite array map | lock-based | 2004 | [ORACLE+04] | |2| Global-lock array map | lock-based | 2016 | [GT+16] | |3| OPTIK global-lock array map | lock-based | 2016 | [GT+16] | || Linked lists |||| |4| Sequential linked list | sequential | | | |5| Hand-over-hand locking linked list | lock-based | | [HS+12] | |6| Pugh's linked list | lock-based | 1990 | [P+90] | |7| Harris linked list | lock-free | 2001 | [H+01] | |8| Michael linked list | lock-free | 2002 | [M+02] | |9| Lazy linked list | lock-based | 2006 | [HHL+06] | |10| Harris linked list with ASCY | lock-free | 2015 | [DGT+15] | |11| Global-lock linked list with wait-free search | lock-based | 2016 | [GT+16] | |12| OPTIK global-lock linked list | lock-based | 2016 | [GT+16] | |13| OPTIK fine-grained linked list | lock-based | 2016 | [GT+16] | |14| OPTIK fine-grained linked list with cache | lock-based | 2016 | [GT+16] | || Hash Tables |||| |15| Sequential hash table | sequential | | | |16| Sequential hash table - less pointer indirections | sequential | | | |17| Hash table using hand-over-hand-locking lists | lock-based | | [HS+12] | |18| Hash table using Pugh's list | lock-based | 1990 | [P+90] | |19| Hash table using Harris' list | lock-free | 2001 | [H+01] | |20| Java's ConcurrentHashMap | lock-based | 2003 | [L+03] | |21| Hash table using Java's CopyOnWrite array map | lock-based | 2004 | [ORACLE+04] | |22| Intel's TBB hash table | lock-based | 2006 | [INTEL+06] | |23| Hash table using lazy list | lock-based | 2006 | [HHL+06] | |24| URCU hash table | lock-free | 2012 | [DMS+12] | |25| Java's ConcurrentHashMap with OPTIK | lock-based | 2016 | [GT+16] | |26| Hash table using fine-grained OPTIK list | lock-based | 2016 | [GT+16] | |27| Hash table using global-lock OPTIK list | lock-based | 2016 | [GT+16] | |28| Hash table using OPTIK array map | lock-based | 2016 | [GT+16] | || Skip Lists |||| |29| Sequential skip list | sequential | | | |30| Pugh skip list | lock-based | 1990 | [P+90] | |31| Fraser skip list | lock-free | 2003 | [F+03] | |32| Herlihy et al. skip list | lock-based | 2007 | [HLL+07] | |33| Fraser skip list with Herlihy's optimization | lock-free | 2011 | [HLS+11] | |34| Herlihy's skip list with OPTIK | lock-based | 2016 | [GT+16] | |35| OPTIK skip list using trylocks (default OPTIK skip list) | lock-based | 2016 | [GT+16] | |36| OPTIK skip list lock-version | lock-based | 2016 | [GT+16] | || Binary Search Trees (BSTs) |||| |37| Sequential external binary search tree | sequential | | | |38| Sequential internal binary search tree | sequential | | | |39| Bronson et al. binary search tree | lock-based | 2010 | [BCH+10] | |40| Ellen et al. binary search tree | lock-free | 2010 | [EFR+10] | |41| Howley and Jones binary search tree | lock-free | 2012 | [HJ+12] | |42| Natarajan and Mittal binary search tree | lock-free | 2014 | [NM+14] | |43| Drachsler et al. binary search tree | lock-based | 2014 | [DVY+14] | |44| BST-TK binary search tree | lock-based | 2015 | [DGT+15] | || Queues |||| |45| Michael and Scott (MS) lock-based queue | lock-based | 1996 | [MS+96] | |46| Michael and Scott (MS) lock-free queue | lock-free | 1996 | [MS+96] | |47| Michael and Scott (MS) hybrid queue | lock-based | 1996 | [MS+96] | |48| MS queue with OPTIK lock-version | lock-based | 2016 | [GT+16] | |49| MS queue with OPTIK trylock-version | lock-based | 2016 | [GT+16] | |50| MS queue with OPTIK trylock-version | lock-based | 2016 | [GT+16] | |51| MS queue with OPTIK and victim queue | lock-based | 2016 | [GT+16] | || Priority Queues |||| |52| Lotan and Shavit priority queue | lock-free | 2000 | [LS+00] | |53| Alistarh et al. priority queue based on Fraser's skip list | lock-based | 2015 | [AKL+15] | |54| Alistarh et al. priority queue based on Herlihy's skip list | lock-based | 2015 | [AKL+15] | |55| Alistarh et al. priority queue based on Pugh's skip list | lock-based | 2015 | [AKL+15] | || Stacks |||| |56| Global-lock stack | lock-based | | | |57| Treiber stack | lock-free | 1986 | [T+86] | |58| Treiber stack with OPTIK trylocks | lock-based | 2016 | [GT+16] |
References
- <a name="AKL+15">[AKL+15]</a> D. Alistarh, J. Kopinsky, J. Li, N. Shavit. The SprayList: A Scalable Relaxed Priority Queue. PPoPP '15.
- <a name="BCH+10">[BCH+10]</a> N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A Practical Concurrent Binary Search Tree. PPoPP '10.
- <a name="DGT+15">[DGT+15]</a> T. David, R. Guerraoui, and V. Trigonakis. Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures. ASPLOS '15.
- <a name="DMS+12">[DMS+12]</a> M. Desnoyers, P. E. McKenney, A. S. Stern, M. R. Dagenais, and J. Walpole. User-level implementations of read-copy update. PDS '12.
- <a name="DVY+14">[DVY+14]</a> D. Drachsler, M. Vechev, and E. Yahav. Practical Concurrent Binary Search Trees via Logical Ordering. PPoPP '14.
- <a name="EFR+10">[EFR+10]</a> F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. Non-blocking Binary Search Trees. PODC '10.
- <a name="F+03">[F+03]</a> K. Fraser. Practical Lock-Freedom. PhD thesis, University of Cambridge, 2004.
- <a name="GT+16">[GT+16]</a> R. Guerraoui, and V. Trigonakis. Optimistic Concurrency with OPTIK. PPoPP '16.
- <a name="H+01">[H+01]</a> T. Harris. A Pragmatic Implementation of Non-blocking Linked Lists. DISC '01.
- <a name="HHL+06">[HHL+06]</a> S. Heller, M. Herlihy, V. Luchangco, M. Moir, W. N. Scherer, and N. Shavit. A Lazy Concurrent List-Based Set Algorithm. OPODIS '05.
- <a name="HS+12">[HS+12]</a> M. Herlihy and N. Shavit. The Art of Multiprocessor Programming, Revised First Edition. 2012.
- <a name="HLL+07">[HLL+07]</a> M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit. A Simple Optimistic Skiplist Algorithm. SIROCCO '07.
- <a name="HLS+11">[HLS+11]</a> M. Herlihy, Y. Lev, and N. Shavit. Concurrent lock-free skiplist with wait-free contains operator, May 3 2011. US Patent 7,937,378.
- <a name="HJ+12">[HJ+12]</a> S. V. Howley and J. Jones. A non-blocking internal binary search tree. SPAA '12.
- <a name="INTEL+06">[INTEL+06]</a> Intel. Intel Thread Building Blocks. https://www.threadingbuildingblocks.org.
- <a name="L+03">**[L+
