Kcas

Use familiar programming techniques

Kcas transactions are written as ordinary functions allowing you to use all the standard control flow constructs of OCaml. Furthermore, as a starting point, traditional sequential algorithms can easily be translated to parallelism-safe transactional algorithms. Transactions can be composed sequentially, conjunctively, conditionally, and disjunctively.

Leverage the work of others

Kcas comes with a companion package of parallelism-safe data structures that you can directly use for application programming. Furthermore, due to the composability of transactions and the interoperability of Kcas, independently developed data structures can be reused in new contexts.

Coordinate by awaiting on arbitrary conditions

Kcas transactions and blocking operations can await, with optional timeouts, on arbitrary conditions over the state of shared memory locations. Data structure implementations do not generally need to be a priori designed to support blocking.

Enjoy scalable performance

Kcas is based on efficient and scalable lock-free algorithms.

• Only k + 1 successful single world CASes are required to commit a transaction that modifies k locations and, as a special case, modifying a single location requires only a single single-word CAS.
• Disjoint accesses progress independently in parallel without interference.
• Read-only, obstruction-free, accesses do not write to shared memory and can progress independently even when not disjoint.
• Transactions can be constructed often in linear time and always in worst case linearithmic time.
• Locations can be allocated to avoid false-sharing and data structure implementations can and do take advantage of that where appropriate.
• Provided data structures use starvation avoiding approaches to perform long-running operations where appropriate.
• Operations use a randomized exponential backoff mechanism to avoid quadratic shared memory traffic in case of contention.

Learn once, write anywhere

Kcas is scheduler agnostic and can work with both existing and future schedulers.

• Blocking and timeouts are not tied to a specific scheduler and even work across multiple schedulers in a single application.
• The non-blocking algorithms employed do not depend on the fairness of the scheduler and can be used in contexts, such as signal handlers, where lock based techniques are not appropriate.
• Kcas also supports OCaml 4, allowing Kcas to be used to implement systhread and parallelism safe code and help projects requiring OCaml 4 support on their way to OCaml 5.