Atomic Reference Counts and the Cycle They Cannot Collect

Shared ownership is what a program reaches for when it cannot prove that exactly one part of the code will finish with an object last. The mechanism is a counter stored beside the object: every new owner increments it, every owner that finishes decrements it, and the owner that drives it to zero destroys the object. The idea is old enough that it predates the languages that made it popular, and its costs are equally old, because they follow from two facts that no implementation escapes. The counter is shared mutable state, so updating it requires synchronisation when owners can be on different threads. And the counter only knows how many references exist, not whether the reference graph is acyclic, so a cycle of mutually referring objects never reaches zero.

Why the increment cannot be ordinary

On a single thread, ++count compiles to a load, an add, and a store. Two threads executing that sequence on the same address can interleave so that one increment is lost, and a lost increment is worse than a lost decrement: the object is destroyed while an owner still holds a reference. The failure is not a leak but a use-after-free, and it surfaces far from the increment that caused it.

Making the update atomic has a price that depends on the instruction set. On x86-64, an atomic increment of a 32-bit counter is a lock-prefixed read-modify-write, which the microarchitecture implements by taking ownership of the cache line and blocking other cores’ accesses to it for the duration. On the common server cores this costs on the order of a few tens of cycles when the line is already in the local cache and is uncontended. When the line is held by another socket, the operation becomes a cache-line transfer and the cost rises to the hundreds of cycles. On architectures with load-linked/store-conditional, the operation is a retry loop: the store succeeds only if no other write to the line occurred since the load, and contention turns the loop into repeated retries.

There is a cheaper option that some libraries use, and it is worth knowing why it is not universal. If an object’s count is known to be at least two, and the thread already holds one of those references, then the other references cannot disappear while this thread holds one, so the count cannot reach zero during the operation. The increment can then be a relaxed atomic add rather than a sequentially consistent one, and no fences are needed. The decrement cannot use the same relaxation in general, because the decrement might be the one that reaches zero and must therefore be ordered after all the reads the owner performed. In practice the pattern is: relaxed increment when the count is provably above one, and an acquire-release decrement that checks for zero. Rust’s Arc uses exactly this structure, with the increment relaxed and the final decrement using a release fence before destroying the value.

The memory ordering is not decoration. The owner that destroys the object must observe every write that the other owners performed before they released their references. A release on the last decrement and an acquire on the destruction path establish that ordering. Getting it wrong produces a race that a test on a weakly ordered machine such as ARM can expose and a test on x86 usually cannot, because x86’s memory model is stronger than the language’s.

Where the count lives and what it costs in space

The counter is usually placed in a header immediately before the object, so that a single pointer still refers to both. The header is typically 16 bytes on a 64-bit target: an 8-byte strong count, an 8-byte weak count, and padding to keep the object’s alignment. std::make_shared allocates the control block and the object in one allocation for this reason; constructing a shared_ptr from a raw pointer instead performs a second allocation, which is why the factory function is the recommended form.

The weak count is a second counter with a different job. Weak references observe the object without keeping it alive, and the object is destroyed when the strong count reaches zero, but the control block itself survives until the weak count also reaches zero. That is what lets a weak_ptr be locked: it atomically checks whether the strong count is still positive and, if so, increments it. The window between the check and the increment is exactly why the control block cannot be freed early.

A 32-bit strong count sets an upper bound on the number of simultaneous owners, and the bound is lower than the address space suggests. shared_ptr implementations typically store a signed count, so the usable maximum is roughly 2^31 references. An implementation that stores a count in a 16-bit field reduces the header but caps owners at 65,535, a limit that is easy to exceed in a graph where each node holds a reference to each of its neighbours.

The cycle that reference counting cannot see

The collector’s rule is local: destroy when the count reaches zero. That rule cannot distinguish a subtree of objects that are reachable from the roots from an island of objects that refer to each other but are reachable from nothing. Both have counts above zero.

class Node:
    def __init__(self):
        self.peer = None

a = Node()
b = Node()
a.peer = b
b.peer = a
del a, b        # both still have a count of 1 from the other

The count-based approach has no way to know that the pair is garbage, because each object in the pair is genuinely referenced. Only a traversal from the roots can establish that. This is the distinction between a reference-counting collector and a tracing collector: the first approximates liveness with a local count, the second computes reachability globally and therefore handles cycles for free, at the cost of having to stop the world or coordinate with the mutator.

Real systems combine the two. CPython counts references and additionally runs a generational cycle detector over container objects. Swift’s ARC is purely count-based, so a strong reference cycle leaks unless one side is declared weak or unowned, and the language makes that declaration the programmer’s responsibility. Rust’s Rc and Arc have the same property, and the standard library documents that a cycle of Rc values will not be freed, suggesting Weak for the back edge.

The standard fix for a cycle is to break it structurally: pick an edge that does not own, and make it weak. The choice of which edge is not arbitrary. The edge from child to parent is usually the weak one, because the parent owns the child and the child merely observes the parent. Getting the direction backwards produces a dangling reference the moment the parent is released while a child still exists.

Costs that show up as cache behaviour

Count updates are writes to memory that is shared between threads, and writes to shared lines are the expensive kind. A workload that copies shared pointers through many threads will serialise on the control block even if the objects themselves are read-only. The effect is not visible as arithmetic cost; it appears as stalls on cache coherence traffic, and it grows with the number of cores touching the same object.

The mitigations trade one cost for another. Copying a shared pointer is more expensive than copying a raw pointer by roughly the cost of one atomic read-modify-write. Passing a reference to the object instead of a copy of the pointer avoids the update entirely, which is why APIs that take const T& rather than shared_ptr<T> by value are preferable when the callee does not need to extend the lifetime. Moving a shared pointer is free, because the count is untouched and the source is nulled.

There is a further cost on the destruction path. Destroying the last reference is a chain of dependent deallocations: the object’s destructor runs, which releases the references it holds, which may destroy their targets, and so on. A long chain turns a single release call into a deep recursive teardown that can exhaust the stack. Implementations that care about this use an iterative destruction queue: the destructor appends newly orphaned objects to a pending list and a loop drains it, rather than recursing. The same concern appears at the scale of a whole process in teardown at exit.

Deciding between counts and something else

The choice is legible once the costs are named. A count buys shared lifetime with a per-copy atomic write and a bounded header, and it fails on cycles. A tracing collector buys cycle collection with a global traversal and either a pause or a write barrier on every pointer store. An arena buys cheap allocation and bulk release, described in arena allocation, but gives up individual deallocation.

The deciding question is usually whether the object graph is a tree. Trees need no cycle handling, so a count or a single owner suffices. Graphs with back edges need either weak edges or a tracing pass. Where the graph is a tree but the lifetime is genuinely shared, the count is the correct tool, and the remaining work is keeping the number of copies small. That is an interface design question, and it connects back to the transfer rules in move semantics, where a move is the operation that updates no count at all.