Philip Reames

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2013-93

May 17, 2013

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-93.pdf

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 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.

Advisors: George Necula

---

BibTeX citation:

@mastersthesis{Reames:EECS-2013-93,
    Author= {Reames, Philip},
    Title= {Hinted Collection},
    School= {EECS Department, University of California, Berkeley},
    Year= {2013},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-93.html},
    Number= {UCB/EECS-2013-93},
    Abstract= {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 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.},
}

EndNote citation:

%0 Thesis
%A Reames, Philip 
%T Hinted Collection
%I EECS Department, University of California, Berkeley
%D 2013
%8 May 17
%@ UCB/EECS-2013-93
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-93.html
%F Reames:EECS-2013-93