Detection of dead regions during incremental collection

• US 7,143,124 B2
• Filed: 12/06/2002
• Issued: 11/28/2006
• Est. Priority Date: 12/06/2002
• Status: Active Grant

• 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,878
• Publication Number:
  US 20040111451A1
• Time in Patent Office: 1,453 Days
• Field of Search: 707/10, 707/205, 707/206, 707100-1041, 717/140, 717/148, 717/153, 717/159, 711/6, 711/133, 711/136, 711/153, 711/159, 711/160
• 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/99957 Garbage collection

Abstract

A garbage collector employs the train algorithm to collect a heap generation incrementally, collecting “car sections” in a collection order. As it updates the “remembered sets” by which it keeps track of where references to objects in respective car sections are located, it also updates oldest- and youngest-car indicators for each car section. The oldest- and youngest-car indicators for a given car section specify limits in the collection sequence beyond which references to objects in the given car have not been found. The garbage collector uses these indicators to identify cars that contain no objects that are reachable except through a reference chain that includes the collection set for the current collection increment. It adds one or more such cars to the collection set, and it collects the thus-expanded collection set without processing the remembered sets associated with the added cars.

Claims

1. A method of performing garbage collection comprising:

A) providing a computer system that includes memory and executes a mutator that modifies references in a dynamically allocated heap in the memory;

B) configuring the computer system to act as a garbage collector that collects respective collection sets in collection increments and that;

i) treats at least a generation in the heap as divided into regions assigned a collection order from oldest to youngest;

ii) maintains for each of a plurality of the regions a respective youngest-region indicator associated therewith, the youngest-region indicator associated with a given region identifying a region such that no region younger than the region thereby identified contains a strong reference to an object in the given region; and

iii) during each of at least some collection increments;

a) performs a region search by employing the youngest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set;

b) if any such region is thereby identified, includes at least a portion of at least one such region in the collection set; and

c) reclaims space occupied by unreachable objects in the collection set;

C) employing the computer system to execute the garbage collector.

2. A method as defined in claim 1 wherein the region search identifies only cars that contain no reachable objects.

3. A method as defined in claim 1 wherein the regions identified in the region search are included in the collection in preference to regions not thus identified.

4. A method as defined in claim 1 wherein the garbage collector implements the train algorithm, treating the generation as divided into car sections grouped into trains and the regions are the car sections.

5. A method as defined in claim 1 wherein the garbage collector, in response to modifications of at least some strong-references located in the generation:

D) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

E) updates the youngest-region indicator associated with the region in which the object referred to is located if necessary to make it identify the region in which the strong reference is located if and only if the region in which the strong reference is located is younger than;

i) the region identified by that youngest-region indicator; and

ii) the region in which the object referred to is located.

6. A method as defined in claim 5 wherein, if no reference to a given region has been found in the generation outside the given region, the youngest-region indicator associated with the given region identifies the region itself.

7. A method as defined in claim 1 wherein the garbage collector, in response to modifications of at least some strong-references located in the generation:

D) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

E)updates the youngest-region indicator associated with the region in which the object referred to is located, if necessary to make it identify the region in which the strong reference is located, if the region in which the strong reference is located is younger than the region identified by that youngest-region indicator, even if the region in which the strong reference is located is not at young as the region in which the object referred to is located.

8. A method as defined in claim 7 wherein the garbage collector:

F) maintains metadata structures, associated with respective regions, that contain order information specifying the collection order, as well as a fictional-region metadata structure associate with a fictional region, which specifies that the fictional region is older than any other region;

G) maintains for each of a plurality of the regions a youngest-region indicator that is associated with that region and identifies one said region by identifying the metadata structure associated therewith; and

H) if no strong reference to any object in a given region has been found in the generation outside the given region, causes the youngest-region indicator associated with the given region to identify the fictional-region metadata structure.

9. A method as defined in claim 1 wherein:

D) the garbage collector maintains a said youngest-region indicator at least for each said region outside the collection set that is older than the oldest region that contains an object directly referred to by a strong reference located outside the generation; and

E) the region search includes;

i) marking as reachable at least the oldest region that contains an object directly referred to by a strong reference located outside the generation;

ii) marking each region outside the collection set that is older than, and whose youngest-region indicator identifies a region at least as young as, the oldest region theretofore marked reachable; and

