Elision of write barriers for stores whose values are in close proximity
First Claim
1. For employing a computer to compile source code that specifies operation of a mutator that includes at least one reference-writing instruction into object code for execution by a computer system, which includes memory, together with a garbage collector that relies on the mutator'"'"'s execution of write-barrier code to keep track of at least some reference modifications and operates in collection increments, in each of at least some of which it collects a respective collection set by reclaiming a portion of the memory that it determines to be occupied by objects that are no longer reachable, a method comprising:
- (A) analyzing the source code to make a determination, for one of said at least one reference-writing instruction, whether that reference-writing instruction satisfies any elision criterion in a set of at least one elision criterion, where each criterion in said set of at least one elision criterion is satisfied only if execution of that reference-writing instruction will result in a heap state in which scanning the reference modified by that reference-writing instruction during any collection set'"'"'s collection will not affect the garbage collector'"'"'s ultimate determination of whether an object in that collection set is reachable; and
(B) generating object code that;
(i) directs the computer system to operate as the mutator;
(ii) includes that reference-writing instruction;
(iii) if said determination is negative, accompanies that reference-writing instruction with a write barrier that alerts the garbage collector to execution of the reference-writing instruction; and
(iv) if the result of said determination is affirmative, omits such a write barrier.
1 Assignment
0 Petitions
Accused Products
Abstract
The present invention provides a technique for reducing the number of write barriers executed in mutator code without compromising garbage collector performance or correctness. Since garbage collectors typically scan a heap (or a portion of a heap) for reachable objects during their collection intervals, most collectors do not need to be notified of reference-writing instructions unless the instructions add new reachable objects to the heap. According to the illustrative embodiment, certain compile-time tests can be performed that, if passed, guarantee that the reference modification in question will make no otherwise unreachable object reachable. One or more of these tests is performed and no write barrier is emitted by the compiler for a given reference-writing instruction if the instruction passes such a test. For example, a compiler does not emit write-barrier code corresponding to mutator instructions that write a self-reference into an object reference field or copy a reference value from one object reference field to another located in the same object or card. By excluding such unnecessary write barrier overhead, the mutator may execute faster and more efficiently.
-
Citations
8 Claims
-
1. For employing a computer to compile source code that specifies operation of a mutator that includes at least one reference-writing instruction into object code for execution by a computer system, which includes memory, together with a garbage collector that relies on the mutator'"'"'s execution of write-barrier code to keep track of at least some reference modifications and operates in collection increments, in each of at least some of which it collects a respective collection set by reclaiming a portion of the memory that it determines to be occupied by objects that are no longer reachable, a method comprising:
-
(A) analyzing the source code to make a determination, for one of said at least one reference-writing instruction, whether that reference-writing instruction satisfies any elision criterion in a set of at least one elision criterion, where each criterion in said set of at least one elision criterion is satisfied only if execution of that reference-writing instruction will result in a heap state in which scanning the reference modified by that reference-writing instruction during any collection set'"'"'s collection will not affect the garbage collector'"'"'s ultimate determination of whether an object in that collection set is reachable; and
(B) generating object code that;
(i) directs the computer system to operate as the mutator;
(ii) includes that reference-writing instruction;
(iii) if said determination is negative, accompanies that reference-writing instruction with a write barrier that alerts the garbage collector to execution of the reference-writing instruction; and
(iv) if the result of said determination is affirmative, omits such a write barrier. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
Specification