skip to content

What does deferred reference counting remove from the fast path, and what does it need in exchange?

level: seniorimportance: nice to knowfreq 28%

answer

  1. most references are short-lived locals
  2. count only what objects hold
  3. zero no longer proves dead
  4. candidate list plus a root scan
  5. throughput bought with promptness

basics

~20 s

Deferred counting leaves the most frequently changed references, those in thread stacks and registers, out of the count, so the fast path stops updating it. In exchange a zero count no longer proves death: the roots must be scanned first.

solid answer

~50 s

Most ownership changes come from short-lived local references, not from links between objects, so Deutsch-Bobrow deferred reference counting simply does not count local references at all: only references stored in object fields adjust the count. The fast path loses its atomic updates almost entirely. The price is that a count of zero now means *no object refers to me*, not *nothing refers to me* — a thread's stack may still hold the only reference. So zero-count objects go onto a candidate list, and periodically the scheme takes a consistent view of the threads' stacks and registers and frees only the candidates that no stack mentions. That buys throughput and costs the scheme's headline property, promptness: objects die at scan points rather than at the instant of the last drop. Coalescing is the same bargain in another form — batch a field's many updates into one net pair.

code

pseudocode · 20 lines
pseudocode
// per-thread buffered counting; flush order is the safety property
buffer = empty list      // entries of (object, +1) or (object, -1)

function share(obj):
    append(buffer, (obj, +1))

function release(obj):
    append(buffer, (obj, -1))

function flush():
    for each (obj, delta) in buffer where delta > 0:
        atomic_add(obj.count, delta)          // all gains applied first
    for each (obj, delta) in buffer where delta < 0:
        old = atomic_add(obj.count, delta)
        if old == 1:
            candidates.add(obj)               // zero: dead only if no stack names it
    buffer = empty list

// applying the losses first could drive a count to zero mid-flush
// and free an object this same buffer is about to re-reference

go deeper

for a junior

Keep the core idea: if you skip counting the references that change most often, the count gets cheap but stops being trustworthy on its own.

for a middle

Explain the split — field references counted, stack and register references not — and why that forces a candidate list plus a periodic scan of the threads' roots before anything is freed.

for a senior

Show you can price the trade for a real service: throughput on the mutator against death observed at a scan point, and name the objects for which that delay is unacceptable because they hold a scarce non-memory resource.

for a principal

Frame deferral as sliding counting toward the reachability end of the spectrum, and own the consequence: you have introduced a periodic step that must run, be scheduled and be observed, in a scheme chosen originally for not having one.

## Where the updates actually come from If you instrument a program's ownership changes, the distribution is lopsided. A large majority come from **references that live for microseconds**: a value loaded into a local slot, passed to a function, returned, discarded. References stored **in object fields** change far less often — building and rewiring a data structure is rare compared with walking it. Deferred reference counting is the design that takes this seriously. Its rule is: - **Count only references stored in object fields.** Writing a reference into a field increments; overwriting or clearing it decrements. - **Do not count references held by thread stacks and registers at all.** Loading, passing and dropping a local reference costs nothing. The effect on the fast path is dramatic, because the fast path is made almost entirely of the second category. The atomic updates that were the tax largely disappear. ## The property you give up The count is now an **incomplete** picture of who refers to the object, and it is incomplete in the dangerous direction: it can read zero while a thread is actively using the object through a local reference. So the scheme can no longer free on the zero transition. Instead: 1. When a count falls to zero, the object is recorded on a **zero-count candidate list** rather than destroyed. 2. Periodically, at a point where the threads' stacks can be examined consistently, the scheme scans every thread's stack and registers and marks the objects it finds. 3. Candidates that no stack mentions are genuinely dead and are freed; candidates that a stack mentions stay, and their entry is dropped or retained for the next round. That scan is the exchange. It is small compared with a full reachability trace — it visits roots, not the whole live set — but it is a scan the pure scheme did not need, it needs a consistent view of the threads, and it means **reclamation now happens at scan points rather than at the instant of the last drop**. Promptness was the reason to choose counting in the first place, so this is not a free optimisation; it is a trade of the scheme's headline property for throughput. ## Coalescing: the same bargain, different axis A second family of techniques batches updates instead of skipping a category of them: - **Per-thread delta buffers.** Each thread records increments and decrements locally and flushes them in a batch, so the shared word is touched once per batch rather than once per event. Safety requires that a batch's **increments are applied before its decrements**; applying them in the other order can drive a count to zero on the way through and free an object that the same batch is about to re-reference. - **Interval coalescing.** Over an interval, a field that is written many times produces one net effect: the object it pointed to at the start loses a reference, the object it points to at the end gains one. Everything in between cancels. Recording only the first and last value of a modified field collapses many pairs into one. Both give up the same thing: the count is not continuously accurate, so death is observed later than it happens. ## Comparing the three | Scheme | Fast path | Accuracy of the count | When objects die | |---|---|---|---| | Immediate counting | atomic update per ownership change | exact at all times | at the last drop | | Deferred counting | field writes only | ignores stack references | at the next root scan | | Coalesced counting | batched or net updates | correct only at flush points | at the next flush | ## When it is worth it Deferral earns its place where the program's ownership churn is dominated by local references and where the objects being counted are not holding anything whose release must be immediate. It is a poor fit where a counted object owns a scarce non-memory resource, because those are the cases in which 'freed a little later' is exactly the cost you refused to pay when you chose counting. It also adds a mechanism that must run — a scan, a flush, a safe point at which threads can be inspected — which is a real operational surface, and it complicates reasoning about when destruction side effects happen. The honest summary is that deferral moves counting toward the reachability-based end of the spectrum: less work on the mutator, a periodic root-inspecting step, and death observed at a boundary rather than at an instant. Choosing it is choosing where on that spectrum this workload belongs.

  • Why must a batched flush apply its increments before its decrements?
    Because the two orders differ in what the count reads midway through. A buffer that gains and then loses a reference to the same object nets out to no change, but applying the loss first can take the count to zero, triggering destruction of an object the flush is about to reference again. Applying gains first means the count never dips below the truth.
  • Does deferred counting remove the need for a cycle collector?
    No, and it does not affect cycles either way. Deferral changes which references are counted and when the count is believed; a group of objects that reference each other still keeps its own counts above zero, and something that inspects structure rather than counts is still required to reclaim it.

saying these in an interview costs you the question

  • Thinks deferral counts everything, just later, with no scan needed
  • Believes a zero count still proves the object is dead
  • Says it makes reclamation prompter rather than less prompt
  • Applies buffered decrements before increments when flushing
  • Claims it removes the need to handle reference cycles
  • Assumes the root scan costs the same as a full heap trace