Lifetime Aware
Much GC effort is, in a sense, wasted. Rather than reclaiming memory directly (which is what the programmer wants), GC expends effort on preventing the premature and unsafe reclamation of space used by live objects. It has long been known that programs' object demographicss are not random. Rather objects are allocated, interact and die in particular patterns. We believe that understanding and exploiting this regularity is the key to the next generation of program-directed memory management. In order to reduce the cost of discovering live objects (tracing), GC must concentrate effort effort reclaiming space on those regions of the heap in which few objects are live.
Accurate prediction of object lifetimes by static analysis is not possible in general. Safe estimates of the liveness of objects is too conservative. Off-line tracing of programs is infeasible (it takes too long). We therefore seek to combine more aggressive predictions with garbage collectors that can tolerate imprecision.The Lifetime Aware GC (LACE) project builds on Beltway to provide a novel GC framework; it can flexibly exploit object lifetime analysis yet tolerates imprecision. A position paper can be found here.
The Beltway framework of collectors, developed with colleagues at the Australian National University and the Universities of Massachussetts and Texas, not only generalises existing copying collectors but also makes possible the design of new collectors that outperform state of the art generational copying collectors.
Our ISMM 2008 study of Java object demographics showed that (i) sites allocate objects with lifetimes in only a small number of narrow ranges, and that (ii) sites cluster strongly with respect to the lifetime distributions of the objects they allocate. Furthermore, (iii) these clusterings are robust against the size of the input given to the program and (iv) are likely to allocate objects that are live only in particular phases of the program's execution. Finally, we showed that, in contrast to previous studies, (v) allocation site alone is not always sufficient as a predictor of object lifetime distribution but one further level of stack context suffices.
Detailed results of this study can be found here.
Traces of program behaviour were gathered with our MemTrace tool. Although this tool takes a simple brute force approach to gathering traces, it is at least an order of magnitude faster than more accurate tools, such as Merlin. MemTrace can be found in the JikesRVM Research Archive.
Pretenuring long-lived and immortal objects into infrequently or never collected regions reduces garbage collection costs significantly. Our SMART 2008 paper considers how program metrics that might be used to predict lifetimes. Our ISMM 2007 paper shows how a simple program analysis, micropatterns, combined with an object lifetime knowledge bank, can be exploited to match both runtime system and application program structure with object lifetimes. The complexity of the analysis is linear in the size of the program, so need not be run ahead of time. We obtain performance gains between 6-77% in GC time against a generational copying collector.
LACE is funded by the Engineering and
Physical Sciences Research Council, grant number EP/D078342.
Prelimiary research was supported by IBM Faculty Awards. We gratefully acknowledge their support.
