A collection of miscellaneous things...

Data Structures

A list of high-performance, mostly non-blocking data structures.

  1. Treiber's Stack R. Kent Treiber. 1986. Systems programming: coping with parallelism. Link
  2. Michael&Scott's Queue Maged M. Michael and Michael L. Scott. 1996. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. DOI
  3. DGLM Queue Simon Doherty, Lindsay Groves, Victor Luchangco, and Mark Moir. 2004. Formal Verification of a Practical Lock-Free Queue Algorithm. DOI
  4. Vechev&Yahav's DCAS Set Martin T. Vechev and Eran Yahav. 2008. Deriving linearizable fine-grained concurrent objects. (Figures 8 and 9.) DOI
  5. Vechev&Yahav's CAS Set Martin T. Vechev and Eran Yahav. 2008. Deriving linearizable fine-grained concurrent objects. (Figures 2.) DOI
  6. ORVVY SetDBLP: Peter W. O'Hearn, Noam Rinetzky, Martin T. Vechev, Eran Yahav, and Greta Yorsh. 2010. Verifying linearizability with hindsight. DOI
  7. Michael's Set Maged M. Michael. 2002. High performance dynamic lock-free hash tables and list-based sets. DOI
  8. Harris' List (Set) Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. DOI
  9. Elimination-backoff Stacks
    • Danny Hendler, Nir Shavit, and Lena Yerushalmi. 2004. A scalable lock-free stack algorithm. DOI
    • Gal Bar-Nissan, Danny Hendler, and Adi Suissa. 2011. A Dynamic Elimination-Combining Stack Algorithm. DOI
  10. More (Optimized) Queues
    • Philippas Tsigas and Yi Zhang. 2001. A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems. DOI
    • Alex Kogan and Erez Petrank. 2011. Wait-free queues with multiple enqueuers and dequeuers. DOI
    • Alex Kogan and Erez Petrank. 2012. A methodology for creating fast wait-free data structures. DOI
    • Adam Morrison and Yehuda Afek. 2013. DOI
  11. Time-stamped Stacks and Queues Stack Mike Dodds, Andreas Haas, and Christoph M. Kirsch. 2015. A Scalable, Correct Time-Stamped Stack. DOI
  12. Priority Queues
    • Greg Barnes. 1992. Wait-Free Algorithms for Heaps. Link
    • Amos Israeli and Lihu Rappoport. 1993. Efficient Wait-Free Implementation of a Concurrent Priority Queue. DOI
    • Håkan Sundell and Philippas Tsigas. 2003. Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems. DOI
  13. Skip Lists
    • Håkan Sundell and Philippas Tsigas. 2003. Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems. DOI
    • Keir Fraser. 2004. Practical lock-freedom. Link
    • Mikhail Fomitchev and Eric Ruppert. 2004. Lock-free linked lists and skip lists. DOI
  14. Doubly-linked and double-ended queues
    • Michael Greenwald. 1990. Non-Blocking Synchronization and System Design. Link
    • Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton. 1998. Thread Scheduling for Multiprogrammed Multiprocessors. DOI
    • Ole Agesen, David Detlefs, Christine H. Flood, Alex Garthwaite, Paul Alan Martin, Nir Shavit, and Guy L. Steele Jr. 2000. DCAS-based concurrent deques. DOI
    • Maged M. Michael. 2003. CAS-Based Lock-Free Algorithm for Shared Deques. DOI
    • Håkan Sundell, Philippas Tsigas. 2004. Lock-Free and Practical Doubly Linked List-Based Deques Using Single-Word Compare-and-Swap. DOI
    • Niloufar Shafiei. 2015. Non-Blocking Doubly-Linked Lists with Good Amortized Complexity. DOI
    • Andreas Haas. 2015. Fast Concurrent Data Structures Through Timestamping. Link
  15. Search Trees
    • Greg Barnes. 1992. Wait-Free Algorithms for Heaps. Link
    • Anastasia Braginsky and Erez Petrank. 2012. A lock-free B+tree. DOI
    • Justin J. Levandoski, David B. Lomet, and Sudipta Sengupta. 2013. The Bw-Tree: A B-tree for new hardware platforms. DOI
    • Aravind Natarajan and Neeraj Mittal. 2014. Fast concurrent lock-free binary search trees. DOI
    • Arunmoezhi Ramachandran and Neeraj Mittal. 2015. A Fast Lock-Free Internal Binary Search Tree. DOI
    • Aravind Natarajan, Arunmoezhi Ramachandran, and Neeraj Mittal. 2020. FEAST: A Lightweight Lock-free Concurrent Binary Search Tree. DOI

Reclamation Schemes

