Patent ID: 7146390

Claim:
A method of garbage collection comprising: A) providing a computer system that includes memory and executes a mutator that modifies references in a dynamically allocated heap in the memory; B) configuring the computer system to act as a garbage collector that: i) treats the heap as comprising at least one generation; and ii) collects at least an incrementally collected one said generation in collection increments, the collection of each collection increment being performed without intervening mutator execution and wherein the garbage collector is modified to perform a collection of at least one collection increment in a plurality of collection intervals dedicated to collection and separated by intervals of mutator execution; iii) associates with each collection increment a respective collection set collected during that increment; iv) maintains for the collection sets respective remembered sets of remembered-set entries that identify locations where references to objects in the respective collection sets have been found before the increments with which those collection sets are associated; v) during a collection increment: a) performs a reference-listing operation in which, by inspecting the locations identified by the remembered-set entries in the remembered set associated with that increment, it compiles a scratch-pad list of locations where it thereby finds references to objects in the collection set associated with that increment; b) performs an evacuation operation in which it evacuates from the collection set objects that it employs the scratch-pad list to identify; and c) thereafter reclaims the collection set; and vi) in at least some collection increments divides performance of the reference-listing operation among a plurality of the collection intervals; and C) employing the computer system to execute the garbage collector.