Python Garbage Collection: Reference Counting and the Cycle Collector

The idea: two collectors in one runtime

CPython frees memory in two ways. Reference counting does almost all the work: every object counts the references to it, and the moment the count reaches 0 the object is freed. Counting cannot see reference cycles, so a second, occasional collector, the cycle GC (the gc module), looks for groups of objects that only keep each other alive. The page runs one small program: locals x, y, z, an old list L, two cycles A ⇄ B and C ⇄ D, a dict E and a string F.

Reference counting: free at the last reference

Every object starts with a header field ob_refcnt. Binding a name, storing into a list or passing an argument runs Py_INCREF; del, rebinding a name or leaving a function runs Py_DECREF. When a decref takes the count to 0, the object's tp_dealloc runs inside that very statement: it drops the object's own references, which can free more objects in a cascade, and gives the memory back. (Demo: del z, refcount frees E and F at once.) del z takes E from 1 to 0; E is freed and drops F, which goes from 1 to 0 too. sys.getrefcount(obj) shows the count (one higher than you expect, because the call's own argument is a reference).

This is why with open(...) is good style but a dropped file object in CPython is closed right away anyway: its __del__ runs at the decref, not "some time later".

Cycles leak under counting alone

(Demo: del y, the C-D cycle leaks.) C and D refer to each other, and the local y refers to C. del y takes C from 2 to 1. Now nothing in the program can reach C or D, but C still holds D's count at 1 and D holds C's count at 1. Neither will ever reach 0. Cycles are everywhere in real Python: a doubly linked list, a parent with self.children whose children keep self.parent, an exception that holds a traceback that holds the frame that holds the exception, a class and its methods.

How the cycle GC finds garbage: subtract the internal references

A tracing collector would start from the roots. CPython cannot list its roots (C extensions hold references the interpreter does not know about), so it works the other way round, on a set of container objects at a time (the "young" set: the generations being collected):

1. update_refs: copy each object's ob_refcnt into a scratch field, gc_refs.
2. subtract_refs: visit every object's references with tp_traverse; for each one that points to another object in the set, take 1 from that object's gc_refs.
3. move_unreachable: what is left in gc_refs counts references from outside the set (a local variable, an older object, a C extension). An object with gc_refs > 0 is alive, and so is everything it reaches. The rest are unreachable.
4. tp_clear each unreachable object: it drops its references, and plain reference counting frees the whole cycle.

(Demo: del y, then gc.collect(0) finds the cycle.) After update_refs, A 2, B 1, C 1, D 1, E 1. Subtracting A → B, B → A, C → D and D → C leaves A 1, B 0, C 0, D 0, E 1. A keeps 1 because its other reference comes from L, which lives in gen2, outside the set; E keeps 1 because of the local z. B has 0 but A reaches it, so B lives. C and D are unreachable: tp_clear(C) drops C → D, D goes to 0 and is freed, which drops D → C, and C goes to 0. gc.collect(0) returns 2.

Generations and thresholds

Every tracked container sits on one of three doubly linked lists. New ones go on gen0. Objects that survive a collection move to the next list: gen0 → gen1 → gen2. gc.collect(n) merges generations 0 to n and examines only those, so collecting gen0 is cheap. The idea is the weak generational hypothesis: most objects die young, and old ones tend to stay. A reference from an older object, like L → A, needs no write barrier here: it simply shows up as a gc_refs that does not drop to 0.

The automatic triggers are gc.get_threshold(), by default (700, 10, 10): gen0 runs when allocations minus deallocations of containers pass 700, gen1 after 10 gen0 runs, gen2 after 10 gen1 runs (and only when the long-lived objects have grown by a quarter since the last full collection). (Demo: a promoted cycle, collect(0) misses it, collect(1) frees it.) A first gc.collect(0) finds no garbage and moves A to E into gen1. Then L.clear() leaves A ⇄ B unreachable. Another gc.collect(0) has an empty gen0 and cannot see the cycle; gc.collect(1) frees it.

(Demo: del x, refcount frees the list, gc.collect(2) frees the cycle.) del x frees L by counting alone, which takes A from 2 to 1 and leaves A ⇄ B as a leaked cycle. gc.collect(2) (what plain gc.collect() does) examines everything and frees it. The two collectors work together: counting frees the tree-shaped garbage, the GC the cycles.

What the GC tracks, finalizers and weak references

• Only objects that can hold references are tracked: lists, dicts, sets, class instances, functions, frames. Strings, ints and floats are not (F on the canvas); gc.is_tracked("abc") is False. CPython even untracks tuples and dicts that hold only such atoms.
• Since Python 3.4 (PEP 442) objects with __del__ in a cycle are collected too: the GC runs all finalizers first, checks that nothing was resurrected, then clears.
• A weakref.ref does not raise the count, so a back pointer (child.parent) made weak means no cycle and no GC work at all.
• gc.disable() stops only the cycle GC; counting still frees everything that is not in a cycle. gc.freeze() moves every object to a permanent generation the GC ignores, useful before fork() so copy-on-write pages stay shared.

CPython vs a tracing JVM collector

Question	CPython	JVM (G1, ZGC)
Main mechanism	reference counting, plus a cycle GC	tracing from the roots
When is most garbage freed?	at once, at the last decref	at the next young collection
How cycles are found	gc_refs subtraction inside a generation, no root scan	never reached from the roots
Do objects move?	no (addresses stay fixed, the id() of an object)	yes, copied and compacted
Old → young references	show up as gc_refs > 0	a write barrier and a card table / remembered set
Cost on every reference write	an incref and a decref	a barrier only

See also Tracing GC vs Reference Counting for the two approaches side by side, and Java Garbage Collectors for eden, survivor spaces and G1 regions.

What the page leaves out

The heap is fixed: nothing is allocated, so collections only run when you press gc.collect(), never from the 700 threshold. Freed memory goes back to pymalloc's arenas, not shown. Not shown either: finalizers and resurrection, gc.garbage and the debug flags, the lazy untracking of tuples and dicts, immortal objects (Python 3.12, PEP 683), the free-threaded build (3.13, PEP 703) with biased reference counting and a non-generational collector, and the reworked collector in recent releases (Python 3.14), which collects incrementally. The core idea, subtracting internal references to find cycles, is the same in all of them.

References

gc: Garbage Collector interface (Python documentation)

Garbage collector design (CPython InternalDocs)

PEP 442: Safe object finalization

Reference Counting (Python C API)