Reference Counting and the Cycle It Cannot Break

Single ownership answers the question “who frees this” with one name. That answer fails as soon as two objects must both reach the same heap value with neither being subordinate to the other. Reference counting replaces the single owner with a counter: each owner holds a share, the count records how many shares exist, and the last one to release the share performs the deallocation. The design is incremental, predictable in latency, and local. It is defeated by exactly one structure, the cycle, which no count can distinguish from live data.

The protocol on every assignment

A counted handle is a pair: a pointer to the object and a pointer to a control block holding the count. Copying the handle increments, destroying the handle decrements, and the decrement that reaches zero runs the destructor and frees both the object and the control block.

#include <atomic>
#include <utility>

template <class T>
class Counted {
    struct Block { std::atomic<long> n; T value; };
    Block* b_;

public:
    explicit Counted(T v) : b_(new Block{1, std::move(v)}) {}

    Counted(const Counted& o) : b_(o.b_) { b_->n.fetch_add(1, std::memory_order_relaxed); }

    Counted& operator=(const Counted& o) {
        if (b_ != o.b_) {                 // self-assignment needs no work
            if (b_->n.fetch_sub(1, std::memory_order_acq_rel) == 1) delete b_;
            b_ = o.b_;
            b_->n.fetch_add(1, std::memory_order_relaxed);
        }
        return *this;
    }

    ~Counted() {
        if (b_->n.fetch_sub(1, std::memory_order_acq_rel) == 1) {
            delete b_;   // last reference: destroy value and control block
        }
    }
    T& operator*() const { return b_->value; }
};

Two details in that code carry most of the cost. The count is atomic, because handles can be copied on different threads, and an atomic increment is a locked read-modify-write: on x86-64 a lock xadd, which on a contended cache line serializes with every other core touching that line. The decrement uses acquire-release ordering because the thread that reaches zero must observe every write made by the threads that released before it; the increment uses relaxed ordering because a new reference does not need to see anything the existing ones published beyond what the copying thread already sees.

The split between strong and weak counts is the standard refinement. A strong count keeps the object alive; a weak count keeps the control block alive so that a weak handle can be upgraded. std::weak_ptr exists for exactly this: a cache or an observer that must not extend an object’s lifetime but must be able to test whether it still exists. Upgrading is a compare-and-swap loop against the strong count, and it can fail, which is why the result is optional rather than a reference.

Rust splits the same idea by threading model rather than by strength. Rc<T> keeps a non-atomic Cell<usize> and is therefore neither Send nor Sync; Arc<T> uses atomic counts and is Send and Sync when T is Send and Sync. The type system makes the choice visible at the use site instead of leaving it to documentation, which is the difference between a cost the programmer opts into and one they discover in a profile.

Why the count cannot see a cycle

Consider two nodes that point at each other, each holding a strong handle to the other, and a local handle to one of them:

use std::rc::Rc;
use std::cell::RefCell;

struct Node { next: Option<Rc<RefCell<Node>>> }

let a = Rc::new(RefCell::new(Node { next: None }));
let b = Rc::new(RefCell::new(Node { next: Some(Rc::clone(&a)) }));
a.borrow_mut().next = Some(Rc::clone(&b));
// a and b now each have strong count 2; the two local handles go out of scope

When the two local handles go out of scope, the counts drop from 2 to 1. Neither reaches zero, so neither destructor runs, and both objects remain allocated with their handles pointing at each other. The heap graph has become unreachable from any root, and the counter cannot express that, because a count measures incoming references rather than reachability. Every node in the cycle has a nonzero count and none of them is reachable; every node outside a cycle with a zero count is genuinely dead.

The same failure appears in every refcounted system: CPython’s PyObject counts, Swift’s ARC, Objective-C’s retain/release, and std::shared_ptr. Each provides a distinct escape hatch. CPython supplements counting with a generational cycle collector that runs periodically over container objects. Swift requires the programmer to annotate one edge of every cycle as weak or unowned. Objective-C has __weak and zeroing weak references. C++ provides std::weak_ptr and expects the programmer to break the cycle by hand. Rust provides Weak and, in practice, expects the same.

