skip to content

You clear one reference into a large object graph and the next collection frees nothing — why?

level: middleimportance: should knowfreq 45%

answer

  1. existence of a path, not a count
  2. closure over the whole root set
  3. one edge of several changes nothing
  4. cut mid-chain frees everything below
  5. marking order cannot change the result

basics

~20 s

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.

solid answer

~50 s

The collector does not ask how many references an object has; it asks whether *some* path of references from *some* root arrives at it. That makes the live set a transitive closure, and closures are insensitive to losing one edge unless that edge was the only way in. So clearing a single reference frees an object exactly when, after the clear, no root-to-object path remains — and frees the graph behind it only for the nodes that had no other path either. The practical reformulation is: stop thinking about the object and start thinking about the **set of remaining paths from roots to it**. An object reached from two independent structures needs both edges cut. An object reached through a long chain is freed by cutting any single edge on that chain, because the closure walk stops there and never reaches the rest.

code

pseudocode · 19 lines
pseudocode
worklist = empty

// seed: the only references findable without tracing
for each r in roots:                      // stacks, registers, globals, handles
    obj = target_of(r)
    if obj != none and not marked(obj):
        mark(obj)
        push(worklist, obj)

// drain: take the transitive closure
while worklist is not empty:
    obj = pop(worklist)
    for each ref in outgoing_references(obj):
        target = target_of(ref)
        if target != none and not marked(target):
            mark(target)
            push(worklist, target)

// every object still unmarked is reachable from no root

go deeper

for a junior

Remember the shape of the rule: if any chain of references starting at a root arrives at the object, it stays. A chain, not a count.

for a middle

Be able to walk the marking loop out loud — seed from roots, follow outgoing references, stop when nothing new is marked — and use it to say precisely when clearing one reference does and does not free memory.

for a senior

Turn it into a method: enumerate the remaining paths from roots, decide which ones you meant to exist, and note that what gets released is the closure behind the cut, not the single object you were looking at.

for a principal

The design lesson is about ownership of edges. If several structures may reference the same graph, no single owner can reason about its lifetime, and retention becomes an emergent property of the system rather than a decision.

## Closure, not counting The rule a tracing collector applies is short: an object is live if there exists **at least one path** of references from **at least one root** to it. Existence, not quantity. That is what makes the live set a *transitive closure* of the root set under the "references" relation, and it explains the behaviour that surprises people — removing a reference usually does nothing, and occasionally frees an enormous amount. Two consequences fall straight out of the definition: - **Cutting one of several paths frees nothing.** The other path still witnesses reachability. - **Cutting the only path frees everything that had no other path.** The walk never arrives at that subgraph, so none of it is marked. ## What the walk actually does 1. Every root is examined and the objects they name are marked and queued. 2. Each queued object's outgoing references are followed; anything not yet marked is marked and queued. 3. When the queue drains, marking is complete: the marked set is the closure. Because an object is marked at most once, the walk visits each reachable object exactly once no matter how many references point at it. An object with a thousand inbound edges costs the same as one with a single edge. ## Why one edge rarely matters Think of the graph rather than the object: | After you clear the edge | Paths from roots remaining | Result at the next collection | |---|---|---| | It was the only path in | None | Object and its exclusive subgraph reclaimed | | Another structure still reaches it | At least one | Nothing is reclaimed | | It was mid-chain, upstream still rooted | The chain above only | Everything below the cut is reclaimed | | It was mid-chain, upstream already unreachable | None either way | The edge was irrelevant; that region was already garbage | The fourth row is the one that catches people during cleanup work: painstakingly nulling fields inside a structure that is itself already unreachable changes nothing, because unreachability is inherited by the whole closure in one step. ## Order does not matter, cost does Any complete traversal computes the same closure. Depth-first, breadth-first, several marking threads sharing work — the marked set is identical, because "a path exists" does not depend on the order you look for it. What traversal order *does* change is locality and how deep the worklist grows, which is an implementation concern rather than a semantic one. If two runs of the same program at the same point ever disagreed about what is reachable, that would be a defect, not a scheduling difference. ## The question to ask when memory will not go away The useful question is never "why is this object still here?" — the object has no say. It is: - **Which paths from roots still reach it?** Enumerate them; there is at least one, or it would be gone. - **Which of those paths did you intend to exist?** Usually one is deliberate and the others are incidental. - **What is the shortest path, and what is at its far end?** The first root on the path is the thing whose lifetime the object has inherited. - **Is the retained cost the object or its closure?** Almost always the closure: a small reachable node can anchor a graph thousands of times its own size. ## A note on where the boundary of this reasoning sits Closure reasoning tells you *whether* something is reachable and *what else comes with it*. It says nothing about how much space a particular subgraph is responsible for when several graphs overlap and share nodes — attributing shared structure to one owner is a separate analysis with its own machinery. Keep the two apart: reachability is a yes-or-no question over paths, and it is the one that decides whether the memory comes back at all.

  • An object is reached by two independent structures. What has to change for it to be freed?
    Both edges must go. Reachability asks only whether some path exists, so as long as either structure is itself reachable and still references the object, the object is marked. Cutting one path is measurable progress only if you then cut the other, or if the structure holding it becomes unreachable itself.
  • Does it help to null out fields inside an object you are discarding?
    No, when the object itself is already unreachable. Unreachability propagates over the closure in one step: nothing inside it will be marked, whatever its fields point at. Clearing internal fields matters only when the containing object stays reachable and you want the things it points at released.
  • Can two runs of a marking phase disagree about which objects are reachable?
    Not for the same heap state. Closure is order-independent, so depth-first, breadth-first and parallel traversals all produce the same marked set. Traversal order affects memory locality and worklist depth, never the outcome; a disagreement would indicate a defect in the traversal, not a legitimate choice.

saying these in an interview costs you the question

  • Thinks the collector counts references into an object
  • Believes clearing any one reference makes an object collectable
  • Says traversal order changes which objects survive
  • Assumes nulling fields inside unreachable objects helps
  • Confuses the object's own size with what it retains