riften::Deque
A bleeding-edge lock-free, single-producer multi-consumer, Chase-Lev work stealing deque as presented in the paper "Dynamic Circular Work-Stealing Deque" and further improved in the follow up paper: "Correct and Efficient Work-Stealing for Weak Memory Models".
This implementation is based on:
This implementation places no constraint on the types which can be placed in the deque and has no memory overhead associated with buffer recycling. Furthermore, it provides the strong exception guarantee.
Usage
// #include <string>
// #include <thread>
// #include "riften/deque.hpp"
// Work-stealing deque of strings
riften::Deque<std::string> deque;
// One thread can push and pop items from one end (like a stack)
std::thread owner([&]() {
for (int i = 0; i < 10000; i = i + 1) {
deque.emplace(std::to_string(i));
}
while (!deque.empty()) {
std::optional item = deque.pop();
}
});
// While multiple (any) threads can steal items from the other end
std::thread thief([&]() {
while (!deque.empty()) {
std::optional item = deque.steal();
}
});
owner.join();
thief.join();
CMake
This is a single-header library. Additionally, the library can be installed:
mkdir build && cd build
cmake ..
make && make install
and then imported into your CMake project by including:
find_package(RiftenDeque REQUIRED)
in your CMakeLists.txt file.
CPM.cmake
The recommended way to consume this library is through CPM.cmake, just add:
CPMAddPackage("gh:ConorWilliams/ConcurrentDeque#v1.0.0")
to your CMakeLists.txt and you're good to go!
Tests
To compile and run the tests:
mkdir build && cd build
cmake ../test
make && make test
6 Sep 9, 2021
1.7k Jan 5, 2023
18 Nov 22, 2022
27 Oct 28, 2022
988 Dec 31, 2022
67 Dec 28, 2022
14 Oct 25, 2022
1k Dec 19, 2022
35 Jan 9, 2022
129 Dec 31, 2022
5 Oct 29, 2022
81 Dec 30, 2022
576 Dec 27, 2022
7.4k Jan 3, 2023
392 Dec 3, 2022
2.1k Jan 4, 2023