vault

The Cyclic Garbage Collector

17 min read

The Cyclic Garbage Collector

CPython’s primary memory-reclamation mechanism is Reference Counting: an object is freed the instant its reference count reaches zero. But reference counting has one fatal blind spot — it can never reclaim a reference cycle, a group of objects that keep each other’s counts above zero even after the program has dropped every external handle to them (see the sibling Reference Cycles and How They Form). To plug that leak, CPython runs a second, cycle-detecting collector on top of reference counting. Its job is narrow but essential: find groups of container objects that are unreachable from outside their own group, break the cycles by clearing their references, and let ordinary reference counting reclaim the corpses. This note traces the trial-deletion (a.k.a. “mark-the-roots-by-subtracting-internal-refs”) algorithm that Python/gc.c implements, as of CPython 3.14.5 (per the garbage-collector design doc and the source itself).

Version scope

This note reflects CPython 3.14.5 (the design doc and gc.c were pulled from the v3.14.5 tag, where NUM_GENERATIONS is 3 and GC_GENERATION_INIT is the classic (2000, 10, 10) three-generation initializer — both verified in pycore_interp_structs.h @ v3.14.5). The cyclic-detection algorithm (update_refs → subtract_refs → move_unreachable) is stable across 3.12–3.14, but the generational structure around it churned: 3.14.0 shipped an incremental collector that was reverted to the classic three-generation design in 3.14.5. The machinery below describes the reverted (3.14.5) design; the incremental interlude is the sibling The Incremental GC and Its Reversion. A reader on 3.14.0–3.14.4 will see different generation internals (check gc.get_threshold() / whether gc.get_objects(generation=1) works on the running interpreter).

Why a second collector must exist

Reference counting is eager and local: every time a reference to an object is created the object’s ob_refcnt field is incremented, every time one is destroyed it is decremented, and the moment the count hits zero tp_dealloc runs and the memory is freed. This is wonderfully prompt — there is no “collection pause,” objects die exactly when the last reference disappears — but it is defeated by a structure that points back at itself. Consider the minimal example from the design doc:

>>> container = []
>>> container.append(container)
>>> sys.getrefcount(container)
3
>>> del container

After container.append(container), the list holds a reference to itself. Its reference count is therefore at least 2 (one from the container variable, one from the internal slot — getrefcount reports 3 because the call itself borrows a temporary reference). When del container removes the external handle, the count drops to 1 — not 0 — because the list’s own internal slot still points at it. The list is now completely unreachable from any live name, yet reference counting will never free it: there is no event that can drive its count to zero, because the only thing still referencing it is itself. That is a leak, and reference counting alone cannot detect it. The cyclic GC exists precisely to find such garbage. (The deeper “why” — why every member of a cycle keeps a nonzero count — is developed in Reference Cycles and How They Form.)

Crucially, the cyclic collector is a supplement, not a replacement. The design doc is explicit that “objects tracked by GC are most often reclaimed by the refcounting system when GC isn’t running at all.” The cyclic GC only deals with the residue that refcounting cannot touch.

What “tracked” means and the GC header

The collector cannot scan every object in the heap; that would be ruinously expensive and pointless, because only container objects — things that can hold references to other objects — can participate in a cycle. An integer or a string cannot point at anything, so it can never be part of a cycle and is never tracked. The collector therefore restricts itself to GC-tracked objects: instances of types that set the Py_TPFLAGS_HAVE_GC flag in their tp_flags slot and supply a tp_traverse function (per the GC C-API docs). Lists, dicts, tuples, sets, class instances, and modules are tracked; int, float, str, bytes are not.

A tracked object is allocated with extra space before its normal PyObject header, called PyGC_Head. In the default (GIL-enabled) build the layout is, per the design doc:

                  +------------------------------------------------+ \
                  |                    *_gc_next                  | |
                  +------------------------------------------------+ | PyGC_Head
                  |                    *_gc_prev                  | |
    object -----> +------------------------------------------------+ /
                  |                    ob_refcnt                  | \
                  +------------------------------------------------+ | PyObject_HEAD
                  |                    *ob_type                   | |
                  +------------------------------------------------+ /

