Arborescent Garbage Collection: A Dynamic Graph Approach to Immediate Cycle Collection

on YouTube ↗23m

" summary

Embeds a spanning forest embedded in reference graph and maintains it on each pointer update so the runtime can perform immediate synchronous cycle reclamation; implements a weak rank per object with adoption and reranking optimizations and stores co-parent links as in-object metadata (no extra allocations). Prototype on Ribbit (Scheme) reclaims cycles immediately but runs about 4.5x slowdown versus mark‑and‑sweep; concurrent or parallel mutator support is left for future work.

AI-written summary · about

" chapters (15)

1. 0:00Introduction to arborescent garbage collection
2. 1:25Collect cycles immediately
3. 2:30Heap as reference graph
4. 3:56ES trees and ranks
5. 6:04Spanning forest maintenance
6. 7:09Edge removal handling
7. 10:00Algorithm optimization
8. 11:49Adoption and reranking
9. 13:57Initial ranks for objects
10. 14:39Implementation details
11. 15:48Benchmark vs mark-sweep
12. 16:52Performance results
13. 17:12Future work
14. 17:56Conclusion
15. 18:41Q&A