Facilitating efficient garbage collection by dynamically coarsening an append-only lock-free trie

1. A computer-implemented method, comprising:

responsive to storing a reference into a location in a referenced memory area during the execution of a software program:

finding, within a trie that serves as a remembered set for the referenced memory area, a particular entry that corresponds to a particular address range that covers the location, the trie comprising interior nodes and leaf nodes, each leaf node storing a plurality of entries that each corresponds to an address range in the referenced memory area, each interior node storing a plurality of entries that each:

points to a child node of the interior node; and

corresponds to a larger address range that covers any address range that corresponds to an entry stored in the child node; and

marking the particular entry to indicate that the particular address range should be processed during a garbage collection on the software program; and

based on a policy,

setting a coarsening threshold that allows an ancestor node of the particular entry to be pruned if a number of marked entries stored in the ancestor node exceeds the coarsening threshold;

based on the coarsening threshold, coarsening a particular subtree of the trie in which the particular entry is stored, wherein a root entry of the particular subtree corresponds to a particular larger address range that covers any address range that corresponds to an entry stored in the subtree;

after coarsening the particular subtree based on the coarsening threshold, adjusting the coarsening threshold one or more times; and

during the garbage collection, processing the particular larger address range when the root entry of the particular subtree is visited.

2. The computer-implemented method of claim 1 , wherein finding the particular entry comprises, for one or more descendant nodes of a root entry of the trie:

visiting, within the descendant node, an entry that corresponds to an address range that covers the location;

if the descendant node is not a leaf node, continuing to search, at a child node pointed to by the visited entry, for the particular entry; and

if the descendant node is a leaf node, selecting the visited entry.

3. The computer-implemented method of claim 1 , wherein coarsening the particular subtree comprises, for one or more ancestor nodes of the particular entry:

if, based on the policy, the ancestor node should be pruned:

marking a parent entry of the ancestor node to indicate that a larger address range that covers the particular address range should be processed during the garbage collection;

pruning the ancestor node from the trie; and

if the parent entry is not a root entry of the trie, continuing to coarsen the particular subtree at a parent node of the ancestor node; and

if, based on the policy, the ancestor node should not be pruned, stopping the coarsening of the particular subtree.

4. The computer-implemented method of claim 3 :

wherein the referenced memory area comprises a heap;

wherein the trie serves as a remembered set for a region of the heap; and

wherein the heap comprises a plurality of regions.

5. The computer-implemented method of claim 4 :

wherein the collection set of the garbage collection comprises a first set of regions of the heap and excludes a second set of regions of the heap; and

wherein processing an address range comprises scanning the address range for objects that reference one of the regions in the collection set.

6. The computer-implemented method of claim 4 , further comprising at least one of:

based on the policy, reducing the coarsening threshold if an amount of free memory available to the software program decreases; and

based on the policy, reducing the coarsening threshold if an amount of memory occupied by one or more remembered sets increases, wherein the one or more remembered sets comprises the remembered set.

7. The computer-implemented method of claim 3 , further comprising at least one of:

based on the policy, increasing the coarsening threshold if a thread count of the software program increases; and

based on the policy, decreasing the coarsening threshold if a thread count of the software program decreases.

8. The computer-implemented method of claim 4 , wherein the coarsening threshold is set based on a property that is unique to the region.

9. The computer-implemented method of claim 1 , wherein an entry comprises at least one of:

a 32 bit address that refers to a child node of the entry;

a 64 bit address that refers to the child node of the entry;

a first special value that indicates that the entry is marked; and

a second special value that indicates that the entry is unmarked.

10. An apparatus, comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to:

responsive to storing a reference into a location in a referenced memory area during the execution of a software program:

find, within a trie that serves as a remembered set for the referenced memory area, a particular entry that corresponds to a particular address range that covers the location, the trie comprising interior nodes and leaf nodes, each leaf node storing a plurality of entries that each corresponds to an address range in the referenced memory area, each interior node storing a plurality of entries that each:

