Author:

Publisher:

Published: 2005

Total Pages:

ISBN-13:

Automatic garbage collection has proven software engineering benefits: fewer memory-related errors and less programmer effort. However, to attain performance competitive with explicit memory management, garbage collection needs much more memory. This key tradeoff exists because the collector only reclaims memory when it is invoked: invoking it more frequently reclaims memory quickly, but incurs a significant cost, while invoking it less frequently fills memory with dead objects. This work comes closer to the best of both worlds by adding novel runtime and compiler support for compiler-inserted frees to a garbage-collected system. The compiler analysis automatically identifies when objects become unreachable and inserts calls to free. The analysis combines a simple interprocedural pointer analysis with liveness information. The free() implementation depends on the allocator, and we demonstrate variations for \emph{free-list} and \emph{bump-pointer} allocators. Explicitly freeing objects reduces memory requirements by reclaiming memory quickly, reduces garbage collection load, and improves performance, often substantially for mark-sweep collectors. Compared to the baseline, free-me cuts total time by 22\% on average, collector time by 50\% to 70\% on average, and allows programs to run in 17\% less memory on average. Our approach differs from stack and region allocation in two crucial ways. First, it frees objects incrementally exactly when they become unreachable, instead of based on program scope. Second, our system does not require allocation-site lifetime homogeneity, and thus can free objects on some program paths and not on others. Our system also handles common design patterns, such as freeing inside loops and objects created by factory methods.