Module Kcas_data

This package provides a collection of compositional lock-free data structures with in-place modification.

All data structure implementations in this library should strive to provide the following guarantees:

Unobvious exceptions to the above guarantees should be clearly and explicitly documented.

The main feature of these data structure implementations is their compositionality. For example, one can easily compose a transaction to atomically transfer a value from a Queue to a Stack:

let tx ~xt =
  match Queue.Xt.take_opt ~xt queue with
  | None -> ()
  | Some value ->
    Stack.Xt.push ~xt stack value
Xt.commit { tx }

If your application does not need compositionality, then other domain safe data structure libraries may potentially offer better performance.

Stdlib style data structures

The data structures in this section are designed to closely mimic the corresponding unsynchronized data structures in the OCaml Stdlib. Each of these provide a non-compositional, but domain safe, interface that is close to the Stdlib equivalent. Additionally, compositional transactional interfaces are provided for some operations.

These implementation will use more space than the corresponding Stdlib data structures. Performance, when accessed concurrently, should be competitive or superior compared to naïve locking.

module Hashtbl : sig ... end

Hash table.

module Queue : sig ... end

First-In First-Out (FIFO) queue.

module Stack : sig ... end

Last-In First-Out (LIFO) stack.


module Accumulator : sig ... end

Scalable accumulator.