Reference counting

Deep dive

How it works

In: pointer copies and drops of shared objects · Out: each object destroyed exactly once, at the drop of its last owner · State: one counter per object (plus a weak counter if weak refs exist) · Cost: O(1) per copy or drop; destroy cost proportional to the freed subgraph

1. Allocate the object with strong = 1.
2. Copying a pointer (clone, AddRef, retain) increments strong.
3. Dropping a pointer decrements it. If the result is 0, run the destructor, which drops the object's own fields and thereby decrements their children (the cascade).
4. Weak references do not keep the value alive. They keep only the allocation (the counter cell) alive through a second counter weak. All strong owners together hold one implicit weak count, so the memory is freed when weak reaches 0, after the value is already destroyed.
5. Weak::upgrade returns a new strong pointer only if strong > 0; otherwise None.
6. Cycles: a group that points to itself never reaches 0. Fix by design (parent to child strong, child to parent weak) or with a cycle collector: Bacon-Rajan trial deletion subtracts internal edges from candidate roots (counts decremented to non-zero) and frees what reaches zero; CPython runs a tracing backup collector over container objects (gc module).
7. Threads: counts are atomic (Arc, C++ shared_ptr) or confined to one thread (Rc, enforced by !Send). shared_ptr keeps strong count, weak count and deleter in a control block, in one allocation with make_shared (cppreference).

Code

Non-atomic Rc with weak references on raw pointers; main asserts one destructor run, a failing upgrade after the last strong drop, a leaking strong 2-cycle and a freed one with a weak back edge. Compiled and run (stable Rust, prints ok); not Miri-checked, as cargo miri is not installed here.

use std::cell::{Cell, RefCell};
use std::mem::ManuallyDrop;
use std::ops::Deref;
use std::ptr::NonNull;
struct Inner<T> {
    strong: Cell<usize>,
    weak: Cell<usize>, // +1 owned collectively by all strong refs
    value: ManuallyDrop<T>,
}
pub struct Rc<T> { ptr: NonNull<Inner<T>> }
pub struct Weak<T> { ptr: NonNull<Inner<T>> }

impl<T> Rc<T> {
    pub fn new(v: T) -> Self {
        let b = Box::new(Inner { strong: Cell::new(1), weak: Cell::new(1), value: ManuallyDrop::new(v) });
        Rc { ptr: NonNull::from(Box::leak(b)) }
    }
    fn inner(&self) -> &Inner<T> { unsafe { self.ptr.as_ref() } }
    pub fn strong_count(&self) -> usize { self.inner().strong.get() }
    pub fn downgrade(&self) -> Weak<T> {
        self.inner().weak.set(self.inner().weak.get() + 1);
        Weak { ptr: self.ptr }
    }
}
impl<T> Clone for Rc<T> {
    fn clone(&self) -> Self {
        self.inner().strong.set(self.inner().strong.get() + 1); // plain add: !Send/!Sync keeps it safe
        Rc { ptr: self.ptr }
    }
}
impl<T> Deref for Rc<T> {
    type Target = T;
    fn deref(&self) -> &T { &self.inner().value }
}
impl<T> Drop for Rc<T> {
    fn drop(&mut self) {
        let p = self.ptr.as_ptr();
        unsafe {
            let s = (*p).strong.get() - 1;
            (*p).strong.set(s);
            if s == 0 {
                // may re-enter drop of other Rcs / Weaks pointing here: counts are already updated
                ManuallyDrop::drop(&mut (*p).value);
                release_weak(p); // drop the implicit weak ref
            }
        }
    }
}
unsafe fn release_weak<T>(p: *mut Inner<T>) {
    let w = (*p).weak.get() - 1;
    (*p).weak.set(w);
    if w == 0 { drop(Box::from_raw(p)); } // ManuallyDrop: frees memory only
}
impl<T> Weak<T> {
    pub fn upgrade(&self) -> Option<Rc<T>> {
        let i = unsafe { self.ptr.as_ref() };
        if i.strong.get() == 0 { return None; }
        i.strong.set(i.strong.get() + 1);
        Some(Rc { ptr: self.ptr })
    }
}
impl<T> Drop for Weak<T> {
    fn drop(&mut self) { unsafe { release_weak(self.ptr.as_ptr()) } }
}

struct Node<'a> {
    drops: &'a Cell<usize>,
    strong_next: RefCell<Option<Rc<Node<'a>>>>,
    weak_prev: RefCell<Option<Weak<Node<'a>>>>,
}
impl<'a> Node<'a> {
    fn new(d: &'a Cell<usize>) -> Rc<Self> {
        Rc::new(Node { drops: d, strong_next: RefCell::new(None), weak_prev: RefCell::new(None) })
    }
}
impl Drop for Node<'_> { fn drop(&mut self) { self.drops.set(self.drops.get() + 1); } }

