Abstract: While the design of garbage collection algorithms has come of age, the analysis of these algorithms is still in its infancy. Current analyses are limited to merely documenting costs of individual collector executions; conclusive results, measuring across entire programs, require a theoretical foundation from which proofs can be offered. A theoretical foundation also allows abstract examination of garbage collection, enabling new designs without worrying about implementation details. We propose a theoretical framework for analyzing garbage collection algorithms and show how our framework could compute the efficiency (time cost) of garbage collectors. The central novelty of our proposed framework is its capacity to analyze costs of garbage collection over an entire program execution. In work on garbage collection, one frequently uses heap traces, which require determining the exact point in program execution at which each heap allocated object "dies" (becomes unreachable). The framework inspired a new trace generation algorithm, Merlin, which runs more than 800 times faster than previous methods for generating accurate traces. The central new result of this paper is using the framework to prove that Merlin's asymptotic running time is optimal for trace generation.

Recent Publications of Neil Immerman