Pathological Cases for a Class of Reachability-Based Garbage Collectors
Pathological Cases for a Class of Reachability-Based Garbage Collectors
计算技术、计算机技术
Matthew Sotoudeh.Pathological Cases for a Class of Reachability-Based Garbage Collectors[EB/OL].(2025-04-15)[2025-11-08].https://arxiv.org/abs/2504.11654.点此复制
Although existing garbage collectors (GCs) perform extremely well on typical
programs, there still exist pathological programs for which modern GCs
significantly degrade performance. This observation begs the question: might
there exist a 'holy grail' GC algorithm, as yet undiscovered, guaranteeing both
constant-length pause times and that memory is collected promptly upon becoming
unreachable? For decades, researchers have understood that such a GC is not
always possible, i.e., some pathological behavior is unavoidable when the
program can make heap cycles and operates near the memory limit, regardless of
the GC algorithm used. However, this understanding has until now been only
informal, lacking a rigorous formal proof.
This paper complements that informal understanding with a rigorous proof,
showing with mathematical certainty that every GC that can implement a
realistic mutator-observer interface has some pathological program that forces
it to either introduce a long GC pause into program execution or reject an
allocation even though there is available space. Hence, language designers must
either accept these pathological scenarios and design heuristic approaches that
minimize their impact (e.g., generational collection), or restrict programs and
environments to a strict subset of the behaviors allowed by our
mutator-observer-style interface (e.g., by enforcing a type system that
disallows cycles or overprovisioning memory).
展开英文信息
评论