Allocation of likely popular objects in the train algorithm
First Claim
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 Assignments
0 Petitions
Accused Products
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.
72 Citations
16 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
Specification