iii) identifying as unreachable any region outside the collection set that is older than the oldest marked region and remains unmarked.

10. A method as defined in claim 1 wherein the garbage collector additionally:

D) maintains for each of a plurality of the regions a respective oldest-region indicator associated therewith, the oldest-region indicator associated with a given region identifying a region such that no region older than the region thereby identified contains a strong reference to an object in the given region; and

E) during each of at least some collection increments;

i) employs the oldest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set; and

ii) if any regions that contain no reachable objects are thereby identified, includes at least a portion of at least one such region in the collection set.

11. A method as defined in claim 10 wherein:

F) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

G) the region search includes;

i) marking as reachable each of the regions in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) processing in collection order each region in the sequence by marking that region as reachable unless its youngest-region indicator identifies no region younger than that region and its oldest region indicator identifies a region younger than the youngest older region previously marked as reachable; and

iii) identifying as unreachable any region thus processed that remains unmarked.

12. A method as defined in claim 10 wherein:

F) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

G) the region search includes;

i) marking as reachable each of the regions in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) processing in reverse collection order each region in the sequence by marking that region as reachable unless its oldest-region indicator identifies no region older than that region and its youngest-region indicator identifies a region older than the oldest younger region previously marked as reachable; and

iii) identifying as unreachable any region thus processed that remains unmarked.

13. A method as defined in claim 10 wherein:

F) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

G) the region search includes;

i) marking as reachable each region in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) marking each region in the sequence whose youngest-region indicator identifies a region at least as young as a marked younger region and each region in the plurality thereof whose oldest-region indicator identifies a region at least as old as a marked older region; and

H) identifying as unreachable any region in the sequence that remains unmarked.

14. A method as defined in claim 10 wherein:

F) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

G) the region search includes;

i) marking as reachable each region in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) associating with each region in the sequence the subsequence of regions that includes and is bordered in the collection sequence by the regions identified by that region'"'"'s oldest- and youngest-region indicators;

iii) marking each region with which the subsequence thereby associated includes a marked region; and

iv) identifying as unreachable any region in the sequence that remains unmarked.

15. A method of performing garbage collection comprising:

A) providing a computer system that includes memory and executes a mutator that modifies references in a dynamically allocated heap in the memory;

B) configuring the computer system to act as a garbage collector that collects respective collection sets in collection increments and that;

i) treats at least a generation of the heap as divided into regions assigned a collection order from oldest to youngest;

ii) maintains for each of a plurality of the regions a respective oldest-region indicator associated therewith, the oldest-region indicator associated with a given region identifying a region such that no region older than the region thereby identified contains a strong reference to an object in the given region; and

iii) during each of at least some collection increments;

a) performs a region search by employing the oldest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set;

b) if any regions that contain no reachable objects are thereby identified, includes at least a portion of at least one such region in the collection set; and

c) reclaims space occupied by unreachable objects in the collection set;

C) employing the computer system to execute the garbage collector.

16. A method as defined in claim 15 wherein the region search identifies only cars that contain no reachable objects.

17. A method as defined in claim 15 wherein the regions identified in the region search are included in the collection in preference to regions not thus identified.

18. A method as defined in claim 15 wherein the garbage collector implements the train algorithm, treating the generation as divided into car sections grouped into trains and the regions are the car sections.

19. A method as defined in claim 15 wherein the garbage collector, in response to modifications of at least some strong-references located in the generation:

D) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

E) updates the oldest-region indicator associated with the region in which the object referred to is located if necessary to make it identify the region in which the strong reference is located if and only if the region in which the strong reference is located is older than;

i)the region identified by that oldest-region indicator; and

ii)the region in which the object referred to is located.

20. A method as defined in claim 19 wherein if no reference to a given region has been found in the generation outside the given region, the oldest-region indicator associated with the given region identifies the region itself.

21. A method as defined in claim 15 wherein the garbage collector, in response to each of at least some write barriers that report strong-reference modifications:

D) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

E) updates the oldest-region indicator associated with the region in which the object referred to is located, if necessary to make it identify the region in which the strong reference is located, if the region in which the strong reference is located is older than the region identified by that oldest-region indicator, even if the region in which the strong reference is located is not at old as the region in which the object referred to is located.

22. A method as defined in claim 21 wherein the garbage collector:

F) maintains metadata structures, associated with respective regions, that contain order information specifying the collection order, as well as a fictional-region metadata structure associate with a fictional region, which specifies that the fictional region is younger than any other region;

