Ctries in Clojure; or, Concurrent Transients
summary
An implementation of Ctries in Clojure (ctrees.clj v0.0.3) offers a lock-free concurrent hash map with constant-time snapshots and a transient-first API that returns in-place mutated maps. Snapshots produce immutable persistent maps (slower than clojure.core maps) and size remains linear-time. The core uses RD-CSS (descriptor-based restricted double-compare-single-swap) and a GCAS-like generational CAS that avoids per-update allocations. Test coverage uses clojure.test.check plus custom operation generators; concurrency stress tests indicate the design works though testing is still evolving.
AI-written summary · about
chapters (12)
- 0:00Intro
- 1:04Shoulders of Giants
- 5:05Ctries: synopsis
- 7:59Blending in with Clojure PDSS
- 10:37PDS-like version graphs
- 12:14j.u.c. ConcurrentMap methods
- 14:08Testing strategy
- 17:56Diff against PHM, THM
- 22:04Ctrie node menagerie
- 26:27edit vs gen-verifying ownership
- 37:47RDCSS descriptors
- 41:54GCAS failure descriptors
related talks
03h 29mConcurrency with Clojure
52mSTM and Structured Concurrency — The Battle with Multithreading Dragons
22mBuilding a lock-free STM for OCaml
01h 13mBack from the 70s — the Concurnas concurrency model!
30mMonadic interpreters for concurrent memory models: Executable semantics of a concurrent(…)
32mConcurrent Size
31mClojure Parallelism Beyond Futures
55m“A lock-free concurrency toolkit for deferred reclamation and optimistic speculation"