points to a child node of the interior node; and

corresponds to a larger address range that covers any address range that corresponds to an entry stored in the child node; and

mark the particular entry to indicate that the particular address range should be processed during a garbage collection on the software program; and

based on a policy,

setting a coarsening threshold that allows an ancestor node of the particular entry to be pruned if a number of marked entries stored in the ancestor node exceeds the coarsening threshold;

based on the coarsening threshold, coarsening a particular subtree of the trie in which the particular entry is stored, wherein a root entry of the particular subtree corresponds to a particular larger address range that covers any address range that corresponds to an entry stored in the subtree;

after coarsening the particular subtree based on the coarsening threshold, adjusting the coarsening threshold one or more times; and

during the garbage collection, processing the particular larger address range when the root entry of the particular subtree is visited.

11. The apparatus of claim 10 , wherein finding the particular entry comprises, for one or more descendant nodes of a root entry of the trie:

visiting, within the descendant node, an entry that corresponds to an address range that covers the location;

if the descendant node is not a leaf node, continuing to search, at a child node pointed to by the visited entry, for the particular entry; and

if the descendant node is a leaf node, selecting the visited entry.

12. The apparatus of claim 10 , wherein coarsening the particular subtree comprises, for one or more ancestor nodes of the particular entry:

if, based on the policy, the ancestor node should be pruned:

marking a parent entry of the ancestor node to indicate that a larger address range that covers the particular address range should be processed during the garbage collection;

pruning the ancestor node from the trie; and if the parent entry is not a root entry of the trie, continuing to coarsen the particular subtree at a parent node of the ancestor node; and

if, based on the policy, the ancestor node should not be pruned, stopping the coarsening of the particular subtree.

13. The apparatus of claim 12 :

wherein the referenced memory area comprises a heap;

wherein the trie serves as a remembered set for a region of the heap; and

wherein the heap comprises a plurality of regions.

14. The apparatus of claim 13 :

wherein a collection set of the garbage collection comprises a first set of regions of the heap and excludes a second set of regions of the heap; and

wherein processing an address range comprises scanning the address range for objects that reference one of the regions in the collection set.

15. The apparatus of claim 13 , further comprising at least one of:

based on the policy, reducing the coarsening threshold if an amount of free memory available to the software program decreases; and

based on the policy, reducing the coarsening threshold if an amount of memory occupied by one or more remembered sets increases, wherein the one or more remembered sets comprises the remembered set.

16. The apparatus of claim 12 , further comprising at least one of:

based on the policy, increasing the coarsening threshold if a thread count of the software program increases; and

based on the policy, decreasing the coarsening threshold if a thread count of the software program decreases.

17. The apparatus of claim 13 , wherein the coarsening threshold is set based on a property that is unique to the region.

18. One or more non-transitory computer-readable storage media storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

responsive to storing a reference into a location in a referenced memory area during the execution of a software program:

finding, within a trie that serves as a remembered set for the referenced memory area, a particular entry that corresponds to a particular address range that covers the location, the trie comprising interior nodes and leaf nodes, each leaf node storing a plurality of entries that each corresponds to an address range in the referenced memory area, each interior node storing a plurality of entries that each:

points to a child node of the interior node; and

corresponds to a larger address range that covers any address range that corresponds to an entry stored in the child node; and

marking the particular entry to indicate that the particular address range should be processed during a garbage collection on the software program; and

based on a policy,

setting a coarsening threshold that allows an ancestor node of the particular entry to be pruned if a number of marked entries stored in the ancestor node exceeds the coarsening threshold;

based on the coarsening threshold, coarsening a particular subtree of the trie in which the particular entry is stored, wherein a root entry of the particular subtree corresponds to a particular larger address range that covers any address range that corresponds to an entry stored in the subtree;

after coarsening the particular subtree based on the coarsening threshold, adjusting the coarsening threshold one or more times; and

during the garbage collection, processing the particular larger address range when the root entry of the particular subtree is visited.