Avoiding remembered-set maintenance overhead for memory segments known to be in a collection set

• US 20040103126A1
• Filed: 11/27/2002
• Published: 05/27/2004
• Est. Priority Date: 11/27/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Granted Patent: US 7,209,935 B2
• Time in Patent Office: Days
• US Class Current: 707/206
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A garbage collector that employs the train algorithm to manage a generation in a computer system'"'"'s dynamically allocated heap maintains for each of the generation'"'"'s cars a respective remembered set that identifies all locations where references to objects in that car have been found by scanning locations identified by the mutator as having been modified. To avoid some of the expense of remembered-set updating, the collector refrains from attempting to add to a remembered set any reference located in a car that will be collected during the next collection increment. Additionally, if no mutator operation will occur before a collection set of one or more cars will be collected, any reference located outside that collection set but referring to an object within the collection set is not recorded in a remembered set but is recorded instead in a scratch-pad list of entries that identify references to collection-set objects that need to be evacuated.

Claims

1. For employing a computer system that includes a memory to operate as a garbage collector that collects at least a portion of the memory in collection increments in which it collects respective collection sets of the memory and that treats at least a portion of the memory as divided into memory segments and maintains remembered sets respectively associated with the memory segments, a method comprising:

A) during each collection increment;

i) scanning for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a memory segment in the collection set;

ii) evacuating from the collection set any objects referred to by references thereby found; and

iii) reclaiming the memory space occupied by the collection set; and

B) before each of at least some collection increments;

i) identifying a collection-set subset that includes at least a subset of the memory segments that will belong to the collection set collected during that collection increment; and

ii) performing reference-memorialization operations in which;

a) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the memory segments containing those objects if those remembered sets do not already include entries that identify them; and

b) no reference that is located in the collection-set subset thus identified is recorded in a remembered set.

2. A method as defined in claim 1 wherein

A) before objects are evacuated during a given collection increment, at least one said collection-set subset for the next collection increment is identified,

B) some of the reference-memorialization operations performed before the next collection increment are performed in response to the evacuation of a reference-containing object during the given collection increment and include recording in remembered sets the locations of the references contained by the reference-containing objects, but no locations of references located in the collection-set subset identified for the next collection set are thereby recorded.

3. A method as defined in claim 1 wherein the collector collects at least a portion of the memory in accordance with the train algorithm, the memory segments being car sections that the collector groups into trains.

4. A method as defined in claim 3 wherein:

A) during each collection increment, entries are placed into scratch-pad lists associated with respective trains;

B) those entries identify the locations of the references that were found by scanning the locations outside the respective collection set that were identified by entries in each remembered set associated with a car section in the collection set; and

C) in the reference-memorialization operation, the locations of at least some references to objects in the identified collection-set subset are recorded in respective ones of the scratch-pad lists without having first been recorded in the remembered sets associated with the car sections containing those objects.

5. A method as defined in claim 4 wherein:

A) the garbage collector operates in collection intervals;

B) in memorialization operations that occur during a collection interval in which a given collection set is reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in respective ones of the scratch-pad lists without having first been recorded in any of the remembered sets; and

C) in memorialization operations that occur during a collection interval in which a given collection set is not reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify those references'"'"' locations.

6. For employing a computer system that includes a memory to operate as a garbage collector that collects at least a portion of the memory according to the train algorithm in collection increments in which it collects respective collection sets of the memory and that treats at least that portion of the memory as divided into car sections grouped into trains and maintains remembered sets respectively associated with the car sections, a method comprising:

A) during each collection increment;

i) providing scratch-pad lists associated with respective trains;

ii) scanning for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a car section in the collection set;

iii) placing into the scratch-pad lists entries that identify the locations of the references thereby found;

iv) evacuating from the collection set any objects referred to by references whose locations the scratch-pad lists identify; and

v) reclaiming the memory space occupied by the collection set; and

B) before each of at least some collection increments;

i) identifying a collection-set subset that includes at least a subset of the car sections that will belong to the collection set collected during that collection increment; and

ii) performing reference-memorialization operations in which;

a) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify them; and

b) the locations of at least some references to objects in the collection-set subset thus identified are, without having first been recorded in the remembered sets associated with the car sections containing those objects, recorded in the scratch-pad lists associated with the trains to which the car sections containing those references belong.

7. A method as defined in claim 6 wherein:

A) the garbage collector operates in collection intervals;

