Patent ID: 7340494

Claim:
A computer system configured by stored instructions as a garbage collector that reclaims for reuse memory allocated from a heap by a mutator executing on the computer system, wherein the garbage collector: A) performs a global marking operation on the heap; B) treats the heap as divided into a plurality of heap regions, wherein the garbage collector maintains a remembered set associated with a heap region of the plurality of heap regions, independently of which other heap regions contain references to objects in the heap region, wherein entries in the remembered set identify the locations of the references; C) performs space-incremental-collection operations, associated with a collection set comprising the heap region, in which the garbage collector employs the remembered set associated with the heap region in the collection set to determine whether objects in the heap region satisfy a potential-reachability criterion and reclaims memory occupied by objects that do not satisfy the potential-reachability criterion; and D) selects the heap region for the collection set by performing a collection-efficiency estimate calculation based on a result of the global marking operation, wherein the collection-efficiency estimate calculation includes determining which of a set of candidate groups of regions yields a greater ratio of likely memory reclamation to reclamation cost, wherein each space-incremental-collection operation includes processing d remembered-set-log-buffer entries, d≧0, in order to update remembered sets, wherein the reclamation cost V(cs) for a candidate group cs of regions is determined in accordance with V ⁡ ( cs ) = V fixed + U · d + ∑ r ∈ cs ⁢ ( S · rsSize ⁡ ( r ) + C · liveBytes ⁡ ( r ) ) , and wherein V fixed represents fixed costs common to all pauses, d is the number of remembered-set-log-buffer entries to be scanned during that space-incremental-collection operation, U is the average cost of scanning a remembered-set-log-buffer entry, S is the cost per remembered-set entry of scanning a remembered set, rsSize(r) is the number of remembered-set entries in the remembered set maintained for region r, C is the cost per byte of evacuating and scanning an object that is not reclaimed, and live-Bytes(r) is an estimate of how man bytes will not be reclaimed from region r.