G) maintains for each of a plurality of the regions an oldest-region indicator that is associated with that region and identifies one said region by identifying the metadata structure associated therewith; and

H) if no strong reference to any object in a given region has been found in the generation outside the given region, causes the oldest-region indicator associated with the given region to identify the fictional-region metadata structure.

23. 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 the computer system as a garbage collector that;

i) treats at least a generation of a garbage collected heap in the memory as divided into regions assigned a collection order from oldest to youngest;

ii) maintains for each of a plurality of the regions a respective youngest-region indicator associated therewith, the youngest-region indicator associated with a given region identifying a region such that no region younger than the region thereby identified contains a strong reference to an object in the given region; and

iii) during each of at least some collection increments;

a) performs a region search by employing the youngest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set;

b) if any such region is thereby identified, includes at least a portion of at least one such region in the collection set; and

C)reclaims space occupied by unreachable objects in the collection set.

24. A computer system as defined in claim 23 wherein the region search identifies only cars that contain no reachable objects.

25. A computer system as defined in claim 23 wherein the regions identified in the region search are included in the collection in preference to regions not thus identified.

26. A computer system as defined in claim 23 wherein the garbage collector implements the train algorithm, treating the generation as divided into car sections grouped into trains and the regions are the car sections.

27. A computer system as defined in claim 23 wherein the garbage collector, in response to modifications of at least some strong-references located in the generation:

D) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

E) updates the youngest-region indicator associated with the region in which the object referred to is located if necessary to make it identify the region in which the strong reference is located if and only if the region in which the strong reference is located is younger than;

i) the region identified by that youngest-region indicator; and

ii) the region in which the object referred to is located.

28. A computer system as defined in claim 27 wherein, if no reference to a given region has been found in the generation outside the given region, the youngest-region indicator associated with the given region identifies the region itself.

29. A computer system as defined in claim 23 wherein the garbage collector, in response to modifications of at least some strong-references located in the generation:

D) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

E) updates the youngest-region indicator associated with the region in which the object referred to is located, if necessary to make it identify the region in which the strong reference is located, if the region in which the strong reference is located is younger than the region identified by that youngest-region indicator, even if the region in which the strong reference is located is not at young as the region in which the object referred to is located.

30. A computer system as defined in claim 29 wherein the garbage collector:

F) maintains metadata structures, associated with respective regions, that contain order information specifying the collection order, as well as a fictional-region metadata structure associate with a fictional region, which specifies that the fictional region is older than any other region;

G) maintains for each of a plurality of the regions a youngest-region indicator that is associated with that region and identifies one said region by identifying the metadata structure associated therewith; and

H) if no strong reference to any object in a given region has been found in the generation outside the given region, causes the youngest-region indicator associated with the given region to identify the fictional-region metadata structure.

31. A computer system as defined in claim 23 wherein:

D) the garbage collector maintains a said youngest-region indicator at least for each said region outside the collection set that is older than the oldest region that contains an object directly referred to by a strong reference located outside the generation; and

E) the region search includes;

i) marking as reachable at least the oldest region that contains an object directly referred to by a strong reference located outside the generation;

ii) marking each region outside the collection set that is older than, and whose youngest-region indicator identifies a region at least as young as, the oldest region theretofore marked reachable; and

iii) identifying as unreachable any region outside the collection set that is older than the oldest marked region and remains unmarked.

32. A computer system as defined in claim 23 wherein the garbage collector additionally:

D) maintains for each of a plurality of the regions a respective oldest-region indicator associated therewith, the oldest-region indicator associated with a given region identifying a region such that no region older than the region thereby identified contains a strong reference to an object in the given region; and

E) during each of at least some collection increments;

i) employs the oldest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set; and

ii) if any regions that contain no reachable objects are thereby identified, includes at least a portion of at least one such region in the collection set.

33. A computer system as defined in claim 32 wherein:

F) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

G) the region search includes;

i) marking as reachable each of the regions in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) processing in collection order each region in the sequence by marking that region as reachable unless its youngest-region indicator identifies no region younger than that region and its oldest-region indicator identifies a region younger than the youngest older region previously marked as reachable; and

iii) identifying as unreachable any region thus processed that remains unmarked.

34. A computer system as defined in claim 32 wherein:

F) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

G) the region search includes;

