Collecting Cars

Each time the train algorithm is invoked, it collects either the lowest numbered car of the lowest numbered train or it collects the entire lowest numbered train. The algorithm first checks for references into any car of the lowest numbered train. If no references exist outside the lowest numbered train that refer to objects contained inside the lowest numbered train, the entire lowest numbered train contains garbage and can be reclaimed. This first step enables the train algorithm to collect large cyclic data structures that don't fit within a single block. Because of the second step of train algorithm, which will be described next, such large cyclic data structures are guaranteed to eventually end up in the same train.

If the lowest numbered train was determined to all be garbage, the train algorithm reclaims the space occupied by all objects in all the cars of the lowest numbered train and returns. (At that point, that invocation of the train algorithm is complete.) If the lowest numbered train was not all garbage, however, the algorithm turns its attention to the lowest numbered car of the lowest numbered train. In the process, the algorithm will either move or free any object in that car. The algorithm starts by moving any object that is referenced from outside the lowest numbered car to some other car. Any objects remaining in the car after this moving process are unreferenced and can be garbage collected. The train algorithm then reclaims the space occupied by the entire lowest numbered car (thereby freeing any unreferenced objects still sitting in the lowest numbered car) and returns.

The key to guaranteeing that cyclic data structures all end up in the same train lies in how the algorithm moves objects. If an object sitting in the car being collected is referenced from outside the mature object space, that object is moved to any train but the one being collected. If an object is referenced from a different train within the mature object space, that object is moved to the referencing train. Moved objects are then scanned for references back into the car being collected. Any newly referenced objects are moved to the referencing train. Newly moved objects are then scanned for references back into the car being collected, and the process repeats until no more references exist from other trains into the car being collected. If a receiving train runs out of space, the algorithm will create a new car (an empty block) and append it to the end of that train.

Once no more references exist from outside the mature object space or from other trains within the mature object space into the car being collected, any objects referenced from outside the car being collected are known to be referenced from other cars of the same train. The algorithm moves such objects to the last car of the same, lowest numbered train. These objects are then scanned for references back into the car being collected. Any newly referenced objects are moved to the end of the same train and scanned. This process repeats until no more references of any kind exist into the car being collected. The algorithm then reclaims the space occupied by the entire lowest-numbered car, freeing any unreferenced objects that still happen to be sitting in that car, and returns.

At each invocation, therefore, the train algorithm either collects the lowest numbered car of the lowest numbered train, or it collects the entire lowest numbered train. One of the most important facets of the train algorithm is that it guarantees that large cyclic data structures will eventually be collected, even though they may not fit in a single block. Because objects are moved into trains from which they are referenced, related objects tend to cluster together. Eventually, all the objects of a garbage cyclic data structure, no matter how large, will end up in the same train. Increasing the size of the cyclic data structure will only increase the number of cars that ultimately form the same train. Because the train algorithm first checks for a lowest numbered train that is completely garbage before settling for just the lowest numbered car, it is able to collect cyclic data structures of any size.