Reference Counting and Its Structural Blindness to Cycles

Take a heap with exactly two objects, each holding one pointer to the other, and no other pointer anywhere in the program. Both objects are unreachable and both will stay allocated forever under reference counting. The counters are each one. Nothing in the scheme’s local information contradicts the belief that these objects are in use, because a count is a statement about the number of incoming pointers, and incoming pointers exist. The leak is not an implementation defect; it is the precise boundary of what the algorithm can know.

That boundary is worth understanding before adopting a counting discipline, because the cost of counting is paid on every assignment rather than once per collection, and the cycle problem has to be solved by an additional mechanism with its own overhead.

The counter as an invariant

Each object carries a count of the strong references to it. The invariant is that for every object, the counter equals the number of stored pointers that target it. Allocation returns an object with a count of one, representing the reference held by the variable about to receive it. A pointer store performs two updates: decrement the old target, increment the new target. If a decrement reaches zero, the object is dead, and its fields are visited to decrement their targets before its storage is released. That recursion is the freeing cascade.

The cascade is why the scheme is attractive. Freeing is incremental and interleaved with execution, so there is no pause proportional to live data. In a system with a latency requirement, a short cascade on the assignment path is easier to tolerate than a stop-the-world mark of a heap containing a gigabyte of live objects, provided the cascade is bounded. When a large tree loses its last root, the cascade is not bounded; a single assignment can trigger the release of every node in the tree, and the work is proportional to the size of the structure that just died. Systems that must bound this either defer the cascade to a queue processed at a safe point or convert it into a bounded number of steps per allocation.

struct obj { long rc; struct obj *left, *right; };

static void release(struct obj *o) {
    if (!o) return;
    if (--o->rc > 0) return;
    /* Dead: recursively drop children before freeing the cell. */
    release(o->left);
    release(o->right);
    free(o);
}

static void assign(struct obj **slot, struct obj *new) {
    struct obj *old = *slot;
    if (new) new->rc++;
    *slot = new;          /* publish before dropping old, in the simple case */
    release(old);
}

The ordering in assign is not arbitrary. The new reference must be established before the old one is dropped, because releasing the old object can cascade through everything it owns: if the new value is reachable only from the old one, the cascade frees it, and the increment would then write into freed memory. The decrement must come after the store, so that the slot no longer names the old target when its count drops. This ordering requirement reappears in every variant.

What the discipline costs at each site

A tracing collector’s cost is concentrated in the collection cycle and is proportional to live data. A counting collector’s cost is spread across the program and is proportional to the number of pointer mutations. That difference decides which workloads favour which scheme.

Every store into a reference field needs an increment and a decrement, each of which is a read-modify-write on a counter that lives in the target object’s header. For a single-threaded program the two operations are a few instructions plus two memory touches, and the counter’s cache line is usually already hot because the program is about to use the object anyway. The arithmetic is cheap; the locality damage is the real cost, because an object’s counter sits in a different line from the pointer slot being written, and the reference may point to a region the program has not touched.

For a multithreaded program the cost jumps by an order of magnitude. A shared counter must be updated atomically, and an atomic increment on a contended cache line serialises the cores that touch it. The standard response is to make most references non-atomic and pay atomicity only for the ones that cross threads, which is what C++‘s std::shared_ptr does by distinguishing an atomic free-function overload from the plain one, and what Rust’s Arc does by making clone an atomic operation while Rc stays plain. Neither language hides the distinction, because hiding it would mean either paying atomic cost everywhere or being wrong in the presence of threads.

There is a further tax specific to counting: the count field must be wide enough. A 32-bit counter overflows if a single object is referenced more than about four billion times, which is reachable in a graph traversal that copies a shared pointer into every visited node. Implementations either use a saturating count with a fallback to a global table, or widen the field, both of which cost bytes in every object header.

Why cycles are invisible

The counter records incoming edges. A cycle is a set of edges with no external entry, and the count of each member is at least one precisely because of the internal edges. Local information cannot distinguish this from a set with an external entry, since in both cases every member has a positive count.

The asymmetry has a useful consequence and a harmful one. The useful consequence is that an acyclic structure is freed exactly when it becomes unreachable, with no delay and no scan. The harmful consequence is that any structure that can form a cycle must be broken explicitly by the programmer, or the runtime must add a cycle detector. Doubly linked lists, parent pointers in trees, observer registries, and graph structures in general all fall into the second category. Languages that rely on pure counting make this the programmer’s problem; a list node that points to its predecessor needs a manual break, or a weak pointer, at teardown.

Weak references are the standard structural answer: one edge of the cycle is declared non-owning, so the count no longer includes it, and the cycle collapses to a chain when the last strong reference drops. A parent pointer that is weak and a child list that is strong gives a tree that frees correctly. The cost is that the weak reference needs a validity check on every use, since the target may have been freed, and the runtime must arrange for the weak slot to be cleared when the target dies.

Trial deletion, in outline

Cycle detectors layered over counting work by finding candidate cycles and testing whether they are externally referenced. The Bacon-Rajan algorithm, published in 2001, is the canonical formulation and runs in the same collector as the counting itself.

The idea: when a counter is decremented but does not reach zero, the object may be part of a cycle that just lost its external reference. It is added to a candidate set. Later, the collector walks the candidate subgraph and computes, for each node, the sum of counts contributed by edges inside the subgraph. Subtracting that internal contribution from the stored count leaves the number of external references. A node whose remainder is zero has no reference from outside, and if the whole strongly connected component has remainder zero, the component is garbage and can be reclaimed.

The algorithm needs a per-object colour to track its progress through the phases, and it needs a buffer for candidates. In the original formulation the buffer is per-thread and bounded; when it fills, the collector stops the world and processes it. This gives a bound on memory but reintroduces pauses, so the scheme is not pause-free in the way plain counting is.

A simpler and more expensive variant is to run a full mark-sweep over the candidate set whenever a threshold of candidates accumulates, using the counting to avoid scanning the rest of the heap. Python’s cyclic garbage collector takes this shape: it tracks container objects, computes a subtraction-based estimate of external references over the tracked set, and collects generations of them when allocation thresholds are crossed. The thresholds are configurable, and raising them trades memory for collector time.

Where counting wins and where it loses

The case for counting is strongest when latency matters more than throughput and when most objects die at a predictable point. A document editor that closes a document and expects the memory back immediately, a compiler that drops an entire syntax tree after each function, a server that holds a bounded working set per connection: all of these free promptly under counting and can hold more memory than necessary under a tracer that waits for a threshold.

The case against counting is strongest in allocation-heavy code with high mutation rates and shared structures. Each mutation pays, and the payment is invisible in profiles that sample only allocation. Functional programs that build many small immutable structures and share them heavily pay the increment cost without ever forming a cycle, which is why counting and tracing coexist in the same runtime rather than one replacing the other. The generational tracing collectors discussed in generational collection and write barriers exploit the same generational hypothesis that makes counting cheap in the common case, but they collect in batches.

One more difference matters for correctness rather than performance. Counting frees at the assignment that drops the last reference, so the release is attributable to a specific program statement, but a cascade runs a destructor at a point determined by the pointer graph rather than by program structure. A tracer frees in batches at safepoints, so the timing is decoupled from any statement and the release order is whatever the sweep encounters. Neither is uniformly better; both are choices about when unpredictable code runs.

The remaining structural question is what happens to the memory after it is freed. Under counting the cells go straight back to an allocator, and the allocator’s ability to reuse them depends on their sizes. That is the same fragmentation problem a tracer faces after sweeping, taken up in mark-sweep and free-list fragmentation.