i) marking as reachable each of the regions in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) processing in reverse collection order each region in the sequence by marking that region as reachable unless its oldest-region indicator identifies no region older than that region and its youngest-region indicator identifies a region older than the oldest younger region previously marked as reachable; and

iii) identifying as unreachable any region thus processed that remains unmarked.

35. A computer system as defined in claim 32 wherein:

F) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

G) the region search includes;

i) marking as reachable each region in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) marking each region in the sequence whose youngest-region indicator identifies a region at least as young as a marked younger region and each region in the plurality thereof whose oldest-region indicator identifies a region at least as old as a marked older region; and

H) identifying as unreachable any region in the sequence that remains unmarked.

36. A computer system as defined in claim 32 wherein:

F) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

G) the region search includes;

i) marking as reachable each region in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) associating with each region in the sequence the subsequence of regions that includes and is bordered in the collection sequence by the regions identified by that region'"'"'s oldest- and youngest-region indicators;

iii) marking each region with which the subsequence thereby associated includes a marked region; and

iv) identifying as unreachable any region in the sequence that remains unmarked.

37. 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 the computer system as a garbage collector that;

i) treats at least a generation of a garbage collected heap in the memory as divided into regions assigned a collection order from oldest to youngest;

ii) maintains for each of a plurality of the regions a respective oldest-region indicator associated therewith, the oldest-region indicator associated with a given region identifying a region such that no region older than the region thereby identified contains a strong reference to an object in the given region; and

iii) during each of at least some collection increments;

a) performs a region search by employing the oldest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set;

b) if any regions that contain no reachable objects are thereby identified, includes at least a portion of at least one such region in the collection set; and

C) reclaims space occupied by unreachable objects in the collection set.

38. A computer system as defined in claim 37 wherein the region search identifies only cars that contain no reachable objects.

39. A computer system as defined in claim 37 wherein the regions identified in the region search are included in the collection in preference to regions not thus identified.

40. A computer system as defined in claim 37 wherein the garbage collector implements the train algorithm, treating the generation as divided into car sections grouped into trains and the regions are the car sections.

41. A computer system as defined in claim 37 wherein the garbage collector, in response to modifications of at least some strong-references located in the generation:

D) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

E) updates the oldest-region indicator associated with the region in which the object referred to is located if necessary to make it identify the region in which the strong reference is located if and only if the region in which the strong reference is located is older than;

i)the region identified by that oldest-region indicator; and

ii)the region in which the object referred to is located.

42. A computer system as defined in claim 41 wherein if no reference to a given region has been found in the generation outside the given region, the oldest-region indicator associated with the given region identifies the region itself.

43. A computer system as defined in claim 37 wherein the garbage collector, in response to each of at least some write barriers that report strong-reference modifications:

D) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

E) updates the oldest-region indicator associated with the region in which the object referred to is located, if necessary to make it identify the region in which the strong reference is located, if the region in which the strong reference is located is older than the region identified by that oldest-region indicator, even if the region in which the strong reference is located is not at old as the region in which the object referred to is located.

44. A computer system as defined in claim 43 wherein the garbage collector:

F) maintains metadata structures, associated with respective regions, that contain order information specifying the collection order, as well as a fictional-region metadata structure associate with a fictional region, which specifies that the fictional region is younger than any other region;

G) maintains for each of a plurality of the regions an oldest-region indicator that is associated with that region and identifies one said region by identifying the metadata structure associated therewith; and

H) if no strong reference to any object in a given region has been found in the generation outside the given region, causes the oldest-region indicator associated with the given region to identify the fictional-region metadata structure.

45. A storage medium containing instructions readable by a computer system that includes memory to configure the computer to operate as a garbage collector that:

A) treats at least a generation of a garbage collected heap in the computer system'"'"'s memory as divided into regions assigned a collection order from oldest to youngest;

B) maintains for each of a plurality of the regions a respective youngest-region indicator associated therewith, the youngest-region indicator associated with a given region identifying a region such that no region younger than the region thereby identified contains a strong reference to an object in the given region; and

C) during each of at least some collection increments;

i) performs a region search by employing the youngest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set;

ii) if any such region is thereby identified, includes at least a portion of at least one such region in the collection set; and

D) reclaims space occupied by unreachable objects in the collection set.

46. A storage medium as defined in claim 45 wherein the region search identifies only cars that contain no reachable objects.

