xenium

xenium is a headeronly library that provides a collection of concurrent data structures and memory reclamation algorithms. The data structures are parameterized so that they can be used with various reclamation schemes (similar to how the STL allows customization of allocators).
The documentation provides more details.
This project is based on my previous work in https://github.com/mpoeter/emr
At the moment the number of provided data structures is rather small since the focus so far was on the reclamation schemes. However, the plan is to add several more data structures in the near future.
michael_scott_queue
 an unbounded lockfree multiproducer/multiconsumer queue proposed by Michael and Scott [MS96].ramalhete_queue
 a fast unbounded lockfree multiproducer/multiconsumer queue proposed by Ramalhete [Ram16].vyukov_bounded_queue
 a bounded multiproducer/multiconsumer FIFO queue based on the version proposed by Vyukov [Vyu10].kirsch_kfifo_queue
 an unbounded multiproducer/multiconsumer kFIFO queue proposed by Kirsch et al. [KLP13].kirsch_bounded_kfifo_queue
 a bounded multiproducer/multiconsumer kFIFO queue proposed by Kirsch et al. [KLP13].nikolaev_queue
 an unbounded multiproducer/multiconsumer queue proposed by Nikolaev [Nik19].nikolaev_bounded_queue
 a bounded multiproducer/multiconsumer queue proposed by Nikolaev [Nik19].harris_michael_list_based_set
 a lockfree container that contains a sorted set of unique objects. This data structure is based on the solution proposed by Michael [Mic02] which builds upon the original proposal by Harris [Har01].harris_michael_hash_map
 a lockfree hashmap based on the solution proposed by Michael [Mic02] which builds upon the original proposal by Harris [Har01].chase_work_stealing_deque
 a work stealing deque based on the proposal by Chase and Lev [CL05].vyukov_hash_map
 a concurrent hashmap that uses fine grained locking for update operations. This implementation is heavily inspired by the version proposed by Vyukov [Vyu08].left_right
 a generic implementation of the LeftRight algorithm proposed by Ramalhete and Correia [RC15].seqlock
 an implementation of the sequence lock (also often referred to as "sequential lock").The implementation of the reclamation schemes is based on an adapted version of the interface proposed by Robison [Rob13].
The following reclamation schemes are implemented:
lock_free_ref_count
[Val95, MS95]hazard_pointer
[Mic04]hazard_eras
[RC17]quiescent_state_based
generic_epoch_based
 this is a generalized epoch based reclaimer that can be configured in several ways. For simplicity, the following aliases are predefined for the corresponding configurations.
stamp_it
[PT18a, PT18b]xenium is a header only library, so in order to use it, it is sufficient to include the xenium folder in your list of include directories. No other 3rd party libraries are required. However, the implementation uses C++17 features, so a compiler with sufficient C++17 support is required. The following compilers are used in the CI builds and are therefore known to be supported:
The unit test require googletest
and the benchmarks require taocpp/json
and taocpp/config
. These dependencies are included as submodules, so the unit tests and/or the benchmarks can be built as follows:
[Bro15]  Trevor Alexander Brown. Reclaiming memory for lockfree data structures: There has to be a better way. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pages 261–270. ACM, 2015. 
[CL05]  David Chase and Yossi Lev. Dynamic circular workstealing deque. In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 21–28. ACM, 2005. 
[Fra04]  Keir Fraser. Practical lockfreedom. PhD thesis, University of Cambridge Computer Laboratory, 2004. 
[Har01]  Timothy L. Harris. A pragmatic implementation of nonblocking linkedlists. In Proceedings of the 15th International Conference on Distributed Computing (DISC), pages 300–314. SpringerVerlag, 2001. 
[HMBW07]  Thomas E. Hart, Paul E. McKenney, Angela Demke Brown, and Jonathan Walpole. Performance of memory reclamation for lockless synchronization. Journal of Parallel and Distributed Computing, 67(12):1270–1285, 2007. 
[KLP13]  Christoph Kirsch, Michael Lippautz, and Hannes Payer. Fast and scalable, lockfree kFIFO queues. In Proceedings of the International Conference on Parallel Computing Technologies (PaCT), pages 208–223, SpringerVerlag, 2013. 
[Mic02]  Maged M. Michael. High performance dynamic lockfree hash tables and listbased sets. In Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 73–82. ACM, 2002. 
[Mic04]  Maged M. Michael. Hazard pointers: Safe memory reclamation for lockfree objects. IEEE Transactions on Parallel and Distributed Systems, 15(6):491–504, 2004. 
[MS95]  Maged M. Michael and Michael L. Scott. Correction of a memory management method for lockfree data structures. Technical report, University of Rochester, 1995. 
[MS96]  Maged M. Michael and Michael L. Scott. Simple, fast, and practical nonblocking and blocking concurrent queue algorithms. In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 267–275. ACM, 1996. 
[Nik19]  Ruslan Nikolaev A scalable, portable, and memoryefficient lockfree fifo queue. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC), 2019. 
[PT18a]  Manuel Pöter and Jesper Larsson Träff. Brief announcement: Stampit, a more threadefficient, concurrent memory reclamation scheme in the C++ memory model. In Proceedings of the 30th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 355–358. ACM, 2018. 
[PT18b]  Manuel Pöter and Jesper Larsson Träff. Stampit, a more threadefficient, concurrent memory reclamation scheme in the C++ memory model. Technical report, 2018. 
[Ram16]  Pedro Ramalhete. FAAArrayQueue  MPMC lockfree queue (part 4 of 4). Blog, November 2016. 
[RC15]  Pedro Ramalhete and Andreia Correia. LeftRight  A Concurrency Control Technique with WaitFree Population Oblivious Reads. October 2015 
[RC17]  Pedro Ramalhete and Andreia Correia. Brief announcement: Hazard eras  nonblocking memory reclamation. In Proceedings of the 29th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 367–369. ACM, 2017. 
[Rob13]  Arch D. Robison. Policybased design for safe destruction in concurrent containers. C++ standards committee paper, 2013. 
[Val95]  John D. Valois. LockFree Data Structures. PhD thesis, Rensselaer Polytechnic Institute, 1995. 
[Vyu08]  Dmitry Vyukov. Scalable hash map. Google Groups posting, 2008. 
[Vyu10]  Dmitry Vyukov. Simple and efficient bounded MPMC queue. Google Groups posting, 2010. 