B) in memorialization operations that occur during a collection interval in which a given collection set is reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in respective ones of the scratch-pad lists without having first been recorded in any of the remembered sets; and

C) in memorialization operations that occur during a collection interval in which a given collection set is not reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify those references'"'"' locations.

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 contains processor instructions readable by the processor circuitry to configure the computer system as a garbage collector that;

i) collects at least a portion of the memory in collection increments in which it collects respective collection sets of the memory;

ii) treats at least a portion of the memory as divided into memory segments;

iii) maintains remembered sets respectively associated with the memory segments;

iv) during each collection increment;

a) scans for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a car section in the collection set;

b) evacuates from the collection set any objects referred to by references thereby found; and

c) reclaims the memory space occupied by the collection set; and

v) before each of at least some collection increments;

a) identifies a collection-set subset that includes at least a subset of the car sections that will belong to the collection set collected during that collection increment; and

b) performs reference-memorialization operations in which;

(1) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify them; and

(2) no reference that is located in the collection-set subset thus identified is recorded in a remembered set.

9. A computer system as defined in claim 8 wherein:

A) before objects are evacuated during a given collection increment, at least one said collection-set subset for the next collection increment is identified,

B) some of the reference-memorialization operations performed before the next collection increment are performed in response to the evacuation of a reference-containing object during the given collection increment and include recording in remembered sets the locations of the references contained by the reference-containing objects, but no locations of references located in the collection-set subset identified for the next collection set are thereby recorded.

10. A computer system as defined in claim 8 wherein the collector collects at least a portion of the memory in accordance with the train algorithm, the memory segments being car sections that the collector groups into trains.

11. A computer system as defined in claim 10 wherein:

A) during each collection increment, entries are placed into scratch-pad lists associated with respective trains;

B) those entries identify the locations of the references that were found by scanning the locations outside the respective collection set that were identified by entries in each remembered set associated with a car section in the collection set; and

C) in the reference-memorialization operation, the locations of at least some references to objects in the identified collection-set subset are recorded in respective ones of the scratch-pad lists without having first been recorded in the remembered sets associated with the car sections containing those objects.

12. A computer system as defined in claim 11 wherein:

A) the garbage collector operates in collection intervals;

B) in memorialization operations that occur during a collection interval in which a given collection set is reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in respective ones of the scratch-pad lists without having first been recorded in any of the remembered sets; and

C) in memorialization operations that occur during a collection interval in which a given collection set is not reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify those references'"'"' locations.

13. A computer system comprising:

A) processor circuitry operable to execute processor instructions;

B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure the computer system as a garbage collector that;

i) collects at least a portion of the memory according to the train algorithm in collection increments in which it collects respective collection sets of the memory;

ii) treats the at least a portion of the memory as divided into car sections grouped into trains;

iii) maintains remembered sets respectively associated with the car sections;

iv) during each collection increment;

a) provides scratch-pad lists associated with respective trains;

b) scans for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a car section in the collection set;

c) places into the scratch-pad lists entries that identify the locations of the references thereby found;

d) evacuates from the collection set any objects referred to by references whose locations the scratch-pad lists identify; and

e) reclaims the memory space occupied by the collection set; and

v) before each of at least some collection increments;

a) identifies a collection-set subset that includes at least a subset of the car sections that will belong to the collection set collected during that collection increment; and

b) performs reference-memorialization operations in which;

(1) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify them; and

(2) the locations of at least some references to objects in the collection-set subset thus identified are, without having first been recorded in the remembered sets associated with the car sections containing those objects, recorded in the scratch-pad lists associated with the trains to which the car sections containing those references belong.

14. A computer system as defined in claim 13 wherein:

A) the garbage collector operates in collection intervals;

B) in memorialization operations that occur during a collection interval in which a given collection set is reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in respective ones of the scratch-pad lists without having first been recorded in any of the remembered sets; and

C) in memorialization operations that occur during a collection interval in which a given collection set is not reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify those references'"'"' locations.

15. A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to operate as a garbage collector that:

A) collects at least a portion of the memory in collection increments in which it collects respective collection sets of the memory;

B) treats at least a portion of the memory as divided into memory segments;

C) maintains remembered sets respectively associated with the memory segments;

D) during each collection increment;

i) scans for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a car section in the collection set;

ii) evacuates from the collection set any objects referred to by references thereby found; and

iii) reclaims the memory space occupied by the collection set; and

E) before each of at least some collection increments;

i) identifies a collection-set subset that includes at least a subset of the car sections that will belong to the collection set collected during that collection increment; and

