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.