Every Data Structure Deserves Lock-Free Memory Reclamation
summary
Presents a fully lock-free memory-reclamation system that combines a lock-free mark-and-sweep base with a lightweight, generic root-gathering mechanism applied automatically via a clang plug-in. It partitions each operation into read-only/write-only periods so roots can be published and short read phases restarted, avoiding redesign of data structures. Evaluated on long and short linked lists and a hashmap on a 64-core machine, it matches no-reclamation throughput within ~0.5% in many cases and only yields small slowdowns; hazard pointers beat it in a few high-contention cases.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 0:36What is Free Data Structure
- 4:20The Hardest Part
- 5:45The Reclamation Scheme
- 12:05The Overall Algorithm
- 12:55Cost Comparison
- 17:02Conclusion
related talks
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"
01h 11mLock-Free Programming (or, Juggling Razor Blades), Part II
21mA Family of Fast and Memory Efficient Lock- and Wait-Free Reclamation
55m “High Performance C++ Concurrent Transactional Data Structures"
01h 30mLive Lock-Free or Deadlock (Practical Lock-free Programming)
23mLock-free Concurrent Level Hashing for Persistent Memory
39mLive Lock-Free or Deadlock (Practical Lock-free Programming)