CompilersGarbage CollectionMedium

Implement Basic Mark-and-Sweep Garbage Collection

Master the fundamental concepts of garbage collection through this focused micro-challenge.

~45 minutes Garbage Collection Ready to learn

Topic Overview

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.

c
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.

Implementation Task

Your Task

Implement a mark-and-sweep garbage collector over a simulated heap driven by a script: objects are allocated, linked to each other, and made reachable (or not) from roots; each collection marks everything reachable and frees the rest.

Input

One command per line:

Command	Meaning
`new NAME SIZE`	allocate object `NAME` of `SIZE` bytes
`link A B`	add a pointer from `A` to `B` (an object can point to many, in order)
`unlink A B`	remove the pointer `A → B` (the first one, if repeated)
`root NAME` / `unroot NAME`	add / remove a root (roots are kept in the order added)
`gc`	run a collection

Names are unique among live objects; a freed object's name may be reused by a later new.

Collection

Mark: depth-first from each root in root order; from an object, visit its pointers in the order they were linked. Each object is marked (and reported) the first time it is reached.
Sweep: every unmarked object is freed; survivors stay (and are unmarked again for next time).

Output

For each gc, numbered from 1:

c
Loading…

At the end: heap: NAME NAME ...: live objects in allocation order (or heap: empty).

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

An object table with a mark bit, size and an ordered list of outgoing pointers.
Mark with an explicit stack or recursion; sweep in allocation order.

Hidden tests cover shared children reached twice, several roots, and reuse of a freed name.