Faster Garbage Collection

Dr. Darko Stefanovic
Princeton University
CS Faculty Candidate

Friday, February 18, 2000
11 a.m.
Fuller Labs 311

Modern programming languages use garbage collection algorithms to provide safe dynamic memory allocation. In Java, for instance, garbage colleciton is a required part of language implementation. Thus the programmer is relieved of the error-prone task of data deallocation. Detecting the time when a data item ("object") will no longer be used is now the responsibility of an automated garbage collection algorithm, and it is important to make this algorithm fast.

The state of the art in garbage collection are generational copying algorithms. By concentrating effort on a smaller region of younger data, they incur shorter pauses and lower total time cost than whole-heap collectors. I will introduce an age-based classification of collection algorithms that generalizes the concept of generations, and includes a newly devised older-first algorithm. Unlike generational, this collector repeatedly selects small regions of contiguous ages, cycling through the heap from older to younger data.

I will review the underlying garbage collection mechanisms that are shared by all these algorithms, and the costs they incur. I will compare generational and new older-first algorithms on a suite of Smalltalk and Java benchmark programs, examining the trade-off between copying cost and pointer-maintenance cost. The flexibility of region positioning in the new algorithm lets it achieve significantly lower copying cost than the generational, for a given heap size. This flexibility is bought at the price of greater pointer maintenance expense, but the balance favors the new algorithm.

The surprising result that a particularly simple nontraditional algorithm is very efficient on real programs opened up new ways of thinking about garbage collection strategies; I will briefly discuss ideas that have come out of this work but are yet awaiting evaluation.

Host

Professor Micha Hofri

Colloquium Coordinator

Professor Carolina Ruiz

Maintained by webmaster@wpi.edu
Last modified: Sep 27, 2006, 16:05 EDT