Hinted Collection (MS Thesis)

(Download PDF) (Download PS) (Tech Report)


Philip Reames. Hinted Collection. Master’s thesis, University of California Berkeley, May 2013.


Garbage collection is widely used and has largely been a boon for programmer productivity. However, traditional garbage collection is approaching both practical and theoretical performance limits. In practice, the maximum heap size and heap structure of large applications are influenced as much by garbage collector behavior as by resource availability.

We present an alternate approach to garbage collection wherein the programmer provides untrusted deallocation hints. Usage of deallocation hints is similar to trusted manual deallocation, but the consequence of an inaccurate hint is lost performance not correctness. Our hinted collection algorithm uses these hints to identify a subset of unreachable objects with both better parallel asymptotic complexity and practical performance.

We present two prototype implementations of a stop-the-world hinted collector: one entirely serial and one parallel. We evaluate our implementations by comparing against the Boehm-Demers-Weiser [12] conservative garbage collector for C/C++. We leverage existing free calls in mature C programs to stand in for deallocation hints. On some benchmarks, our serial collector implementation achieves 10-20% pause time reductions over a well-tuned baseline. On four cores, our parallel implementation achieves similar benefits.

We include a discussion of the design trade-offs inherent in our approach, and lessons to be learned from our collectors. We close with a discussion of several design variants which we have not been able to explore in depth, but believe would be worthwhile to explore in future work.


hinted collection, deallocation hint, memory management, parallel garbage collection, mark and sweep