Dynamic feedback for determining collection-set size

• US 7,096,238 B2
• Filed: 12/06/2002
• Issued: 08/22/2006
• Est. Priority Date: 08/19/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US10/313,256
• Publication Number:
  US 20040111448A1
• Time in Patent Office: 1,355 Days
• Field of Search: 707/103.R, 707/200, 707/205, 707/206, 711/6, 711/159, 711/160, 711/165
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A garbage collector collects a generation of a dynamically allocated heap in a computer'"'"'s memory incrementally. A collection set within the generation is associated with each collection increment. The collector reclaims for reuse the memory space occupied by any collection-set object not reachable by a reference chain that extends from outside the collection set. The collector monitors the total amount of allocation that occurs within the generation between collection increments, and it bases the collection-set size on those allocation amounts.

Claims

1. For employing a computer system, which includes memory of which at least some is used as a heap for dynamic allocation, to perform garbage collection incrementally on an incrementally collected generation of the heap, a method comprising:

A) monitoring the rate of allocation within the incrementally collected generation;

B) calculating collection-set sizes from the allocation rates thus monitored; and

C) collecting the generation in increments that employ collection sets whose minimum sizes are the collection-set sizes thus determined.

2. A method as defined in claim 1 further comprising:

D) treating the heap as additionally including at least one younger generation, into which objects are allocated;

E) promoting into the incrementally collected generation from the at least one younger generation objects that meet predetermined promotion criteria.

3. A method as defined in claim 2 wherein:

F) the method further comprises allocating objects directly into the incrementally collected heap; and

G) the monitored allocation rate includes not only the rate at which objects are promoted into the incrementally collected heap but also the rate at which they are allocated into it directly.

4. A method as defined in claim 1 wherein the calculation of collection-set sizes includes determining the allocation rate from the volumes of allocation in the incrementally collected generation that occur during intervals between increments of the incrementally collected generation'"'"'s collection.

5. A method as defined in claim 4 wherein:

D) the method further includes monitoring the rate at which objects in the generation survive collection; and

E) the calculation of collection-set sizes includes calculating the collection-set sizes from the rate thus monitored as well as from the allocation rate.

6. A method as defined in claim 4 wherein:

D) the method further includes monitoring the distances through which objects are evacuated during collection; and

E) the calculation of collection-set sizes includes calculating the collection-set sizes from the distances thus monitored as well as from the allocation rate.

7. A method as defined in claim 4 wherein the calculation of a collection-set size includes determining the allocation rate from the volumes of allocation in the incrementally collected generation that occur during a plurality of previous intervals between increments of the incrementally collected generation'"'"'s collection.

8. A method as defined in claim 7 further including:

D) monitoring the rate at which objects in the generation survive collection; and

E) the calculation of collection-set sizes includes calculating the collection-set sizes from the rate thus monitored as well as from the allocation rate.

9. A computer system comprising:

A) processor circuitry operable to execute processor instructions; and

B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure it to treat at least a heap portion of the memory as a heap, in which dynamic allocation occurs, and act as a garbage collector that incrementally collects an incrementally collected generation of the heap by;

i) monitoring the rate of allocation within the incrementally collected generation;

ii) calculating collection-set sizes from the allocation rates thus monitored; and

iii) collecting the generation in increments that employ collection sets whose minimum sizes are the collection-set sizes thus determined.

10. A computer system as defined in claim 9 wherein the garbage collector:

C) treats the heap as additionally including at least one younger generation, into which objects are allocated;

D) promotes into the incrementally collected generation from the at least one younger generation objects that meet predetermined promotion criteria.

11. A computer system as defined in claim 10 wherein:

E) the garbage collector allocates objects directly into the incrementally collected heap; and

F) the monitored allocation rate includes not only the rate at which objects are promoted into the incrementally collected heap but also the rate at which they are allocated into it directly.

12. A computer system as defined in claim 9 wherein the calculation of collection-set sizes includes determining the allocation rate from the volumes of allocation in the incrementally collected generation that occur during intervals between increments of the incrementally collected generation'"'"'s collection.

13. A computer system as defined in claim 12 wherein:

C) the garbage collector monitors the rate at which objects in the generation survive collection; and

D) the calculation of collection-set sizes includes calculating the collection-set sizes from the rate thus monitored as well as from the allocation rate.

14. A computer system as defined in claim 12 wherein:

C) the garbage collector monitors the distances through which objects are evacuated during collection; and

D) the calculation of collection-set sizes includes calculating the collection-set sizes from the distances thus monitored as well as from the allocation rate.

15. A computer system as defined in claim 12 wherein the calculation of a collection-set size includes determining the allocation rate from the volumes of allocation in the incrementally collected generation that occur during a plurality of previous intervals between increments of the incrementally collected generation'"'"'s collection.

16. A computer system as defined in claim 15 wherein:

C) the garbage collector monitors the rate at which objects in the generation survive collection; and

the calculation of collection-set sizes includes calculating the collection-set sizes from the rate thus monitored as well as from the allocation rate.

17. A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to treat at least a portion of the memory as a heap, in which dynamic allocation occurs, and act as a garbage collector that incrementally collects an incrementally collected generation of the heap by:

A) monitoring the rate of allocation within the incrementally collected generation;

B) calculating collection-set sizes from the allocation rates thus monitored; and

C) collecting the generation in increments that employ collection sets whose minimum sizes are the collection-set sizes thus determined.

18. A storage medium as defined in claim 17 wherein the garbage collector:

D) treats the heap as additionally including at least one younger generation, into which objects are allocated;

E) promotes into the incrementally collected generation from the at least one younger generation objects that meet predetermined promotion criteria.

19. A storage medium as defined in claim 18 wherein:

F) the garbage collector allocates objects directly into the incrementally collected heap; and

G) the monitored allocation rate includes not only the rate at which objects are promoted into the incrementally collected heap but also the rate at which they are allocated into it directly.

20. A storage medium as defined in claim 17 wherein the calculation of collection-set sizes includes determining the allocation rate from the volumes of allocation in the incrementally collected generation that occur during intervals between increments of the incrementally collected generation'"'"'s collection.

21. A storage medium as defined in claim 20 wherein:

D) the garbage collector monitors the rate at which objects in the generation survive collection; and

E) the calculation of collection-set sizes includes calculating the collection-set sizes from the rate thus monitored as well as from the allocation rate.

22. A storage medium as defined in claim 20 wherein:

D) the garbage collector monitors the distances through which objects are evacuated during collection; and

E) the calculation of collection-set sizes includes calculating the collection-set sizes from the distances thus monitored as well as from the allocation rate.

23. A storage medium as defined in claim 20 wherein the calculation of a collection-set size includes determining the allocation rate from the volumes of allocation in the incrementally collected generation that occur during a plurality of previous intervals between increments of the incrementally collected generation'"'"'s collection.

24. A storage medium as defined in claim 23 wherein:

D) the garbage collector monitors the rate at which objects in the generation survive collection; and

E) the calculation of collection-set sizes includes calculating the collection-set sizes from the rate thus monitored as well as from the allocation rate.

25. For incrementally collecting an incrementally collected generation of a heap where dynamic allocation occurs in a computer system'"'"'s memory, a garbage collector including:

A) means for monitoring the rate of allocation within the incrementally collected generation;

B) means for calculating collection-set sizes from the allocation rates thus monitored; and

C) means for collecting the generation in increments that employ collection sets whose minimum sizes are the collection-set sizes thus determined.