Fast, generalized, implementation of the Chase-Lev lock-free work-stealing deque for C++17

Overview

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
You might also like...
GECOS: A lock-free synchronization mechanism

GECOS GECOS is a lock-free synchronization mechanism, and this repository compares various well-known mechanisms such as RCU and HP (Hazard Pointers).

Rpmalloc - Public domain cross platform lock free thread caching 16-byte aligned memory allocator implemented in C
Rpmalloc - Public domain cross platform lock free thread caching 16-byte aligned memory allocator implemented in C

rpmalloc - General Purpose Memory Allocator This library provides a public domain cross platform lock free thread caching 16-byte aligned memory alloc

Design and Implementation of kernel level threads for xv6 operating system. Adding system call related to threading environment in xv6 along with userland threading library with one to one mapping and semaphore implementation as synchronisation primitive   DwThreadPool - A simple, header-only, dependency-free, C++ 11 based ThreadPool library.
DwThreadPool - A simple, header-only, dependency-free, C++ 11 based ThreadPool library.

dwThreadPool A simple, header-only, dependency-free, C++ 11 based ThreadPool library. Features C++ 11 Minimal Source Code Header-only No external depe

🧵 Fast and easy multithreading for React Native using JSI
🧵 Fast and easy multithreading for React Native using JSI

react-native-multithreading 🧵 Fast and easy multithreading for React Native using JSI. Installation npm install react-native-multithreading npx pod-i

Light, fast, threadpool for C++20

riften::Thiefpool A blazing-fast, lightweight, work-stealing thread-pool for C++20. Built on the lock-free concurrent riften::Deque. Usage #include "r

lc is a fast multi-threaded line counter.
lc is a fast multi-threaded line counter.

Fast multi-threaded line counter in Modern C++ (2-10x faster than `wc -l` for large files)

Bistro: A fast, flexible toolkit for scheduling and running distributed tasks

Bistro is a flexible distributed scheduler, a high-performance framework supporting multiple paradigms while retaining ease of configuration, management, and monitoring.

Termite-jobs - Fast, multiplatform fiber based job dispatcher based on Naughty Dogs' GDC2015 talk.

NOTE This library is obsolete and may contain bugs. For maintained version checkout sx library. until I rip it from there and make a proper single-hea

Comments
  • CPM issue

    CPM issue

    Tried adding this with the README directions for CPM (and also adding it to target_link_libraries). But I'm having compiler errors, as it's unable to find riften/deque.hpp. Do you have a working example of this? I'm looking through the cmake right now to see if i can identify the issue.

    Can confirm that it is found and added to my build though: image

    opened by andersfylling 1
Releases(v2.0.0)
  • v2.0.0(Sep 10, 2021)

    At the expense of requiring types to be trivially destructible the deque can now store more general types without allocating on each push.

    Source code(tar.gz)
    Source code(zip)
  • v1.1.0(Mar 15, 2021)

    This version detects types that can be stored directly in the ring buffer (std::atomic<T>::is_always_lock_free && std::is_trivially_destructible_v<T> == true) and no longer allocates heap storage when this is the case.

    Source code(tar.gz)
    Source code(zip)
Owner
Conor Williams
Physicist / Computer-Scientist @ Cambridge University. Open source enthusiast!
Conor Williams
Forkpool - A bleeding-edge, lock-free, wait-free, continuation-stealing scheduler for C++20

riften::Forkpool A bleeding-edge, lock-free, wait-free, continuation-stealing scheduler for C++20. This project uses C++20's coroutines to implement c

Conor Williams 128 Nov 15, 2022
Work Stealing Thread Pool

wstpool Work Stealing Thread Pool, Header Only, C++ Threads Consistent with the C++ async/future programming model. Drop-in replacement for 'async' fo

Yasser Asmi 5 Oct 29, 2022
Bikeshed - Lock free hierarchical work scheduler

Branch OSX / Linux / Windows master master bikeshed Lock free hierarchical work scheduler Builds with MSVC, Clang and GCC, header only, C99 compliant,

Dan Engelbrecht 81 Oct 26, 2022
Lev - Lightweight C++ wrapper for LibEvent 2 API

lev Lightweight C++ wrapper for LibEvent 2 API LibEvent is a great library. It uses a C interface which is well designed but has a learning curve. Thi

Yasser Asmi 46 Sep 15, 2022
A bounded single-producer single-consumer wait-free and lock-free queue written in C++11

SPSCQueue.h A single producer single consumer wait-free and lock-free fixed size queue written in C++11. Example SPSCQueue<int> q(2); auto t = std::th

Erik Rigtorp 566 Nov 22, 2022
Awesome-lockfree - A collection of resources on wait-free and lock-free programming

Awesome Lock-Free A collection of resources on wait-free and lock-free programming. ?? ?? ?? Even better resource from MattPD: C++ links: atomics, loc

Erik Rigtorp 1.4k Nov 18, 2022
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Cameron 7.3k Nov 21, 2022
A fast single-producer, single-consumer lock-free queue for C++

A single-producer, single-consumer lock-free queue for C++ This mini-repository has my very own implementation of a lock-free queue (that I designed f

Cameron 2.8k Nov 22, 2022
Simple and fast C library implementing a thread-safe API to manage hash-tables, linked lists, lock-free ring buffers and queues

libhl C library implementing a set of APIs to efficiently manage some basic data structures such as : hashtables, linked lists, queues, trees, ringbuf

Andrea Guzzo 391 Nov 19, 2022
Concurrency Kit 2.1k Nov 19, 2022