package kcas_data

  1. Overview
  2. Docs

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.

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 implementations 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.

Communication and synchronization primitives

module Mvar : sig ... end

Synchronizing variable.

module Promise : sig ... end

A promise of a value to be resolved at some point in the future.

Linked data structures

module Dllist : sig ... end

Doubly-linked list.

Utilities

module Accumulator : sig ... end

Scalable accumulator.