### 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 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 scan 52 52 8 b 7 53 53 0 j 10 54 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 scan 53 53 0 j 10 54 54 0 d 5 55 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 scan 53 53 0 j 10 54 54 0 d 5 55 55 0 c 0 56 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 scan 54 54 0 d 5 55 55 0 c 0 56 56 10 k 0 57 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 scan 55 55 0 c 0 56 56 10 k 0 57 57 0 f 0 58 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 scan 56 56 10 k 0 57 57 0 f 0 58 58 0 a 0 59 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 scan, next 60 61 62

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