ii) performs reference-memorialization operations in which;

a) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify them; and

b) no reference that is located in the collection-set subset thus identified is recorded in a remembered set.

16. A storage medium as defined in claim 15 wherein:

A) before objects are evacuated during a given collection increment, at least one said collection-set subset for the next collection increment is identifled,

B) some of the reference-memorialization operations performed before the next collection increment are performed in response to the evacuation of a reference-containing object during the given collection increment and include recording in remembered sets the locations of the references contained by the reference-containing objects, but no locations of references located in the collection-set subset identified for the next collection set are thereby recorded.

17. A storage medium as defined in claim 15 wherein the collector collects at least a portion of the memory in accordance with the train algorithm, the memory segments being car sections that the collector groups into trains.

18. A storage medium as defined in claim 17 wherein:

A) during each collection increment, entries are placed into scratch-pad lists associated with respective trains;

B) those entries identify the locations of the references that were found by scanning the locations outside the respective collection set that were identified by entries in each remembered set associated with a car section in the collection set; and

C) in the reference-memorialization operation, the locations of at least some references to objects in the identified collection-set subset are recorded in respective ones of the scratch-pad lists without having first been recorded in the remembered sets associated with the car sections containing those objects.

19. A storage medium as defined in claim 18 wherein:

A) the garbage collector operates in collection intervals;

B) in memorialization operations that occur during a collection interval in which a given collection set is reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in respective ones of the scratch-pad lists without having first been recorded in any of the remembered sets; and

C) in memorialization operations that occur during a collection interval in which a given collection set is not reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify those references'"'"' locations.

20. A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to operate as a garbage collector that:

A) collects at least a portion of the memory according to the train algorithm in collection increments in which it collects respective collection sets of the memory;

B) treats that portion of the memory as divided into car sections grouped into trains;

C) maintains remembered sets respectively associated with the car sections;

D) during each collection increment;

i) provides scratch-pad lists associated with respective trains;

ii) scans for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a car section in the collection set;

iii) places into the scratch-pad lists entries that identify the locations of the references thereby found;

iv) evacuates from the collection set any objects referred to by references whose locations the scratch-pad lists identify; and

v) reclaims the memory space occupied by the collection set; and

E) before each of at least some collection increments;

i) identifies a collection-set subset that includes at least a subset of the car sections that will belong to the collection set collected during that collection increment; and

ii) performs reference-memorialization operations in which;

a) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify them; and

b) the locations of at least some references to objects in the collection-set subset thus identified are, without having first been recorded in the remembered sets associated with the car sections containing those objects, recorded in the scratch-pad lists associated with the trains to which the car sections containing those references belong.

21. A storage medium as defined in claim 20 wherein:

A) the garbage collector operates in collection intervals;

B) in memorialization operations that occur during a collection interval in which a given collection set is reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in respective ones of the scratch-pad lists without having first been recorded in any of the remembered sets; and

C) in memorialization operations that occur during a collection interval in which a given collection set is not reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify those references'"'"' locations.

22. An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory, cause the computer system to operate as a garbage collector that:

A) collects at least a portion of the memory in collection increments in which it collects respective collection sets of the memory;

B) treats at least a portion of the memory as divided into memory segments;

C) maintains remembered sets respectively associated with the memory segments;

D) during each collection increment;

i) scans for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a car in the collection set;

ii) evacuates from the collection set any objects referred to by references thereby found; and

iii) reclaims the memory space occupied by the collection set; and

E) before each of at least some collection increments;

i) identifies a collection-set subset that includes at least a subset of the car sections that will belong to the collection set collected during that collection increment; and

ii) performs reference-memorialization operations in which;

a) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify them; and

b) no reference that is located in the collection-set subset thus identified is recorded in a remembered set.

23. A electromagnetic signal as defined in claim 22 wherein:

A) before objects are evacuated during a given collection increment, at least one said collection-set subset for the next collection increment is identified,

B) some of the reference-memorialization operations performed before the next collection increment are performed in response to the evacuation of a reference-containing object during the given collection increment and include recording in remembered sets the locations of the references contained by the reference-containing objects, but no locations of references located in the collection-set subset identified for the next collection set are thereby recorded.

24. A electromagnetic signal as defined in claim 22 wherein the collector collects at least a portion of the memory in accordance with the train algorithm, the memory segments being car sections that the collector groups into trains.

25. A electromagnetic signal as defined in claim 24 wherein:

