Building a lock-free STM for OCaml
summary
kcas implements a lock-free software transactional memory for OCaml built on a multi-word compare-and-set primitive, with composable transactions, scheduler-friendly modular blocking and a companion library of lock-free data structures. It adds domain-local services (eg domain-local wait service and timeout) so blocking and timeouts work across effect-based and plain domain runtimes. Benchmarks show the kcas queue sometimes outperforms a Michael-Scott lock-free queue and the kcas hash table scales past two domains; overhead exists but performance is practical.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 0:13Transactional Memory
- 1:09KCAS
- 1:50KCAS Overview
- 2:03KCAS Transactions
- 5:46Location State
- 7:08Transaction Overview
- 11:07Blocking and Timeouts
- 15:13Tradeoff
- 17:34Performance
- 20:24Hardware support
related talks
24mSaturn: a library of verified concurrent data structures for OCaml 5
52mSTM and Structured Concurrency — The Battle with Multithreading Dragons
52mNonblocking algorithms/ CAS/Atomics
01h 08mDesigning fast lock free algorithms by understanding cache coherence dynamics
15mCosmo: A Concurrent Separation Logic for Multicore Ocaml
01h 33mWhy You Should Use Software Transactional Memory
01h 00mWhat did C++ do for Transactional Memory?
30mMonadic interpreters for concurrent memory models: Executable semantics of a concurrent(…)