Grouped space allocation for copied objects
A method of efficiently allocating space for copied objects during garbage collection by grouping many objects together, and after determining which objects belong to a group, allocating space for them in one unit and copying the objects to the allocated space (possibly in parallel).
1 . A method of allocating space for copied objects in a computer comprising a group flusher, the method comprising:
collecting more than one object into one or more groups of objects to be copied; and
in response to one of the groups growing too big, flushing the group.
2 . The method of claim 1 , wherein flushing the group comprises:
allocating space for the entire group;
dividing the allocated space among the objects in the group; and
copying each object in the group to its allocated space.
3 . The method of claim 1 , wherein the objects added to a group represent trees of objects rooted at said objects.
4 . The method of claim 1 , wherein collecting objects into the group comprises incrementally computing the size of the group as objects are added to the group.
5 . The method of claim 4 , wherein the offset of each object in the group is computed when it is added to the group.
6 . The method of claim 1 , wherein space for the entire group is allocated using substantially a single atomic operation.
7 . The method of claim 1 , wherein the group into which an object is added is selected at least partially in response to its age.
8 . The method of claim 1 , wherein the group into which an object is added is selected at least partially based on its proximity to a cluster.
9 . The method of claim 1 , wherein at least one group is local to a garbage collection thread.
10 . The method of claim 1 , wherein at least one group is shared by more than one garbage collection thread.
11 . The method of claim 1 , wherein the flushing comprises replacing at least one pointer in at least one object by a persistent object identifier.
12 . The method of claim 1 , wherein the flushing comprises encoding at least one object into a transfer encoding.
13 . The method of claim 1 , wherein the flushing comprises copying at least two objects in the group at least partially in parallel.
14 . A computer comprising:
an object grouper; and
a group flusher configured to allocate space for and copy the objects contained in a group in response to the group becoming too big.
15 . The computer of claim 14 , wherein the group flusher comprises:
a group allocator configured to allocate space for objects in a group; and
a group copier configured to copy the objects in the group to the space allocated by the group allocator.
16 . The computer of claim 14 , wherein the object grouper is configured to store roots of trees of objects in at least one group, said roots representing all objects in trees rooted by said roots.
17 . The computer of claim 14 , wherein the object grouper is configured to select a group for each of a plurality of objects to be copied, the selection based at least partially on the age of the objects.
18 . The computer of claim 14 , wherein the object grouper assigns for each object added to a group an offset at which it will be stored in the space to be allocated for the group.
19 . The computer of claim 14 , wherein the object grouper is configured to select the group of an object at least partially in response to its distance from a cluster center.
20 . A computer readable medium operable to cause a computer to:
collect more than one object into a group of objects to be copied; and
in response to the group having grown too big:
allocate space for the entire group, and
copy each object in the group to its allocated space.