The two extra words, _gc_next and _gc_prev, chain all tracked objects into doubly linked lists — these lists are the GC generations. Because the PyGC_Head sits immediately before the object, the runtime converts between the two with a single pointer cast: _Py_AS_GC(op) does ((char*)op) - sizeof(PyGC_Head) and _Py_FROM_GC(gc) does the reverse (Include/internal/pycore_gc.h). An object is allocated and tracked through _PyObject_GC_New / _PyObject_GC_NewVar and registered with PyObject_GC_Track, which simply sets it into the generation-0 linked list; _PyObject_GC_IS_TRACKED reports gc->_gc_next != 0 (a nonzero next-pointer means “I am on a GC list”). You can observe this from Python with gc.is_tracked:

>>> gc.is_tracked(0)          # int — never tracked
False
>>> gc.is_tracked([])         # list — tracked
True
>>> gc.is_tracked(())         # empty tuple is special-cased, not tracked
False
>>> gc.is_tracked({"a": 1})   # dict — tracked
True

The two header words are also fat pointers: their low bits, which are always zero on word-aligned addresses, store flags. _gc_prev’s low bits hold _PyGC_PREV_MASK_FINALIZED (the object’s finalizer has run) and PREV_MASK_COLLECTING (the object is in the generation currently being collected). During a collection _gc_prev is temporarily repurposed to hold a copy of the reference count — which is the entire trick the algorithm hinges on, explained next. _gc_next’s low bit holds NEXT_MASK_UNREACHABLE during the unreachable-partitioning phase. (Include/internal/pycore_gc.h, design-doc “Optimization: reusing fields to save memory”.)

Mental model: subtract internal references, see what’s left

The algorithm answers one question: which tracked objects are reachable only through other tracked objects in the same group? Those, and only those, are collectible cycle garbage. The trick is to compute, for each candidate object, how many of its references come from inside the candidate set versus from outside (a live variable, a C global, a frame). If you take the object’s total reference count and subtract every reference that originates inside the set, a positive remainder means “something outside still points at me — I am a root, keep me.” A zero remainder means “every reference I have comes from within this doomed group” — a candidate for collection.

flowchart TD
    subgraph candidates["Candidate set (generation being collected)"]
        A["link_1<br/>refcnt=2, gc_ref→?"]
        B["link_2<br/>refcnt=1, gc_ref→?"]
        C["link_3<br/>refcnt=1, gc_ref→?"]
        D["link_4 (self-cycle)<br/>refcnt=1, gc_ref→?"]
    end
    EXT(["External root:<br/>variable A"]) -->|reference from outside| A
    A -->|next_link| B
    B -->|next_link| C
    C -->|next_link| A
    D -->|next_link| D
    style EXT fill:#2d6,stroke:#161
    style D fill:#e88,stroke:#900

Diagram: the design doc’s canonical example. link_1 → link_2 → link_3 → link_1 is a three-node cycle, but A still references link_1 from outside, so the whole ring is reachable and survives. link_4 references only itself with no external root, so after internal references are subtracted its adjusted count falls to zero and it is collected. The insight: cycle membership alone does not condemn an object — having no external reference into the cycle does.

The trial-deletion algorithm, step by step

The whole sequence lives in deduce_unreachable (Python/gc.c), which calls three functions in order:

static inline void
deduce_unreachable(PyGC_Head *base, PyGC_Head *unreachable) {
    validate_list(base, collecting_clear_unreachable_clear);
    update_refs(base);  // gc_prev is used for gc_refs
    subtract_refs(base);
    move_unreachable(base, unreachable);
    ...
}

base is the linked list of candidate objects (one generation, plus younger ones merged in); unreachable is an empty list that will receive the garbage. Walk each step.

Step 1 — update_refs: snapshot every refcount into gc_refs

