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
Issues
  • 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 123 Jun 20, 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 3 Jul 20, 2021
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 Jun 7, 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 79 Jun 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 499 Jun 21, 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.3k Jun 25, 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 6.8k Jun 24, 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.7k Jun 23, 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 381 Jun 15, 2022
Concurrency Kit 2.1k Jun 18, 2022
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).

null 6 Sep 9, 2021
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

Mattias Jansson 1.5k Jun 23, 2022
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

Dihara Wijetunga 26 May 29, 2022
🧵 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

Marc Rousavy 911 Jun 24, 2022
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

Conor Williams 60 Jun 8, 2022
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)

Pranav 12 Feb 17, 2022
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.

Facebook 1k Jun 9, 2022
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

Sepehr Taghdisian 35 Jan 9, 2022