Method and apparatus for optimizing exact garbage collection of array nodes in a carded heap

• US 5,903,900 A
• Filed: 04/23/1997
• Issued: 05/11/1999
• Est. Priority Date: 04/23/1997
• Status: Expired due to Term

• Current Assignee: DSM B.V., Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Beylin, Boris, Knippel, Ross C.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/842,139
• Time in Patent Office: 748 Days
• Field of Search: 707/206, 707/103, 711/170, 711/171
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Apparatus, methods, systems and computer program products are disclosed that optimize a programmed loop that stores pointer variables in an array in a card-marked heap. These methods also optimize garbage collection operations on these pointer variables. Instead of implementing a write-barrier in the body of a programmed loop, the loop is parameterized. This parameterization is associated with the pointer array stored in the heap. This parameterization specifies the first and last modified elements in the array. It further specifies the stride (which indicates how many elements are skipped to reach the next modified element of the array). The parameterization is modified by successive loops that access the array. During a garbage collection operation, the array'"'"'s parameterization is used to optimize the process of locating modified elements in the array.

Claims

1. A computer controlled method for optimizing a garbage collection operation on a plurality of pointer values in a pointer array in a card-marked heap, said pointer array having a plurality of elements, wherein said method comprises steps of:

(a) parameterizing said pointer array dependent on a programmed loop operation resulting in a pointer data parameterization specifying a pattern of pointer assignments associated with said pointer array;

(b) storing, within said programmed loop operation, said plurality of pointer values into said plurality of elements without marking said card-marked heap within said programmed loop operation; and

(c) optimizing said garbage collection operation on said plurality of elements dependent on said pointer data parameterization.

2. The computer controlled method of claim 1 wherein said pointer data parameterization comprises a first changed element index specifying a first modified element in said pointer array, a last changed element index specifying a last modified element, and a stride value.

3. The computer controlled method of claim 1 wherein said pointer data parameterization is stored in an array header within said pointer array.

4. A computer controlled method for optimizing an assignment operation within a programmed loop operation to a plurality of elements in a pointer array in a card-marked heap, wherein said method comprises steps of:

(a) parameterizing said pointer array dependent on a programmed loop operation characterized by a current pointer data parameterization and an existing pointer data parameterization associated with said pointer array resulting in a modified pointer data parameterization being associated with said pointer array; and

(b) storing, within said programmed loop operation, said plurality of pointer values into said plurality of elements without marking said card-marked heap within said programmed loop operation.

5. The computer controlled method of claim 4 wherein said existing pointer data parameterization, said current pointer data parameterization, and said modified pointer data parameterization each comprise a first changed element index specifying a first modified element in said pointer array, a last changed element index specifying a last modified element, and a stride value.

6. The computer controlled method of claim 5 wherein said existing pointer data parameterization and said modified pointer data parameterization are stored in an array header within said pointer array.

7. The computer controlled method of claim 4 further comprising disabling a garbage collection operation on said card-marked heap during step (b) and step (c).

8. The computer controlled method of claim 4 further comprising marking said pointer array in said card-marked heap.

9. The computer controlled method of claim 4 further comprising steps of:

(a) optimizing step (b), by a compiler, dependent on said current pointer data parameterization of a compile-time determinable loop and said pointer array'"'"'s upper and lower bounds.

10. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU for optimizing a garbage collection operation on a plurality of pointer values in a pointer array in a card-marked heap of said memory, said pointer array having a plurality of elements, said apparatus comprising:

a parameterization mechanism configured to parameterize said pointer array dependent on a programmed loop operation resulting in a pointer data parameterization specifying a pattern of pointer assignments associated with said pointer array;

a storage mechanism configured to store, within said programmed loop operation, said plurality of pointer values into said plurality of elements without marking said card-marked heap within said programmed loop operation; and

an optimization mechanism configured to optimize said garbage collection operation on said plurality of elements dependent on said pointer data parameterization.

11. The apparatus of claim 10 wherein said pointer data parameterization comprises a first changed element index specifying a first modified element in said pointer array, a last changed element index specifying a last modified element, and a stride value.

12. The apparatus of claim 10 wherein said pointer data parameterization is stored in an array header within said pointer array.

13. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU for optimizing an assignment operation within a programmed loop operation to a plurality of elements in a pointer array in a card-marked heap of said memory, comprising:

a parameterizing mechanism configured to parameterize said pointer array dependent on a programmed loop operation characterized by a current pointer data parameterization and an existing pointer data parameterization associated with said pointer array resulting in a modified pointer data parameterization being associated with said pointer array; and

a storage mechanism configured to store, within said programmed loop operation, said plurality of pointer values into said plurality of elements without marking said card-marked heap within said programmed loop operation.

14. The apparatus of claim 13 wherein said existing pointer data parameterization, said current pointer data parameterization, and said modified pointer data parameterization each comprise a first changed element index specifying a first modified element in said pointer array, a last changed element index specifying a last modified element, and a stride value.

15. The apparatus of claim 14 wherein said existing pointer data parameterization and said modified pointer data parameterization are stored in an array header within said pointer array.

16. The apparatus of claim 13 further comprising a disabling mechanism configured to disable a garbage collection operation on said card-marked heap during operation of the parameterizing mechanism and the storage mechanism.

17. The apparatus of claim 13 further comprising a marking mechanism configured to mark said pointer array in said card-marked heap.

18. The apparatus of claim 13 further comprising:

an optimization mechanism in a compiler configured to optimize the parameterizing mechanism, the optimization mechanism dependent on said current pointer data parameterization of a compile-time determinable loop and said pointer array'"'"'s upper and lower bounds.

19. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer to optimize a garbage collection operation on a plurality of pointer values in a pointer array in a card-marked heap of said memory, said pointer array having a plurality of elements, said computer readable code comprising;

computer readable program code devices configured to cause said computer to effect a parameterization mechanism configured to parameterize said pointer array dependent on a programmed loop operation resulting in a pointer data parameterization specifying a pattern of pointer assignments associated with said pointer array;

computer readable program code devices configured to cause said computer to effect a storage mechanism configured to store, within said programmed loop operation, said plurality of pointer values into said plurality of elements without marking said card-marked heap within said programmed loop operation; and

computer readable program code devices configured to cause said computer to effect an optimization mechanism configured to optimize said garbage collection operation on said plurality of elements dependent on said pointer data parameterization.

20. The computer program product of claim 19 wherein said pointer data parameterization comprises a first changed element index specifying a first modified element in said pointer array, a last changed element index specifying a last modified element, and a stride value.

21. The computer program product of claim 19 wherein said pointer data parameterization is stored in an array header within said pointer array.

22. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer to optimize an assignment operation within a programmed loop operation to a plurality of elements in a pointer array in a card-marked heap of said memory, said computer readable code comprising;

computer readable program code devices configured to cause said computer to effect a parameterizing mechanism configured to parameterize said pointer array dependent on a programmed loop operation characterized by a current pointer data parameterization and an existing pointer data parameterization associated with said pointer array resulting in a modified pointer data parameterization being associated with said pointer array; and

computer readable program code devices configured to cause said computer to effect a storage mechanism configured to store, within said programmed loop operation, said plurality of pointer values into said plurality of elements without marking said card-marked heap within said programmed loop operation.

23. The computer program product of claim 22 wherein said existing pointer data parameterization, said current pointer data parameterization, and said modified pointer data parameterization each comprise a first changed element index specifying a first modified element in said pointer array, a last changed element index specifying a last modified element, and a stride value.

24. The computer program product of claim 23 wherein said existing pointer data parameterization and said modified pointer data parameterization are stored in an array header within said pointer array.

25. The computer program product of claim 22 further comprising computer readable program code devices configured to cause said computer to effect a disabling mechanism configured to disable a garbage collection operation on said card-marked heap during operation of the parameterizing mechanism and the storage mechanism.

26. The computer program product of claim 22 further comprising computer readable program code devices configured to cause said computer to effect a marking mechanism configured to mark said pointer array in said card-marked heap.

27. The computer program product of claim 22 further comprising:

computer readable program code devices configured to cause said computer to effect an optimization mechanism in a compiler configured to optimize the parameterizing mechanism, the optimization mechanism dependent on said current pointer data parameterization of a compile-time determinable loop and said pointer array'"'"'s upper and lower bounds.