Automatic garbage collection has spared programmers from an entire class of programming errors related to memory leaks and attempting to access objects that were incorrectly freed. As programs have grown in size and complexity, so have the systems that manage garbage collection. Each algorithm makes a different set of tradeoffs between factors such as the space used by objects, the space used by bookkeeping, the number of unused objects (garbage) that remain uncollected, the time spent in allocation, and the time spent in
collection.
The Train Algorithm is an incremental generational garbage collector that was designed to deal with the long and unpredictable pause times caused by other algorithms. It does this by grouping objects together on "cars" in "trains". The algorithm provides a strategy for moving objects from the younger generation into different cars, moving objects from one car to another, and collecting cars and trains. It was first described by Hudson and Moss in the paper "Incremental
Collection of Mature Objects".
In their paper "Incremental Mature Garbage Collection Using the Train Algorithm," Seligmann and Grarup describe what they believe is the first implementation of the Train Algorithm, which they used to replace the traditional mark-and-sweep collector that was used in the BETA programming language. They discuss their implementation and present information about the performance characteristics of the new algorithm as compared to the original.