一句话：将程序特定的 GC 调度形式化为优化问题，用动态规划求非分代与分代 GC 的最优回收时机。
论文研究程序特定的垃圾回收（GC）性能极限，关注给定程序运行与堆空间下如何最优选择回收时机。作者将 GC 调度刻画为优化问题，针对非分代收集器给出线性时间的动态规划最优调度算法。为处理分代 GC，他们分析堆对象图以计算对象的 pre-birth time，把非分代调度推广到两代情形，得到代价随 trace 长度二次增长的动态规划解，并进一步推广到多代。实验在 DaCapo Java 程序 trace 上评估两代情形，表明程序特定回收策略可降低 GC 开销：固定空间预算下常节省少量但有用的时间，固定时间预算下可节省可观空间。
We consider the ultimate limits of program-specific garbage collector (GC) performance for real programs. We first characterize the GC schedule optimization problem. Based on this characterization, we develop a linear-time dynamic programming solution that, given a program run and heap size, computes an optimal schedule of collections for a non-generational collector. Using an analysis of a heap object graph of the program, we compute a property of heap objects that we call their pre-birth time. This information enables us to extend the non-generational GC schedule problem to the generational GC case in a way that also admits a dynamic programming solution with cost quadratic in the length of the trace (number of objects allocated). This improves our previously reported approximately optimal result. We further extend the two-generation dynamic program to any number of generations, allowing other generalizations as well. Our experimental results for two generations on traces from Java programs of the DaCapo benchmark suite show that there is considerable promise to reduce garbage collection costs for some programs by developing program-specific collection policies. For a given space budget, optimal schedules often obtain modest but useful time savings, and for a given time budget, optimal schedules can obtain considerable space savings.
@article{paperbot718,
title = {Optimal Choice of When to Garbage Collect},
author = {Nicholas Jacek and Meng-Chieh Chiu and Benjamin M. Marlin and J. Eliot B. Moss},
journal = {ACM Transactions on Programming Languages and Systems},
volume = {41},
number = {1},
year = {2019},
doi = {10.1145/3282438}
}