Path-Sensitive Pretenuring
An algorithm that profiles a program and rewrites its code so long-lived objects skip the young generation.
Pharo, Garbage collection, Program transformation
The problem
Generational garbage collectors assume most objects die young. Objects that live long are copied again and again before they reach the old generation, which wastes time. Pretenuring allocates those objects directly in the old generation, but you have to know which allocations produce them.
Classic pretenuring decides per allocation site: the place in the code where the object is created. In Pharo every allocation goes through a few shared primitive methods, so all sites collapse into the same handful of methods. Pretenuring them gives limited, inconsistent gains, and can even slow programs down by pretenuring short-lived objects that come from unrelated callers.
What I built
Path-sensitive pretenuring uses the full chain of calls that led to an allocation instead of a single site. The pipeline:
- profiles the application with FiLiP to get object lifetimes and call stacks,
- builds a weighted graph of allocation calls,
- classifies its edges as short-lived, long-lived or immortal,
- walks the graph to find call chains that only produce long-lived objects,
- rewrites the code so only those chains allocate directly in the old generation.
Results
Path-sensitive pretenuring consistently improves on the classic strategy and speeds up real Pharo applications by up to 11%. It was evaluated on four benchmarks: an agent-based simulation (Cormas), loading a one-million-row CSV (DataFrame), a fluid simulator (HoneyGinger) and loading a large Java model into Moose. It is the final chapter of my PhD thesis.