Implement Copying Garbage Collection

Semispace Copying Collectors

Copying GC divides heap into from-space and to-space. Cheney's algorithm copies reachable objects to to-space, updates pointers, swaps spaces. Lisp machines and nursery collections in generational GC use copying for fast bump allocation. The tradeoff is memory: you need twice the heap capacity because only one semispace is active at a time.

Cheney Scan

Forward pointer scan iterates to-space. For each object, copy unforwarded children, leave forwarding pointer in from-space slot. Scan and free pointer chase each other through to-space until all reachable objects are copied.

cCopy
Loading…

• Bump pointer allocation in to-space is O(1)
• Only live data copied; dead objects vanish
• Requires 2x heap reservation
• Forwarding pointers fix interior references

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement copying garbage collection with semispaces. This exercise asks you to copy live objects, maintain forwarding pointers, and swap spaces after collection.