Kcas — STM for OCaml (original) (raw)

Software Transactional Memory for OCaml

Create and use modular and composable concurrent abstractions with ease

Use familiar programming techniques

Kcas transactions are written as ordinary functions allowing you touse 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 becomposed sequentially, conjunctively,conditionally, and disjunctively.

Leverage the work of others

Kcas comes witha 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

Kcastransactions and blocking operations can await, withoptional 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 isbased on efficient and scalable lock-free algorithms.

• Only k + 1 successful single world CASes are required to commit a transaction that modifiesk 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 constructedoften in linear time and always in worst case linearithmic time.
• Locations can be allocated toavoid false-sharing and data structure implementations can and do take advantage of that where appropriate.
• Provided data structures usestarvation avoiding approaches to perform long-running operations where appropriate.
• Operations usea 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 andtimeouts are not tied to a specific scheduler and even work across multiple schedulers in a single application.
• Thenon-blocking algorithms employeddo 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.

Additional resources

Kcas: Building a Lock-Free STM for OCaml (1/2) and (2/2)

Building a lock-free STM for OCaml, seevideo andslides.

Kcas is part of theMulticore OCaml project and is supported by Tarides.