static void
update_refs(PyGC_Head *containers)
{
    PyGC_Head *gc = GC_NEXT(containers);
    while (gc != containers) {
        PyGC_Head *next = GC_NEXT(gc);
        PyObject *op = FROM_GC(gc);
        if (_Py_IsImmortal(op)) {
            assert(!_Py_IsStaticImmortal(op));
            _PyObject_GC_UNTRACK(op);
            gc = next;
            continue;
        }
        gc_reset_refs(gc, Py_REFCNT(op));
        _PyObject_ASSERT(op, gc_get_refs(gc) != 0);
        gc = next;
    }
}

Line by line: it walks the candidate list. For each object it copies the real reference count Py_REFCNT(op) into a private scratch field called gc_refs, via gc_reset_refs, which stuffs the count into the high bits of _gc_prev (the temporary repurposing described above) and sets the PREV_MASK_COLLECTING flag. The algorithm works on this copy so it can freely mutate it without corrupting the live ob_refcnt. The _Py_IsImmortal short-circuit is a 3.12+ detail: Immortal Objects (whose refcount is a sentinel, never decremented) cannot be part of collectible garbage, so they are simply untracked and skipped — including them would corrupt the arithmetic. The closing assert gc_get_refs(gc) != 0 encodes a deep invariant: the cyclic GC should never see a tracked object with an incoming refcount of zero, because such an object would already have been deallocated by refcounting; if it triggers, a tp_dealloc left a dying object tracked.

Step 2 — subtract_refs: remove every reference internal to the set

static int
visit_decref(PyObject *op, void *parent)
{
    if (_PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        if (gc_is_collecting(gc)) {   // only objects in this generation
            gc_decref(gc);
        }
    }
    return 0;
}
 
static void
subtract_refs(PyGC_Head *containers)
{
    PyGC_Head *gc = GC_NEXT(containers);
    for (; gc != containers; gc = GC_NEXT(gc)) {
        PyObject *op = FROM_GC(gc);
        traverseproc traverse = Py_TYPE(op)->tp_traverse;
        (void) traverse(op, visit_decref, op);
    }
}

This is where tp_traverse earns its keep. For every candidate object, subtract_refs calls the object’s tp_traverse slot, which is a type-specific function that calls a visitor callback once for each object the container directly references. The visitor here is visit_decref: for each referenced object that is itself a GC candidate (gc_is_collecting), it decrements that object’s gc_refs copy by one. The check gc_is_collecting(gc) ensures references to objects outside the current generation are ignored — only internal references are subtracted. After this pass completes, each candidate’s gc_refs equals (original refcount) − (references from within the candidate set) — that is, exactly the number of references coming from outside. The function’s own comment states the result: “gc_refs is >= 0 for all objects in containers. The ones with gc_refs > 0 are directly reachable from outside containers, and so can’t be collected.”

A type’s tp_traverse must visit every object directly contained by the instance, or the subtraction undercounts and a still-reachable object can be misclassified as garbage and freed. The GC C-API docs state the contract precisely: implementations “must call the visit function for each object directly contained by self,” and “must not have any side effects … may not modify the reference counts of any Python objects nor create or destroy any Python objects” — which is why visit_decref only touches the scratch gc_refs copy, never the real refcount. The Py_VISIT(self->field) macro exists to make a correct traversal a one-liner per field. A type that sets Py_TPFLAGS_HAVE_GC must supply a tp_traverse, and a mutable container must also supply tp_clear.

Step 3 — move_unreachable: partition into reachable and unreachable

After subtraction, an object with gc_refs > 0 is definitely reachable (some external root points at it). An object with gc_refs == 0 is only a suspect — it has no direct external reference, but it might still be reachable indirectly, through a reachable object. link_2 in the diagram is the classic case: after subtraction its gc_ref == 0, yet link_1 (which is externally reachable) points at it, so it is alive. move_unreachable resolves this with a graph traversal:

