Combining write-barriers within an inner loop with fixed step

• US 20040187102A1
• Filed: 03/21/2003
• Published: 09/23/2004
• Est. Priority Date: 03/21/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Granted Patent: US 7,225,439 B2
• Time in Patent Office: Days
• US Class Current: 717/160
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

The present invention provides a technique for reducing the number of write barriers executed in mutator code without compromising garbage collector performance. To that end, when mutator instructions located within an inner-most nested loop (“inner loop”) modify references stored in one or more arrays, a compiler defers emitting write barriers corresponding to the reference modifications until after the inner loop is emitted. By deferring emission of write barriers, the mutator may execute a write barrier for each card spanned by the array instead of executing a typically larger number of write barriers corresponding to each reference modification made in an array. Thus, the invention enables the compiler to reduce the amount of write-barrier overhead performed by the mutator, consequently enabling the mutator to execute faster and more efficiently.

Claims

1. For employing a computer to compile source code that specifies operation of a mutator, which includes a loop including at least one reference-modifying instruction that modifies a reference stored in an array of references, into object code for execution by a computer system, which includes a memory of which at least a portion is logically partitioned into cards, 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, a method comprising:

(A) determining whether execution of the loop included in the mutator would result in modifications, by the least one reference-modifying instruction included in the loop, of at least one reference stored in the array of references within each card spanned by the array of references;

(B) deferring, in response to determining that execution of the loop would result in at least one reference stored in the array of references being modified within each card spanned by the array of references, emission of write-barrier code corresponding to the reference modifications made to the references contained in the array of references;

(C) emitting write-barrier code that executes subsequent to the execution of the object code implementing the loop, the write-barrier code executing a write barrier corresponding to each card spanned by the array of references; and

(D) providing, in response to determining that execution of the loop would result in at least one reference stored in the array of references being modified within each card spanned by the array of references, a data structure containing an indication of a location that stores the memory address of the array of references, the data structure being accessible to the collector.

2. The method according to claim 1, wherein the step of providing further includes:

generating at least one bitmap having a bit that is mapped to a memory location associated with the array of references, where the bit is assigned a value that indicates to the garbage collector that the array of references is modified by the at least one reference-modifying instruction in the loop.

3. The method according to claim 1, further comprising:

emitting code that stores an initial loop-index value in a slot of a stack frame associated with a method containing the loop.

4. The method according to claim 2, wherein the step of generating at least one bitmap further comprises:

generating a current index bitmap and a previous index bitmap for each possible safe point in the loop, where both generated bitmaps include a bit that is mapped to a memory location associated with the array of references.

5. The method according to claim 4, wherein in the current index bitmap, the bit mapped to the memory location associated with the array of references is assigned a first value if the array of references is modified before the loop reaches the possible safe point corresponding to the current index bitmap, otherwise the bit is assigned a second value.

6. The method according to claim 4, wherein in the previous index bitmap, the bit mapped to the memory location associated with the array of references is assigned a first value if the array of references is not modified before the loop reaches the possible safe point corresponding to the previous index bitmap, otherwise the bit is assigned a second value.

7. The method according to claim 1, wherein the loop is an inner loop.