Survivors

A collector that reclaims a megabyte of garbage has not done a megabyte of work. It has done work proportional to the objects that survived — it never touches the dead ones at all, it just stops regarding their space as taken. That one fact decides nearly every argument in garbage collection, and it is easier to measure than to argue about.

So: three collectors, one program. Same seed, same objects, same order, same address space. Every word any of them touches is charged to a line item, and the pause work is kept apart from the tax the program pays while it runs.

The two costs, and where they cross

Divide each collector’s pause work by the words it reclaimed. For a heap of H words with survival rate s and mean object size a:

copying      2sH / (1−s)H                     = 2s / (1−s)
mark–sweep   (sH + H/64 + (1−s)H/a) / (1−s)H  = (s + 1/64 + (1−s)/a) / (1−s)

Copying traces the survivors and moves them: two touches per live word, none per dead one. Mark–sweep traces the survivors, reads a mark bitmap over the whole heap, and then visits every corpse individually to put it on the free list. That last term is the whole difference, and it does not go away:

As s → 0, copying’s cost goes to zero. Mark–sweep’s goes to 1/a + 1/64 and stops there. With cons cells, a sweeping collector can never get below 0.311 words of work per word reclaimed, no matter how much memory you buy. That is the argument for a copying nursery, stated as a number.

Below the crossing copying is doing less work; above it, sweeping is. And smaller objects widen the band where copying wins, because small objects mean more corpses per byte, and sweeping is billed per corpse.

Nobody tunes the survival rate. They tune the heap.

s is not a property of your program. It is the live set divided by the space you were willing to leave empty, and it only moves when the heap does. Same program, same live set, eleven heap sizes:

Copying falls by more than two orders of magnitude across that range and is still falling when the table runs out. Mark–sweep falls by 7× and then flattens against its floor, with nothing left to buy. Throughput in a collected runtime is a purchase, and what you are buying is emptiness. (The two largest heaps have no mark–sweep row because it collects fewer than three times in this allocation budget — too few to average.)

Note the other half of that table: at the same total memory, copying’s survival rate runs about double mark–sweep’s, because only half the address space is ever available to fill. A copying collector does not get the heap you gave it. It gets half, and pays for the other half in a higher s.

And it still wins on work at the right-hand end — 0.213 against 0.239 at 16k words, despite sitting at twice the survival rate — because the floor is worth more than the half-space costs once memory is generous. What actually argues against copying at that size is not the work. It is the address space, and the hole in the next section.

Which is the whole argument for the generational arrangement, and it is not a compromise — it is putting each collector on the side of the crossing where it wins. Copy the nursery, where survival is around 10% and the floor would hurt. Sweep the old generation, where survival is high and copying would be absurd.

What the nursery actually buys

The same run, three ways, at 16,384 words — and total work is close to a wash:

Generational does 9% more total work than mark–sweep and cuts the typical pause by 3.8×. It cuts the p99 by 1.3×. The red bars in the pauses view are the majors, and a major is still a full collection over the whole old space — so the tail is more or less exactly where it was. The nursery buys the median. It does not buy the tail, and nothing in this design could.

The price is on the mutator, continuously: 9,687 write-barrier checks over the run, one on every pointer store into a heap object. What they buy is the remembered set — the old→young pointers a minor collection must treat as roots. It peaked at 91 entries, standing in for scanning all 12,288 words of old space, 135× bigger. That ratio is the whole bet, and it is the reason the barrier is worth its instructions.

The hole you own and cannot use

Mark–sweep never moves anything, so its free space is wherever the dead happened to lie. At 16,384 words with the live set holding about half of it, after 70–80 collections:

9.5k words free — 58% of the heap — and with cons-cell-sized objects not one of the 1,252 pieces could hold a 512-byte array. Worst point in the run: 99.6% of free space out of reach of any single object. The run does not crash; it just quietly stops being able to allocate anything larger than its own rubble, which is the failure mode that looks like a memory leak and is not one.

A copying collector cannot reach this state at all. Compaction is not a feature it has; it is a consequence of moving every survivor into a fresh space, and free memory is therefore always exactly one block. It pays for that with the half-space standing empty — which, per the table above, is a higher survival rate and so a higher cost per word. There is no free move anywhere in this subject.

Reading it

