A Family of Fast and Memory Efficient Lock- and Wait-Free Reclamation
summary
Crystalline is a family of non-blocking reclamation schemes (Crystalline L, LW, W) that guarantees wait-free reclamation in its strongest variant, supports asynchronous cross-thread reclamation, and balances reclamation work across threads. It uses dynamic batches and hardware primitives like double-wide CAS to bound protect/retire loops, runs on x86-64 and ARM64, and shows superior throughput to EBR as threads scale (maintains good throughput past 96 threads) while matching hazard pointers’ memory efficiency; code and evaluated artifacts are available on GitHub/Zenodo.
AI-written summary · about
chapters (15)
- 0:00Lock- and wait-free reclamation intro
- 1:49Stale pointers in concurrent data structures
- 3:16Progress guarantees explained
- 5:22Workload balancing in reclamation
- 7:09Reference counting limitations
- 8:57Introducing CrystalNL family
- 11:05Progress guarantees across structures
- 13:13HighLine’s annotation mechanism
- 14:39CrystalNL API design
- 16:26Dynamic batches in CrystalNL
- 17:27Weight-free challenges
- 18:52CrystalNLW with hardware primitives
- 19:38Evaluation vs state-of-the-art
- 20:39Performance and memory results
- 21:00Conclusion and Q&A
related talks
01h 15mWait-free memory reclamation and data structures
21mEvery Data Structure Deserves Lock-Free Memory Reclamation
20mRRR-SMR: Reduce, Reuse, Recycle: Better Methods for Practical Lock-Free Data Structures
55m“A lock-free concurrency toolkit for deferred reclamation and optimistic speculation"
36mImplementing wait-free space bounded shared memory primitives on concurrent systems
22mRelaxed Memory Concurrency Re-executed
01h 08mDesigning fast lock free algorithms by understanding cache coherence dynamics
01h 38mLock-free Programming is Dead - Long Live Lock-free Programming!