Patent ID: 6415302
Filing Date: 2002-07-02
Classification: G06F,Y10S

Abstract:
A method of garbage collection that includes treating a generation of a collected heap as divided into car sections that belong to trains, collecting the generation in collection cycles, in each of which a collection set of at least one car section is collected in accordance with the train algorithm, employing remembered sets, associated with respective car sections, of remembered-set entries that identify regions containing inter-car references to objects contained in the car sections with which those remembered sets are respectively associated, and processing the remembered sets associated with each car section of the collection set to identify objects that will survive the collection cycle, and wherein:A) the method includes treating the generation as divided into segments and maintaining, for each segment, a farthest-forward-car value that is associated with that segment and identifies at least the train to which the farthest-forward-car section into which that segment contains a reference belongs; and B) during at least some collection cycles, the processing of a remembered set includes: i) reading the farthest-forward-car value associated with at least one segment that includes or is included in a region associated with at least one remembered-set entry in the remembered set; and ii) searching in that segment only if the farthest-forward-car value associated with that segment identifies a train that is at least as old as one to which a car section in the collection set belongs.