Concurrent-deque - Lock-free concurrent work stealing deque in C++

Overview

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();
You might also like...
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

Concurrent data structures in C++
Concurrent data structures in C++

Junction is a library of concurrent data structures in C++. It contains several hash map implementations: junction::ConcurrentMap_Crude junction::Conc

A C++ library of Concurrent Data Structures

CDS C++ library The Concurrent Data Structures (CDS) library is a collection of concurrent containers that don't require external (manual) synchroniza

:copyright: Concurrent Programming Library (Coroutine) for C11

libconcurrent tiny asymmetric-coroutine library. Description asymmetric-coroutine bidirectional communication by yield_value/resume_value native conte

A bounded multi-producer multi-consumer concurrent queue written in C++11
A bounded multi-producer multi-consumer concurrent queue written in C++11

MPMCQueue.h A bounded multi-producer multi-consumer concurrent queue written in C++11. It's battle hardened and used daily in production: In the Frost

A C++ library providing various concurrent data structures and reclamation schemes.

xenium xenium is a header-only library that provides a collection of concurrent data structures and memory reclamation algorithms. The data structures

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, generalized, implementation of the Chase-Lev lock-free work-stealing deque for C++17

riften::Deque A bleeding-edge lock-free, single-producer multi-consumer, Chase-Lev work stealing deque as presented in the paper "Dynamic Circular Wor

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

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

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

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

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,

A bounded single-producer single-consumer wait-free and lock-free queue written in C++11
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 SPSCQueueint q(2); auto t = std::th

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

A collection of hash tables for parallel programming, including lock-free, wait-free tables.

Hatrack Hash tables for parallel programming This project consisists of fast hash tables suitable for parallel programming, including multiple lock-fr

Use an esp32 as gateway for the Eqiva Bluetooth smart lock to integrate it in Home Assistant as MQTT lock

esp32-keyble-homeassistant Use an esp32 as gateway for the Eqiva Bluetooth smart lock to integrate it in Home Assistant as MQTT lock Based on the grea

This PoC uses two diferent technics for stealing  the primary token from all running processes, showing that is possible to impersonate and use whatever token present at any process
This PoC uses two diferent technics for stealing the primary token from all running processes, showing that is possible to impersonate and use whatever token present at any process

StealAllTokens This PoC uses two diferent technics for stealing the primary token from all running processes, showing that is possible to impersonate

Comments
  • Possible error

    Possible error

    Hi there, on line 206 in steal() you have moved the ->get() call into the CAS if, (as oppose to before like Figure 1. in the reference material). I believe this introduces a bug as:

    1. Thread A executes a steal() and hangs just after successfully completing the CAS.
    2. A push occurs, from thread B, that overwrites the stolen item (due to buffer wrap around).
    3. A wakes up and retrieves the wrong item.

    This could be fixed by moving the ->get() before the CAS branch but then a copy must be made for every steal, even the unsuccessful ones :(

    opened by ConorWilliams 2
Owner
Shubham Lagwankar
Shubham Lagwankar
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 129 Dec 31, 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
Concurrency Kit 2.1k Jan 4, 2023
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.4k Jan 3, 2023
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 Dec 30, 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 576 Dec 27, 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 Jan 1, 2023
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.9k Jan 5, 2023
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 392 Dec 3, 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