Cheney's Copying Collector

The Fenichel-Yochelson collector given in the CopyingGarbageCollector page has the disadvantage of using a recursive copying algorithm. Since Cheney's discovery of an efficient iterative technique for its implementation copying collection has proved popular with implementors. Although garbage collection technology has moved beyond simple stop-and-copy collection, this technique remains the most widely adopted basis for more sophisticated techniques, such as generational and incremental collectors.

Cheney's algorithm:

flip() =
    Fromspace, Tospace = Tospace, Fromspace
    top_of_space = Tospace + space_size
    scan = free = Tospace

    for R in roots
        R = copy(R)

    while scan < free
        for P in Children(scan)
            *P = copy(*P)
        scan = scan + size (scan)

copy(P) =
    if forwarded(P)
        return forwarding_address(P)
    else
        addr = free
        move(P,free)
        free = free + size(P)
        forwarding_address(P) = addr
        return addr

extracted from:
Garbage Collection: Algorithms for Automatic Dynamic Memory Management
by Richard Jones and Rafael Sims
 http://www.cs.kent.ac.uk/people/staff/rej/gc.html