Garbage Collection 2

Thursday, 30 October – 10:30-12:00

MarkCopy: Fast Copying GC with Less Space Overhead

Narendran Sachindran, University of Massachusetts Amherst, naren@cs.umass.edu
Eliot Moss, University of Massachusetts Amherst, moss@cs.umass.edu

Copying garbage collectors have several advantages over non-copying collectors, including cheap allocation and prevention of fragmentation. However, in order to provide completeness (the guarantee to reclaim each garbage object eventually), standard copying collectors require space equal to twice the size of the maximum live data for a program.

We present a mark-copy collection algorithm that extends generational copying collection and significantly reduces the heap space required to run a program. The new collector runs in space that is nearly a factor of two smaller than that required by standard copying garbage collectors, increasing the range of applications that can use copying garbage collection. We show that when the collector is given the same amount of space as a generational copying collector, it improves program execution time of Java benchmarks by 20-85% in tight heaps and by 5-10% in moderate size heaps.

We also compare the performance of the mark-copy collector with that of a mark-sweep collector. We find that, for several benchmarks, the mark-copy collector can run in heaps comparable in size to the minimum heap space required by the mark-sweep collector. We also find that for some benchmarks the mark-copy collector is significantly faster than a mark-sweep collector in tight heaps.

Ulterior Reference Counting: Fast Garbage Collection without a Long Wait

Steve Blackburn, Australian National University, Steve.Blackburn@anu.edu.au
Kathryn McKinley, University of Texas at Austin, mckinley@cs.utexas.edu

General purpose garbage collectors have yet to combine short pause times with fast throughput. For example, non-concurrent generational collectors can achieve high throughput and have modest average pause times, but occasionally collect the whole heap and consequently incur long pauses. On the other extreme, concurrent collectors, including reference counters, attain short pause times with significant performance penalties. This paper introduces GenRC, which combines copying generational collection and reference counting the older generation to achieve both goals in a uniprocessor setting. Key to our algorithm is a generalization of deferred reference counting which allows GenRC to safely ignore mutations to nursery objects. GenRC thus restricts copying and reference counting to the object demographics for which they perform well. The contiguous allocation of a copying collector is extremely fast, and collection time is proportional to the live objects whose survival rates are usually low in a fixed size nursery. Reference counting time is proportional to object mutations and the number of dead objects, both of which are typically low for older objects. We further restrict the time spent reference counting with collection triggers and buffering. We compare GenRC using a fixed nursery (FG-RC) with pure reference counting (RC), high performance copying and mark-sweep fixed nursery generational (FG-MS), and pure mark-sweep collectors (MS). We show that FG-RC is competitive with FG-MS on throughput, and attains much lower average and maximum pause times.

Connectivity-Based Garbage Collection

Martin Hirzel, University of Colorado at Boulder, hirzel@cs.colorado.edu
Amer Diwan, University of Colorado at Boulder, diwan@cs.colorado.edu
Matthew Hertz, University of Massachusetts Amherst, hertz@cs.umass.edu

We introduce a new family of connectivity-based garbage collectors (CBGC) that are based on potential object-connectivity properties. The key feature of these collectors is that the placement of objects into partitions is determined by performing one of several forms of connectivity analyses on the program. This enables partial garbage collections, as in generational collectors, but without the need for any write barrier.

The contributions of this paper are 1) a novel family of garbage collection algorithms based on object connectivity; 2) a detailed description of an instance of this family; and 3) an empirical evaluation of CBGC using simulations. Using simulations allows us to explore a broad range of possibilities for CBGC, ranging from simplistic ones that determine connectivity based on type information to oracular ones that use run-time information to determine connectivity. Our experiments with the oracular CBGC configurations give us an indication of the potential for CBGC and also identify weaknesses in the realistic configurations. We found that even the simplistic implementations beat state-of-the-art generational collectors with respect to some metrics (e.g., pause times and memory footprint).