Allocation of likely popular objects in the train algorithm

• US 7,539,713 B2
• Filed: 11/05/2002
• Issued: 05/26/2009
• Est. Priority Date: 11/05/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): COLAN, GIOVANNA B
• Application Number:
  US10/287,930
• Publication Number:
  US 20040088338A1
• Time in Patent Office: 2,394 Days
• Field of Search: 707/206, 707/202, 719/315, 718/107, 709/315
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection

Abstract

A garbage collector for reclaiming computer-memory space occupied by unreachable data objects operates incrementally in accordance with the train algorithm. Although most objects share car sections with other objects, objects found to be referred to by a large number of references are placed in their own individual car sections so that the “popular” object'"'"'s train membership can be changed without relocating the object and thus requiring the numerous references to it to be updated. The collector keeps track of different object classes to have instances that are popular. If a class exhibits a strong tendency to have popular instances, the collector initially places instances of that class into respective single-object cars even if those objects have not yet been identified as popular.

Claims

1. In the method of garbage collection that treats a generation of a collected heap as divided into car sections that belong to trains, links the car sections as to order them within the trains to which they belong, and collects the generation in collection cycles, in each of which a collection set of at least one car section is collected in accordance with a train algorithm, the improvement comprising:

A) designating at least one car section as a popular-object car section;

B) storing no more than one object in each said popular-object car section;

C) for at least one class, monitoring at run time a tendency of that class'"'"'s instances to become popular;

D) determining whether the tendency of that class'"'"'s instances to become popular meets a popular-class criterion, wherein the tendency for a class'"'"'s instances to become popular is determined from an average of instance counts over previous increments;

E) when each of at least some objects is allocated in the generation of a collected heap, performing the allocation of each object in a popular-object car section independently of whether the object has already become popular if the object is an instance of a class for which the tendency of the class'"'"'s objects to become popular has been determined to meet the popular-class criterion; and

F) whenever any said popular-object car section containing a popular object is collected, collecting it by re-linking that car section without relocating the object that it contains.

2. The method as defined in claim 1 wherein the monitoring of the tendency of a class'"'"'s instances to become popular includes maintaining for that class:

A) an instance count, which is a measure of the rate at which instances of that class are allocated in the generation; and

B) a popular-object count, which is a measure of the rate at which instances of that class became popular in the generation.

3. The method as defined in claim 2 wherein the popular-class criterion is that the ratio of the popular-object count to the instance count exceeds a popular-class threshold.

4. The method as defined in claim 1 further comprising:

A) for at least one object in the collection set that is not in a popular-object car section, determining whether the object meets a first popular-object criterion; and

B) placing into a popular-object car section any object thereby determined to meet the first popular-object criterion.

5. The method as defined in claim 4 further comprising:

A) for at least one popular-object car section that contains an object and belongs to the collection set, determining whether the object contained by that popular-object car section meets a second popular-object criterion; and

B) if that object is reachable, placing it into a car section that is not a popular object car section if it is thereby found not to meet the second popular- object criterion.

6. The method as defined in claim 5 wherein the first and second popular-object criteria differ.

7. The method as defined in claim 1 wherein:

A) the collected heap is treated as divided into a young generation and at least one old generation;

B) the at least one old generation is the generation that is collected in accordance with the train algorithm;

C) some objects are initially allocated in the young generation and then allocated in the old generation only after they have met a predetermined promotion criterion;

D) some objects are initially allocated directly in the old generation without having first been allocated in the young generation; and

E) the allocation of objects belonging to popular classes into popular-object cars independently of whether they have already become popular occurs at least for objects that are initially allocated directly in the old generation without being first allocated in the young generation.

8. The method as defined in claim 7 wherein the allocation of objects belonging to popular classes into popular-object cars independently of whether they have already become popular additionally occurs for objects that were initially allocated in the young generation.

9. A computer system comprising:

memory;

a processor;

a display; and

an interconnection mechanism coupling the memory, the processor, and the display, allowing communication therebetween;

wherein the memory of the computer system is encoded with a garbage collector application, that when executed in the processor, provides a garbage collector process that treats a generation of a dynamically allocated heap portion of the memory as divided into car sections that belong to trains, links the car sections as to order them within the trains to which they belong, and collects the generation in collection cycles, in each of which a collection set of at least one car section is collected in accordance with a rain algorithm, by causing the computer system to perform operations of;

i) designating at least one car section as a popular-object car section;

ii) storing no more than one object in each said popular-object car section;

iii) for at least one class, monitoring at run time a tendency of that class'"'"'s instances to become popular;

iv) determining whether the tendency of that class'"'"'s instances to become popular meets a popular-class criterion, wherein the tendency for a class'"'"'s instances to become popular is determined from an average of instance counts over previous increments;

v) when each of at least some objects is allocated in the generation of a collected heap, performing the allocation of each object in a popular object car section independently of whether the object has already become popular if the object is an instance of a class for which the tendency of the class'"'"'s objects to become popular has been determined to meet the popular-class criterion; and

vi) whether any said popular-object car section containing a popular object is collected, collecting it by re-linking that car section without relocating the object that it contains.

10. The computer system as defined in claim 9 wherein the monitoring of the tendency of a class'"'"'s instances to become popular includes maintaining for that class:

A) an instance count, which is a measure of the rate at which instances of that class are allocated in the generation; and

B) a popular-object count, which is a measure of the rate at which instances of that class become popular in the generation.

11. The computer system as defined in claim 10 wherein the popular-class criterion is that the ratio of the popular-object count to the instance count exceeds a popular-class threshold.

12. The computer system as defined in claim 9 wherein the computer system performs additional operations of:

A) determining, for at least one object in the collection set that is not in a popular-object car section, whether that object meets a first popular-object criterion; and

B) placing into a popular-object car section any object thereby determined to meet the first popular-object criterion.

13. The computer system as defined in claim 12 wherein the computer system performs additional operations of:

A) determining, for at least one popular-object car section that contains an object and belongs to the collection set, whether the object contained by that popular-object car section meets a second popular-object criterion; and

B) if that object is reachable, placing it into a car section that is not a popular-object car section if it is thereby found not to meet the second popular-object criterion.

14. The computer system as defined in claim 13 wherein the first and second popular-object criteria differ.

15. The computer system as defined in claim 9 wherein:

A) the collected heap is treated as divided into a young generation and at least one old generation;

B) the at least one old generation is the generation that is collected in accordance with the train algorithm;

C) some objects are initially allocated in the young generation and then allocated in the old generation only after they have met a predetermined promotion criterion;

D) some objects are initially allocated directly in the old generation without having first been allocated in the young generation; and

E) the allocation of objects belonging to popular classes into popular-object cars independently of whether they have already become popular occurs at least for objects that are initially allocated directly in the old generation without being first allocated in the young generation.

16. The computer system as defined in claim 15 wherein the allocation of objects belonging to popular classes into popular-object cars independently of whether they have already become popular additionally occurs for objects that were initially allocated in the young generation.