Efficient encoding of references into a collection set
First Claim
1. For employing a computer system, which includes memory of which at least some is used as a heap for dynamic allocation, to perform garbage collection on an incrementally collected generation of the heap in collection increments with which respective collections sets are associated, a method comprising, in each of at least some of the collection increments:
- A) identifying references that are located outside the collection set and refer to objects in the collection set;
B) creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;
i) an individual-reference location in which a single reference represented by that reference-list entry is located;
or ii) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;
C) performing an evacuation operation that includes, for each of at least some of the reference-list entries;
i) identifying each reference represented by that reference-list entry by;
a) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and
b) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and
ii) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and
D) reclaiming the memory space occupied by the collection set.
2 Assignments
0 Petitions
Accused Products
Abstract
A garbage collector employs the train algorithm, in which a generation of a heap is divided into so-called car sections that are grouped into “trains.” Remembered sets associated with respective car sections contain entries that list locations where references to objects in the respective car sections have been found as a result of scanning locations identified by write barriers. In each collection increment, the entries in the remembered sets associated with the car sections to be collected during that increment are processed to find which of the locations thus listed still contain references into the cars to be collected. The resultant locations are stored in scratch-pad lists, and each entry in that list includes a mode indicator that specifies whether the entry represents a single reference'"'"'s location or the locations of more than one reference. One possible value of the mode indicator indicates that the entry consists of two computer words rather than one, the second computer word containing a list of offsets into a region specified by the first word. Another possible mode-indicator value indicates that a region contains references, but it does not specify where within the region those references occur.
-
Citations
37 Claims
-
1. For employing a computer system, which includes memory of which at least some is used as a heap for dynamic allocation, to perform garbage collection on an incrementally collected generation of the heap in collection increments with which respective collections sets are associated, a method comprising, in each of at least some of the collection increments:
-
A) identifying references that are located outside the collection set and refer to objects in the collection set;
B) creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;
i) an individual-reference location in which a single reference represented by that reference-list entry is located;
orii) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;
C) performing an evacuation operation that includes, for each of at least some of the reference-list entries;
i) identifying each reference represented by that reference-list entry by;
a) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and
b) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and
ii) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and
D) reclaiming the memory space occupied by the collection set. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A computer system comprising:
-
A) processor circuitry operable to execute processor instructions; and
B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure it to treat at least a portion of the memory as a heap in which dynamic allocation occurs and act as a garbage collector that collects an incrementally collected generation of the heap in increments, with which respective collection sets are associated, by, in each of at least some of the collection increments;
i) identifying references that are located outside the collection set and refer to objects in the collection set;
ii) creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;
a) an individual-reference location in which a single reference represented by that reference-list entry;
orb) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;
iii) performing an evacuation operation that includes, for each reference-list entry;
a) identifying each reference represented by that reference-list entry by;
(1) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and
(2) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and
b) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and
iv) reclaiming the memory space occupied by the collection set. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to treat at least a portion of the memory as a heap in which dynamic allocation occurs and act as a garbage collector that collects an incrementally collected generation of the heap in increments, with which respective collection sets are associated, by, in each of at least some of the collection increments:
-
A) identifying references that are located outside the collection set and refer to objects in the collection set;
B) creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;
i) an individual-reference location in which a single reference represented by that reference-list entry;
orii) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;
C) performing an evacuation operation that includes, for each reference-list entry;
i) identifying each reference represented by that reference-list entry by;
a) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and
b) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and
ii) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and
D) reclaiming the memory space occupied by the collection set. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory, configure the computer system to treat at least a portion of the memory as a heap in which dynamic allocation occurs and act as a garbage collector that collects an incrementally collected generation of the heap in increments, with which respective collection sets are associated, by, in each of at least some of the collection increments:
-
A) identifying references that are located outside the collection set and refer to objects in the collection set;
B) creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;
i) an individual-reference location in which a single reference represented by that reference-list entry;
orii) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;
C) performing an evacuation operation that includes, for each reference-list entry;
i) identifying each reference represented by that reference-list entry by;
a) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and
b) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and
ii) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and
D) reclaiming the memory space occupied by the collection set. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. For collecting an incrementally collected generation of a heap portion of a computer system'"'"'s memory, where dynamic allocation occurs, in collection increments, with which respective collection sets are associated, a garbage collector comprising:
-
A) means for identifying references that are located outside the collection set and refer to objects in the collection set;
B) means for creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;
i) an individual-reference location in which a single reference represented by that reference-list entry;
orii) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;
C) means for performing an evacuation operation that includes, for each reference-list entry;
i) identifying each reference represented by that reference-list entry by;
a) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and
b) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and
ii) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and
D) means for reclaiming the memory space occupied by the collection set.
-
Specification