How the Garbage Collector Finds Cycles

A tree of Node objects keeps a list of children, and each child keeps a link back to its parent. You drop the last name for the root, but memory does not go down. "What Keeps an Object Alive" showed why. The parent and the child point at each other, so their reference counts never reach zero. This article shows how the garbage collector finds such a cycle, when its timing matters, and how to walk the references yourself.

Watch the collector free a cycle

The example turns automatic collection off, so the cycle survives until gc.collect(). It checks on the two nodes with weak references. A weak reference, made with weakref.ref(obj), does not keep its object alive. Calling it returns the object, or None once the object is freed. A later article covers weak references in full.

import gc
import weakref


class Node:
    def __init__(self) -> None:
        self.parent: Node | None = None
        self.children: list[Node] = []


was_enabled = gc.isenabled()
gc.disable()
try:
    root = Node()
    child = Node()
    root.children.append(child)
    child.parent = root
    root_ref = weakref.ref(root)
    child_ref = weakref.ref(child)
    del root, child

    print(root_ref() is None, child_ref() is None)  # False False: still alive
    gc.collect()
    print(root_ref() is None, child_ref() is None)  # True True: freed
finally:
    if was_enabled:
        gc.enable()

del root, child removes two names. The references inside the graph are still there. The root's children list points at the child, and the child's parent points at the root. gc.collect() frees the pair, even while automatic collection is off.

How the collector decides what to free

The collector looks at containers, the objects that can point at other objects, such as lists, dictionaries and instances of your classes. It works out which of them the rest of the program can still reach. The others are reachable only from inside their own cycles, so the collector frees them.

The collector checks new objects more often than old ones. It sorts objects into generations by age, because most objects become garbage soon after your code creates them. The exact schedule changes between Python versions, so read gc.get_threshold() and gc.get_stats() on your own runtime instead of assuming numbers.

Check your understanding A service spends noticeable time in garbage collection. Would raising a threshold help? Show answer

Maybe. A higher threshold makes automatic collections run less often. Then unreachable cycles wait longer, and each collection can have more work to do. Measure before you decide. Over a realistic workload, record how often collections run, how long they take, request latency and memory use. Change one setting, and compare. gc.callbacks lets you run code at the start and end of each collection.

A cycle you can still reach is not garbage

An unreachable cycle waits until the collector runs, so memory use can stay higher for a while. A cycle that a cache or a registry still points at is a different problem. The program can still reach it, so the collector keeps it. That is a real leak, and only your code can fix it, by removing the entry.

These cycles are common:

a parent that holds its children, and children that hold their parent;
an observer and the object it watches, each holding the other;
a callback stored on an object that uses that same object;
an exception saved in a local variable of a function it passed through. Its traceback holds that function's local variables, including the one that holds the exception.

Draw the real references before you choose a fix. A weak reference for the link back, such as child to parent, breaks the cycle. The code must then handle a parent that is already gone.

The collector can free a cycle whose objects have __del__ methods, but it does not promise when, or in what order. Close files and connections with with, as earlier articles showed.

Check your understanding Should a request handler call gc.collect() before it returns? Show answer

Usually not. A full collection checks every container in the process, not only the ones this request made. It can run __del__ methods and add latency to the request. It also cannot free data that the program can still reach. Call it only where measurements show it helps.

Walk the references yourself

gc.get_referents(obj) returns the objects that obj points at, as far as the collector can see. For a plain list, those are its items. It can miss references held inside C extensions, so treat it as a debugging tool. gc.get_referrers(obj) goes the other way and finds what points at obj. It is slow, so use it only while you debug.

To walk a graph of lists, track the nodes you have visited by id(), not by value. Two empty lists are equal but are different nodes, and a list cannot go in a set. A set[int] of IDs avoids both problems. The IDs stay valid while the graph is alive.

Use an explicit stack, a list of the objects still to visit, instead of a function that calls itself. Python stops at 1,000 nested calls by default, and a chain of 10,000 lists is deeper than that.