Saturn β parallelism-safe data structures for Multicore OCaml
This repository is a collection of parallelism-safe data structures for OCaml 5. They are contained in two packages:
Saturnthat includes every data structures and should be used by default if you just want parallelism-safe data structures..Saturn_lockfreethat includes only lock-free data structures.
The available data structures are :
| Names | Names in Saturn (in Saturn_lockfree) |
What is it ? | Sources |
|---|---|---|---|
| Treiber stack | Stack (same) |
A classic multi-producer multi-consumer stack, robust and flexible. Recommended starting point when needing a LIFO structure | |
| Michael-Scott queue | Queue (same) |
A classic multi-producer multi-consumer queue, robust and flexible. Recommended starting point when needing a FIFO structure. | Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms |
| Chase-Lev Work-Stealing Dequeue | Work_stealing_deque (same) |
Single-producer, multi-consumer dynamic-size double-ended queue (deque). Ideal for throughput-focused scheduling using per-core work distribution. Note, pop and steal follow different ordering (respectively LIFO and FIFO) and have different linearization contraints. |
Dynamic circular work-stealing deque and Correct and efficient work-stealing for weak memory models) |
| SPSC Queue | Single_prod_single_cons_queue (same) |
Simple single-producer single-consumer fixed-size queue. Thread-safe as long as at most one thread acts as producer and at most one as consumer at any single point in time. | |
| MPMC bounded relaxed queue | Relaxed queue (same) |
Multi-producer, multi-consumer, fixed-size relaxed queue. Optimised for high number of threads. Not strictly FIFO. Note, it exposes two interfaces: a lockfree and a non-lockfree (albeit more practical) one. See the mli for details. | |
| MPSC Queue | Single_consumer_queue (same) |
A multi-producer, single-consumer, thread-safe queue without support for cancellation. This makes a gooddata structure for a scheduler's run queue. It is used in Eio. | It is a single consumer version of the queue described in Implementing lock-free queues. |
Usage
Saturn can be installed from opam: opam install saturn. Sample usage of
Work_stealing_deque is illustrated below.
module Ws_deque = Work_stealing_deque.M
let q = Ws_deque.create ()
let () = Ws_deque.push q 100
let () = assert (Ws_deque.pop q = 100)Tests
Several kind of tests are provided for each data structure:
- unitary tests and
qchecktests: check semantics and expected behaviors with one and more domains; STMtests: check linearizability for two domains (see multicoretests library);dscheck: checks non-blocking property for as many domains as wanted (for two domains most of the time). See dscheck.
See test/README.md for more details.
Benchmarks
There is a number of benchmarks in bench directory. You can run them with
make bench. See bench/README.md for more details.
Contributing
Contributions are appreciated! If you intend to add a new data structure, please read this before.