skip to content

A collector cannot tell a reference from an integer in a thread's stack slot — what does guessing cost?

level: seniorimportance: nice to knowfreq 26%

answer

  1. an untyped word, two possible meanings
  2. compiler maps or a guess
  3. over-approximates, never under-approximates
  4. a false root retains a whole closure
  5. an ambiguous word cannot be rewritten

basics

~20 s

It must treat every stack word that looks like a heap address as a reference, so it retains objects nothing really points to along with everything they reach — and it cannot safely rewrite such a word to relocate the object.

solid answer

~50 s

Precise scanning relies on metadata the compiler emits: at this instruction, these stack slots and registers hold references and those hold plain values. Without that metadata the collector scans **conservatively** — any word whose bit pattern falls inside the heap is treated as if it were a reference. The result is still safe, because it can only over-approximate the root set, never miss a real reference. What it costs is retention and mobility. A stale integer that happens to look like an address keeps an object alive along with its entire closure, so the extra retention is unbounded rather than one object per ambiguous word, and it varies run to run with whatever leftover values sit on the stack. And an object reached only by an ambiguous word cannot be relocated, because rewriting a word that might be an integer would corrupt program data; hybrid designs pin exactly those objects and move the rest.

code

pseudocode · 9 lines
pseudocode
for each word w in thread_stack_and_registers:
    if w is inside heap_bounds:
        obj = object_containing(w)        // interior addresses count too
        if obj != none and not marked(obj):
            mark(obj)                     // w may really be an integer
            pin(obj)                      // its address must not change
            push(worklist, obj)

// no real reference is ever missed; some non-references are treated as roots

go deeper

for a junior

The idea to hold on to is that a stack word does not say what it is. Either the compiler recorded which words are references, or the collector guesses by their bit pattern.

for a middle

Explain the direction of the error — conservative scanning finds every real reference plus some false ones — and name the two costs that follow: extra retention and an object that cannot be moved.

for a senior

Show that you would characterise a real system region by region rather than with one label, and that you know the retention is unbounded and run-dependent, which is why it is easy to misattribute to the application.

for a principal

The trade is metadata against independence: precise maps buy exactness and mobility at the cost of toolchain coupling and constrained stop points. Decide which you are buying before adopting a runtime whose scanning strategy you cannot change.

## Two ways to read a stack When a collector scans a thread's frames for roots, it faces an untyped sequence of machine words. Deciding which of them are references can be done in one of two ways. **Precise (also called exact) scanning.** The compiler records, for each point where a thread may be stopped, a map saying which slots and registers hold references at that instruction. The collector reads the map and knows the answer. This requires toolchain cooperation, storage for the maps, and a discipline about where threads may be stopped — the map is only valid at those points. **Conservative scanning.** No map exists. The collector inspects every word and applies a test: does this bit pattern fall inside the heap, and does it land inside an allocated object? If so, treat it as a reference. The test cannot distinguish a genuine reference from an integer, a float or a leftover value that happens to have the same bits. ## Why the guess is safe The direction of the error matters. Conservative scanning **over-approximates**: every real reference is certainly found, because a real reference always passes the test, and some non-references are found as well. It therefore never frees a reachable object. The danger of a conservative collector is retaining too much, never releasing too early — mistaking that direction is the classic error when discussing it. ## What the guess costs | Property | Precise scanning | Conservative scanning | |---|---|---| | Toolchain support | Required — reference maps per stop point | None needed | | Extra retention | None from scanning | False roots retain whole closures | | Determinism | Same heap, same result | Depends on leftover stack values | | Relocation | Free to move and update slots | Cannot rewrite ambiguous words | | Frames from other toolchains | Cannot be described | Handled the same as any other | The entries worth expanding: - **Retention is not one object per false root.** A single ambiguous word retains the object it appears to name *and the whole closure behind it*, so a few unlucky words can hold an arbitrarily large graph. It is bounded by what the heap contains, not by the stack's size. - **It is not reproducible.** Whether a word is ambiguous depends on what an earlier call left in that slot and on where the heap happens to sit, so the same workload can retain different amounts on different runs. That makes the effect awkward to measure and easy to blame on something else. - **It constrains layout, not just marking.** To move an object, every reference to it must be rewritten. A word that might be an integer must not be rewritten, so an object reachable only through an ambiguous word must stay where it is. Designs that want both usually pin only the ambiguous referents and relocate everything else. - **Interior references complicate the test.** A word may point into the middle of an object rather than at its start, so the collector must be able to resolve an arbitrary address to the object containing it, which constrains how the heap records object boundaries. ## Why anyone chooses it Conservative scanning buys independence from the toolchain. It works when frames were produced by a compiler that emits no maps, when the collector is a library added to a language that never anticipated one, and when stopping threads only at points with valid maps is impractical. It also keeps the runtime simpler: no map generation, no map storage, no invalidation when code is recompiled. ## Hybrids are the common answer The choice is not all-or-nothing, and mature designs mix the two. A frequent arrangement is precise scanning of the heap — where objects have a known layout that says which fields are references — combined with conservative scanning of thread stacks, where the metadata is expensive or unavailable. The retained closure of a false root is then still an over-approximation, but every reference *inside* the heap is exact, so marking beyond the first hop is precise and the collector can move any object whose ambiguous referents are pinned. The right way to describe a real system is usually "conservative in these regions, precise in those", not one label for the whole collector.

  • Can conservative scanning ever free an object that is still reachable?
    No. The error is one-directional: a genuine reference always passes the address test, so it is always found. The collector can only add roots that are not real, never miss ones that are. Everything it costs is on the retention and mobility side, which is what makes the technique usable at all.
  • Why does an ambiguous root prevent moving the object it appears to name?
    Moving an object means rewriting every reference to its new address. The collector cannot rewrite a word it is not certain is a reference — if that word were really an integer, overwriting it would silently corrupt program data. So the object is pinned at its current address, while objects reached only through known-precise references can still be relocated.
  • Why is extra retention from conservative scanning hard to measure?
    Because whether a word is ambiguous depends on leftover values from earlier calls and on where the heap happens to be mapped, so it varies between runs of the same workload. A single unlucky word can also retain a very large closure, which makes the magnitude lumpy rather than proportional to anything you can control.

It is a left-luggage office whose clerk cannot read tickets, only recognise their shape. Anything ticket-shaped in a customer's pocket keeps a bag on the shelf, so the shelf never quite empties — but no bag is ever handed away by mistake.

saying these in an interview costs you the question

  • Thinks conservative scanning may free a live object
  • Calls the over-approximation a correctness defect
  • Says precise scanning needs no compiler-emitted metadata
  • Assumes each false root retains only one object
  • Believes a conservative collector can compact freely