Staging the processing of remembered-set entries as part of collection based on the train algorithm
First Claim
1. 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.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
22 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. 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, 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; d) 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. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. 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; B) 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; C) associates with each collection increment a respective collection set collected during that increment; D) 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; E) during a collection increment; i) 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; ii) performs an evacuation operation in which it evacuates from the collection set objects that it employs the scratch-pad list to identify; and iii) thereafter reclaims the collection set; and F) in at least some collection increments divides performance of the reference-listing operation among a plurality of the collection intervals. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
-
22. For reclaiming memory in a dynamically allocated heap in which a mutator modifies references, a garbage collector comprising:
-
A) means for treating the heap as comprising at least one generation; B) means for collecting 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; C) means for associating with each collection increment a respective collection set collected during that increment; D) means for maintaining 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; E) means operable during a collection increment; i) for performing 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; ii) for performing an evacuation operation in which it evacuates from the collection set objects that it employs the scratch-pad list to identify; and iii) for thereafter reclaiming the collection set; and F) means operable in at least some collection increments for dividing performance of the reference-listing operation among a plurality of the collection intervals.
-
Specification