Pathological Cases for a Class of Reachability-Based Garbage Collectors
summary
Paper proves that any reachability-based GC that implements a realistic mutator‑observer interface has a pathological program forcing it to either long GC pause or reject allocation despite available heap, via a formal reduction to dynamic reachability (dynamic graph connectivity). Proof holds even with unlimited side metadata and gives tight worst‑case lower bounds; author adapts graph‑data‑structure techniques to build a GC with provable worst‑case guarantees but finds the runtime overhead too large for practical use.
AI-written summary · about
chapters (8)
- 0:00Garbage collection pathological cases
- 2:06Can GC achieve perfection
- 3:31Thrashing in reachability collectors
- 6:21Garbage collection and dynamic connectivity
- 9:10Formalizing GC interface
- 11:38Dynamic connectivity lower bounds
- 12:19Cycle collection with reference counting
- 13:01Summary and acknowledgments
related talks
21mGarbage Collection for Higher Inductive Types
50mAn insight into Go Garbage Collection
28mA Mechanically Verified Garbage Collector for OCaml
54mGarbage Collection, State of the Art
16mSound Garbage Collection for C using Pointer Provenance
19mPolymorphic Reachability Types: Tracking Freshness, Aliasing, and Separation in(…)
18mPolymorphic Reachability Types: Tracking Freshness, Aliasing, and Separation in ...
17mA Better Approximation for Interleaved Dyck Reachability