xenium

A C++ library providing various concurrent data structures and reclamation schemes.

Description

xenium is a header-only 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).

* header only * highly customizable * no initialization code needed * supports dynamic number of threads (no fixed compile time specification)

Programming language: C++

License: MIT License

Tags: Concurrency     Lock-Free     C++17     Reclamation-schemes    

README

xenium

xenium is a header-only 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).

• header only
• highly customizable
• no initialization code needed
• supports dynamic number of threads (no fixed compile time specification)

The documentation provides more details.

This project is based on my previous work in https://github.com/mpoeter/emr

Usage Example

#include <xenium/ramalhete_queue.hpp>
#include <xenium/reclamation/epoch_based.hpp>

struct msg { ... };

xenium::ramalhete_queue<
  std::unique_ptr<msg>,
  xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
  xenium::policy::entries_per_node<2048>
> queue;

queue.push(std::make_unique<msg>());

std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
    // do something with data
}

Data Structures

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 lock-free multi-producer/multi-consumer queue proposed by Michael and Scott [MS96].
• ramalhete_queue - a fast unbounded lock-free multi-producer/multi-consumer queue proposed by Ramalhete [Ram16].
• vyukov_bounded_queue - a bounded multi-producer/multi-consumer FIFO queue based on the version proposed by Vyukov [Vyu10 ].
• kirsch_kfifo_queue - an unbounded multi-producer/multi-consumer k-FIFO queue proposed by Kirsch et al. [KLP13].
• kirsch_bounded_kfifo_queue - a bounded multi-producer/multi-consumer k-FIFO queue proposed by Kirsch et al. [KLP13].
• nikolaev_queue - an unbounded multi-producer/multi-consumer queue proposed by Nikolaev [Nik19].
• nikolaev_bounded_queue - a bounded multi-producer/multi-consumer queue proposed by Nikolaev [Nik19].
• harris_michael_list_based_set - a lock-free 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 lock-free hash-map 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 hash-map 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").

Reclamation Schemes

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.
  • epoch_based [Fra04]
  • new_epoch_based [HMBW07]
  • debra [Bro15]
• stamp_it [PT18a, PT18b]

Building

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:

• gcc9
• clang10
• Visual Studio 2019

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:

git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark

References

[Bro15] Trevor Alexander Brown. Reclaiming memory for lock-free 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 work-stealing 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 lock-freedom. PhD thesis, University of Cambridge Computer Laboratory, 2004. [Har01] Timothy L. Harris. A pragmatic implementation of non-blocking linked-lists. In Proceedings of the 15th International Conference on Distributed Computing (DISC), pages 300–314. Springer-Verlag, 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, lock-free k-FIFO queues. In Proceedings of the International Conference on Parallel Computing Technologies (PaCT), pages 208–223, Springer-Verlag, 2013. [Mic02] Maged M. Michael. High performance dynamic lock-free hash tables and list-based 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 lock-free 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 lock-free data structures. Technical report, University of Rochester, 1995. [MS96] Maged M. Michael and Michael L. Scott. Simple, fast, and practical non-blocking 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 memory-efficient lock-free 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: Stamp-it, a more thread-efficient, 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. Stamp-it, a more thread-efficient, concurrent memory reclamation scheme in the C++ memory model. Technical report, 2018. [Ram16] Pedro Ramalhete. FAAArrayQueue - MPMC lock-free queue (part 4 of 4). Blog, November 2016. [RC15] Pedro Ramalhete and Andreia Correia. Left-Right - A Concurrency Control Technique with Wait-Free Population Oblivious Reads. October 2015 [RC17] Pedro Ramalhete and Andreia Correia. Brief announcement: Hazard eras - non-blocking 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. Policy-based design for safe destruction in concurrent containers. C++ standards committee paper, 2013. [Val95] John D. Valois. Lock-Free 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.