The Train Algorithm

TheTrainAlgorithm, aka the Mature Object Space Garbage Collector, is an incremental copying [evacuating] GC.

The algorithm divides the heap into blocks, called cars. Each car belongs to a train. Trains are ordered, and cars are ordered within trains. All cars have a remembered set, but it only contains references from higher cars, because lower cars are always collected first. Each train also has a remembered set.

Each collection cycle, if the remembered set of the first train is empty, the entire train is reclaimed. If not, the remembered set of the first car is examined. Objects referenced by the roots may be copied into the last car of any train [if there is available space], or a new train may be allocated to contain them. Objects referenced by an object contained in another train must be copied to that train, although if referenced by more than one train, it may be copied to either. Objects referenced only by other cars of the same train are copied to the last car of that train; if there is no room, a new car is allocated as necessary. When an object is copied, any outgoing references are traced; if they refer to lower cars/trains, those cars' remembered sets are updated accordingly.

When every object referred to by the remembered set has been evacuated, the first car can be reclaimed.

It has been proven that the train algorithm is guaranteed to eventually move cyclic garbage into a single train, where it can all be collected at once. The amount of work done per collection cycle is mostly bounded, as the GC never evacuates more than one car at a time, thus making copying costs bounded. Potentially unbounded operations include pointer updates, but these are typically reduced to O(1) at the cost of locality via a TombStone.

As the name implies, the Mature Object Space Collector is intended to be used as the tenured generation of a generational garbage collector. It is part of the GarbageCollection system for BetaLanguage.

Variants of TheTrainAlgorithm/MOS include PMOS, which is designed to collect garbage in persistent storage mediums, and DMOS, for distributed systems.

CategoryGarbageCollection CategoryAlgorithm