Patent ID: 7636745

Claim:
A storage medium that contains instructions executable by a computer system to configure the computer system as a garbage collector, wherein the garbage collector reclaims for reuse memory allocated in a heap by a mutator executing on the computer system, wherein the garbage collector performs a plurality of successive marking cycles, and wherein to perform a marking cycle in the plurality of successive marking cycles, the garbage collector: performs a marking operation in which the garbage collector traces reference chains from a root set and makes marks associated with respective objects thereby encountered; performs a plurality of collection space increments within the marking cycle after performing the marking operation, wherein each of the plurality of collection space increments reclaims a collection set within the heap, wherein the garbage collector bases a selection of the collection set on the marks made by the marking operation, wherein the garbage collector treats the heap as divided into regions, for which the garbage collector maintains respective remembered sets that the garbage collector uses in the plurality of collection space increments to determine whether objects in the collection set are referred to from outside the collection set and are therefore potentially reachable, and wherein the garbage collector additionally bases the selection of the collection set on sizes of the remembered sets; repeatedly calculates a measure of a cumulative efficiency of collection that has taken place during the marking cycle and determines whether the cumulative efficiency thereby calculated satisfies a set of at least one marking-initiation criterion, wherein the cumulative efficiency is calculated as a ratio of an amount of memory reclaimed in the marking cycle to an amount of time taken by collection during the marking cycle; and terminates the marking cycle and begins a subsequent marking cycle when the cumulative efficiency satisfies the set of at least one marking-initiation criterion.