Incremental Mature Garbage Collection Using the Train Algorithm

✨ Summary

Contributions and approach

The paper presents the first reported implementation of the Train Algorithm, an incremental garbage collector for the mature or old generation of a generational memory-management system. The implementation replaces the Mjølner BETA runtime system’s traditional mark-sweep collector with a collector designed to avoid long, unpredictable pauses.

The algorithm partitions mature object space into fixed-size blocks called cars. Cars are grouped into ordered collections called trains. Each collection step processes the earliest car in the earliest train rather than scanning the entire mature space. Objects referenced from outside the car are evacuated to appropriate later cars or trains, while unreferenced objects are reclaimed. The ordering and clustering properties of trains allow even cyclic garbage structures larger than an individual car to be recognized and eventually collected.

The implementation relies on remembered sets associated with cars and a train table that maps mature-space addresses to their train and car. The authors also describe a correction to a progress flaw in the original algorithm: after a futile collection, an external reference into a later car is retained as an additional root until a non-futile collection occurs. This prevents a mutator from repeatedly changing references in a way that could otherwise prevent the collector from making progress.

The collector was integrated into the Mjølner BETA runtime using 64-KB cars. Practical policies were introduced for evacuation, train creation, collection frequency, garbage-ratio estimation, and highly referenced objects. The implementation did not adopt a general popular-object scheme; instead, it isolated BETA’s frequently referenced basic environment object in a specially handled car.

Experiments using the BETA compiler, an interactive hyper-structure editor, and a discrete-event simulation showed that old-generation pauses were reduced to only a few milliseconds. Across the benchmarks, median Train Algorithm pauses were 0.01–0.04 seconds, 90th-percentile pauses were 0.03–0.06 seconds, and maximum pauses were 0.05–0.12 seconds under the normal configuration. The authors reported total execution-time changes of +0.6% for the compiler, +1.0% for the editor, and −8% for the simulation. Old-generation storage overhead was approximately 10–20%, corresponding to roughly 4–8% increases in total application storage requirements. The experiments also found that copying overhead remained below 20% on average in the tested configurations.

Influence and subsequent use

The work established a concrete implementation and empirical evaluation of the Train Algorithm, complementing the earlier theoretical proposal by Hudson and Moss. Later garbage-collection literature identifies Seligmann and Grarup’s implementation as an important validation of the approach and discusses the algorithm in analyses of incremental relocation, remembered sets, cyclic garbage, and the “popular object” problem. (beta.cs.au.dk)

Subsequent research applied train-style ideas to persistent and distributed object systems. For example, research on PMOS developed incremental collection for persistent object stores, while later work investigated distributed garbage collection mechanisms based on the Train Algorithm. (researchgate.net) The algorithm has also continued to appear in instructional and systems literature as a representative incremental collector that processes one heap block at a time and uses trains to handle interlinked and cyclic structures. (oracle.com)

The paper was published as a peer-reviewed ECOOP 1995 conference contribution and remains listed in bibliographic and garbage-collection research resources. (dblp.org)