Saturn — parallelism-safe data structures for Multicore OCamlThis repository is a collection of parallelism-safe data structures for OCaml 5. They are contained in two packages:
Saturn that includes every data structures and should be used by default if you just want parallelism-safe data structures..Saturn_lockfree that includes only lock-free data structures.The available data structures are :
Names | Names in | What is it ? | Sources |
|---|---|---|---|
| A classic multi-producer multi-consumer stack, robust and flexible. Recommended starting point when needing a LIFO structure | ||
| 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 | |
| Single-producer, multi-consumer dynamic-size double-ended queue (deque). Ideal for throughput-focused scheduling using per-core work distribution. Note, | Dynamic circular work-stealing deque and Correct and efficient work-stealing for weak memory models) | |
| 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. | ||
| 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. | ||
| 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. |
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)Several kind of tests are provided for each data structure:
qcheck tests: check semantics and expected behaviors with one and more domains;STM tests: 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.
There is a number of benchmarks in bench directory. You can run them with make bench. See bench/README.md for more details.
Contributions are appreciated! If you intend to add a new data structure, please read this before.