Reference Counting Deeply Immutable Data Structures with Cycles
summary
Claim: deeply frozen object graphs are collectible by reference counting by collapsing strongly connected components and maintaining single reference counter per SCC. Algorithm combines path-based SCC + union-find, runs almost linear (inverse-Ackermann overhead), and freezing costs ~2–2.5× a simple mark traversal in measured benchmarks. Prototype allocator and freezer is implemented, handles cycles precisely without backup cycle detector, and is practical for long-lived frozen structures (caveat: cache effects slow large graphs).
AI-written summary · about
chapters (7)
- 0:00Deeply immutable data structures
- 2:10Reference counting with cycles
- 3:57SCC-based reference counting
- 7:31Algorithm walkthrough
- 10:01Performance analysis
- 12:54Shared immutable state apps
- 14:42Q&A
related talks
40mImmutable Data Structures in C++
21mEvery Data Structure Deserves Lock-Free Memory Reclamation
17mConcurrent Immediate Reference Counting
19mDesigning Wait-free Weak Reference Counting
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 02m“Beyond the Issaquah Challenge: High-Performance Scalable Complex Updates"
17mArctic: A Practical Lock-Free Adaptive Radix Tree