Combining external and intragenerational reference-processing in a garbage collector based on the train algorithm
First Claim
1. For operating a computer system, which includes memory, as a garbage collector that treats at least a generation of a garbage-collected heap in the memory as divided into sections and collects the generation in collection increments with which the garbage collector associates respective collection sets in the generation, a method comprising, in at least some of the collection increments:
- A) finding references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation, listing the external references thereby found that refer to objects in the collection set, and marking sections of the generation that contain objects to which the external references thereby found refer;
B) identifying and including in the collection set at least one section, denominated a dead section, not reachable through a reference chain that includes an external reference thereby found;
C) finding references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set;
D) evacuating from the collection set objects reachable from outside the collection set without evacuating therefrom any object located in a dead section even if that dead section contains an object referred to by an internal reference; and
E) reclaiming the collection set.
2 Assignments
0 Petitions
Accused Products
Abstract
A garbage collector collects at least a generation of a dynamically allocated heap in increments. In each increment, it identifies references located outside a collection set that refer to objects that belong to the collection set, and it evacuates the objects thus referred to before it reclaims the memory space that the collection set occupies. In some collection increments, references to collection-set objects are located both inside and outside the generation. The collector locates all such references, both those inside the generation and those outside it, before it evacuates any objects in response to any of them. By doing so, it is able to reduce the cost of locating references and evacuating objects.
109 Citations
15 Claims
-
1. For operating a computer system, which includes memory, as a garbage collector that treats at least a generation of a garbage-collected heap in the memory as divided into sections and collects the generation in collection increments with which the garbage collector associates respective collection sets in the generation, a method comprising, in at least some of the collection increments:
-
A) finding references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation, listing the external references thereby found that refer to objects in the collection set, and marking sections of the generation that contain objects to which the external references thereby found refer; B) identifying and including in the collection set at least one section, denominated a dead section, not reachable through a reference chain that includes an external reference thereby found; C) finding references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set; D) evacuating from the collection set objects reachable from outside the collection set without evacuating therefrom any object located in a dead section even if that dead section contains an object referred to by an internal reference; and E) reclaiming the collection set. - View Dependent Claims (2)
-
-
3. 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 to operate as a garbage collector that; i) treats at least a generation of a garbage-collected heap in the memory as divided into sections; and ii) collects the generation in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector; a) finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation b) lists the external references thereby found that refer to objects in the collection set; c) marks sections of the generation that contain objects to which the external references thereby found refer; d) identifies and includes in the collection set at least one section, denominated a dead section, not reachable through a reference chain that includes an external reference thereby found; e) finds references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set; f) evacuates from the collection set objects reachable from outside the collection set without evacuating therefrom any object located in a dead section even if that dead section contains an object referred to by an internal reference; and iii) reclaims the collection set. - View Dependent Claims (4)
-
-
5. 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) treats at least a generation of a garbage-collected heap in the memory as divided into sections; and B) collects the generation in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector; i) finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation ii) lists the external references thereby found that refer to objects in the collection set; iii) marks sections of the generation that contain objects to which the external references thereby found refer; iv) identifies and includes in the collection set at least one section, denominated a dead section, not reachable through a reference chain that includes an external reference thereby found; v) finds references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set; vi) evacuates from the collection set objects reachable from outside the collection set without evacuating therefrom any object located in a dead section even if that dead section contains an object referred to by an internal reference; and vii) reclaims the collection set. - View Dependent Claims (6)
-
-
7. For collecting at least a generation of a garbage-collected heap in a computer system'"'"'s memory in collection increments with which each of which a garbage collector associates a respective collection set in the generation, the garbage collector comprising:
-
A) means for treating the generation as divided into sections; B) means for finding references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation C) means for listing the external references thereby found that refer to objects in the collection set; D) means for marking sections of the generation that contain objects to which the external references thereby found refer; E) means for identifying and including in the collection set at least one section, denominated a dead section, not reachable through a reference chain that includes an external reference thereby found; F) means for finding references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set; G) means for evacuating from the collection set objects reachable from outside the collection set without evacuating therefrom any object located in a dead section even if that dead section contains an object referred to by an internal reference; and H) means for reclaiming the collection set.
-
-
8. For operating a computer system, which includes memory, as a garbage collector that treats at least a generation of a garbage-collected heap in the memory as divided into car sections grouped into trains and collects the generation in accordance with the train algorithm in collection increments with which the garbage collector associates respective collection sets in the generation, a method comprising, in each of at least some of the collection increments:
-
A) finding references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation; B) finding references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set; C) evacuating potentially reachable objects from the collection set in operations that include; i) in response to at least one said external reference that refers to an object in the collection set, evacuating that object to a car section belonging to a train, denominated an external-reference train, that is empty at the beginning of that collection increment; and ii) in response to at least one internal reference that refers to an object in the collection set also referred to by at least one external reference, evacuating that object to a car section in the train to which the car containing that internal reference belongs; and D) reclaiming the collection set.
-
-
9. 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 to operate as a garbage collector that; i) treats at least a generation of a garbage-collected heap in the memory as divided into car sections grouped into trains; and ii) collects the generation in accordance with the train algorithm in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector; a) finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation; b) finds references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set; c) evacuates potentially reachable objects from the collection set in operations that include; (1) in response to at least one said external reference that refers to an object in the collection set, evacuating that object to a car section belonging to a train, denominated an external-reference train, that is empty at the beginning of that collection increment; and (2) in response to at least one internal reference that refers to an object in the collection set also referred to by at least one external reference, evacuating that object to a car section in the train to which the car containing that internal reference belongs; and d) reclaims the collection set.
-
-
10. 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) treats at least a generation of a garbage-collected heap in the memory as divided into car sections grouped into trains; and B) collects the generation in accordance with the train algorithm in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector; i) finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation; ii) finds references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set; iii) evacuates potentially reachable objects from the collection set in operations that include; a) in response to at least one said external reference that refers to an object in the collection set, evacuating that object to a car section belonging to a train, denominated an external-reference train, that is empty at the beginning of that collection increment; and b) in response to at least one internal reference that refers to an object in the collection set also referred to by at least one external reference, evacuating that object to a car section in the train to which the car containing that internal reference belongs; and iv) reclaims the collection set.
-
-
11. For collecting at least a generation of a garbage collected heap in a computer system'"'"'s memory in accordance with the train algorithm in collection increments with which each of which a garbage collector associates a respective collection set in the generation, the garbage collector comprising:
-
A) means for treating the generation as divided into car sections grouped into trains; and B) means for finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation; C) means for finding references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set; D) means for evacuating potentially reachable objects from the collection set in operations that include; i) in response to at least one said external reference that refers to an object in the collection set, evacuating that object to a car section belonging to a train, denominated an external-reference train, that is empty at the beginning of that collection increment; and ii) in response to at least one internal reference that refers to an object in the collection set also referred to by at least one external reference, evacuating that object to a car section in the train to which the car containing that internal reference belongs; and E) means for reclaiming the collection set.
-
-
12. In the method of operating a computer system, which includes memory, as a garbage collector that collects at least a generation of a garbage-collected heap in the memory in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector locates references, denominated external references, that are located outside the generation but refer to objects in the collection set, locates references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are inside the collection set, evacuates from the collection set objects referred to by references thereby found, and reclaims the collection set, the improvement wherein, in at least some collection increments, the garbage collector locates both the internal and the external references before any object is evacuated from the collection set in response to references thereby located.
-
13. A computer system comprising including memory that:
-
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 to operate as a garbage collector that collects at least a generation of a garbage-collected heap in the memory in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector; i) locates references, denominated external references, that are located outside the generation but refer to objects in the collection set; ii) locates references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are inside the collection set; iii) evacuates from the collection set objects referred to by references thereby found, each such collection-set object being evacuated only after the garbage collector has located both the external and the external references; and iv) reclaims the collection set.
-
-
14. 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 collects at least a generation of a garbage-collected heap in the memory in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector:
-
A) locates references, denominated external references, that are located outside the generation but refer to objects in the collection set; B) locates references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are inside the collection set; C) evacuates from the collection set objects referred to by references thereby found, each such collection-set object being evacuated only after the garbage collector has located both the external and the external references; and D) reclaims the collection set.
-
-
15. For collecting at least a generation of a garbage-collected heap in a computer system'"'"'s memory in collection increments with each of which a garbage collector associates respective collection set in the generation, the garbage collector comprising:
-
A) means for locating references, denominated external references, that are located outside the generation but refer to objects in the collection set; B) means for locating references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are inside the collection set; C) means for evacuating from the collection set objects referred to by references thereby found, each such collection-set object being evacuated only after the garbage collector has located both the external and the external references; and D) means for reclaiming the collection set.
-
Specification