concurrent-deque

concurrent-deque copied to clipboard

A lock-free work-stealing deque

This is a C++ implementation of the Chase-Lev deque, a concurrent single-producer, multi-consumer queue presented in the paper "Dynamic Circular Work-Stealing Deque". Additionally, this deque handles reclamation of unused storage at the cost of some coordination between the stealers and the worker.

This implementation is heavily based on the improved version presented in the paper "Correct and Efficient Work-Stealing for Weak Memory Models". The Rust crossbeam crate also provided a ton of inspiration.

Usage

With deque.hpp in your include path:

#include "deque.hpp"

auto ws = deque::deque<int>();
auto worker = std::move(ws.first);
auto stealer = std::move(ws.second);

// The worker can push and pop from one end of the queue.
worker.push(1);
worker.pop();

// Stealers can pop from the other end of the queue.
worker.push(1);
std::thread stealer_thread([&stealer]() {
  // Each stealer thread creates a copy.
  auto stealer_copy = stealer;
  stealer_copy.steal();
});

stealer.steal();
stealer_thread.join();