Bikeshed - Lock free hierarchical work scheduler

Overview
Branch OSX / Linux / Windows
master Build Status
master Codacy Badge

bikeshed

Lock free hierarchical work scheduler Builds with MSVC, Clang and GCC, header only, C99 compliant, MIT license.

See github for latest version: https://github.com/DanEngelbrecht/bikeshed

See design blogs at: https://danengelbrecht.github.io

Version history

Version v1.0 29/5 2019

Release 1.0

Fixes

  • Use explicit int32_t for instead of long to ensure 32-bit values on GCC/Clang x64-builds
  • Corrected URL to blog in README.md
  • Added sample code for performance tests (in examples folder)

Version v0.4 18/5 2019

Pre-release 4

API changes

  • Bikeshed_AddDependencies to take array of parent task task_ids
  • Bikeshed_ReadyCallback now gets called per channel range

API additions

  • Bikeshed_FreeTasks
  • BIKESHED_L1CACHE_SIZE to control ready head alignement - no padding/alignement added by default
  • BIKESHED_CPU_YIELD to control yielding in high-contention scenarios

Fixes

  • Added default (non-atomic) implementations for helper for unsupported platforms/compilers
  • Codacy analisys and badge
  • More input validation on public apis when BIKESHED_ASSERTS is enabled
  • Batch allocation of task indexes
  • Batch allocation of dependency indexes
  • Batch free of task indexes
  • Batch free of dependency indexes
  • Fixed broken channel range detection when resolving dependencies

Version v0.3 1/5 2019

Pre-release 3

Fixes

  • Ready callback is now called when a task is readied via dependency resolve
  • Tasks are readied in batch when possible

Version v0.2 29/4 2019

Pre-release 2

Fixes

  • Internal cleanups
  • Fixed warnings and removed clang warning suppressions
    • -Wno-sign-conversion
    • -Wno-unused-macros
    • -Wno-c++98-compat
    • -Wno-implicit-fallthrough
  • Made it compile cleanly with clang++ on Windows

Version v0.1 26/4 2019

Pre-release 1

Features

  • Generic tasks scheduling with dependecies between tasks
    • Each task has zero or many dependecies (as defined by user)
    • User should Ready any tasks that can execute (has zero dependencies)
    • Automatic ready of tasks that reaches zero dependecies
    • Automatic free of tasks that has completed
  • A task can have many parents and many child dependecies
  • Task channels - execute tasks based on task channel
  • No memory allocations once shed is created
  • Minimal dependencies
  • Memory allocation and threading are users responsability
  • Lifetime of data associated with tasks is users responsability
  • Configurable and optional assert (fatal error) behavior
  • Configurable platform dependant functions with default implementation provided
  • Header only - define BIKESHED_IMPLEMENTATION in one compilation unit and include bikeshed.h

Non-features

  • Cyclic dependency detection and resolving
    • API is designed to help user avoid cyclic dependecies but does not do any analisys
  • Built in threading or syncronization code - API to add it is available
  • Unlimited number of active tasks - currently limited to 8 388 607 active tasks
  • Cancelling of tasks
  • Tagging of tasks

Dependencies

Minimal dependecies with default overridable method for atomic operations.

  • <stdint.h>
  • <string.h>
  • The default (optional) MSVC implementation depends on <Windows.h>.

Optional default methods

The default implementations for the atomic and CPU yield functions can be overridden with your own implementation by overriding the macros:

  • BIKESHED_ATOMICADD Atomically adds a 32-bit signed integer to another 32-bit signed integer and returns the result
  • BIKESHED_ATOMICCAS Atomically exchange a 32-bit signed integer with another 32-bit signed integer if the value to be swapped matches the provided compare value, returns the old value.
  • BIKESHED_CPU_YIELD Yield CPU (mm_pause() / YieldProcessor()).

Test code dependecies

Test code has dependencies added as drop-in headers from

Test code has dependencies added as git sub-modules from

Releases(1.0)
  • 1.0(May 29, 2019)

    Release 1.0

    Fixes

    • Use explicit int32_t for instead of long to ensure 32-bit values on GCC/Clang x64-builds
    • Corrected URL to blog in README.md
    • Added sample code for performance tests (in examples folder)
    Source code(tar.gz)
    Source code(zip)
  • v0.4(May 18, 2019)

    Pre-release 4

    API changes

    • Bikeshed_AddDependencies to take array of parent task task_ids
    • Bikeshed_ReadyCallback now gets called per channel range

    API additions

    • Bikeshed_FreeTasks
    • BIKESHED_L1CACHE_SIZE to control ready head alignement - no padding/alignement added by default
    • BIKESHED_CPU_YIELD to control yielding in high-contention scenarios

    Fixes

    • Added default (non-atomic) implementations for helper for unsupported platforms/compilers
    • Codacy analisys and badge
    • More input validation on public apis when BIKESHED_ASSERTS is enabled
    • Batch allocation of task indexes
    • Batch allocation of dependency indexes
    • Batch free of task indexes
    • Batch free of dependency indexes
    • Fixed broken channel range detection when resolving dependencies
    Source code(tar.gz)
    Source code(zip)
  • v0.3(May 1, 2019)

  • v0.2(Apr 29, 2019)

    Fixes

    • Internal cleanups
    • Fixed warnings and removed clang warning suppressions
      • -Wno-sign-conversion
      • -Wno-unused-macros
      • -Wno-c++98-compat
      • -Wno-implicit-fallthrough
    • Made it compile cleanly with clang++ on Windows
    Source code(tar.gz)
    Source code(zip)
  • v0.1(Apr 26, 2019)

Owner
Dan Engelbrecht
Ericsson Radio Systems AB, Propellerheads AB, Aphelion AB, Autodesk, Frostbite, King, Embark Studios
Dan Engelbrecht
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

null 43 May 18, 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.

Hyoung Min Suh 12 Jun 4, 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

Conor Williams 113 May 29, 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

Shubham Lagwankar 25 Mar 13, 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
Concurrency Kit 2.1k Jun 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 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
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
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

Google 1.4k Jun 24, 2022
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.

null 11 Jul 14, 2021
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++

Doug Binks 1.3k Jun 20, 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

Spencer Bosma 212 Jun 21, 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
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
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
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

null 43 May 18, 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.

Hyoung Min Suh 12 Jun 4, 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

Conor Williams 113 May 29, 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

Shubham Lagwankar 25 Mar 13, 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 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

null 55 Jun 10, 2022
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

null 7 Apr 28, 2022
A modern-day Boss Key software tool. Switch instantly from work to play & play to work with Bosky.

Bosky By: Seanpm2001, Bosky-dev Et; Al. Top README.md Read this article in a different language Sorted by: A-Z Sorting options unavailable ( af Afrika

Sean P. Myrick V19.1.7.2 1 Nov 11, 2021
Hexagonal hierarchical geospatial indexing system

H3: A Hexagonal Hierarchical Geospatial Indexing System H3 is a geospatial indexing system using a hexagonal grid that can be (approximately) subdivid

Uber Open Source 3.5k Jun 27, 2022