Incremental Collection of Mature Objects
📜 Abstract
We present a garbage collection algorithm that extends generational scavenging to collect large older generations (mature objects) non-disruptively. The algorithm’s approach is to process bounded-size pieces of mature object space at each collection; the subtleties lie in guaranteeing that it eventually collects any and all garbage. The algorithm does not assume any special hardware or operating system support, e.g., for forwarding pointers or protection traps. The algorithm copies objects, so it naturally supports compaction and reclustering.
✨ Summary
The paper presents Mature Object Space (MOS), an incremental copying collector for objects that have survived the young generations of a generational garbage collector. Its goal is to avoid the long pauses that occur when a large old generation is collected all at once, while retaining the benefits of copying collection, including compaction and object reclustering.
MOS divides mature space into bounded-size areas, called cars, and groups related cars into trains. The collector processes one car at a time in round-robin order. Remembered sets identify references into the car being processed. Reachable objects are copied into other cars or trains according to their incoming references, while objects that become isolated from all roots are reclaimed. This migration progressively collapses cross-train garbage structures, including cycles that cannot be identified as garbage using only local information. The bounded car size limits the amount of work and movement performed by an individual collection, while the copying process also reduces fragmentation and permits locality-oriented rearrangement.
The paper argues that the algorithm requires only ordinary hardware and operating-system facilities. Its correctness argument is based on the fact that each pass either reclaims garbage or moves externally referenced objects out of a train, thereby reducing the remaining structure; a garbage structure spanning a train of size n is eventually reclaimed or evacuated within an O(n²) bound on car collections. The principal trade-offs are possible repeated copying of live objects, policy dependence in choosing destination trains, and additional complications for very large objects or persistent heaps.
The work directly influenced subsequent research on the Train algorithm. An implementation for the BETA programming language replaced a traditional mark-sweep collector with an incremental Train collector and reported negligible time and storage overheads. (beta.cs.au.dk) Later work on distributed mature-object collection described DMOS as being derived from MOS, extending the approach to distributed object systems. (memorymanagement.org) The Train algorithm is also cited in later research and patent literature as an example of space-incremental collection, alongside subsequent partial-compaction techniques. (patents.google.com) The available sources document substantial conceptual influence on incremental and mature-object garbage collection, but do not establish that the precise MOS algorithm became a standard production collector.