Detection of dead regions during incremental collection

A method of 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 dead-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.

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 dead-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.

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 dead-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.

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 dead-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.

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 dead-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.

An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory, cause it 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 dead-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.

An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory, cause it 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 dead-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.

A garbage collector 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 dead-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.

A garbage collector 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 dead-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.