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:

• Provided operations are strictly serializable (i.e. both linerizable and serializable).
• Provided operations are efficient, either (amortized) constant time, O(1), or logarithmic time, O(log(n)).
• Provided operations are lock-free and designed to avoid starvation under moderate contention.
• Provided read-only operations scale perfectly when only read-only operations are performed in parallel.

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
in
Xt.commit { tx }

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