Breaking cycles without a collector

The manual techniques all amount to making one edge non-owning. A parent owns its children strongly and children point back weakly; a cache holds weak handles to entries so that an entry is dropped when nothing else references it; an observer registry holds weak handles so that a destroyed subject does not keep its observers alive.

Weak handles have their own cost. Creating or destroying a weak handle is an additional atomic update on a second count, and upgrading one is a compare-and-swap loop on the strong count that can fail and retry, so a path that repeatedly upgrades pays more than a path that only clones a strong handle. The weak count also delays the control block’s release until the last weak handle dies, so a long-lived weak handle keeps a small allocation alive after the object it observed is gone. That is the intended trade, but it means “the object is freed” and “the memory is returned” are separate events. Building a mutable graph on this machinery runs into the borrow-flag problem described in interior mutability, because a shared handle must be able to update the node it points at.

Trial deletion is the algorithmic alternative. Instead of counting incoming edges, mark every object reachable from a suspected cycle, subtract the internal counts, and if the remainder is zero the group is garbage:

1. For each candidate object, copy its count and subtract one for every internal reference it receives, recording the result in a scratch field.
2. Any object whose scratch value is nonzero is externally referenced; mark it and everything it reaches as live.
3. Everything else in the candidate set is unreachable and can be collected.

This is the algorithm CPython’s collector uses, restricted to objects that can contain references. The cost is a full traversal of the candidate set, so it is amortized by running only when allocations since the last run exceed a threshold. Bacon and Rajan’s formulation places reference counting and tracing on a single axis: counting is incremental tracing of the reference graph, and a cycle collector is a tracing pass applied to the subset the counter cannot resolve.

Latency, throughput, and the pause profile

Counting has a property that tracing collectors do not: deallocation happens at a known point, on the thread that released the last handle, with no global pause. That is why it dominates in latency-sensitive systems (audio, game engines, real-time control) and in systems where the collector cannot run, such as inside a kernel or across an FFI boundary.

The cost is paid on every operation. A handle copy is an atomic read-modify-write, roughly tens of cycles uncontended and far worse when many threads share one object. A pointer-chasing workload that copies handles constantly will spend a measurable fraction of its time on those atomics. A tracing collector pays nothing on assignment and pays a larger, less frequent cost at collection time.

Destruction order is the second structural difference. A tracing collector can relocate and reorder freely; counting destroys deterministically, which matters when a destructor releases a resource whose release order matters. It also means a destructor runs on whichever thread dropped the last handle, which is why a counted type holding a resource must be safe to destroy from any thread that can hold a handle to it.

There is a third cost that is easy to miss: the object graph becomes a chain of separate allocations. Every counted node is its own malloc, plus a header, and in C++ std::make_shared folds the control block into the same allocation while constructing from a bare pointer with std::shared_ptr<T>(new T) produces a second one. A tree of a million nodes is therefore a million headers and poor locality. Tracing collectors typically allocate from contiguous regions, which is why refcounted systems that need performance end up putting an arena or a pool in front of the allocator, reimplementing allocation strategy around the counting scheme.

The narrow place it fits

Reference counting is the right default when lifetimes are mostly tree-shaped, when destruction must be prompt, and when the number of aliases is small. It is the wrong default when the data is a general graph, when handle copies dominate the work, or when a collection pause is acceptable and a per-operation tax is not.

The intermediate position is a hybrid: count strongly, and run a periodic trial-deletion pass over the subset of objects that could form cycles. That is what CPython does, what several JavaScript engines did before adopting tracing, and what a C++ codebase can approximate by keeping cycle-capable objects in a registry that a background pass scans. The alternative for graph-shaped data is arena allocation, which sidesteps the problem entirely by making the region the unit of reclamation and never asking which node owns which. The counting scheme also interacts with interior mutability, because a counted cell that permits mutation through a shared handle must still enforce that no borrow is outstanding when the count reaches zero.