Remembered Sets and Popular Objects

As mentioned previously, the goal of the train algorithm is to provide time-bounded incremental collections of the mature object space of a generational collector. Because the blocks (cars) can be given a maximum size and only one block is collected at each invocation, the train algorithm can most often ensure that each invocation will require less than some maximum amount of time. Unfortunately, the train algorithm can't guarantee that each invocation will take less than some maximum amount of time, because the algorithm must do more than just copy the objects.

To facilitate the collection process, the train algorithm makes use of remembered sets. A remembered set is a data structure that contains information about all references that reside outside a car or train but point into that car or train. The algorithm maintains one remembered set for each car and each train in the mature object space. The remembered set for a particular car, therefore, contains information about the set of references that refer to (or "remember") the objects in that car. An empty remembered set indicates that the objects contained in the car or train are unreferenced (have been "forgotten") by any objects or variables outside the car or train. Forgotten objects are unreachable and can be garbage collected.

The remembered set is an implementation technique that helps the train algorithm do its work more efficiently. When the train algorithm discovers a car with an empty remembered set, it knows the car contains only garbage and can immediately reclaim all the memory occupied by the car. Likewise, when the train algorithm discovers a train with an empty remembered set, it can immediately reclaim all the memory occupied by the entire train. When the train algorithm moves an object to a different car or train, the information in the remembered set helps it efficiently update all references to the moved object so that they correctly refer to the objects new location.

Although the amount of bytes the train algorithm may have to copy during one invocation is limited by the size of a block, the amount of work required to move a popular object, an object that has many references to it, is impossible to limit. Each time the algorithm moves an object, it must traverse the remembered set of that object and update each reference to that object so that the reference points to the new location. Because the number of references to an object cannot be limited, the amount of time required to update the references to a moved object cannot be limited. Thus, in certain cases the train algorithm may still be disruptive. Nevertheless, despite the degenerative case of popular objects, the train algorithm for the most part does a very good job of collecting the mature object space of a generational garbage collector in an incremental, non-disruptive way.