Copying entire subgraphs of objects without traversing individual objects
Copying or compacting performance in garbage collection is improved by copying a first memory area (preferably comprising multiple objects) to a second memory area without traversing individual objects in the copied memory area and adjusting all copied memory locations identified as pointers in a metadata data structure. An entire linearized subgraph of the object graph can be copied at a time.
1 . A pointer-adjusting data copying method comprising:
copying, by a data processing device, a first memory area to a second memory area; and
adjusting at least one copied memory location identified as a pointer in a metadata data structure.
2 . The method of claim 1 , wherein the data processing device participates in garbage collection.
3 . The method of claim 1 , wherein the metadata data structure is a bitmap.
4 . The method of claim 1 , wherein the adjusting is performed by adding to each identified pointer the difference of the starting addresses of the second and first memory areas.
5 . The method of claim 1 , wherein the copying is done using the memcpy function or its equivalent.
6 . The method of claim 1 , wherein the memory is copied before adjusting internal pointers.
7 . The method of claim 1 , wherein the memory is copied after adjusting internal pointers.
8 . The method of claim 1 , wherein the copying and adjusting steps are interlaced.
9 . The method of claim 1 , wherein the internal pointers are adjusted in more than one steps.
10 . The method of claim 1 , wherein at least one of the source and destination memory areas in copying is in non-volatile memory.
11 . The method of claim 1 , wherein one of the source and destination memory areas in copying is on a second node in a distributed system.
12 . The method of claim 1 , wherein:
the first memory area comprises an essentially contiguous distinguished subgraph comprising more than one object;
the pointers identified in the metadata data structure are the internal pointers of the distinguished subgraph; and
the copying is performed without traversing individual objects in the distinguished subgraph.
13 . The method of claim 12 , wherein the distinguished subgraph is a multiobject.
14 . The method of claim 12 , wherein the distinguished subgraph is a nested multiobject.
15 . The method of claim 12 , wherein the distinguished subgraph is a relaxed multiobject.
16 . The method of claim 12 , wherein the distinguished subgraph comprises at least one smaller distinguished subgraph.
17 . The method of claim 12 , further comprising:
constructing the distinguished subgraph, the constructing comprising:
dividing a plurality of objects into subsets that, together with vertices pointing between objects within each subset, are subgraphs of the object graph;
copying the objects in at least one subset into essentially consecutive memory locations;
updating internal pointers in the copied objects to point to the respective new copies of their targets; and
associating metadata with the distinguished subgraph, said metadata at least identifying which cells in the distinguished subgraph comprise internal pointers.
18 . The method of claim 12 , further comprising marshalling access to the distinguished subgraph using a cache coherency protocol.
19 . The method of claim 12 , further comprising removing holes from the distinguished subgraph.
20 . The method of claim 12 , further comprising combining at least one other distinguished subgraph into the distinguished subgraph.
21 . The method of claim 12 , further comprising swizzling or unswizzling at least one pointer in or to the distinguished subgraph.
22 . A data processing device comprising:
a pointer adjusting memory copier, wherein the memory copier:
copies a first memory area to a second memory area; and
adjusts at least one copied memory location identified as a pointer in a metadata data structure.
23 . The data processing device of claim 22 , wherein the metadata data structure is a bitmap.
24 . The data processing device of claim 22 , further characterized in that it participates in garbage collection.
25 . The data processing device of claim 22 , wherein the adjusting is performed by adding to each identified pointer the difference of the starting addresses of the second and first memory areas.
26 . The data processing device of claim 22 , wherein:
the first memory area comprises an essentially contiguous distinguished subgraph comprising more than one object;
the pointers identified in the metadata data structure comprise the internal pointers of the distinguished subgraph; and
the copying is performed without traversing individual objects in the distinguished subgraph.
27 . The data processing device of claim 26 , wherein the distinguished subgraph is a multiobject.
28 . The data processing device of claim 26 , wherein the distinguished subgraph is a nested multiobject.
29 . The data processing device of claim 26 , wherein the distinguished subgraph is a relaxed multiobject.
30 . The data processing device of claim 26 , wherein the distinguished subgraph comprises at least one smaller distinguished subgraph.
31 . A computer program product stored on a tangible computer-usable medium, operable to cause a data processing device to:
participate in garbage collection;
copy a first memory area to a second memory area as part of such garbage collection; and
adjust at least one copied memory location identified as a pointer in a metadata data structure.
32 . The computer program product of claim 31 , wherein:
the first memory area comprises an essentially contiguous distinguished subgraph comprising more than one object;
the pointers identified in the metadata data structure comprise the internal pointers of the distinguished subgraph; and
the copying is performed without traversing individual objects in the distinguished subgraph.
33 . The computer program product of claim 32 , wherein the distinguished subgraph is a multiobject.
34 . The computer program product of claim 32 , wherein the distinguished subgraph is a nested multiobject.
35 . The computer program product of claim 32 , wherein the distinguished subgraph is a relaxed multiobject.
36 . The computer program product of claim 32 , wherein the distinguished subgraph comprises at least one smaller distinguished subgraph.