Space and Time Bounded Multiversion Garbage Collection
summary
Implements a versioned-CAS layer built from ordinary CAS and a global integer timestamp so any CAS-based structure gains a constant-time snapshot handle; memory uses multiversion lists, per-thread batches and a shared queue to discover obsolete versions. Main claims: tracker size ≤ about 2×H plus small additive terms (H = needed versions), CAS/read/snapshot are amortized constant time, reading an old value costs steps proportional to versions since the snapshot, and overall space is within a constant factor of H plus P and log L additives.
AI-written summary · about
chapters (9)
- 0:00Introduction to multiversion garbage collection
- 3:40Concurrent data structure challenges
- 11:20Multiversioning in systems
- 13:29Memory goals and limits
- 18:05Tracking obsolete versions
- 20:16Removing versions
- 25:57Simplified version lists
- 28:54Reference counting reclamation
- 30:45Complexity and performance
related talks
52mNonblocking algorithms/ CAS/Atomics
39mSecure Cache Designs: State of the Art and ...
15mNoisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds
41mUsing Microarchitectural Design to Break KASLR and More
27mConsistency and Coherence of the NVIDIA Grace-Hopper Superchip
17mFalcon: A Scalable Analytical Cache Model
27mScheme Pearl: Quantum Continuations
13mMemPool Flavors: Between Versatility and Specialization in a RISC-V Manycore Cluster