Implement Basic Mark-and-Sweep Garbage Collection

Mark-and-Sweep Collection

Managed runtimes reclaim unreachable objects automatically. Mark-and-sweep: trace from roots (stack, globals), mark reachable objects, sweep unmarked objects back to the free list. Python's cyclic GC layers atop refcount; Go uses concurrent mark-sweep.

Phases

Mark: DFS/BFS from roots, set mark bit in object header. Sweep: walk heap, free unmarked objects, clear marks on survivors for next cycle.

cCopy
Loading…

• Stop-the-world pauses simplify correctness
• Object headers carry mark bit and type info
• No compaction: fragmentation accumulates
• Roots must include CPU registers and native stacks

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 basic mark-and-sweep garbage collection. This exercise requires tracing from roots, marking reachable heap objects, and reclaiming unmarked memory in a sweep pass.