skip to content

Why does a collector that marks while the program keeps running reclaim less than the heap's true garbage at cycle end?

level: middleimportance: nice to knowfreq 28%

answer

  1. reachability judged over a window, not an instant
  2. marked early, died later, still kept
  3. new objects counted live for this cycle
  4. bounded and cleared by the next cycle
  5. flat post-collection floor, unlike a leak

basics

~20 s

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.

solid answer

~50 s

A concurrent trace cannot take an instantaneous photograph of the heap, so it works against reachability as it stood when each object was visited. Two sources of survivors follow. First, an object marked early in the cycle that becomes unreachable before the cycle ends is still marked, so it is kept. Second, objects allocated during the cycle are normally counted as live rather than traced, because tracing them would let the program keep generating work and the cycle might not terminate. Both classes are genuinely dead and both are reclaimed by a later cycle, so this is a delay, not a leak. The practical consequence is capacity: a concurrent collector's reported live set overstates the real one, and the heap must carry headroom for at most roughly one cycle's worth of floating garbage on top of the true live set.

go deeper

for a junior

Remember the idea rather than the term: a collector that looks while the program keeps working can decide something is in use just before it stops being used, and that memory waits for the next round.

for a middle

Explain the two sources - objects marked before they died, and objects allocated mid-cycle - and why counting new allocations as live is what lets the cycle terminate at all.

for a senior

Use it when reading capacity: post-collection occupancy is an upper bound on the live set, and a flat elevated floor is normal while a climbing floor is a leak.

for a principal

Treat it as part of the memory budget you sign off: a low-pause collector is paid for in headroom, and sizing to the live set alone will fail under a spike.

## Reachability is measured against a moving target A stop-the-world trace has a luxury a concurrent one does not: the heap does not change while it looks. Reachability is evaluated once, against a single consistent state, and every object not reached is definitively dead at that instant. A collector that marks while the program keeps running has no such instant. It visits objects over a window of time, and the program is rewriting the graph throughout that window. The consequence is a deliberate, well understood **overestimate** of what is live. The collector guarantees the safe direction of the error: anything genuinely live is retained. It does not guarantee the other direction, so some dead objects are retained too. Those are **floating garbage**: memory that is unreachable in fact, but is not reclaimed by the cycle that was running when it died. ## Where floating garbage comes from - **Objects that died after being marked.** The collector reached the object while a reference to it still existed, marked it, and moved on. The program then dropped the last reference. Nothing re-examines an object once it is marked, so it survives to the end of the cycle. - **Objects allocated during the cycle.** New objects appear in a part of the graph the trace may already have passed. The usual treatment is to count them as live for this cycle outright rather than trace them. - **Objects retained by a conservative barrier decision.** When the program rewrites a reference mid-trace, the runtime must keep whatever might have been reachable through the old or the new edge. Erring toward retention keeps the trace correct and keeps some dead objects alive. - **Whole subgraphs.** Retaining one dead object keeps everything only it references, so a single retained root of a dead structure can hold a large amount of memory for a cycle. ## Why the collector does not simply keep tracing The obvious fix - keep marking until nothing more changes - fails for a plain reason: the program keeps producing new work. If every store that creates an edge feeds the collector, and the program stores faster than the collector traces, the worklist may never drain and the cycle may never end. A collector that cannot promise to finish cannot promise to give memory back. Bounding the cycle against a fixed notion of reachability is what makes termination provable, and accepting floating garbage is the price of that bound. This is also why a shorter cycle produces less floating garbage: the window in which a marked object can die is exactly the remaining length of the cycle. ## What it is and what it is not | Category | Reachable now? | Reclaimed by this cycle? | Reclaimed later? | |---|---|---|---| | Live data | Yes | No | Not while it stays reachable | | Ordinary garbage | No | Yes | Already gone | | Floating garbage | No | No | Yes, by a following cycle | | Leaked memory | Yes, through a reference nobody intended | No | No, not until the code changes | The crucial line is the last two rows. Floating garbage is bounded, self-correcting and repeats at a steady level; a leak grows without bound because the object really is still reachable. Confusing them sends an investigation in the wrong direction. The way to tell them apart is the **trend across cycles**: measure occupancy immediately after each collection and watch several cycles. Floating garbage makes each post-collection floor slightly higher than the true live set but flat over time; a leak makes that floor climb cycle after cycle. ## What it costs and what to do about it 1. **Size for it.** The heap must hold the true live set plus roughly one cycle's worth of floating garbage plus whatever the program allocates during a cycle. Sizing a concurrent collector against the live set alone is a common capacity error. 2. **Expect noisier measurements.** Occupancy readings taken after a concurrent cycle include floating garbage, so live-set figures derived from them are an upper bound, not the real number. 3. **Shorten cycles if the volume hurts.** Less time between the marking of an object and the end of the cycle means fewer objects can die in that window. This usually means running cycles more often, which costs processor time. 4. **Do not chase it as a bug.** A steady few percent of retained dead memory is the designed behaviour of every collector that traces without stopping the program. A service with a hard tail-latency budget is precisely the one that chooses a concurrent trace, so it is precisely the one that must budget memory for floating garbage. The two are the same decision seen from different sides: the pause is bought with headroom.

  • How do you tell floating garbage from a genuine leak in a running service?
    Watch the occupancy floor immediately after each collection over many cycles. Floating garbage lifts that floor slightly above the true live set but keeps it flat, because each cycle clears the previous cycle's survivors. A leak makes the floor climb steadily, because the objects really are reachable and no cycle will ever reclaim them.
  • Does a longer concurrent cycle produce more floating garbage?
    Generally yes. An object becomes floating garbage if it dies after the collector marked it and before the cycle ends, so the exposure window is the remaining length of the cycle. Stretching the cycle widens that window for every object already marked, and also admits more allocations that are counted as live for the cycle.
  • Why not trace the objects allocated during a cycle instead of assuming they are live?
    Because the program can create them faster than the collector can trace them, so the worklist might never drain and the cycle might never terminate. Counting them as live for this cycle gives the trace a fixed job and a guaranteed end; they are traced normally in the following cycle, when most have already died.

saying these in an interview costs you the question

  • Calls floating garbage a memory leak
  • Thinks a concurrent cycle reclaims all unreachable objects
  • Believes marked objects are re-examined when references are dropped
  • Assumes post-collection occupancy equals the true live set
  • Says cycle length has no bearing on how much survives