Non-blocking data structures require careful reclamation of unused memory in order to avoid accessing already reclaimed memory (use-after-free bugs) and related to that avoiding the ABA problem. Here is a (fabulously incomplete) list of safe memory reclamation schemes for non-blocking data structures (as of mid 2021), in no particular order.

  1. Free Lists
    • IBM. 1983. IBM System/370 Extended Architecture: Principles of Operation. Link
    • R. Kent Treiber. 1986. Systems programming: coping with parallelism. Link
  2. Epoch-based Reclamation (EBR)
    • Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. DOI
    • Keir Fraser. 2004. Practical lock-freedom. Link
  3. Hazard Pointers (HP) Maged M. Michael. 2002. Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. DOI
  4. Non-blocking Reference Counting
    • David Detlefs, Paul Alan Martin, Mark Moir, Guy L. Steele Jr. 2001. Lock-free reference counting. DOI
    • Maurice Herlihy, Victor Luchangco, Paul A. Martin, and Mark Moir. 2005. Nonblocking memory management support for dynamic-sized data structures. DOI
  5. DEBRA Trevor A. Brown. 2015. Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way. DOI
  6. Hyaline Ruslan Nikolaev and Binoy Ravindran. 2019. Hyaline: Fast and Transparent Lock-Free Memory Reclamation DOI
  7. Repeat Offender Maurice Herlihy, Victor Luchangco, and Mark Moir. 2002. The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures. DOI
  8. <unnamed> Zahra Aghazadeh, Wojciech M. Golab, and Philipp Woelfel. 2014. Making objects writable. DOI
  9. <unnamed> Dave Dice, Maurice Herlihy, and Alex Kogan. 2016. Fast non-intrusive memory reclamation for highly-concurrent data structures. DOI
  10. Cadence Oana Balmau, Rachid Guerraoui, Maurice Herlihy, and Igor Zablotchi. 2016. Fast and Robust Memory Reclamation for Concurrent Data Structures. DOI
  11. Dynamic Collect Aleksandar Dragojevic, Maurice Herlihy, Yossi Lev, and Mark Moir. 2011. On the power of hardware transactional memory to simplify memory management. DOI
  12. StackTrack Dan Alistarh, Patrick Eugster, Maurice Herlihy, Alexander Matveev, and Nir Shavit. 2014. StackTrack: an automated transactional approach to concurrent memory reclamation. DOI
  13. ThreadScan Dan Alistarh, William M. Leiserson, Alexander Matveev, and Nir Shavit. 2015. ThreadScan: Automatic and Scalable Memory Reclamation. DOI
  14. Drop the Anchor Anastasia Braginsky, Alex Kogan, and Erez Petrank. 2013. Drop the anchor: lightweight memory management for non-blocking data structures. DOI
  15. Optimistic Access Nachshon Cohen and Erez Petrank. 2015. Efficient Memory Management for Lock-Free Data Structures with Optimistic Access. DOI
  16. Automatic Optimistic Access Nachshon Cohen and Erez Petrank. 2015. Automatic memory reclamation for lock-free data structures. DOI
  17. QSense Oana Balmau, Rachid Guerraoui, Maurice Herlihy, and Igor Zablotchi. 2016. Fast and Robust Memory Reclamation for Concurrent Data Structures. DOI
  18. Stamp-it Manuel J. Pöter. 2018. Effective Memory Reclamation for Lock-Free Data Structures in C++. Link
  19. Hazard Eras (HE) Pedro Ramalhete and Andreia Correia. 2017. Hazard Eras—Non-Blocking Memory Reclamation. DOI
  20. Interval-based Reclamation (IBR) Haosen Wen, Joseph Izraelevitz, Wentao Cai, H. Alan Beadle, and Michael L. Scott. 2018. Interval-based memory reclamation. DOI
  21. Wait-Free Eras Ruslan Nikolaev and Binoy Ravindran. 2020. Universal wait-free memory reclamation. DOI
  22. PEBR Jeehoon Kang and Jaehwang Jung. 2020. A marriage of pointer- and epoch-based reclamation. DOI
  23. Free Access Nachshon Cohen. 2018. Every data structure deserves lock-free memory reclamation. DOI
  24. Beware&Cleanup Anders Gidenstam, Marina Papatriantafilou, Håkan Sundell, and Philippas Tsigas. 2005. Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting. DOI
  25. Isolde Albert Mingkun Yang and Tobias Wrigstad. 2017. Type-assisted automatic garbage collection for lock-free data structures. DOI
  26. NBR Ajay Singh, Trevor Brown, and Ali Mashtizadeh. 2021. NBR: neutralization based reclamation. DOI
  27. VBR Gali Sheffi, Maurice Herlihy, and Erez Petrank 2021. VBR: Version Based Reclamation. DOI

For performance comparisons, you might consider, among others:

  1. Thomas E. Hart, Paul E. McKenney, Angela Demke Brown, and Jonathan Walpole. 2007. Performance of memory reclamation for lockless synchronization. DOI
  2. Manuel J. Pöter. 2018. Effective Memory Reclamation for Lock-Free Data Structures in C++. Link