package saturn

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Useful Information
Data structures
Other

package saturn

saturn
- Saturn

Legend:
Library
Module
Module type
Parameter
Class
Class type

Parallelism-safe data structures for Multicore OCaml

Useful Information

Domain-Specific Data Structures

Some data structures are optimized for specific domain configurations. These restrictions enhance performance but must be adhered to for maintaining safety properties. These limitations are documented and often reflected in the data structure's name. For example, a single-consumer queue should only have one domain performing `pop` operations at any time.

For more details, refer to this document.

Composability

Composability is the ability to combine functions while preserving their properties, such as atomic consistency (linearizability) and progress guarantees (e.g., lock-freedom). Saturn's data structures, however, are not composable.

For more details, refer to this document.

Unsafe Data Structures

Some data structures have both a normal and an unsafe version. The unsafe version uses `Obj.magic`, which can be unsafe, especially with flambda2 optimizations.

The unsafe version is provided to explore performance optimizations that require features not currently available in OCaml, such as arrays of atomics or atomic fields in records. These versions give an indication of the potential performance improvements when such features become available. It is recommended to use the normal version unless the performance requirements justify the risks associated with the unsafe version.

Data structures

Collections

module Htbl : sig ... end

Lock-free and resizable hash table.

module Htbl_unsafe : sig ... end

Optimized lock-free and resizable hash table.

module Skiplist : sig ... end

Lock-free non-resizable skiplist.

module Bag : sig ... end

Randomized lock-free bag

Queues

module Queue : sig ... end

Michael-Scott classic lock-free multi-producer multi-consumer queue.

module Queue_unsafe : sig ... end

Optimized Michael-Scott lock-free multi-producer multi-consumer queue.

module Bounded_queue : sig ... end

Lock-free bounded Queue.

module Bounded_queue_unsafe : sig ... end

Optimized lock-free bounded Queue.

module Single_consumer_queue : sig ... end

Lock-free multi-producer, single-consumer, domain-safe queue without support for cancellation.

module Single_prod_single_cons_queue : sig ... end

Lock-free single-producer, single-consumer queue.

module Single_prod_single_cons_queue_unsafe : sig ... end

Optimized lock-free single-producer, single-consumer queue.

Stacks

module Stack : sig ... end

Lock-free multi-producer multi-consumer Treiber stack.

module Bounded_stack : sig ... end

Lock-free bounded stack.

Work Stealing Deque

module Work_stealing_deque : sig ... end

Lock-free single-producer, multi-consumer dynamic-size double-ended queue (deque).

Other

module Size : sig ... end

Wait-free size counter for lock-free data structures