A Toy Mark-and-Sweep Garbage Collector

Authors

K19G

grok-bot

Updated

October 31, 2026

A Toy Mark-and-Sweep Garbage Collector

Thesis

Mark-and-sweep is the GC shape most languages still echo: start from roots, mark everything reachable, then reclaim the rest. Building a 40-line toy in C makes the invariants obvious before you read Go’s pacer or Python’s generational collector. This chapter marks from a single root, prints which objects survive, and sweeps the garbage.

Mental model

  roots ──mark──► reachable graph (bit / flag per object)
                      │
                      ▼
                 sweep: free unmarked; clear marks on survivors

Step	Rule
Alloc	Bump into a fixed heap array (no free-list yet)
Mark	DFS/BFS from roots; set `marked=1`
Sweep	Compact or free unmarked objects; reset marks

Worked examples

Case 1: root keeps a child; garbage dies

// gc.c (toy) — single-child objects in a fixed heap
// ... mark(root) then sweep() ...

Full listing used in this run allocates root → child plus two unreachable objects.

cc -O2 -o gc gc.c && ./gc

Output:

before mark: heap_len=4
  [0] root marked=1
  [1] child marked=1
  [2] garbage1 marked=0
  [3] garbage2 marked=0
sweep: kept 2 / 4 objects

Only the root and its child stay marked; sweep reports kept 2 / 4.

Trap

Pointer updates after compacting sweep. The toy prints counts and does not rewrite child pointers when slots move. A real compacting collector needs a handle table or forwarding pointers. Skipping that is how teaching demos quietly become use-after-free demos.

Boring rule

Use a toy GC to learn the vocabulary (roots, mark bits, barriers). Do not invent a production GC in application code — call the language runtime or an arena.

Try this

Add a free-list instead of bump allocation.
Introduce a second root and a diamond-shaped graph.
Compare to reading Go’s runtime.gcMark comments after this lab.

Sources

Jones, Hosking, Moss — The Garbage Collection Handbook
Go GC guide (production contrast)