# Mark & Sweep

Software garbage collection made physical: a 64\-cell heap on a workbench where real mark\-sweep, compaction and generational copying run before your eyes

By Numa

Topic: Computing, AI & Electronics

[Open the interactive Jig](https://ask.jig.com/j/a164Rccxp2Ku)

## Guide

### 1. The heap, running

This plate is a 64\-cell heap\. Porcelain blocks are objects, copper cables are pointers, and the trays on the left are the roots: stack frames and globals\. Watch a whole collection cycle run at speed, then take it apart one phase at a time\.

Click any object to inspect its address, colour and references\.

### 2. new is a pointer bump

Right after a compaction, free space is one contiguous run\. Allocation compares top plus the object size with the limit, returns top and moves top forward\. No search, no free list, no lock on a thread\-local buffer\.

Microsoft describes \.NET heap allocation as almost as fast as allocating on the stack\.

### 3. Alive means reachable

The collector never asks whether you will use an object again\. It asks whether a chain of pointers leads to it from a root\. Return from parse\(\) and its whole subgraph is cut loose, three\-object cycle included\.

Reference counting would keep that cycle forever: each member still has a count of one\. A tracer simply never reaches it\.

### 4. Tri\-colour marking

White: not seen yet\. Grey: reached, fields still to scan, waiting on the mark stack\. Black: reached and scanned\. Pop a grey object, shade its white children grey, blacken it, repeat until the stack is empty\. Whatever is still white is garbage\.

Dijkstra, Lamport, Martin, Scholten and Steffens, 1978\. The strong invariant: no black object points to a white one\.

### 5. The lost object

Now the program keeps running while we mark\. It stores a pointer to white C into black A, then clears the only grey path to C\. The marker never rescans A, so C stays white and is freed while A still points at it\. Pick a write barrier and watch again\.

Dijkstra shades the new target on a store\. Yuasa shades the overwritten one, a snapshot at the beginning\. Go has run both together since 1\.8\.

### 6. Sweep

The sweeper walks the heap in address order\. White blocks are reclaimed and threaded onto a free list; black blocks flip back to white for the next cycle\. Nothing moves, so every surviving address stays valid\.

The price is fragmentation: plenty of free cells, scattered between the survivors\.

### 7. Compact

A four\-cell array needs a contiguous run, and there is none\. Sliding compaction makes three passes: compute each live object's forwarding address, rewrite every pointer to it, then slide the objects down in address order\.

This is the Lisp 2 algorithm\. Order is preserved, neighbours stay neighbours, and allocation is a pointer bump again\.

### 8. Most objects die young

Split the heap: a nursery called eden, two survivor spaces and an old generation\. Eden fills fast, and most of it is already dead\. A minor collection copies the few survivors out with Cheney's algorithm, then resets eden in one move\.

The scan pointer chases the free pointer through to\-space: the copies themselves are the work queue\. C\. J\. Cheney, 1970\.

### 9. Old points to young

A minor collection traces only the young generation, so pointers from old objects must be found another way\. A write barrier dirties a card when an old object is stored into, and the next minor collection scans only the dirty cards\. Survivors age with each copy until they are promoted\.

G1 cards cover 512 bytes\. HotSpot promotes after at most 15 copies, because the age is a 4\-bit field in the object header\.