fn main() {
    let drops = Cell::new(0);
    // 1. dropped exactly once, weak upgrade fails after last strong drop
    let a = Node::new(&drops);
    let b = a.clone();
    let w = a.downgrade();
    assert_eq!(a.strong_count(), 2);
    drop(a);
    assert_eq!(drops.get(), 0);
    assert!(w.upgrade().is_some());
    drop(b);
    assert_eq!(drops.get(), 1);
    assert!(w.upgrade().is_none());
    drop(w); // frees the allocation
    // 2. strong 2-cycle leaks
    drops.set(0);
    let x = Node::new(&drops);
    let y = Node::new(&drops);
    *x.strong_next.borrow_mut() = Some(y.clone());
    *y.strong_next.borrow_mut() = Some(x.clone());
    let probe = x.downgrade();
    drop(x);
    drop(y);
    assert_eq!(drops.get(), 0); // leaked: still alive
    let x = probe.upgrade().unwrap();
    *x.strong_next.borrow_mut() = None; // break the cycle by hand
    drop(x);
    drop(probe);
    assert_eq!(drops.get(), 2);
    // 3. back edge weak: freed
    drops.set(0);
    let x = Node::new(&drops);
    let y = Node::new(&drops);
    *x.strong_next.borrow_mut() = Some(y.clone());
    *y.weak_prev.borrow_mut() = Some(x.downgrade());
    drop(y);
    assert_eq!(drops.get(), 0);
    drop(x); // x dies -> drops its strong ref to y -> y dies
    assert_eq!(drops.get(), 2);
    println!("ok");
}

Complexity and constants

• Copy and drop: O(1); destroy O(freed objects + fields). Recursive drop of a long list overflows the stack; unlink iteratively.
• Space: one word per object for strong (CPython: ob_refcnt in every header), plus weak and a control block when weak refs or deleters exist.
• Cost drivers: a write per pointer copy and drop (dirties the object's cache line, hurts copy-on-write after fork), an atomic read-modify-write when shared, a branch on every drop, and the pause of a large cascade. Cheap: borrow instead of clone, move instead of copy, use non-atomic counts when single-threaded.

Efficiency

• Cost: self-measured on an Apple M4 Pro, release build, one clone plus drop under black_box: Rc order of 4 ns, Arc uncontended order of 4 ns; several threads cloning the same Arc: 2 threads about 19 ns, 4 threads about 95 ns per operation per thread. Bound: coherence traffic on the counter's cache line, not ALU.
• Levers:
  • Non-atomic counts when data stays on one thread — Rc docs vs Arc docs say atomics cost more than ordinary accesses (std docs) — single-threaded owners.
  • Borrow, move, or hold one clone per thread rather than per call — removes the shared write entirely — hot paths.
  • Biased counting — owner thread uses plain ops, others use an atomic shared count (PEP 703, Choi et al. PACT 2018) — mostly thread-local objects.
  • Immortal objects — Py_INCREF/Py_DECREF become no-ops for interned strings, None and similar; PEP 683 reports order of 2-4% slowdown for its naive form but saves memory under fork — constants shared by all threads.
  • Deferred and coalesced counting — skip counts for stack and register references (Deutsch-Bobrow) or log only the first write to a field per epoch (Levanoni-Petrank) — write-heavy mutators, at the cost of delayed frees.
• Naive → standard → state of the art:
  • Atomic increment and decrement on every copy · contended line, tens of ns at 4 threads in my run.
  • Non-atomic where unshared, atomic where shared, elide balanced pairs · about one cached write per copy.
  • Biased or deferred counting, immortal constants, compiler-removed retain/release pairs (Swift/ObjC optimizer, Perceus ownership inference) · most counts never executed.

Implementation notes

• Use Relaxed for the increment, Release for the decrement and an Acquire fence before destroying, as Arc does; the last dropper must see all prior writes.
• Update counts before running the destructor (as the code does) so re-entrant drops see consistent state.
• Intrusive counts (kref embedded in the struct) and make_shared save an allocation and a cache miss.

Pitfalls

• A single strong cycle (parent to child to parent, closures capturing self, observers) leaks forever and nothing warns you.
• Dropping a large structure spikes latency in whichever thread held the last reference, often a UI or request thread.
• shared_ptr from the same raw pointer twice creates two control blocks and a double free.
• Weak upgrade must check-then-increment as one compare-exchange in a thread-safe version.

Variants and alternatives

In production

• CPython — ob_refcnt per object plus a generational cycle collector (gc module, three generations); the free-threaded build uses biased counting, immortalization and limited deferred counting (PEP 703); immortal objects per PEP 683.
• Swift and Objective-C ARC — the compiler inserts retain/release (Clang ARC spec) and optimizes balanced pairs; Swift atomic counts and weak side tables are from memory.
• Rust Rc/Arc, C++ shared_ptr — non-atomic and atomic counts; Arc docs: a cycle of Arcs is never deallocated, break it with Weak.
• Linux kref — embedded refcount with kref_get/kref_put calling a release function at zero (kernel docs). File-system hard-link counts and page or buffer pin counts follow the same pattern (from memory).
• COM and Godot — IUnknown::AddRef per copy of an interface pointer (Microsoft docs); Godot's RefCounted base class for resources.
• Lean 4 and Koka — precise RC with reuse of unique objects (Counting Immutable Beans; Perceus).

Implementations

Sources

• Bacon, Rajan, Concurrent Cycle Collection in Reference Counted Systems, ECOOP 2001, LNCS 2072. paper
• Deutsch, Bobrow, An efficient, incremental, automatic garbage collector, CACM 19(9), 1976 (DOI returns 403 to bots). paper
• Levanoni, Petrank, An on-the-fly reference counting garbage collector for Java, OOPSLA 2001 (DOI returns 403 to bots). paper
• Choi, Shull, Torrellas, Biased reference counting, PACT 2018 (DOI returns 403 to bots). paper
• Reinking, Xie, de Moura, Leijen, Perceus: garbage free reference counting with reuse, PLDI 2021. paper
• Ullrich, de Moura, Counting Immutable Beans. paper
• PEP 703, Making the GIL optional · PEP 683, Immortal objects · gc module
• Rust Arc · C++ shared_ptr · Linux kref
• Clang ARC · COM AddRef · Godot RefCounted