static void
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
{
    PyGC_Head *prev = young;
    PyGC_Head *gc = GC_NEXT(young);
    while (gc != young) {
        if (gc_get_refs(gc)) {
            /* gc is definitely reachable from outside the original 'young'.
             * Mark it, and traverse its pointers to find any other objects
             * that may be directly reachable from it. */
            PyObject *op = FROM_GC(gc);
            traverseproc traverse = Py_TYPE(op)->tp_traverse;
            (void) traverse(op, visit_reachable, (void *)young);
            _PyGCHead_SET_PREV(gc, prev);
            gc_clear_collecting(gc);     // mark as visited & reachable
            prev = gc;
        }
        else {
            /* This *may* be unreachable. Assume it is and move it to the
             * unreachable list; visit_reachable will move it back if it
             * turns out to be reachable from an object we reach later. */
            prev->_gc_next = gc->_gc_next;
            PyGC_Head *last = GC_PREV(unreachable);
            last->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)gc);
            _PyGCHead_SET_PREV(gc, last);
            gc->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)unreachable);
            unreachable->_gc_prev = (uintptr_t)gc;
        }
        gc = (PyGC_Head*)prev->_gc_next;
    }
    young->_gc_prev = (uintptr_t)prev;
    unreachable->_gc_next &= ~NEXT_MASK_UNREACHABLE;
}

Reading it: the loop scans the young list left to right. If the current object has gc_refs > 0, it is a confirmed root — its references are reachable too, so the function calls tp_traverse again with the visit_reachable visitor, which resurrects any suspect it points at by setting that suspect’s gc_refs back to 1 (and, if the suspect had already been moved to the unreachable list, yanks it back into young so it will be re-scanned). The object is then marked visited (gc_clear_collecting) and kept. If the current object has gc_refs == 0, it is tentatively unreachable: the code unlinks it from young and appends it to the unreachable list, tagging it with NEXT_MASK_UNREACHABLE. Because visit_reachable may pull objects back into young after they were tentatively condemned, the scan is effectively a breadth-first search of the reachable subgraph. When the loop finishes, every object still in unreachable is provably garbage: no chain of references from any external root reaches it.

The design doc highlights a non-obvious optimization in which set gets moved. Moving the (usually few) unreachable objects, rather than the (usually many) reachable ones, costs more on the first scan of a cycle — reachable objects get bounced into unreachable and back. But the bouncing reverses their order in the list, and on every subsequent collection none of them move at all. Since most objects are never in cycles, this “save an unbounded number of moves across an unbounded number of later collections.”

Breaking the cycle: tp_clear and delete_garbage

Identifying the garbage is half the job; the other half is destroying it without corrupting the interpreter. The unreachable objects form cycles, so calling tp_dealloc on one directly would be wrong — its members still hold references to each other, so no count is zero yet. Instead, delete_garbage calls each object’s tp_clear slot, which drops the object’s internal references:

static void
delete_garbage(PyThreadState *tstate, GCState *gcstate,
               PyGC_Head *collectable, PyGC_Head *old)
{
    while (!gc_list_is_empty(collectable)) {
        PyGC_Head *gc = GC_NEXT(collectable);
        PyObject *op = FROM_GC(gc);
        ...
        inquiry clear;
        if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
            Py_INCREF(op);
            (void) clear(op);          // drop op's references to others
            if (_PyErr_Occurred(tstate)) {
                PyErr_FormatUnraisable("Exception ignored in tp_clear of %s",
                                       Py_TYPE(op)->tp_name);
            }
            Py_DECREF(op);
        }
        if (GC_NEXT(collectable) == gc) {
            gc_clear_collecting(gc);
            gc_list_move(gc, old);
        }
    }
}

The Py_INCREF/Py_DECREF bracket around clear(op) pins the object while its own references are torn out, so it cannot be freed mid-clear. As tp_clear runs across the unreachable set, each object releases its grip on the others; the cycle’s internal reference counts fall, and the moment any object’s ob_refcnt hits zero ordinary reference counting fires tp_dealloc and reclaims it — which in turn decrements the next object’s count, and the whole ring unravels. The cyclic GC never frees memory itself; it just breaks the cycle and lets refcounting finish. This is why a tracked type that can form cycles must supply both tp_traverse (to be found) and tp_clear (to be broken); the design doc notes a tp_clear is mandatory “unless it can be proven that the objects cannot form reference cycles.”

The full destruction sequence, per the design doc, runs in order: (1) clear weak references and queue their callbacks; (2) move any object with a legacy finalizer (tp_del) to gc.garbage; (3) call modern finalizers (tp_finalize, the __del__ machinery — see Finalizers and the del Method); (4) re-run cycle detection on anything a finalizer resurrected; (5) call tp_clear to break the survivors.

