Garbage Collection

A root is a reference the collector can find without tracing anything first — a running thread's stack slot or register, a global table entry, a handle registered by code outside the collected heap. Everything the program can still touch starts at one of them.

Black means already scanned, so the marker will not revisit it on its own. A reference from a black object to a white one is therefore a live object the trace never reaches — and would wrongly reclaim.

Many brief suspensions rather than one long one. The collector marks a bounded slice of the heap, hands control back, and resumes later from where it stopped. The longest pause shrinks; total collection work usually grows.

Tracing cost follows the live set, not the free space, while each cycle reclaims everything above the live set. Extra headroom therefore spreads the same tracing work over far more allocation before the next cycle is needed.

Collection work is paid in one of three currencies: spare memory, application throughput, or pause time. Buying one corner spends another - spare heap makes cycles rarer, and a tight pause target adds barrier work to ordinary program execution.

Survival rate decides it. A tracing collector pays for live objects, not for garbage, so a young area that is a few percent live reclaims almost all of itself for very little work, while a mature area that is mostly live traces a great deal to reclaim little.

Because it decides liveness by reachability, not by usefulness: if any chain of references from a root still leads to the object, it stays. Whether the program will ever read it again is not a property the collector can compute.

Sweeping walks every block in address order, live and dead alike, to rebuild the free list, so its cost tracks heap size. Evacuation follows references and copies only survivors, so its cost tracks the live set, not the garbage.

A weak reference is not a path that keeps its target alive. Once no strong path reaches the object, the collector is free to reclaim it and to clear the weak reference, which then reads as empty.

Collection is triggered by memory pressure, not by handle pressure. A small object guarding a scarce handle creates almost no pressure, so the handle pool can run dry while the heap is still comfortable and the hook has not run.

Marking is allowed to err in one direction only. Keeping a dead object costs a cycle's worth of memory and is collected next time, while freeing a live one corrupts the program — so barriers over-approximate liveness on purpose.

Cost on the hot path. A reference store happens constantly, so the record is made as cheap as a shift and a byte write: mark the block containing the field dirty. Precision is paid back later, by scanning dirty blocks for references into the young area.

Liveness is the transitive closure over the whole root set: an object survives if any path from any root still reaches it. Clearing one edge frees only what that edge was the sole path to.

The table holds its values strongly, so a value that points back at its own key keeps that key strongly reachable. The weak key is then never cleared, the entry never leaves, and the cache grows without bound.

The old location keeps a forwarding record pointing at the copy, and a read barrier on reference loads detects it, follows it, and writes the corrected reference back into the slot it came from, so the program only ever works on the current copy.

Pauses are rare and arrive whole. They miss most requests entirely and land in full on a few, so an average spreads a concentrated cost evenly and describes nobody's experience; the tail keeps the concentration users actually feel.

Short pauses come from doing collection alongside the running program, which puts a check on the program's own reference accesses, repeats work the program invalidates mid-cycle, and consumes processor time the application would otherwise use.

The young area is collected when it fills, so doubling the allocation rate halves the interval between collections. Objects whose lifetime is unchanged now span a larger share of that shorter interval, so more of them are still live when the collector arrives, and more get promoted.

A registered handle. Code outside the collected heap holds an opaque handle that the runtime records in a table, and that table is scanned as a root set. A raw address held abroad is invisible to the collector and keeps nothing alive.

Semispace copying, because it touches only the 5% that survives and abandons the rest in one step. Its price is reserved space able to hold every survivor. A sweep is charged for the whole heap; sliding compaction adds address-computing and pointer-rewriting passes on top of marking.

Make the invariant checkable instead of hoping a test hits the race: scan for black-to-white edges at the end of a cycle, compare against a trace taken with the program stopped, and prove every reference store reaches the barrier.

Treat it as one inequality: allocation rate multiplied by cycle duration must stay under the free space available when a cycle starts. Measure all three at peak, then pick the lever that fixes the ratio at the peak you must survive.

Start from the peak live set measured after a collection, choose a multiple of it based on which corner the service can afford to lose, then price the choice: headroom is per replica, so each extra gigabyte is two hundred across the fleet.

Decide on evidence, not on the range: the copy path only pays where the survivor share is genuinely low, and it must be funded with reserved space in every cycle, including the ones that sweep. Measure the survivor share per cycle, cost both finishes on real traces, and prefer separating workloads over a collector with two paths.

Rarely, and only for values that are cheap to rebuild and genuinely hard to size. The strength delegates eviction to a collector that knows heap pressure but nothing about hit rate, entry cost or fairness, so a fleet service should state a bound instead.

Because a concurrent trace measures reachability against a moving target. An object that was reachable when the collector saw it, and died a moment later, is already marked and survives the cycle. That unreclaimed dead memory is floating garbage.

A black-to-white edge is safe when the white target is still reachable from some grey object through a chain of white objects — the weak tri-colour invariant, which requires only that the pending frontier can still walk to the target.

Collector work per allocated byte is the live set divided by the free space, and free space is the quantity being removed. As the denominator shrinks toward zero the ratio grows without bound, so the last gigabyte taken away costs far more than the first.

One survival is weak evidence of a long life: an object allocated just before a collection survives on timing alone. Requiring several survivals filters those out, so the mature area receives objects that have genuinely proved long-lived rather than unlucky ones.