Garbage Collection Fundamentals

Why You Need a Collector At All

Every string, function, closure, and instance your VM allocates lives on the heap for an unpredictable amount of time. A script that runs in a loop allocating a new string each iteration will exhaust memory quickly if nothing ever frees the old ones. You can't free eagerly (the language has no manual free), so you need an automatic strategy: mark-and-sweep, the simplest general-purpose garbage collector.

The idea in one sentence: periodically figure out which heap objects are still reachable from the running program, and free everything else.

Triggering Collection

You don't want to scan the heap after every single allocation — that's enormously wasteful. Instead, track an allocation counter (or total bytes allocated) and only run the collector once it crosses a threshold:

Growing the threshold relative to live memory after each collection (rather than using a fixed constant) is what keeps a long-running program from GC-thrashing as its working set grows.

Mark Phase: What's Reachable?

Garbage is defined negatively: an object is garbage if the running program can never reach it again from anything it currently has direct access to. Those direct-access starting points are the roots:

• every value currently sitting on the VM's operand stack
• every value bound in the globals table
• open upvalues (locals captured by a not-yet-closed closure)
• any temporary the compiler itself is holding onto mid-compilation

Marking is a graph traversal from the roots, following every outgoing reference an object holds (a closure holds its function and captured upvalues; a function's constant pool may hold nested functions or strings; an instance holds a fields table). An explicit worklist keeps this iterative instead of recursive, so a long reference chain can't blow the host stack:

Sweep Phase: Free the Rest

Once marking finishes, every reachable object has marked = True. Sweep walks the entire heap (every object ever allocated, not just the reachable ones — this is why the collector keeps its own master list of all live allocations) and frees anything left unmarked:

That final reset matters: marks must return to "unmarked" before the next collection, or every object looks permanently reachable after its first collection.

Correctness Hazards

Two mistakes will bite you immediately if you skip a root category: forget to include the operand stack and the VM will free a value mid-expression, corrupting the next instruction that reads it — a use-after-free. Forget to include closed-over locals and a closure will read garbage the next time it runs. On the flip side, holding onto references longer than necessary (never clearing a stale "temp" root) causes a memory leak — not a crash, but unbounded growth.

What to build

Implement alloc (bump a counter, register the object), collect (mark from roots via a worklist, then sweep unmarked objects), and expose GC STATS reporting allocated, freed, and collections. Test that an object referenced only by another garbage object gets collected transitively, and that an object still reachable through a root survives.