next up previous contents
Next: About this document ... Up: 13.2 Automatic Garbage Collection Previous: 13.2.1 Mark-and-Sweep Garbage Collection   Contents

13.2.2 Copying Garbage Collection

A copying garbage collector uses two heaps:

  1. from-space: the current working heap
  2. to-space: needs to be in memory during garbage collection only
At garbage collection time, the garbage collector creates an empty to-space heap in memory (of the same size as the from-space), copies the live objects from the from-space to the to-space (making sure that pointers are referring to the to-space), disposes the from-space, and finally uses the to-space as the new from-space.

Converting a pointer p that points to a from-space into a pointer that points to the to-space space, is called forwarding a pointer:

forward (p) {
   if p points t from-space
      then if p.f1 points to to-space
                 then return p.f1
      else for each field fi of p
                    next.fi := p.fi
             p.f1 := next
             next := next + (size of *p)
             return p.f1
   else return p

Forwarding pointers can be done in breadth-first-search, using Cheney's Algorithm. Compared to depth-first-search, breadth-first-search has better locality of reference:

scan := begin-of-to-space
next := scan
for each root r
    r := forward(r)
while scan < next
    for each field fi of *scan
           scan.fi := forward(scan.fi)
    scan := scan + (size of *scan)

Cheney's Algorithm uses a very simple allocation algorithm and has no need for stack (since is not recursive). More importantly, its run time depends on the number of live objects, not on the heap size. Furthermore, it does not suffer from data fragmentation, resulting into a more compact memory. In addition, it allows incremental (concurrent) garbage collection. On the other hand, it needs double the amount of memory and needs to recognize all pointers to heap.

For example,

roots


1
6
9
1 1 6 e 3
2 2 0 i 4
3 3 0 d 5
4 4 0 g 0
5 5 0 a 0
6 6 8 b 7
7 7 10 k 0
8 8 0 c 0
9 9 0 j 10
10 10 0 f 0
11 11 0 h 12
12 12 11 l 0


from-space
51         $ \leftarrow$ scan, next
52          
53          
54          
55          
56          
57          
58          
59          
60          
61          
62          


to-space


After we forward the roots from the from-space to the to-space, the to-space will contain the forwarded roots, and the roots and the forward pointers of the root elements in the from-space will point to the to-space, as shown below:

roots


51
52
53
1 51 6 e 3
2 2 0 i 4
3 3 0 d 5
4 4 0 g 0
5 5 0 a 0
6 52 8 b 7
7 7 10 k 0
8 8 0 c 0
9 53 0 j 10
10 10 0 f 0
11 11 0 h 12
12 12 11 l 0


from-space
51 51 6 e 3 $ \leftarrow$ scan
52 52 8 b 7  
53 53 0 j 10  
54         $ \leftarrow$ next
55          
56          
57          
58          
59          
60          
61          
62          


to-space


Then, we forward the pointers of the first element of the to-space pointed by the scan pointer (element 51). The first pointer 6 has already been forwarded to 52, as we can see from the element 6 in the from-space. The second pointer 3 is forwarded at the end of the to-space to 54:

roots


51
52
53
1 51 6 e 3
2 2 0 i 4
3 54 0 d 5
4 4 0 g 0
5 5 0 a 0
6 52 8 b 7
7 7 10 k 0
8 8 0 c 0
9 53 0 j 10
10 10 0 f 0
11 11 0 h 12
12 12 11 l 0


from-space
51 51 52 e 54  
52 52 8 b 7 $ \leftarrow$ scan
53 53 0 j 10  
54 54 0 d 5  
55         $ \leftarrow$ next
56          
57          
58          
59          
60          
61          
62          


to-space


Now we forward the pointer 8 of element 52:

roots


51
52
53
1 51 6 e 3
2 2 0 i 4
3 54 0 d 5
4 4 0 g 0
5 5 0 a 0
6 52 8 b 7
7 7 10 k 0
8 55 0 c 0
9 53 0 j 10
10 10 0 f 0
11 11 0 h 12
12 12 11 l 0


from-space
51 51 52 e 54  
52 52 55 b 7 $ \leftarrow$ scan
53 53 0 j 10  
54 54 0 d 5  
55 55 0 c 0  
56         $ \leftarrow$ next
57          
58          
59          
60          
61          
62          


to-space


and the pointer 7 of element 52:

roots


51
52
53
1 51 6 e 3
2 2 0 i 4
3 54 0 d 5
4 4 0 g 0
5 5 0 a 0
6 52 8 b 7
7 56 10 k 0
8 55 0 c 0
9 53 0 j 10
10 10 0 f 0
11 11 0 h 12
12 12 11 l 0


from-space
51 51 52 e 54  
52 52 55 b 56  
53 53 0 j 10 $ \leftarrow$ scan
54 54 0 d 5  
55 55 0 c 0  
56 56 10 k 0  
57         $ \leftarrow$ next
58          
59          
60          
61          
62          



to-space


Now we forward the pointer 10 of element 53:

roots


51
52
53
1 51 6 e 3
2 2 0 i 4
3 54 0 d 5
4 4 0 g 0
5 5 0 a 0
6 52 8 b 7
7 56 10 k 0
8 55 0 c 0
9 53 0 j 10
10 57 0 f 0
11 11 0 h 12
12 12 11 l 0


from-space
51 51 52 e 54  
52 52 55 b 56  
53 53 0 j 57  
54 54 0 d 5 $ \leftarrow$ scan
55 55 0 c 0  
56 56 10 k 0  
57 57 0 f 0  
58         $ \leftarrow$ next
59          
60          
61          
62          


to-space


Then we forward the pointer 5 of element 54:

roots


51
52
53
1 51 6 e 3
2 2 0 i 4
3 54 0 d 5
4 4 0 g 0
5 58 0 a 0
6 52 8 b 7
7 56 10 k 0
8 55 0 c 0
9 53 0 j 10
10 57 0 f 0
11 11 0 h 12
12 12 11 l 0


from-space
51 51 52 e 54  
52 52 55 b 56  
53 53 0 j 57  
54 54 0 d 58  
55 55 0 c 0 $ \leftarrow$ scan
56 56 10 k 0  
57 57 0 f 0  
58 58 0 a 0  
59         $ \leftarrow$ next
60          
61          
62          


to-space


The pointer 10 of element 56 has already been forwarded. Therefore, we get:

roots


51
52
53
1 51 6 e 3
2 2 0 i 4
3 54 0 d 5
4 4 0 g 0
5 58 0 a 0
6 52 8 b 7
7 56 10 k 0
8 55 0 c 0
9 53 0 j 10
10 57 0 f 0
11 11 0 h 12
12 12 11 l 0
51 51 52 e 54  
52 52 55 b 56  
53 53 0 j 57  
54 54 0 d 58  
55 55 0 c 0  
56 56 57 k 0  
57 57 0 f 0  
58 58 0 a 0  
59         $ \leftarrow$ scan, next
60          
61          
62          


Finally, the to-space becomes the new heap and the from-space is deallocated from memory.


next up previous contents
Next: About this document ... Up: 13.2 Automatic Garbage Collection Previous: 13.2.1 Mark-and-Sweep Garbage Collection   Contents
fegaras 2012-01-10