Clustering related objects during garbage collection

• US 20100293206A1
• Filed: 05/12/2009
• Published: 11/18/2010
• Est. Priority Date: 05/12/2009
• Status: Abandoned Application

• Current Assignee: Clausal Computing Oy (Tatu Juhani Ylönen)
• Original Assignee: TATU Ylonen OY Limited
• Inventors: Ylonen, Tatu J.
• Application Number:
  US12/464,231
• Publication Number:
  US 20100293206A1
• Time in Patent Office: Days
• US Class Current: 707/813
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory

Abstract

Clustering related objects in a region-based garbage collector is solved by associating one or more regions with each cluster, and allocating objects from a region belonging to the primary cluster for the object. Relatedness may refer to, e.g., proximity to a cluster center (such as topic) in a persistent knowledge base or a home node in a distributed object system. The cluster for an object may be determined, e.g., from reachability from particular roots or objects during global tracing. For new objects, the initial cluster may be guessed based on history of where objects allocated in that call site have recently been clustered (possibly several stack frames deep).

Claims

1. A method of clustering related objects in a computer comprising a region-based garbage collector, the method comprising:

associating an object with at least one cluster; and

allocating, by the garbage collector, space for the object from a region associated with at least one of the clusters.

2. The method of claim 1, further comprising

caching allocation information referencing a region for at least one of the clusters, and

using the cached allocation information to select the same region for allocating space for a second object associated with the same cluster.

3. The method of claim 2, wherein:

a global cache is used for caching at least a portion of the cached allocation information;

the global cache is used by more than one thread;

the cache is arranged such that allocation information can in the common case be read from the cache without using atomic operations; and

one or more atomic operations are used to update the cache in response to associating a fresh region with a cluster.

4. The method of claim 2, wherein:

the allocating comprises allocating an allocation buffer (LAB) referencing the region associated with the cluster for at least one thread; and

the caching comprises caching the thread-local allocation buffer in a cache local to the thread.

5. The method of claim 2, further characterized by keeping allocation information for at least one cluster cached across more than one evacuation pause.

6. The method of claim 2, further comprising removing allocation information referencing a region from the cache in response to including the region in a collection set.

7. The method of claim 2, further comprising preventing the inclusion of a region in a collection set in response to cached allocation information referencing it.

8. The method of claim 1, further comprising:

collecting more than one object associated with at least one cluster into a group; and

allocating space for all objects in the group from one or more regions associated with at least one of the clusters associated with the objects in the group.

9. The method of claim 8, wherein at least one group is thread-local.

10. The method of claim 1, wherein at least one object is the root of a tree of objects comprising at least two objects, and non-root objects in the tree are allocated from the same region as the root without selecting a region for them separately.

11. The method of claim 1, wherein at least one object is the root of a multiobject, and the entire multiobject is associated and allocated as one unit.

12. The method of claim 1, further comprising associating a fresh region with at least one of the clusters associated with the object.

13. The method of claim 1, wherein said associating an object with at least one cluster comprises computing cluster tags for the object.

14. The method of claim 13, wherein at least one tag is at least partially computed from a measure selected from the group consisting of:

the object'"'"'s proximity to a cluster head;

the object'"'"'s reachability from garbage collection roots;

the return addresses contained in the call stack when the object is created;

the frequency of use of the object;

the home node of the object in a distributed system;

the persistence of the object;

the frequency of writes to the object;

the frequency of object graph modifying writes to the object;

the class of the object;

the clusters associated with objects that reference the object;

the age of the object as measured in bytes allocated since the object was created;

the age of the object as measured in the number of times the object has been promoted; and

the age of the object as measured in wall clock time.

15. The method of claim 13, wherein one of the tags computed for the object is selected as the primary tag.

16. The method of claim 13, further comprising storing allocation information in an array indexed by one or more cluster tags.

17. The method of claim 13, wherein at least one cluster tag associated with the object is computed by quantizing a value computed at least partially from at least one measure selected from the group consisting of:

the object'"'"'s proximity to a cluster head;

the object'"'"'s reachability from garbage collection roots;

the return addresses contained in the call stack when the object is created;

the frequency of use of the object;

the home node of the object in a distributed system;

the persistence of the object;

the frequency of writes to the object;

the frequency of object graph modifying writes to the object;

the class of the object;

the clusters associated with objects that reference the object;

the age of the object as measured in bytes allocated since the object was created;

the age of the object as measured in the number of times the object has been promoted; and

the age of the object as measured in wall clock time.

18. The method of claim 1, wherein associating an object with at least one cluster comprises computing a relatedness metric at least partially based on one or more measures between the object and at least one candidate cluster, and associating the object with the candidate cluster with which it has the highest computed relatedness metric.

19. The method of claim 18, wherein at least one of the measures is selected from the group consisting of:

the object'"'"'s proximity to a cluster head;

the object'"'"'s reachability from garbage collection roots;

the return addresses contained in the call stack when the object is created;

the frequency of use of the object;

the home node of the object in a distributed system;

the persistence of the object;

the frequency of writes to the object;

the frequency of object graph modifying writes to the object;

the class of the object;

the clusters associated with objects that reference the object;

the age of the object as measured in bytes allocated since the object was created;

the age of the object as measured in the number of times the object has been promoted; and

the age of the object as measured in wall clock time.

20. The method of claim 1, further comprising selecting one or more regions for a collection set such that the selection is responsive to the need for reclustering objects in at least one region.

21. The method of claim 1, wherein at least part of the cluster selection is performed by a process running as a mutator.

22. A computer comprising:

a cluster selector; and

a region-based garbage collector comprising a cluster allocator.

23. The computer of claim 22, wherein the cluster selector comprises a relatedness determinator.

24. The computer of claim 22, wherein the cluster selector comprises a tagger.

25. The computer of claim 22, wherein the cluster allocator comprises an allocation information cache.

26. The computer of claim 25, wherein the cache is at least partially thread-local.

27. The computer of claim 22, wherein the cluster allocator comprises a grouped allocator.

28. A computer program product operable to cause a computer to:

associate an object with at least one cluster; and

use a region-based garbage collector to allocate space for the object from a region associated with at least one of the clusters.

29. The computer program product of claim 28, further operable to cause a computer to:

cache allocation information referencing a region for at least one cluster; and

use the cached allocation information to select the same region for allocating space for a second object associated with the same cluster.