47. A storage medium as defined in claim 45 wherein the regions identified in the region search are included in the collection in preference to regions not thus identified.

48. A storage medium as defined in claim 45 wherein the garbage collector implements the train algorithm, treating the generation as divided into car sections grouped into trains and the regions are the car sections.

49. A storage medium as defined in claim 45 wherein the garbage collector, in response to modifications of at least some strong-references located in the generation:

E) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

F) updates the youngest-region indicator associated with the region in which the object referred to is located if necessary to make it identify the region in which the strong reference is located if and only if the region in which the strong reference is located is younger than;

i) the region identified by that youngest-region indicator; and

ii) the region in which the object referred to is located.

50. A storage medium as defined in claim 49 wherein, if no reference to a given region has been found in the generation outside the given region, the youngest-region indicator associated with the given region identifies the region itself.

51. A storage medium as defined in claim 45 wherein the garbage collector, in response to modifications of at least some strong-references located in the generation:

E) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

F) updates the youngest-region indicator associated with the region in which the object referred to is located, if necessary to make it identify the region in which the strong reference is located, if the region in which the strong reference is located is younger than the region identified by that youngest-region indicator, even if the region in which the strong reference is located is not at young as the region in which the object referred to is located.

52. A storage medium as defined in claim 51 wherein the garbage collector:

G) maintains metadata structures, associated with respective regions, that contain order information specifying the collection order, as well as a fictional-region metadata structure associate with a fictional region, which specifies that the fictional region is older than any other region;

H) maintains for each of a plurality of the regions a youngest-region indicator that is associated with that region and identifies one said region by identifying the metadata structure associated therewith; and

I) if no strong reference to any object in a given region has been found in the generation outside the given region, causes the youngest-region indicator associated with the given region to identify the fictional-region metadata structure.

53. A storage medium as defined in claim 45 wherein:

E) the garbage collector maintains a said youngest-region indicator at least for each said region outside the collection set that is older than the oldest region that contains an object directly referred to by a strong reference located outside the generation; and

F) the region search includes;

i) marking as reachable at least the oldest region that contains an object directly referred to by a strong reference located outside the generation;

ii) marking each region outside the collection set that is older than, and whose youngest-region indicator identifies a region at least as young as, the oldest region theretofore marked reachable; and

iii) identifying as unreachable any region outside the collection set that is older than the oldest marked region and remains unmarked.

54. A storage medium as defined in claim 45 wherein the garbage collector additionally:

E) maintains for each of a plurality of the regions a respective oldest-region indicator associated therewith, the oldest-region indicator associated with a given region identifying a region such that no region older than the region thereby identified contains a strong reference to an object in the given region; and

F) during each of at least some collection increments;

i) employs the oldest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set; and

ii) if any regions that contain no reachable objects are thereby identified, includes at least a portion of at least one such region in the collection set.

55. A storage medium as defined in claim 54 wherein:

G) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

H) the region search includes;

i) marking as reachable each of the regions in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) processing in collection order each region in the sequence by marking that region as reachable unless its youngest-region indicator identifies no region younger than that region and its oldest-region indicator identifies a region younger than the youngest older region previously marked as reachable; and

iii) identifying as unreachable any region thus processed that remains unmarked.

56. A storage medium as defined in claim 54 wherein:

G) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

H) the region search includes;

i) marking as reachable each of the regions in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) processing in reverse collection order each region in the sequence by marking that region as reachable unless its oldest-region indicator identifies no region older than that region and its youngest-region indicator identifies a region older than the oldest younger region previously marked as reachable; and

iii) identifying as unreachable any region thus processed that remains unmarked.

57. A storage medium as defined in claim 54 wherein:

G) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

H) the region search includes;

i) marking as reachable each region in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) marking each region in the sequence whose youngest-region indicator identifies a region at least as young as a marked younger region and each region in the plurality thereof whose oldest-region indicator identifies a region at least as old as a marked older region; and

I) identifying as unreachable any region in the sequence that remains unmarked.

58. A storage medium as defined in claim 54 wherein:

G) the garbage collector maintains a respective youngest-region indicator and oldest-region indicator at least for each said region in a sequence thereof uninterrupted in the collection order; and

H) the region search includes;

i) marking as reachable each region in the sequence that contains an object directly referred to by a strong reference located outside the generation;

