Patent ID: 7302515

Claim:
A computer system configured by machine instructions to operate as a virtual machine that responds to virtual-machine code, which virtual-machine code defines a mutator that dynamically allocates memory in a heap to data objects and writes in reference fields references to such objects, by: A) executing a garbage collector that: treats the heap as divided into regions, determines whether objects to which memory in the heap has been dynamically allocated satisfy a popular-object criterion, places into certain, popular-object regions the objects that it thereby determines satisfy such a criterion and excludes from such regions objects that it thereby determines do not satisfy such a criterion, maintains for each of a plurality of the regions other than the popular-object regions a respective remembered set that lists where references in other regions to that region have been written, updates the remembered sets in response to reference-written notifications from the mutator, and excludes from garbage collection a remembered set that fails to satisfy an expected collection efficiency criterion, wherein the expected collection efficiency criterion is based on V ⁡ ( cs ) = V fixed + U × d + ∑ r ∈ cs ⁢ ⁢ ( S × rsSize ⁡ ( r ) + C × liveBytes ⁡ ( r ) ) , wherein V(cs) is a cost of collecting a collection set Cs, V fixed is a fixed cost common to all collection pauses, U is an average collection cost per collection set entry, d is a number of remembered-set-log-buffer entries, S is a cost per entry of scanning a remembered set, rsSize(r) is a number of entries in a remembered set for a region r, C is a cost per byte of evacuating and a number of entries in a remembered set for a region r, C is a cost per byte of evacuating and scanning a live object, and liveBytes(r) is an estimate of how many live bytes the region r contains; and B) so executing the mutator that, in at least some situations in which the mutator writes a reference into a reference field in the heap, the mutator: makes a normal-region determination of whether the reference refers to an object that is not located in a popular-object region, makes a reference-written notification to the garbage collector if the normal-region determination's result is that the reference refers to an object that is not located in a popular-object region, and otherwise refrains from making such a notification.