Copying Garbage Collector
Clone this wiki locally
Best algo against fragmentation, extremely fast (one-pass only), but needs double memory.
Esp. Cheney's Two-Finger variant is desirable. potion/p2 uses that and has a medium gc time of 4ms for medium sized heaps; i.e. real-time. But for guaranteed real-time you'd need to pause the GC, and this is not possible with a Copying collector, only Mark & Sweep.
"Garbage Collection: Algorithms for Automatic Dynamic Memory Management"
The following is an excerpt from Garbage Collection: Algorithms for Automatic Dynamic Memory Management by Richard Jones and Rafael Sims. For a further discussion of the 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
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 forwardingaddress(P) = P' P' = copy(temp) for i = 1 to n-1 -- copy each field of P into P' P'[i] = copy(P[i]) return forwarding_address(P)
First, the roles of
Fromspace are swapped by a flip, which resets the variables
top_of_space. Each cell reachable from a root is then copied from
copy(P) scavenges the fields of the cell pointed to by
P. Care has to be taken when copying data structures to ensure that the topology of the shared data structures is preserved. Failure to do this would lead to multiple copies of shared objects, which at best would increase heap residency of the program but may also break the user program (for example, if it updated one copy of a cell, but then read the value from another). Copying cyclic data structures without preserving sharing would also require a lot of room!
Copying collectors preserve sharing by leaving a forwarding address in the
Fromspace object when it is copied. The forwarding address is the address of the copy in
Tospace. When a cell in
Fromspace is visited,
copy() checks to see if it has already been copied, if it has the forwarding address is returned, otherwise memory is reserved for the copy in
Tospace. In this recursive copying algorithm, the forwarding address is set to point to this reserved memory before the constituent fields of the object are copied -- this ensures termination and that sharing is preserved.
The forwarding address might be held in its own field in the cell. More generally it can be written over the first word in the cell provided that the original value of the cell is saved beforehand. In the above it is assumed that the forwarding address field in cell
P, and forwarding
P are used interchangeably.
Garbage Collection: Algorithms for Automatic Dynamic Memory Management
by Richard Jones and Rafael Sims