Four views, 1 2 3 4. space plays and pauses, r resets, [ and ] step the heap size.

• heap — the live simulation. Three address spaces filling and being collected, cell per word. Garbage is the dark red: it is most of the heap most of the time, which is the normal state of a collected runtime and not a problem. Watch survival at collection differ between the first two panels at the same heap size.
• headroom — the two curves, the crossing, and the floor. The points are measured runs, one per heap size; the curves are the same accounting in closed form, so agreement means the simulator bills what the formula says, not that the formula is independently confirmed.
• holes — fragmentation. Total free against the largest single block, and every free block in the list sorted biggest first, with a 64-word request drawn across it.
• pauses — every collection in one run as a bar. Majors in red.

tenure moves how much of the allocation survives; sizes moves the mean object, and so the crossing; nursery moves where the generational split sits.

Reuse

src/survivors.js is a framework-free ES module. No DOM, no timers, no rendering.

• createSim({policy, heapWords, tenure, sizeMix, nurseryFrac, link, spineSlots, seed}) → a stepping simulator. .step(), .run(n), .refreshLive(), .cells (one byte per word: FREE / LIVE / DEAD), .regions, .freeBlocks(), .freeStats(), .bill, .survival, .stats.
• POLICIES / POLICY_ORDER — mark-sweep, copying, generational.
• SIZE_MIXES / meanSize(key) — the object-size distributions.
• modelCost({s, avgSize}), crossing({avgSize}), copyPerReclaimed(s) — the closed forms, so a claim can be checked against the counters.
• sweepHeadroom(...), fragmentationRun(...), pauseRuns(...) — the three batch experiments the views are built on, each returning plain data.
• quantiles(array), rng(seed), fmtWords, fmtBytes, pct.

Liveness is computed, not scheduled: objects hold real references, a root set and one long-lived spine hold the graph, and marking is an actual traversal. The three policies consume the same number of random draws per step in the same order, so a seed names one program and all three collectors run it.

Gotchas

• The cost unit is a word touched, not a nanosecond. Copying a word and reading a bitmap word are charged the same, and they are not the same on real hardware — a copy writes, a bitmap scan is sequential and cache-friendly, and a sweep’s free-list writes scatter. The ranking of the two curves is robust; the exact crossing is not. Changing BITMAP_WORDS_PER_HEAP_WORD moves it.
• trace charges an object’s whole size. A real mark phase reads the header and the ref slots, not the payload. This overcharges tracing for objects with few pointers, which flatters the sweeping collector slightly.
• References are object ids, so moving costs no explicit fixup pass. The trace charge is standing in for the pointer rewriting a real copying collector does while scanning.
• The free list is next-fit over one address-ordered list. It is a real policy and a common one, but a production allocator uses size-class bins and pays closer to a bump pointer. Read allocation, words/alloc as a fragmentation reading — it climbs as the list fills with slivers — rather than as the number your runtime pays.
• The nursery is copy-on-first-survival. No aging, no survivor spaces, no tenuring threshold; anything alive at a minor collection is promoted. Real nurseries hold objects back for a generation or two, which lowers promotion and raises minor cost.
• A major collection here is a stop-the-world full mark–sweep. Every modern tail-latency story — concurrent marking, incremental sweeping, region-based collection with evacuation pauses — is about attacking exactly the red bars this does nothing about. The p99 row is the problem statement, not a result.
• The write barrier is charged, not implemented faithfully. One check per pointer store into a heap object, with the remembered set as an exact (object, slot) set rather than card marks; card tables trade precision for a smaller barrier and a bigger scan.
• Survival is measured, not set. The tenure slider moves how much is retained; what comes out at a collection depends on the heap size too, which is the point of the headroom view. Don’t read the slider as the x-axis.
• Fragmentation needs a tight heap, so fragmentationRun sizes the long-lived structure to fill about half the space. A free list swimming in room has nothing to show.
• The demo bundles its own copy of survivors.js (self-contained by contract); re-copy after editing src/.
• node scripts/screenshot-demo.mjs [out] [--view=heap|headroom|holes|pauses] [--heap=] [--mix=] [--tenure=] [--nursery=] [--words=] [--w= --h=] regenerates thumb.png and media/ through site/scripts/lib/chromium.mjs, running the simulation to a fixed word count so a capture is reproducible.