A collection of Concurrent Lockfree Data Structures for OCaml 5. It contains:
-
Treiber Stack A classic multi-producer multi-consumer stack, robust and flexible. Recommended starting point when needing LIFO structure.
-
Michael-Scott Queue A classic multi-producer multi-consumer queue, robust and flexible. Recommended starting point when needing FIFO structure. It is based on Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.
-
Chase-Lev Work-Stealing Deque Single-producer, multi-consumer dynamic-size double-ended queue (deque) (see Dynamic circular work-stealing deque and Correct and efficient work-stealing for weak memory models). 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.
-
SPSC Queue 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 Relaxed Queue 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 A multi-producer, single-consumer, thread-safe queue without support for cancellation. This makes a good data 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.
lockfree can be installed from opam: opam install lockfree. Sample usage of
Ws_deque is illustrated below.
module Ws_deque = Ws_deque.M
let q = Ws_deque.create ()
let () = Ws_deque.push q 100
let () = assert (Ws_deque.pop q = 100)There is a number of benchmarks in bench/ directory. You can run them with make bench. See bench/README.md for more details.
Contributions of more lockfree data structures appreciated! Please create issues/PRs to this repo.