skip to content

How does a cycle collector using trial deletion decide that a group of mutually referencing objects is garbage without tracing from roots?

level: seniorimportance: nice to knowfreq 26%

answer

  1. work locally, never from the roots
  2. candidates: a decrement that stopped above zero
  3. subtract the group's own edges once each
  4. survivors above zero get restored
  5. left at zero means held only from inside

basics

~20 s

It subtracts the group's own internal references from its members' counts. Anything left above zero is referenced from outside and is restored; anything left at zero was held only from inside the group, and is freed.

solid answer

~50 s

Trial deletion tests a group locally instead of walking the whole graph. Only an object whose count was decremented to a value **still above zero** can have turned a live ring into a garbage one, so those objects are buffered as candidates: a decrement to zero frees normally, and a count that never fell has lost nothing. For each candidate the collector walks the subgraph reachable from it and subtracts one from the target of every edge it crosses, which simulates deleting every reference that originates inside the group. Then it rescans. An object still above zero must be held by a reference from outside the group, so it is restored — the subtractions are added back for it and everything it reaches. Whatever is still at zero was kept alive only by references inside the group, and is freed. This is the Bacon-Rajan trial-deletion scheme.

code

pseudocode · 31 lines
pseudocode
collect(candidates):
    for each c in candidates: trial_delete(c)
    for each c in candidates: rescan(c)
    for each c in candidates: free_condemned(c)

trial_delete(x):
    if colour(x) != VISITED:
        colour(x) <- VISITED
        for each t in outgoing(x):
            count(t) <- count(t) - 1     // subtract this internal edge once
            trial_delete(t)

rescan(x):
    if colour(x) == VISITED:
        if count(x) > 0:                 // held from outside the group
            restore(x)
        else:
            colour(x) <- CONDEMNED
            for each t in outgoing(x): rescan(t)

restore(x):
    colour(x) <- LIVE
    for each t in outgoing(x):
        count(t) <- count(t) + 1         // put the subtraction back
        if colour(t) != LIVE: restore(t)

free_condemned(x):
    if colour(x) == CONDEMNED:
        colour(x) <- LIVE
        for each t in outgoing(x): free_condemned(t)
        free(x)

go deeper

for a junior

Know that a counted system can ship a second mechanism whose whole job is finding rings, and that it works by subtracting a group's own references rather than scanning the entire heap.

for a middle

Be able to walk the passes on a small ring: subtract the internal edges once each, look at what is still above zero, restore that part and everything it reaches, free the rest.

for a senior

Show that you know the preconditions — exact counts, a still subgraph, a real restore pass — and say why the candidate buffer keeps the work proportional to recent decrements rather than to the heap.

for a principal

Judge whether the machinery earns its complexity. It reclaims rings without needing roots enumerated, and charges repeated traversals, a quiescent point or a barrier, and a failure mode that frees live memory whenever the counts are not exact.

## Why a local test is possible at all A reachability-based collector answers "is this object garbage?" by starting from the roots and walking outward, which means enumerating every root and touching the whole live set. Trial deletion answers a narrower question — "is this *group* held only from inside itself?" — and that question can be settled with information the group already carries, because a reference count is a complete census of the edges pointing at an object. If you know how many of those edges come from inside the group, the remainder is the number that come from outside. Subtracting the inside edges is how you find out. ## Step one: choosing candidates Searching from every object would cost more than tracing. The candidate rule narrows it sharply, and it follows from one observation: a live ring can only become a garbage ring when a reference into it disappears. - A decrement that reaches **zero** frees the object immediately and cascades along its outgoing edges, so it cannot have left a garbage ring behind. - A count that has **not fallen** means no reference was lost, so nothing about that object's reachability changed. - A decrement that lands **above zero** is the only remaining case, and it is exactly the event that can orphan a ring. So the counting fast path buffers an object whenever a decrement leaves it above zero, and the collector searches only from that buffer. The work is therefore proportional to recent decrement activity and to the subgraphs those candidates reach — not to the size of the heap. ## Step two: the three passes | pass | what it does | what it leaves behind | |---|---|---| | trial delete | walks the subgraph from a candidate, subtracting one from the target of each edge crossed, visiting each object once | counts that reflect only references from outside the group | | rescan | looks at each visited object: above zero means externally referenced, zero means internally held | a set of survivors and a set of condemned objects | | restore and collect | adds the subtractions back for every survivor and everything it reaches; frees what is still at zero | a correct set of counts, and the ring reclaimed | Marking each object as it is first visited is what makes the arithmetic right: each internal edge is subtracted **exactly once**, no matter how many paths lead to the object holding it. ## Why the restore pass is not optional The subtraction is a hypothesis, not a decision. Consider a candidate subgraph containing a ring plus one object that some live code outside still holds. After the trial deletion that object's count is above zero, because the outside reference was never subtracted — but everything the object points at *was* subtracted, and some of those targets may now read zero even though they are perfectly alive. Restoring therefore has to propagate: add the subtractions back for the survivor, then for everything reachable from it, marking as you go so no edge is added back twice. Skip this and the collector frees live objects on a later pass, which is a far worse failure than the leak it was built to fix. ## What it costs, and what it assumes - **Repeated traversal.** An object can be walked in the trial-delete pass, again in the rescan, and again in the restore, so the constant factor per object is several visits. - **A bad candidate is expensive.** A candidate near the top of a large structure drags the whole structure through all three passes, and the cost then approaches that of tracing that structure. - **The counts must be exact.** Schemes that defer or coalesce updates give approximate counts between flushes, and trial deletion over approximate counts can condemn live objects. - **The subgraph must be still.** If another thread links or unlinks an edge mid-pass, a restored count can end up wrong in either direction: too high and the ring leaks anyway, too low and something live is freed. Implementations either stop the mutator at a quiescent point or add a barrier that records edge changes made during the pass. - **No roots are needed.** This is the property that makes the technique attractive in settings where enumerating every root precisely is impossible. ## The alternative shape The other way to reclaim rings in a counted system is to keep a reachability pass in reserve: run a full walk from the roots occasionally and free everything it did not visit. It is simpler and it catches every ring, including ones with no good candidate, but it charges a pause proportional to the live set and it requires exactly the precise root enumeration that trial deletion avoids. Which of the two a system can use is usually decided by whether those roots can be found at all, not by which algorithm is more elegant.

  • Why is a decrement to a non-zero value the candidate signal?
    It is the only event that can turn a live ring into a garbage one. A decrement to zero frees the object at once and cascades along its edges, and an object whose count never fell has lost no reference, so its reachability is unchanged. Buffering just those objects keeps the search proportional to recent activity.
  • What does trial deletion cost compared with a full reachability pass?
    It touches the subgraphs reachable from buffered candidates rather than the whole live set, and it needs no root enumeration. The bad case is a candidate near the top of a large structure: the walk, the rescan and the restore then approach the cost of walking that structure, and each object is visited several times.
  • What must be true of the graph while the collector runs?
    The counts must be exact and the edges must not move underneath it. If another thread links or unlinks mid-pass, a restored count can come out wrong in either direction, leaking the ring or freeing something still referenced. Implementations either quiesce the mutator or add a barrier that records edge changes during the pass.

saying these in an interview costs you the question

  • Describes it as an ordinary walk from the roots, just run less often
  • Thinks the objects whose counts survive the subtraction are the ones freed
  • Omits the restore pass and leaves live objects with wrong counts
  • Treats every object as a candidate instead of buffering decrements above zero
  • Assumes it stays correct while other threads mutate the same edges
  • Says it works fine on counts that are deferred or coalesced