Optimization and Training of Generational Garbage Collectors

Garbage collectors are nearly ubiquitous in modern programming languages, and we want to minimize the cost they impose in terms of time and space. Generally, a collector waits until its space is full and then performs a collection to reclaim needed memory. However, this is not the only option; a collection could be performed early when some free space remains. For copying collectors, which are what we consider here, the system must traverse the graph of live objects and copy them, so the cost of a collection is proportional to the volume of objects that are live. Since this value fluctuates during a program\u27s execution, a collector can minimize its cost by carefully choosing the points at which it collects. We help to realize this goal in two ways. First, by developing an algorithm that analyzes after-the-fact traces and computes optimal collection points, we can explore the theoretical limits of garbage collectors. This gives insight into what performance gains are possible, and can guide future collector development into areas that could be most fruitful. Second, we use techniques from machine learning to find improved garbage collection policies that could be implemented in real systems. The optimal collection points provide ground truth from which a model can learn