US 2004/0167946 A1 · Staging the processing of remembered-set entries as part of collection based on the train algorithm

Abstract

A garbage collector that reclaims memory space no longer needed by a mutator treats a generation of a dynamically allocated heap as being divided into “car” sections. For each car section, the collector maintains a remembered-set structure in which it keeps a record of the locations in the generation where the collector has previously found references to locations in that car section. The collector operates in increments in each of which it collects a respective collection set consisting of one or more of the generation's car sections. From the remembered sets associated with a collection set's car sections, it generates scratch-pad lists whose entries tell where locations identified by those remembered sets still contain references to collection-set locations. In situations in which the remembered sets are particularly large, the collector divides the operation of generating the scratch-pad lists into a plurality of collection intervals separated by mutator intervals. The collector bases its identification of reachable collection-set objects on the scratch-pad-list entries. By dividing the scratch-pad-list generation into multiple collection intervals, the collector can keep pause times low while employing relatively large collection sets.

Claims33

Dependent claims

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, at least one of which the garbage collector performs in a plurality of collection intervals dedicated to collection and separated by intervals of mutator execution;
and
C) employing the computer system to execute the garbage collector.

4 more elements

A computer system comprising:

A) processor circuitry operable to execute processor instructions;
and
B) memory circuitry, to which the processor circuitry is responsive, that includes a heap comprising at least one generation in which memory space is dynamically allocated and that contains processor instructions readable by the processor circuitry to configure the computer system as a mutator that modifies references in the heap and 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, at least one of which the garbage collector performs in a plurality of collection intervals dedicated to collection and separated by intervals of mutator execution;
and
C) employing the computer system to execute the garbage collector.

5 more elements

A storage medium containing instructions readable, by a computer system that includes memory including a heap in which space is dynamically allocated to a mutator that modifies references therein, to configure the computer system to operate as a garbage collector that:

A) treats the heap as comprising at least one generation;
and
B) collects at least an incrementally collected one said generation in collection increments, at least one of which the garbage collector performs in a plurality of collection intervals dedicated to collection and separated by intervals of mutator execution.

An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory including a heap in which space is dynamically allocated to a mutator that modifies references therein, cause the computer system to operate as a garbage collector that:

A) treats the heap as comprising at least one generation;
and
B) collects at least an incrementally collected one said generation in collection increments, at least one of which the garbage collector performs in a plurality of collection intervals dedicated to collection and separated by intervals of mutator execution.

Dependencies are inferred from the claim text.

Staging the processing of remembered-set entries as part of collection based on the train algorithm

Life of this patent

Staging the processing of remembered-set entries as part of collection based on the train algorithm

Life of this patent

Abstract

Claims33