Two objects in a counted heap hold references to each other and nothing outside can reach them; why is neither ever freed?
answer
- counting asks a purely local question
- pointed-at is not the same as reachable
- each member is held by another member
- both counts settle at one, never zero
- only the other's death would decrement it
basics
~20 sEach object's count is held above zero by the other, so no decrement ever reaches zero. A count records whether anything points at an object, not whether anything reachable does, so an unreachable ring keeps itself alive.
solid answer
~40 sReference counting frees an object the moment its count falls to zero, and that count answers a purely local question: *is any reference pointing at me right now?* On a ring every member is pointed at by another member, so every count stays at least one. Drop the last outside handle on a two-object cycle and both counts settle at `1` — the section's child list still holds the paragraph, and the paragraph's back-pointer still holds the section. Because nothing outside can reach either object, no code can ever drop those two edges, so the only event that would decrement one count is the destruction of the other, which is itself waiting on the first. The pair is unreachable and permanently retained, along with everything it alone keeps alive.
code
pseudocode · 11 linessection <- new Node() // count(section) = 1 (local handle)
paragraph <- new Node() // count(paragraph) = 1 (local handle)
append(section.children, paragraph) // count(paragraph) = 2
paragraph.parent <- section // count(section) = 2
drop(paragraph) // count(paragraph) = 1 (section's list)
drop(section) // count(section) = 1 (back-pointer)
// nothing outside can reach either object, yet both counts are 1
// and no code remains that could ever clear either edgego deeper
Recall the shape: two objects pointing at each other keep each other's count above zero, so a counting scheme never frees them even when nothing else can reach them.
Explain the mechanics. Walk the counts through creation, linking and the last handle being dropped, and say why a count answers whether anything points at an object rather than whether anything reachable does.
Show the cost in a running system: the ring pins everything reachable only through it, and because the counts stop moving once it is unreachable, there is no event the runtime could report.
Frame it as a property of the algorithm rather than a defect to patch. Choosing counting buys prompt, local reclamation and takes on cycles as a standing liability the design must answer for somewhere.
## What a count actually knows Reference counting gives every object one small integer: how many references currently point at it. Copying a reference increments it, dropping one decrements it, and a decrement that reaches **zero** destroys the object immediately, which in turn decrements everything that object pointed at. The appeal is that reclamation is prompt and **local** — no root scan, no separate pass over the heap, no pause while a collector thinks. That locality is also the whole of the problem. The count answers *is any reference pointing at me right now?* The question that actually decides whether memory is garbage is a different one: *can the program still get to me?* For every acyclic shape the two answers agree, which is why counting works at all. They come apart in exactly one situation: a cycle. ## Walking the counts on a ring Take an editor's document tree. A section holds a list of its paragraphs, and every paragraph keeps a back-pointer to its section so it can ask about inherited formatting. Both edges are ordinary owning references, so both move a count. 1. The editor creates the section and one paragraph. Each has a count of `1`, held by the local handle that created it. 2. The section's child list takes the paragraph: the paragraph's count becomes `2`. 3. The paragraph's back-pointer takes the section: the section's count becomes `2`. 4. The document is closed and both local handles are dropped. Each count falls by one, from `2` to `1`. Now look at what is left. The paragraph's count is `1` because the section's list holds it. The section's count is `1` because the paragraph's back-pointer holds it. Nothing outside the pair can reach either object, so no code will ever run that clears the child list or nulls the back-pointer. The only event that would decrement either count is the destruction of the other member — and that destruction is waiting on this one. The ring is unreachable and immortal. ## What generalises from the two-object case - **Length does not matter.** A three-object ring, a ten-object ring, and a single object whose field points at itself all behave identically: every member is pointed at from inside. - **The ring is often invisible in any one file.** It can close through a container, a captured closure, a registered callback, or an index that maps a key back at the object holding the index. - **The waste is the retained set, not the ring.** Everything reachable only through a ring member keeps a count above zero too, so two small objects at the top of a subtree can pin the whole subtree. - **It is not an implementation defect.** No amount of care inside the increment and decrement paths fixes it; the algorithm is deciding with information that does not include reachability. - **There is no event to observe.** Once the ring is unreachable its counts never move again, so nothing in the counting machinery can notice that the objects became garbage. ## Against a reachability-based scheme | | reference counting | reachability-based collection | |---|---|---| | question answered | is any reference pointing at me? | can I be walked to from a root? | | information used | one object's own count | the graph, walked from the roots outward | | garbage ring | never reclaimed | reclaimed like any other unvisited object | | when the cost is paid | on every copy and drop | during a collection, over the live set | | ordering of destruction | immediate and cascading | deferred to the collection | A scheme that walks the graph never consults the edges inside an unreachable ring at all: it simply never arrives there, and everything it did not arrive at is garbage. That is precisely the information a per-object count cannot hold. ## The three ways out A system built on counting has to answer for cycles in one of three ways, and real systems often combine them: - **Design the ring away.** Make exactly one edge of each cycle non-owning, so following it is possible but it contributes nothing to a count. - **Search for rings.** Run a cycle collector that takes objects whose counts recently fell without reaching zero as candidates, and tests whether a group is held only from inside itself. - **Keep a reachability pass in reserve.** Run a full walk from the roots occasionally, purely to catch what counting left behind — complete, but it needs roots that can be enumerated exactly. ## What an interviewer is listening for The weak answer says the objects are freed "because nothing can reach them", which quietly substitutes reachability for the thing the count measures. The strong answer walks the two counts through creation, linking and the final drop, lands on both counts at `1`, and then names the general property: counting makes a local decision, and being garbage is a global one.
- Does the problem need exactly two objects?No. Any ring works: three objects, ten, or one object whose own field points at itself. The ring can also close through a container, a captured closure or a registry entry, so it is often invisible in any single file. All that matters is that every member is pointed at from somewhere inside the ring.
- How much memory does one small ring actually cost?Far more than the ring. Everything reachable only through a ring member is held too, because those objects' counts are kept above zero by members that never die. A two-object cycle sitting at the top of a document subtree retains the entire subtree, so the honest figure is the retained set, not two object headers.
- Can a program notice that it has created such a ring?Not from the counts. Once the ring is unreachable its counts stop moving, so there is no event to hook or alert on. You either reason about the shape when you write the edges, run a cycle collector that searches candidate subgraphs, or take an occasional reachability pass and treat whatever it reclaims as the rings counting missed.
Two colleagues each waiting for the other to leave before locking up the office: both have a perfectly good reason to stay, nobody is doing anything wrong, and the lights never go off.
saying these in an interview costs you the question
- Says the pair is freed because nothing can reach it any more
- Claims only two-object rings leak and longer ones resolve themselves
- Thinks the counts keep drifting down in the background until they hit zero
- Counts the waste as two objects, ignoring everything the ring retains
- Blames a buggy counting implementation rather than the algorithm's local view