Generations: limiting how much is scanned each time

Scanning every tracked object on every collection would be O(heap) and far too slow. The default build uses generational collection (see Generational Garbage Collection for the full treatment), built on the weak generational hypothesis: most objects die young. Tracked objects are partitioned into three generations (0, 1, 2). New objects enter generation 0; an object that survives a collection of its generation is promoted to the next. The collector keeps a count of allocations-minus-deallocations and, when generation 0’s count exceeds threshold0, collects generation 0; if generation 0 has been collected more than threshold1 times since generation 1 was last collected, generation 1 is folded in, and so on. The defaults are visible from Python (design doc):

>>> import gc
>>> gc.get_threshold()
(2000, 10, 10)

So generation 0 is collected after ~2000 net new container allocations; the older generations far less often. (The (2000, 10, 10) defaults are verified against the 3.14.5 design doc and a running 3.14.5 interpreter; threshold0 is larger than the 700 reported in older Python documentation, but I have not pinned the exact release in which it changed — treat the transition as unverified.) The oldest generation has an extra brake — a full collection runs only when the ratio of long-lived-pending to long-lived-total objects exceeds a hardwired 25%, which keeps the amortized cost linear in the number of objects rather than quadratic. NUM_GENERATIONS is 3 in 3.14.5 (Python/gc.c); on 3.14.0–3.14.4 the incremental collector restructured this — see the version warning at the top and The Incremental GC and Its Reversion.

The free-threaded build runs a different collector

The GIL-free build (PEP 703, Free-Threaded CPython) cannot use the _gc_prev-refcount-copy trick, because in a free-threaded interpreter another thread could mutate a refcount mid-collection. Its collector lives in Python/gc_free_threading.c (“Cyclic garbage collector implementation for free-threaded build”) and differs structurally, per the design doc’s “Differences between GC implementations”:

  • It does not use PyGC_Head linked lists at all. There is no _gc_next/_gc_prev; GC state lives in a one-byte ob_gc_bits field present on every object (_PyGC_BITS_TRACKED, _PyGC_BITS_ALIVE, _PyGC_BITS_UNREACHABLE, etc.). To find tracked objects it scans the embedded mimalloc heap rather than walking a list.
  • It is non-generational — every collection scans the entire heap.
  • It uses two stop-the-world pauses (all other threads halted) so it can read refcounts and object fields safely.
  • It begins with a “mark alive” pass (gc_mark_alive_from_roots): starting from known roots (interp->sysdict, interp->builtins, interp->types, and all objects referenced by active frames), it marks the transitive closure as _PyGC_BITS_ALIVE and excludes them from cycle detection entirely. A software-prefetch optimization (tuned March 2025, enabled above ~200,000 long-lived objects) speeds this pass by 20–40% on cache-unfriendly graphs.

The conceptual result is the same — find unreachable cycles, break them with tp_clear — but the data structures and thread-safety mechanism are wholly different.

Failure modes and how to observe them

  • A __del__ finalizer used to make a cycle uncollectable before Python 3.4. PEP 442 changed this: objects with __del__ in a cycle are now finalized and collected normally, and gc.garbage stays empty in almost all programs. Only C extension types with a non-NULL legacy tp_del slot still land in gc.garbage (gc docs). See Finalizers and the del Method.
  • A broken or missing tp_traverse in a C extension causes the GC to undercount external references and free a live object — a hard-to-debug crash. There is no Python-level analogue; this is a C-extension correctness bug.
  • Observing cycle collection: gc.collect() returns the number of objects it reclaimed — in the design-doc Link example, gc.collect() returns 2 (the unreachable link_4 and its __dict__). gc.get_stats() reports per-generation collection counts; gc.set_debug(gc.DEBUG_SAVEALL) diverts all unreachable objects into gc.garbage for inspection instead of freeing them. The mechanics of creating cycles, and tools like objgraph, are covered in Reference Cycles and How They Form.

See Also

Graph View

Backlinks