Alex Garthwaite         
Sun Microsystems, USA
alex.garthwaite@sun.com

Making the Trains Run on Time


One approach to limiting pause times in the collection of older generations
is to use an incremental collection technique.  Collectors based on the train
algorithm are one example: at each collection, a portion of the older
generation is collected.  Train-based collectors have advantages over other
incremental collectors because they allow objects to be
relocated. Unfortunately, there are several problems that make train-based
collectors fail to live up to their promise:

   *  their reliance on remembered sets and the fact that
      these remembered sets may grow to represent the size of the heap
   *  the fact that objects in data structure may have to be
      copied O(d^2) times before the collector may tell if they
      are garbage (where d is the depth of the data structure)
   *  the tension between collecting too aggressively (to
      keep up with allocation in the generation and to deal with
      the need to reorder data structures to identify garbage)
      and collecting at a slow pace (to allow objects a chance
      to die and to constrain pause times)

We will present techniques that allow us to overcome these 
limitations though:

   *  better remembered-set representation
   *  separation of issues such as the size of oversized objects
      versus the size of normal cars
   *  the isolation of popular objects through dynamic feedback
   *  the placement of objects in large (1GB) heaps to reduce
      the amount of floating garbage

The result is that it is possible to constrain pause times,
achieve good throughput, and still support incremental,
copying garbage collection.