Patent ID: 7062518

Claim:
For employing a computer system that includes memory to perform garbage collection in accordance with a train algorithm, a method comprising: A) treating a generation in the memory as divided into car sections organized into trains that have a front-to-rear order, at least one train being divided into a plurality of subtrains such that each car belonging to that train belongs to one subtrain thereof; and B) collecting the generation in accordance with the train algorithm in collection increments with which respective collection sets in the generation are associated, i) wherein in at least some of the collection increments: a) an object which is in a collection set and is referred to by references outside the collection set is evacuated to a given car in a train that has been divided into subtrains and contains those references, only if the given car belongs to a subtrain that also contains a reference to that object; and b) the collection set is reclaimed; and ii) in each of at least some of which collection increments: a) a determination is made of whether any references located outside the farthest-forward train refer to objects within that train; and b) each car section belonging to that train is reclaimed if there are no such references.