Method and apparatus for optimizing the assignment of hash values to nodes residing in a garbage collected heap

• US 5,911,144 A
• Filed: 04/23/1997
• Issued: 06/08/1999
• 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., Ungar, David M.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/842,140
• Time in Patent Office: 776 Days
• Field of Search: 707/206
• 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 generate a hash value for a node allocated from a generational garbage collected heap. The heap is associated with a global hash offset that is updated on every scavenge operation. This global hash offset is added to the address of the node to generate a hash offset. The hash offset is only generated upon a generate hash condition. The generate hash condition occurs when the hash value for the node is accessed or when the node is copied from the creation area. Thus, the invention generates hash values for nodes that require them while in the creation area of the heap. When the active nodes are copied from the creation area of the heap the hash value is generated as part of the copy process without additional memory accesses.

Claims

1. A computer controlled method for generating a hash value for a node allocated from a generational garbage collected heap associated with a global hash offset, wherein said method comprises steps of:

(a) allocating said node within a creation area, said node having a node address;

(b) invoking a generate hash condition; and

(c) determining said hash value from said global hash offset and said node address.

2. The computer controlled method of claim 1 wherein step (c) comprises returning the sum of said node address and said global hash offset as said hash value for said node.

3. The computer controlled method of claim 2 wherein said node is an instantiated object and step (b) comprises invoking an object oriented method for obtaining said hash value.

4. The computer controlled method of claim 2 wherein step (b) comprises copying said node from said creation area.

5. The computer controlled method of claim 4 wherein step (c) further comprises updating said global hash offset.

6. A computer system having a central processing unit (CPU) and a memory coupled to said CPU, for generating a hash value for a node allocated from a generational garbage collected heap associated with a global hash offset, said system comprising:

a node allocation mechanism configured to allocate said node within a creation area, said node having a node address;

a hash condition invocation mechanism configured to invoke a generate hash condition; and

a hash value determination mechanism configured to determine said hash value from said global hash offset and said node address upon invocation of the generate hash condition.

7. The computer system of claim 6 wherein the hash value determination mechanism further comprises a return mechanism configured to return the sum of said node address and said global hash offset as said hash value for said node.

8. The computer system of claim 7 wherein said node is an instantiated object and the hash condition invocation mechanism further comprises an object oriented mechanism for obtaining said hash value.

9. The computer system of claim 7 wherein the hash condition invocation mechanism further comprises a copy mechanism configured to copy said node from said creation area.

10. The computer system of claim 9 wherein the hash value determination mechanism further comprises an update mechanism configured to update said global hash offset.

11. An apparatus having a central processing unit (CPU) and a memory coupled to said CPU, for generating a hash value for a node allocated from a generational garbage collected heap associated with a global hash offset, said apparatus comprising:

a node allocation mechanism configured to allocate said node within a creation area, said node having a node address;

a hash condition invocation mechanism configured to invoke a generate hash condition; and

a hash value determination mechanism configured to determine said hash value from said global hash offset and said node address upon invocation of the generate hash condition.

12. The apparatus of claim 11 wherein the hash value determination mechanism further comprises a return mechanism configured to return the sum of said node address and said global hash offset as said hash value for said node.

13. The apparatus of claim 12 wherein said node is an instantiated object and the hash condition invocation mechanism further comprises an object oriented mechanism for obtaining said hash value.

14. The apparatus of claim 12 wherein the hash condition invocation mechanism further comprises a copy mechanism configured to copy said node from said creation area.

15. The apparatus of claim 14 wherein the hash value determination mechanism further comprises an update mechanism configured to update said global hash offset.

16. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for generating a hash value for a node allocated from a generational garbage collected heap associated with a global hash offset, said computer readable code comprising;

computer readable program code devices configured to cause said computer to effect a node allocation mechanism configured to allocate said node within a creation area, said node having a node address;

computer readable program code devices configured to cause said computer to effect a hash condition invocation mechanism configured to invoke a generate hash condition; and

computer readable program code devices configured to cause said computer to effect a hash value determination mechanism configured to determine said hash value from said global hash offset and said node address upon invocation of the generate hash condition.

17. The computer program product of claim 16 wherein said hash value determination mechanism further comprises computer readable program code devices configured to cause said computer to effect a return mechanism configured to return the sum of said node address and said global hash offset as said hash value for said node.

18. The computer program product of claim 17 wherein said node is an instantiated object and the hash condition invocation mechanism further comprises computer readable program code devices configured as an object oriented mechanism to cause said computer to obtain said hash value.

19. The computer program product of claim 17 wherein the hash condition invocation mechanism further comprises computer readable program code devices configured to cause said computer to effect a copy mechanism configured to copy said node from said creation area.

20. The computer program product of claim 19 wherein the hash value determination mechanism further comprises computer readable program code devices configured to cause said computer to effect an update mechanism configured to update said global hash offset.