Copying Garbage Collector

(see TT #616)

The basic concept of a Copying Collector is that the heap is divided into two equal semi-spaces, one of which contains the current data and the other obsolete data. The Garbage Collection phase starts by flipping the roles of the two semi-spaces. The collector then scans the active data in the old semi-space, Fromspace, copying each live cell into the new semi-space, Tospace. On completion of the collection phase, Tospace contains all the active data and Fromspace is effectively abandoned.

One major advantage of this is that the active data is compacted at the bottom of Tospace. Compacting collectors can allocate space much more efficiently than collectors in which fragmentation is a problem.

Allocation costs are extremely low. The out-of-space check is a simple pointer comparison. New memory is acquired by simply incrementing the free-space pointer. Fragmentation is eliminated by simply copying the active data into the bottom of Tospace.

The chief drawback of copying collectors is the need to divide the available memory into two semi-spaces. As the residency of a program increases the performance of the collector degrades, as less free space is recovered and collections become more frequent.

The basic Copying algorithm:

```init() =
Tospace = Heap_bottom
space_size = Heap_size / 2
top_of_space = Tospace + space_size
Fromspace = top_of_space + 1
free = Tospace

New(n) =
if free + n > top_of_spece
flip()
if free + n > top_of_space
abort "Memory exhausted"
newcell = free
free = free + n
return newcell

flip() =
Fromspace, Tospace = Tospace, Fromspace
top_of_space = Tospace + space_size
free = Tospace
for R in roots
R = copy(R)

-- P points to a word not a cell
copy(P) =
if atomic(P) or P == nil        -- P is not a pointer
return P

if not forwarded(P)
n = size(P)
P' = free                   -- reserve space in Topace
free = free + n
temp = P                 -- field 0 will hold the forwarding address
P' = copy(temp)
for i = 1 to n-1            -- copy each field of P into P'
P'[i] = copy(P[i])