Forkpool - A bleeding-edge, lock-free, wait-free, continuation-stealing scheduler for C++20

Last update: Dec 31, 2022

Overview

`riften::Forkpool`

A bleeding-edge, lock-free, wait-free, continuation-stealing scheduler for C++20. This project uses C++20's coroutines to implement continuation-stealing scheduler without the use of any macros/inline assembly. The interface is designed to mirror Cilk.

#include "riften/thiefpool.hpp"

using namespace riften;

Task<int> fib(int n) { // Define a task to be run on the threadpool
    if (n < 2) {
        co_return n;
    } else {
        Future a = co_await fork(fib, n - 1); // Tasks can recursivly spawn tasks 
        Future b = co_await fork(fib, n - 2);

        co_await tag_sync(); // Sync before consuminging the futures

        co_return *a + *b;
    }
}

int main(){

    int result = root(fib, 10) // Submit a root task to the threadpool and block until it completes

    return 0;
}

Installation

The recommended way to consume this library is through CPM.cmake, just add:

CPMAddPackage("gh:ConorWilliams/Forkpool#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

Reference

This project implements many of the ideas in (available in reference/):

F. Schmaus et al., “Nowa: A Wait-Free Continuation-Stealing Concurrency Platform”. In: 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 2021.
C. -X. Lin, T. -W. Huang and M. D. F. Wong, "An Efficient Work-Stealing Scheduler for Task Dependency Graph," 2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS), 2020, pp. 64-71, doi: 10.1109/ICPADS51040.2020.00018.

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).

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

1.7k Jan 5, 2023

A hybrid thread / fiber task scheduler written in C++ 11

Marl Marl is a hybrid thread / fiber task scheduler written in C++ 11. About Marl is a C++ 11 library that provides a fluent interface for running tas

1.5k Jan 4, 2023

Sqrt OS is a simulation of an OS scheduler and memory manager using different scheduling algorithms including Highest Priority First (non-preemptive), Shortest Remaining Time Next, and Round Robin

A CPU scheduler determines an order for the execution of its scheduled processes; it decides which process will run according to a certain data structure that keeps track of the processes in the system and their status.

10 Sep 7, 2022

afl/afl++ with a hierarchical seed scheduler

This is developed based on AFLplusplus (2.68c, Qemu mode), thanks to its amazing maintainers and community Build and Run Please follow the instruction

47 Nov 25, 2022

EnkiTS - A permissively licensed C and C++ Task Scheduler for creating parallel programs. Requires C++11 support.

Support development of enkiTS through Github Sponsors or Patreon enkiTS Master branch Dev branch enki Task Scheduler A permissively licensed C and C++

1.4k Dec 27, 2022

Scheduler - Modern C++ Scheduling Library

Scheduler Modern C++ Header-Only Scheduling Library. Tasks run in thread pool. Requires C++11 and ctpl_stl.h in the path. Inspired by the Rufus-Schedu

232 Dec 21, 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

27 Oct 28, 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 SPSCQueueint q(2); auto t = std::th

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

1.4k Jan 1, 2023

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

62 Dec 13, 2022

Teracube 2e (4.19.y) - Extremely bleeding edge, you have been warned

Linux kernel ============ There are several guides for kernel developers and users. These guides can be rendered in a number of formats, like HTML an

4 Dec 16, 2022

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

120 Dec 22, 2022

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

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 t

30 Jan 7, 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,

81 Dec 30, 2022

A continuation of FSund's pteron-keyboard project. Feel free to contribute, or use these files to make your own! Kits and PCBs are also available through my facebook page.

pteron-pcb Intro This project is the evolution of the Pteron-Keyboard project, an incredible ergonomic keyboard that was handwired only. I aimed to in

17 Oct 11, 2022

A easy to use multithreading thread pool library for C. It is a handy stream like job scheduler with an automatic garbage collector. This is a multithreaded job scheduler for non I/O bound computation.

A easy to use multithreading thread pool library for C. It is a handy stream-like job scheduler with an automatic garbage collector for non I/O bound computation.

12 Jun 4, 2022

Canny edge detection, one of the efficient edge detection algorithms is implemented on a Zedboard FPGA using verilog

In this project, Canny edge detection, one of the efficient edge detection algorithms is implemented on a Zedboard FPGA using verilog. The input image is stored on a PC and fed to the FPGA. The output processed image is displayed on a VGA monitor.

4 Jan 4, 2023

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

8 Nov 22, 2022

Comments

Update the doctest version in /test/CMakeLists.txt

Hi, when I'm trying to compile the program, I was having the same issue as mentioned in Can't compile with glibc master (future 2.34): SIGSTKSZ is no longer a constant. I was trying to update the doctest version into 2.4.6 but was having this error:

Would appreciate it very much if anyone can give me some advice on how to fix this. Thanks!

opened by ccjeff 2
Performance, benchmarks, ...

Hi, I've just discovered this potential gem. But to be sure the features reflect in practical setting, we'd need to test it first.

Do you have any such performance benchmarks (even if not rigorous...)?

I'd be mostly interested in direct comparison with Nim's Weave which I myself consider as state-of-the-art library. So ideally the benchmarks could be aligned with Weave's ones :wink:.

Thoughts?

opened by dumblob 2

Forkpool - A bleeding-edge, lock-free, wait-free, continuation-stealing scheduler for C++20

Related tags

Overview

riften::Forkpool

Installation

Tests

Reference

You might also like...

GECOS: A lock-free synchronization mechanism

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

A hybrid thread / fiber task scheduler written in C++ 11

Sqrt OS is a simulation of an OS scheduler and memory manager using different scheduling algorithms including Highest Priority First (non-preemptive), Shortest Remaining Time Next, and Round Robin

afl/afl++ with a hierarchical seed scheduler

EnkiTS - A permissively licensed C and C++ Task Scheduler for creating parallel programs. Requires C++11 support.

Scheduler - Modern C++ Scheduling Library

DwThreadPool - A simple, header-only, dependency-free, C++ 11 based ThreadPool library.

A bounded single-producer single-consumer wait-free and lock-free queue written in C++11

Awesome-lockfree - A collection of resources on wait-free and lock-free programming

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

Teracube 2e (4.19.y) - Extremely bleeding edge, you have been warned

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

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

Bikeshed - Lock free hierarchical work scheduler

A continuation of FSund's pteron-keyboard project. Feel free to contribute, or use these files to make your own! Kits and PCBs are also available through my facebook page.

A easy to use multithreading thread pool library for C. It is a handy stream like job scheduler with an automatic garbage collector. This is a multithreaded job scheduler for non I/O bound computation.

Canny edge detection, one of the efficient edge detection algorithms is implemented on a Zedboard FPGA using verilog

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

Comments

Update the doctest version in /test/CMakeLists.txt

Performance, benchmarks, ...

Releases(v1.0.0)

v1.0.0(Sep 12, 2021)

Owner

Conor Williams

Awesome-lockfree - A collection of resources on wait-free and lock-free programming

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

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

Bikeshed - Lock free hierarchical work scheduler

A easy to use multithreading thread pool library for C. It is a handy stream like job scheduler with an automatic garbage collector. This is a multithreaded job scheduler for non I/O bound computation.

Work Stealing Thread Pool

Concurrency primitives, safe memory reclamation mechanisms and non-blocking (including lock-free) data structures designed to aid in the research, design and implementation of high performance concurrent systems developed in C99+.

A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

A fast single-producer, single-consumer lock-free queue for C++

Simple and fast C library implementing a thread-safe API to manage hash-tables, linked lists, lock-free ring buffers and queues

`riften::Forkpool`