ii) associating with each region in the sequence the subsequence of regions that includes and is bordered in the collection sequence by the regions identified by that region'"'"'s oldest- and youngest-region indicators;

iii) marking each region with which the subsequence thereby associated includes a marked region; and

iv) identifying as unreachable any region in the sequence that remains unmarked.

59. A storage medium containing instructions readable by a computer system that includes memory to configure the computer to operate as a garbage collector that:

A) treats at least a generation of a garbage collected heap in the computer system'"'"'s memory as divided into regions assigned a collection order from oldest to youngest;

B) maintains for each of a plurality of the regions a respective oldest-region indicator associated therewith, the oldest-region indicator associated with a given region identifying a region such that no region older than the region thereby identified contains a strong reference to an object in the given region; and

C) during each of at least some collection increments;

i) performs a region search by employing the oldest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set;

ii) if any regions that contain no reachable objects are thereby identified, includes at least a portion of at least one such region in the collection set; and

D) reclaims space occupied by unreachable objects in the collection set.

60. A storage medium as defined in claim 59 wherein the region search identifies only cars that contain no reachable objects.

61. A storage medium as defined in claim 59 wherein the regions identified in the region search are included in the collection in preference to regions not thus identified.

62. A storage medium as defined in claim 59 wherein the garbage collector implements the train algorithm, treating the generation as divided into car sections grouped into trains and the regions are the car sections.

63. A storage medium as defined in claim 59 wherein the garbage collector, in response to modifications of at least some strong-references located in the generation:

E) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

F) updates the oldest-region indicator associated with the region in which the object referred to is located if necessary to make it identify the region in which the strong reference is located if and only if the region in which the strong reference is located is older than;

i) the region identified by that oldest-region indicator; and

ii) the region in which the object referred to is located.

64. A storage medium as defined in claim 63 wherein if no reference to a given region has been found in the generation outside the given region, the oldest-region indicator associated with the given region identifies the region itself.

65. A storage medium as defined in claim 59 wherein the garbage collector, in response to each of at least some write barriers that report strong-reference modifications:

E) identifies the region in which the object to which a strong reference whose modification is thereby reported refers; and

F) updates the oldest-region indicator associated with the region in which the object referred to is located, if necessary to make it identify the region in which the strong reference is located, if the region in which the strong reference is located is older than the region identified by that oldest-region indicator, even if the region in which the strong reference is located is not at old as the region in which the object referred to is located.

66. A storage medium as defined in claim 65 wherein the garbage collector:

G) maintains metadata structures, associated with respective regions, that contain order information specifying the collection order, as well as a fictional-region metadata structure associate with a fictional region, which specifies that the fictional region is younger than any other region;

H) maintains for each of a plurality of the regions an oldest-region indicator that is associated with that region and identifies one said region by identifying the metadata structure associated therewith; and

I) if no strong reference to any object in a given region has been found in the generation outside the given region, causes the oldest-region indicator associated with the given region to identify the fictional-region metadata structure.

67. A garbage collector operating in the memory of a computer comprising:

A) means for treating at least a generation of a garbage collected heap in a computer system'"'"'s memory as divided into regions assigned a collection order from oldest to youngest;

B) means for maintaining for each of a plurality of the regions a respective youngest-region indicator associated therewith, the youngest-region indicator associated with a given region identifying a region such that no region younger than the region thereby identified contains a strong reference to an object in the given region; and

C) means for, during each of at least some collection increments;

i) performing a region search by employing the youngest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set;

ii) if any such region is thereby identified, including at least a portion of at least one such region in the collection set; and

iii) reclaiming space occupied by unreachable objects in the collection set.

68. A garbage collector operating in the memory of a computer comprising:

A) means for treating at least a generation of a garbage collected heap in a computer system'"'"'s memory as divided into regions assigned a collection order from oldest to youngest;

B) means for maintaining for each of a plurality of the regions a respective oldest-region indicator associated therewith, the oldest-region indicator associated with a given region identifying a region such that no region older than the region thereby identified contains a strong reference to an object in the given region; and

C) means for, during each of at least some collection increments;

i) performing a region search by employing the oldest-region indicators to attempt to identify regions that are unreachable, at least with respect to the portion or the heap outside the collection set;

ii) if any regions that contain no reachable objects are thereby identified, including at least a portion of at least one such region in the collection set; and

iii) reclaiming space occupied by unreachable objects in the collection set.