Method and apparatus for decreasing object copying by a generational, copying garbage collector

• US 20070174370A1
• Filed: 01/12/2006
• Published: 07/26/2007
• Est. Priority Date: 01/12/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Printezis, Antonios, Detlefs, David, Heller, Steven
• Granted Patent: US 7,599,973 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection

Abstract

In a generational, copying garbage collector, young generation collection may be made more efficient by dynamically measuring object survival rates as a function of “fine-grained” allocation age, and choosing, on the basis of these survival rates, part of the young generation that will be not be collected, but instead scanned for pointers to objects in the rest of the young generation. The rest of the young generation, including objects referenced by the pointers, is then collected.

Claims

1. A method for decreasing object copying during a garbage collection cycle by a generational, copying garbage collector operating in the memory of a computer system, wherein space is allocated in a plurality of memory regions in an allocation age sequence to form a young generation that the garbage collector collects during the collection cycle, the method comprising:

(a) dividing the sequence into a first set of regions and a second set of regions based on object survival rates as a function of allocation age;

(b) scanning objects in the first set of regions for pointers into the second set of regions and exempting the first set of regions from collection; and

(c) collecting regions in the second set of regions.

2. The method of claim 1 wherein step (b) comprises scanning all objects in the first set of regions for pointers into the second set of regions.

3. The method of claim 1 wherein step (b) comprises scanning root objects to locate reachable objects in the first set of regions and then scanning only the reachable objects for pointers into the second set of regions.

4. The method of claim 1 wherein step (c) comprises measuring object survival rates by counting the number of bytes copied during collection.

5. The method of claim 4 wherein step (c) comprises measuring object survival rates by using a portion of an object address to index a data structure representing heap regions in order to determine from which heap region bytes were collected.

6. The method of claim 1 further comprising:

(d) after each collection cycle, determining the number of regions in the first set of regions by calculating a garbage collection efficiency for a range of numbers of regions and then selecting a number of regions that produces a highest garbage collection efficiency.

7. The method of claim 1 further comprising:

(d) using a conventional technique to identify allocation sites whose objects are likely to be short-lived, allocating the short-lived objects in a third set of regions that are collected during the collection interval and applying steps (a)-(c) to the remaining allocation regions.

8. The method of claim 7 wherein the conventional technique is static escape analysis.

9. The method of claim 7 wherein the conventional technique is pre-tenuring.

10. Apparatus for decreasing object copying during a garbage collection cycle by a generational, copying garbage collector operating in the memory of a computer system, wherein space is allocated in a plurality of memory regions in an allocation age sequence to form a young generation that the garbage collector collects during the collection cycle, the apparatus comprising:

a mechanism that divides the sequence into a first set of regions and a second set of regions based on object survival rates as a function of allocation age;

a mechanism that scans objects in the first set of regions for pointers into the second set of regions and exempts the first set of regions from collection;

a collector that collects regions in the second set of regions.

11. The apparatus of claim 10 wherein the mechanism that scans objects in the first set of regions comprises a mechanism that scans all objects in the first set of regions for pointers into the second set of regions.

12. The apparatus of claim 10 wherein the mechanism that scans objects in the first set of regions comprises a mechanism that scans root objects to locate reachable objects in the first set of regions and then scans only the reachable objects for pointers into the second set of regions.

13. The apparatus of claim 10 wherein the collector comprises a mechanism that measures object survival rates by counting the number of bytes copied during collection.

14. The apparatus of claim 13 wherein the mechanism that measures object survival rates comprises a mechanism that measures object survival rates by using a portion of an object address to index a data structure representing heap regions in order to determine from which heap region bytes were collected.

15. The apparatus of claim 10 further comprising a mechanism, operable after each collection cycle, which determines the number of regions in the first set of regions by calculating a garbage collection efficiency for a range of numbers of regions and then selecting a number of regions that produces a highest garbage collection efficiency.

16. The apparatus of claim 10 further comprising a mechanism that identifies allocation sites whose objects are likely to be short-lived, allocates the short-lived objects in a third set of regions that are collected during the collection interval and wherein the mechanism that divides the sequence into a first set of regions and a second set of regions, the mechanism that scans objects in the first set of regions and the collector process the remaining allocation regions.

17. The apparatus of claim 16 wherein the mechanism that identifies allocation sites whose objects are likely to be short-lived uses static escape analysis.

18. The apparatus of claim 16 wherein the mechanism that identifies allocation sites whose objects are likely to be short-lived uses pre-tenuring.

19. Apparatus for decreasing object copying during a garbage collection cycle by a generational, copying garbage collector operating in the memory of a computer system, wherein space is allocated in a plurality of memory regions in an allocation age sequence to form a young generation that the garbage collector collects during the collection cycle, the apparatus comprising:

means for dividing the sequence into a first set of regions and a second set of regions based on object survival rates as a function of allocation age;

means for scanning objects in the first set of regions for pointers into the second set of regions and exempting the first set of regions from collection; and

means for collecting regions in the second set of regions.

20. The apparatus of claim 19 wherein the means for collecting comprises means for measuring object survival rates by counting the number of bytes copied during collection.