Method and apparatus for localizing nodes in a garbage collected carded heap

• US 6,038,572 A
• Filed: 04/23/1997
• Issued: 03/14/2000
• Est. Priority Date: 04/23/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Schwartz, David C., Knippel, Ross C.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US08/842,070
• Time in Patent Office: 1,056 Days
• Field of Search: 707/1-206, 364/280.2, 395/561, 395/652, 395/830, 395/843, 395/848, 711/147
• 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 describing processes that optimize generational garbage collection techniques in a card-marked heap. The invention localizes nodes in an older generation that have a pointer to a newer generation. This node localization increases the density of such nodes in the cards marked as having these nodes and thus reduces the number of marked cards that need to be examined for nodes having pointers to the newer generation.

Claims

1. A computer controlled method for localizing a first plurality of nodes in a card-marked older generation heap area, each of said first plurality of nodes containing a pointer to an address in a younger generation heap area, said card-marked older generation heap area having an intermixed plurality of nodes of said first plurality of nodes with a second plurality of remaining nodes, wherein said method comprises steps of:

(a) collecting said first plurality of nodes to a card-marked copied generation; and

(b) collecting said second plurality of remaining nodes to said card-marked copied generation.

2. The computer controlled method of claim 1 wherein step (a) comprises steps of:

(a1) iterating over said intermixed plurality of nodes;

(a2) remembering said second plurality of remaining nodes; and

(a3) copying each of said first plurality of nodes to said card-marked copied generation.

3. The computer controlled method of claim 2 wherein step (b) comprises steps of:

(b1) iterating over said second plurality of remaining nodes; and

(b2) copying each of said second plurality of remaining nodes to said card-marked copied generation.

4. The computer controlled method of claim 2 wherein step (a) further comprises marking a card marker in said card-marked copied generation.

5. A computer controlled system having a central processing unit (CPU) and a memory coupled to said CPU, for localizing a first plurality of nodes in a card-marked older generation heap area of said memory, each of said first plurality of nodes containing a pointer to an address in a younger generation heap area of said memory, said card-marked older generation heap area having an intermixed plurality of nodes of said first plurality of nodes with a second plurality of remaining nodes, wherein said system comprises:

a first collection mechanism configured to collect said first plurality of nodes to a card-marked copied generation in said memory; and

a second collection mechanism configured to collect said second plurality of remaining nodes to said card-marked copied generation.

6. The computer controlled system of claim 5 wherein the first collection mechanism comprises:

a first iteration mechanism configured to iterate over said intermixed plurality of nodes;

a storage mechanism configured to remember said second plurality of remaining nodes; and

a first copy mechanism configured to copy each of said first plurality of nodes to said card-marked copied generation.

7. The computer controlled system of claim 6 wherein the second collection mechanism comprises:

a second iteration mechanism configured to iterate over said second plurality of remaining nodes; and

a second copy mechanism configured to copy each of said second plurality of remaining nodes to said card-marked copied generation.

8. The computer controlled system of claim 6 wherein the first collection mechanism further comprises a card marking mechanism configured to mark a card marker in said card-marked copied generation.

9. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU for localizing a first plurality of nodes in a card-marked older generation heap area of said memory, each of said first plurality of nodes containing a pointer to an address in a younger generation heap area of said memory, said card-marked older generation heap area having an intermixed plurality of nodes of said first plurality of nodes with a second plurality of remaining nodes, wherein said system comprises:

a first collection mechanism configured to collect said first plurality of nodes to a card-marked copied generation in said memory; and

a second collection mechanism configured to collect said second plurality of remaining nodes to said card-marked copied generation.

10. The apparatus of claim 9 wherein the first collection mechanism comprises:

a first iteration mechanism configured to iterate over said intermixed plurality of nodes;

a storage mechanism configured to remember said second plurality of remaining nodes; and

a first copy mechanism configured to copy each of said first plurality of nodes to said card-marked copied generation.

11. The apparatus of claim 10 wherein the second collection mechanism comprises:

a second iteration mechanism configured to iterate over said second plurality of remaining nodes; and

a second copy mechanism configured to copy each of said second plurality of remaining nodes to said card-marked copied generation.

12. The apparatus of claim 10 wherein the first collection mechanism further comprises a card marking mechanism configured to mark a card marker in said card-marked copied generation.

13. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer to locate a first plurality of nodes in a card-marked older generation heap area, each of said first plurality of nodes containing a pointer to an address in a younger generation heap area, said card-marked older generation heap area having an intermixed plurality of nodes of said first plurality of nodes with a second plurality of remaining nodes, said computer readable code comprising;

computer readable program code devices configured to cause said computer to effect a first collection mechanism configured to collect said first plurality of nodes to a card-marked copied generation; and

computer readable program code devices configured to cause said computer to effect a second collection mechanism configured to collect said second plurality of remaining nodes to said card-marked copied generation.

14. The computer program product of claim 13 wherein the first collection mechanism comprises:

computer readable program code devices configured to cause said computer to effect a first iteration mechanism configured to iterate over said intermixed plurality of nodes;

computer readable program code devices configured to cause said computer to effect a storage mechanism configured to remember said second plurality of remaining nodes; and

computer readable program code devices configured to cause said computer to effect a first copy mechanism configured to copy each of said first plurality of nodes to said card-marked copied generation.

15. The computer program product of claim 14 wherein the second collection mechanism comprises:

computer readable program code devices configured to cause said computer to effect a second iteration mechanism configured to iterate over said second plurality of remaining nodes; and

computer readable program code devices configured to cause said computer to effect a second copy mechanism configured to copy each of said second plurality of remaining nodes to said card-marked copied generation.

16. The computer program product of claim 14 wherein the first collection mechanism further comprises computer readable program code devices configured to cause said computer to effect a card marking mechanism configured to mark a card marker in said card-marked copied generation.