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();
1.7k Jan 5, 2023
1.3k Dec 31, 2022
2.2k Jan 3, 2023
350 Sep 2, 2022
836 Dec 25, 2022
351 Dec 28, 2022
27 Oct 28, 2022
120 Dec 22, 2022
2.1k Jan 4, 2023
7.4k Jan 3, 2023
5 Oct 29, 2022
81 Dec 30, 2022
62 Dec 13, 2022
8 Nov 22, 2022
50 Dec 13, 2022
129 Dec 31, 2022
2.1k Jan 4, 2023
7.4k Jan 3, 2023
5 Oct 29, 2022
81 Dec 30, 2022
576 Dec 27, 2022
392 Dec 3, 2022
6 Sep 9, 2021