Low overhead cardinality estimation for incoming references in regional garbage collection

A method comprising:

• concurrently with execution of a mutator application that modifies a heap memory comprising a plurality of memory regions and prior to initiating a garbage collection pause to perform a garbage collection operation:
• for each of the plurality of regions in the heap memory, computing an estimate indicative of a time required to evacuate the respective region by applying a probabilistic cardinality estimator algorithm to the region to estimate a number of unique objects present within a set that includes the region;
• during the garbage collection pause having a particular pause duration:
• selecting, from the plurality of memory regions in the heap memory, a candidate subset of memory regions for evacuation, the candidate subset being selected based at least in part on the particular pause duration and the estimates computed prior to the garbage collection pause;
• merging the estimates that (a) correspond to the selected candidate subset of memory regions and (b) are computed prior to the garbage collection pause to determine a total estimated evacuation time to evacuate the candidate subset of memory regions;
• determining a first remaining time during the pause;
• determining that the total estimated evacuation time to evacuate the candidate subset of regions does not exceed the determined first remaining time;
• and
• evacuating each region in the candidate subset of memory regions for evacuation;
• wherein the method is performed by at least one device including a hardware processor.

A system comprising:

• at least one device including a hardware processor;
• the system being configured to perform operations comprising:
• concurrently with execution of a mutator application that modifies a heap memory comprising a plurality of memory regions and prior to initiating a garbage collection pause to perform a garbage collection operation:
• for each of the plurality of regions in the heap memory, computing an estimate indicative of a time required to evacuate the respective region by applying a probabilistic cardinality estimator algorithm to the region to estimate a number of unique objects present within a set that includes the region;
• during the garbage collection pause having a particular pause duration:
• selecting, from the plurality of memory regions in the heap memory, a candidate subset of memory regions for evacuation, the candidate subset being selected based at least in part on the particular pause duration and the estimates computed prior to the garbage collection pause;
• merging the estimates that (a) correspond to the selected candidate subset of memory regions and (b) are computed prior to the garbage collection pause to determine a total estimated evacuation time to evacuate the candidate subset of memory regions;
• determining a first remaining time during the pause;
• determining that the total estimated evacuation time to evacuate the candidate subset of regions does not exceed the determined first remaining time;
• and
• evacuating each region in the candidate subset of memory regions for evacuation.