A) during each collection increment, entries are placed into scratch-pad lists associated with respective trains;

B) those entries identify the locations of the references that were found by scanning the locations outside the respective collection set that were identified by entries in each remembered set associated with a car section in the collection set; and

C) in the reference-memorialization operation, the locations of at least some references to objects in the identified collection-set subset are recorded in respective ones of the scratch-pad lists without having first been recorded in the remembered sets associated with the car sections containing those objects.

26. A electromagnetic signal as defined in claim 25 wherein:

A) the garbage collector operates in collection intervals;

B) in memorialization operations that occur during a collection interval in which a given collection set is reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in respective ones of the scratch-pad lists without having first been recorded in any of the remembered sets; and

C) in memorialization operations that occur during a collection interval in which a given collection set is not reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify those references'"'"' locations.

27. An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory, cause the computer system to operate as a garbage collector that:

A) collects at least a portion of the memory according to the train algorithm in collection increments in which it collects respective collection sets of the memory;

B) treats that portion of the memory as divided into car sections grouped into trains;

C) maintains remembered sets respectively associated with the car sections;

D) during each collection increment;

i) provides scratch-pad lists associated with respective trains;

ii) scans for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a car section in the collection set;

iii) places into the scratch-pad lists entries that identify the locations of the references thereby found;

iv) evacuates from the collection set any objects referred to by references whose locations the scratch-pad lists identify; and

v) reclaims the memory space occupied by the collection set; and

E) before each of at least some collection increments;

i) identifies a collection-set subset that includes at least a subset of the car sections that will belong to the collection set collected during that collection increment; and

ii) performs reference-memorialization operations in which;

a) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify them; and

b) the locations of at least some references to objects in the collection-set subset thus identified are, without having first been recorded in the remembered sets associated with the car sections containing those objects, recorded in the scratch-pad lists associated with the trains to which the car sections containing those references belong.

28. A electromagnetic signal as defined in claim 27 wherein:

A) the garbage collector operates in collection intervals;

B) in memorialization operations that occur during a collection interval in which a given collection set is reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in respective ones of the scratch-pad lists without having first been recorded in any of the remembered sets; and

C) in memorialization operations that occur during a collection interval in which a given collection set is not reclaimed, the locations of references that are located outside the given collection set, refer to objects in the given collection set, and reside in locations identified as having been modified since the last memorialization operation are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify those references'"'"' locations.

29. A garbage collector comprising:

A) means for collecting at least a portion of a computer system'"'"'s memory in collection increments in which respective collection sets of the memory are collected;

B) means for treating at least a portion of the memory as divided into memory segments and maintaining remembered sets respectively associated with the memory segments;

C) means for, during each collection increment;

i) scanning for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a car section in the collection set;

ii) evacuating from the collection set any objects referred to by references thereby found; and

iii) reclaiming the memory space occupied by the collection set; and

D) means for, before each of at least some collection increments;

i) identifying a collection-set subset that includes at least a subset of the car sections that will belong to the collection set collected during that collection increment; and

ii) performing reference-memorialization operations in which;

a) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify them; and

b) no reference that is located in the collection-set subset thus identified is recorded in a remembered set.

30. A garbage collector comprising:

A) means for collecting at least a portion of the memory according to the train algorithm in collection increments in which respective collection sets of the memory are collected;

B) means for treating at least a portion of the memory as divided into car sections grouped into trains and maintaining remembered sets respectively associated with the car sections;

C) means for, during each collection increment;

i) providing scratch-pad lists associated with respective trains;

ii) scanning for references to objects in the collection set the locations outside the collection set identified by entries in each remembered set associated with a car section in the collection set;

iii) placing into the scratch-pad lists entries that identify the locations of the references thereby found;

iv) evacuating from the collection set any objects referred to by references whose locations the scratch-pad lists identify; and

v) reclaiming the memory space occupied by the collection set; and

D) means for, before each of at least some collection increments;

i) identifying a collection-set subset that includes at least a subset of the car sections that will belong to the collection set collected during that collection increment; and

ii) performing reference-memorialization operations in which;

a) the locations of at least some references not located in the collection-set subset thus identified that refer to objects are recorded in the remembered sets associated with the car sections containing those objects if those remembered sets do not already include entries that identify them; and

b) the locations of at least some references to objects in the collection-set subset thus identified are, without having first been recorded in the remembered sets associated with the car sections containing those objects, recorded in the scratch-pad lists associated with the trains to which the car sections containing those references belong.