Design a Garbage Collection System

The ask

A running program creates objects in a heap, the memory area it allocates from. Programs forget most objects quickly and never free them by hand.

Garbage collection finds the objects no longer in use and returns their memory for reuse. It runs inside the program's runtime, beside the program itself.

The collector must never free memory still in use. One such error corrupts the program far worse than a leak.

Pauses matter as much as totals. A collector that frees plenty but stops the program for seconds fails its users.

Estimate the scale

The worked heap is 100 GB. The program allocates 1 GB per second.

100 GB / 1 GB per second = 100 seconds to fill the heap if nothing is collected.

Collection therefore runs on a rhythm of seconds, not hours. Free space is a fast-moving budget.

Of the 100 GB, 60 GB is still in use at a full cycle. That is a stated figure for the worked heap.

100 GB - 60 GB = 40 GB reclaimed by a full cycle.

The pause budget is about 100 milliseconds. A cycle that needs more time must split its work or move it beside the program.

API and data

The collector has no network API. Its surface is the runtime contract between the program and the memory manager.

The allocation operation takes a size. It returns a pointer to free space, and it triggers collection when free space runs low.

The runtime tells the collector where the roots are. Roots are the starting references, in globals, stacks and registers.

An object header holds a size, a type pointer and a mark bit. The mark bit records whether the current cycle has reached the object.

Type data lists which fields inside an object are references. The collector follows only those fields when it walks the object graph.

High-level design

The allocator hands out space from free regions of the heap. It keeps the common case fast, a pointer move and a size check.

The marker walks from the roots through references. Everything it reaches counts as in use for this cycle.

The sweeper scans the heap after marking. Unmarked objects join the free lists for reuse.

Mark and sweep is this two-phase method, where marking finds the living objects and sweeping frees the rest. The two phases share one cycle and one mark bit per object.

A scheduler decides when cycles run. It watches the allocation rate and the free space left.

Deep dive: mark and sweep step by step

A cycle starts by clearing every mark bit. The roots are marked first, since the program can still reach them directly.

The marker follows each marked object's references. Every newly reached object gets marked and queued for its own scan.

The walk ends when no unmarked object is reachable from a marked one. Reachable is the whole test, and the walk computes it exactly.

The sweep then passes over the heap once. Marked objects keep their space and lose the mark, ready for the next cycle.

Unmarked objects become free space. Neighbouring free objects merge into one larger free region.

Deep dive: cycles and counting

A simple rival method counts references to each object. A count of zero means the object can be freed.

Two objects can point only at each other. Each count stays above zero, yet no root can reach either object.

Counting leaks such cycles forever. Marking from the roots handles them, because reachability ignores self-contained loops.

Counting frees objects the moment they die, with no pause. Mark and sweep trades that smoothness for exact handling of cycles.

Pauses and parallel work

The plain design stops the program during marking and sweeping. That stop is the pause, and the budget is about 100 milliseconds.

A big live set makes one full stop too long. The cycle then splits into short pieces between pieces of program work.

Split marking has a hazard. The running program can move a reference behind the marker's back.

A write barrier is a small check on every reference write while marking runs. It records moved references so the marker revisits them.

The barrier costs a little on every write. It buys pauses far below one long stop.

Fragmentation

Freeing scattered objects leaves free holes between living ones. Total free space can look healthy while no hole fits a large new object.

Free lists keep holes by size, so the allocator finds a fitting hole fast. Small leftovers split off and stay listed.

A compacting cycle moves living objects together and leaves one large free region. Moving costs time and updates every reference to a moved object.

Compaction therefore runs rarely, when holes grow severe. Sweeping handles the normal rhythm.

Evaluation and trade-offs

Mark and sweep is simple, exact and cycle-safe. Its costs are pauses and a heap scan that touches every object.

Barriers and split cycles shrink the pauses. They add steady small costs to the program's own writes.

Never freeing live memory outranks every speed goal. Garbage collection earns trust by making that error impossible by construction.

The worked numbers set the rhythm. At 1 GB per second of new objects, the collector is a core part of the program, never a background extra.

Scale at a glance