Eliminating write barriers for young objects
View Patent ↗In a computer system that uses a generational garbage collector in which objects are promoted from a “young” generation to an “old” generation, a compiler output designates certain dynamic-allocation instructions as being ones whose resultant allocated objects will be considered “pinned.” The compiler associates with such allocation instructions respective segments of the code following the instructions and objects allocated within one of those segments are considered to remain pinned until program execution passes beyond that segment. The garbage collector refrains from promoting any pinned object, and as a consequence, an instruction that writes a reference into an object field while that object is pinned does not need to be accompanied by a write barrier.
1. A source-instruction executor that, in response to source code that specifies operation of a mutator that includes at least one dynamic allocation in a heap of an object that includes a reference field:
A) runs the mutator and a garbage collector that so manages the heap as to organize it into a young generation and an old generation and relies on results of write-barrier execution to keep track of references located in the old generation but not to keep track of those located in the young generation;
B) chooses at least one said dynamic allocation to be an allocation of an initially pinned object;
C) causes the allocation of the initially pinned object to occur in the young generation;
D) assigns a respective unpinning point in the mutator to at least one said allocation of an initially pinned object;
E) causes a source-code-specified write operation to a reference field of an initially pinned object to be performed without a write barrier if that write operation occurs before the unpinning point assigned to that initially pinned object's allocation;
F) causes a source-code-specified write operation to a reference field of an initially pinned object to be performed with a write barrier if that operation occurs after the unpinning point assigned to that initially pinned object's allocation; and
G) causes the garbage collector to promote an initially pinned object from the young generation to the old generation if and only if that initially pinned object meets promotion criteria that include the mutator's having reached the unpinning point assigned to that initially pinned object's allocation.
2. A source-code executor as defined in claim 1 wherein:
A) the mutator places in a pin-indicator field of the initially pinned object an indication of its pinned condition when it is allocated and removes that indication when the mutator reaches the unpinning point assigned to that object's allocation; and
B) the garbage collector determines whether the mutator has reached the unpinning point assigned to the initially pinned object's allocation by reading the contents of the object's pin-indicator field.
3. A source-code executor as defined in claim 2 wherein, when an object is not pinned, the garbage collector uses the pin-indicator field as an age field to indicate how many garbage-collection cycles the object has survived.
4. A source-code executor as defined in claim 1 wherein:
A) the source-code executor generates, for respective collection points in the mutator, stack maps containing pin-indicator entries, associated with respective references, that indicate whether the objects to which the references refer are pinned at the collection points for which the stack maps were generated; and
B) the garbage collector uses the pin-indicator entries associated with references to the initially pinned object to determine whether the mutator has reached the unpinning point assigned to the initially pinned object's allocation.
5. A source-code executor as defined in claim 1 wherein the source-code executor bases a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the amount of memory allocated to pinned objects within some portion of the mutator that includes that allocation.
6. A source-code executor as defined in claim 1 wherein the source-code executor bases a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the number of times a write operation to a reference field in the object occurs in some portion of the mutator that follows that allocation.
7. A source-code executor as defined in claim 6 wherein the source-code executor bases a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the amount of memory allocated to pinned objects within some portion of the mutator that includes that allocation.
8. A source-code executor as defined in claim 1 wherein:
A) the mutator includes mutator methods that call other mutator methods; and
B) to determine whether the object allocated by at least one allocation in one such mutator method will be initially pinned, the source-code executor traverses the call graph of mutator methods called by that mutator method and computes the amount of memory potentially allocated to pinned objects by the mutator methods thus encountered.
9. For executing a mutator that dynamically allocates in a heap objects that include reference fields, a method including:
A) running the mutator and a garbage collector that so manages the heap as to organize it into a young generation and an old generation and relies on results of write-barrier execution to keep track of references located in the old generation but not to keep track of those located in the young generation;
B) choosing at least one said dynamic allocation to be an allocation of an initially pinned object;
C) allocating the initially pinned object in the young generation;
D) assigning a respective unpinning point in the mutator's execution to at least one said initially pinned object;
E) performing a source-code-specified write operation to a reference field of an initially pinned object without a write barrier if that write operation occurs before that initially pinned object's unpinning point;
F) performing a source-code-specified write operation to a reference field of an initially pinned object with a write barrier if that operation occurs after the unpinning point assigned to that initially pinned object's allocation; and
G) causing the garbage collector to promote an initially pinned object from the young generation to the old generation if and only if that initially pinned object meets promotion criteria that include the mutator's having reached the unpinning point assigned that initially pinned object's allocation.
10. A method as defined in claim 9 wherein:
A) the mutator places in a pin-indicator field of the initially pinned object an indication of its pinned condition when it is allocated and removes that indication when the mutator reaches the unpinning point assigned to that object's allocation; and
B) the garbage collector determines whether the mutator has reached the unpinning point assigned to the initially pinned object's allocation by reading the contents of the object's pin-indicator field.
11. A method as defined in claim 10 wherein, when an object is not pinned, the garbage collector uses the pin-indicator field as an age field to indicate how many garbage-collection cycles the object has survived.
12. A method as defined in claim 9 wherein:
A) the method further includes generating, for respective collection points in the mutator, stack maps containing pin-indicator entries, associated with respective references, that indicate whether the objects to which the references refer are pinned at the collection points for which the stack maps were generated; and
B) the garbage collector uses the pin-indicator entries associated with references to the initially pinned object to determine whether the mutator has reached the unpinning point assigned to the initially pinned object's allocation.
13. A method as defined in claim 9 that further includes basing a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the amount of memory allocated to pinned objects within some portion of the mutator that includes that allocation.
14. A method as defined in claim 9 that further includes basing a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the number of times a write operation to a reference field in the object occurs in some portion of the mutator that follows that allocation.
15. A method as defined in claim 14 that further includes basing a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the amount of memory allocated to pinned objects within some portion of the mutator that includes that allocation.
16. A method as defined in claim 9 wherein:
A) the mutator includes mutator methods that call other mutator methods; and
B) the method includes traversing, to determine whether the object allocated by at least one allocation in one such mutator method will be initially pinned, the call graph of mutator methods called by that mutator method and computes the amount of memory potentially allocated to pinned objects by the mutator methods thus encountered.
17. A storage medium containing instructions readable by a computer to configure the computer to operate as a source-instruction executor that, in response to source code that specifies operation of a mutator that includes at least one dynamic allocation in a heap of an object that includes a reference field: A) runs the mutator and a garbage collector that so manages the heap as to organize it into a young generation and an old generation and relies on results of write-barrier execution to keep track of references located in the old generation but not to keep track of those located in the young generation; B) chooses at least one said dynamic allocation to be an allocation of an initially pinned object; C) causes the allocation of the initially pinned object to occur in the young generation; D) assigns a respective unpinning point in the mutator to at least one said allocation of an initially pinned object; E) causes a source-code-specified write operation to a reference field of an initially pinned object to be performed without a write barrier if that write operation occurs before the unpinning point assigned to that initially pinned object's allocation; F) causes a source-code-specified write operation to a reference field of an initially pinned object to be performed with a write barrier if that operation occurs after the unpinning point assigned to that initially pinned object's allocation; and G) causes the garbage collector to promote an initially pinned object from the young generation to the old generation if and only if that initially pinned object meets promotion criteria that include the mutator's having reached the unpinning point assigned to that initially pinned object's allocation.
18. A storage medium as defined in claim 17 wherein:
A) the mutator places in a pin-indicator field of the initially pinned object an indication of its pinned condition when it is allocated and removes that indication when the mutator reaches the unpinning point assigned to that object's allocation; and
B) the garbage collector determines whether the mutator has reached the unpinning point assigned to the initially pinned object's allocation by reading the contents of the object's pin-indicator field.
19. A storage medium as defined in claim 18 wherein, when an object is not pinned, the garbage collector uses the pin-indicator field as an age field to indicate how many garbage-collection cycles the object has survived.
20. A storage medium as defined in claim 17 wherein:
A) the source-code executor generates, for respective collection points in the mutator, stack maps containing pin-indicator entries, associated with respective references, that indicate whether the objects to which the references refer are pinned at the collection points for which the stack maps were generated; and
B) the garbage collector uses the pin-indicator entries associated with references to the initially pinned object to determine whether the mutator has reached the unpinning point assigned to the initially pinned object's allocation.
21. A storage medium as defined in claim 17 wherein the source-code executor bases a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the amount of memory allocated to pinned objects within some portion of the mutator that includes that allocation.
22. A storage medium as defined in claim 17 wherein the source-code executor bases a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the number of times a write operation to a reference field in the object occurs in some portion of the mutator that follows that allocation.
23. A storage medium as defined in claim 22 wherein the source-code executor bases a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the amount of memory allocated to pinned objects within some portion of the mutator that includes that allocation.
24. A storage medium as defined in claim 17 wherein:
A) the mutator includes mutator methods that call other mutator methods; and
B) to determine whether the object allocated by at least one allocation in one such mutator method will be initially pinned, the source-code executor traverses the call graph of mutator methods called by that mutator method and computes the amount of memory potentially allocated to pinned objects by the mutator methods thus encountered.
25. A computer readable medium storing sequences of instructions that, when executed by a processor, cause it to operate as a source-instruction executor that, in response to source code that specifies operation of a mutator that includes at least one dynamic allocation in a heap of an object that includes a reference field:
A) runs the mutator and a garbage collector that so manages the heap as to organize it into a young generation and an old generation and relies on results of write-barrier execution to keep track of references located in the old generation but not to keep track of those located in the young generation;
B) chooses at least one said dynamic allocation to be an allocation of an initially pinned object;
C) causes the allocation of the initially pinned object to occur in the young generation;
D) assigns a respective unpinning point in the mutator to at least one said allocation of an initially pinned object;
E) causes a source-code-specified write operation to a reference field of an initially pinned object to be performed without a write barrier if that write operation occurs before the unpinning point assigned to that initially pinned object's allocation;
F) causes a source-code-specified write operation to a reference field of an initially pinned object to be performed with a write barrier if that operation occurs after the unpinning point assigned to that initially pinned object's allocation; and
G) causes the garbage collector to promote an initially pinned object from the young generation to the old generation if and only if that initially pinned object meets promotion criteria that include the mutator's having reached the unpinning point assigned to that initially pinned object's allocation.
26. A computer readable medium storing as defined in claim 25 wherein:
A) the mutator places in a pin-indicator field of the initially pinned object an indication of its pinned condition when it is allocated and removes that indication when the mutator reaches the unpinning point assigned to that object's allocation; and
B) the garbage collector determines whether the mutator has reached the unpinning point assigned to the initially pinned object's allocation by reading the contents of the object's pin-indicator field.
27. A computer readable medium storing as defined in claim 26 wherein, when an object is not pinned, the garbage collector uses the pin-indicator field as an age field to indicate how many garbage-collection cycles the object has survived.
28. A computer readable medium storing as defined in claim 25 wherein:
A) the source-code executor generates, for respective collection points in the mutator, stack maps containing pin-indicator entries, associated with respective references, that indicate whether the objects to which the references refer are pinned at the collection points for which the stack maps were generated; and
B) the garbage collector uses the pin-indicator entries associated with references to the initially pinned object to determine whether the mutator has reached the unpinning point assigned to the initially pinned object's allocation.
29. A computer readable medium storing as defined in claim 25 wherein the source-code executor bases a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the amount of memory allocated to pinned objects within some portion of the mutator that includes that allocation.
30. A computer readable medium storing as defined in claim 25 wherein the source-code executor bases a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the number of times a write operation to a reference field in the object occurs in some portion of the mutator that follows that allocation.
31. A computer readable medium storing as defined in claim 30 wherein the source-code executor bases a determination of whether an object allocated by an allocation in the mutator will be initially pinned on a function of the amount of memory allocated to pinned objects within some portion of the mutator that includes that allocation.
32. A computer readable medium storing as defined in claim 25 wherein:
A) the mutator includes mutator methods that call other mutator methods; and
B) to determine whether the object allocated by at least one allocation in one such mutator method will be initially pinned, the source-code executor traverses the call graph of mutator methods called by that mutator method and computes the amount of memory potentially allocated to pinned objects by the mutator methods thus encountered.
33. A source-instruction executor implemented on a memory of a computer that receives source code that specifies operation of a mutator that includes at least one dynamic allocation in a heap of an object that includes a reference field, the source-instruction executor including:
A) means for running the mutator and a garbage collector that so manages the heap as to organize it into a young generation and an old generation and relies on results of write-barrier execution to keep track of references located in the old generation but not to keep track of those located in the young generation;
B) means for choosing at least one said dynamic allocation to be an allocation of an initially pinned object;
C) means for causing the allocation of the initially pinned object to occur in the young generation;
D) means for assigning a respective unpinning point in the mutator to at least one said allocation of an initially pinned object;
E) means for causing a source-code-specified write operation to a reference field of an initially pinned object to be performed without a write barrier if that write operation occurs before the unpinning point assigned to that initially pinned object's allocation;
F) means for causing a source-code-specified write operation to a reference field of an initially pinned object to be performed with a write barrier if that operation occurs after the unpinning point assigned to that initially pinned object's allocation; and
G) means for causing the garbage collector to promote an initially pinned object from the young generation to the old generation if and only if that initially pinned object meets promotion criteria that include the mutator's having reached the unpinning point assigned to that initially pinned object's allocation.