Awesome

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