Python's Cyclic Garbage Collector

The Problem Revisited: Unreachable but Not Unreferenced

Let's recall the scenario that stumps the reference counting mechanism. When two or more objects refer to each other, they create a self-contained ecosystem of references.

# From the previous lesson
class Node:
    def __init__(self, name):
        self.name = name
        self.neighbor = None
    def __del__(self):
        print(f"Node '{self.name}' destroyed.")




# Create a cycle
n1 = Node("A")
n2 = Node("B")
n1.neighbor = n2
n2.neighbor = n1




# Remove external references
del n1
del n2




# The objects are still in memory, __del__ is not called.
# Their reference counts are both 1, thanks to each other.

After del n1 and del n2, the objects are "unreachable" from our program's global scope, but their reference counts are not zero. This is precisely where the cyclic garbage collector steps in. Its sole purpose is to find these isolated islands of objects and reclaim their memory.

An Efficiency Boost: The Generational Collector

Scanning every single object in memory for cycles would be prohibitively slow. To optimize this, Python employs a generational garbage collector. This approach is based on a well-observed heuristic known as the "generational hypothesis": most objects are short-lived.

Python groups objects into three "generations":

• Generation 0 (The Young Generation): All new container objects (lists, dicts, custom objects, etc.) start here. This generation is collected most frequently.
• Generation 1 (The Middle Generation): Objects from Generation 0 that survive a collection cycle are "promoted" to Generation 1. This generation is collected less often.
• Generation 2 (The Old Generation): Objects that survive a collection in Generation 1 are promoted here. This is the least frequently collected generation.

The collection of a younger generation is called a "minor collection," while collecting an older generation is a "major collection." A collection of an older generation always includes all younger generations as well.

The following video provides a clear overview of this generational structure and the thresholds that trigger collections.

This generational scheme allows the garbage collector to focus its efforts on Generation 0, where most garbage is likely to be found, without repeatedly scanning long-lived objects in the older generations.

Under the Hood: Tracking Container Objects

As a developer with a computer engineering background, you'll appreciate that this system is built on specific C-level data structures. The GC doesn't need to track simple types like integers or strings because they cannot participate in reference cycles. It only tracks "container" objects.

To enable this tracking, CPython adds an extra header, PyGC_Head, before the standard PyObject header for every container object. This header contains two pointers: _gc_next and _gc_prev.

These pointers create a doubly linked list of all container objects within a single generation. When the GC runs, it doesn't scan all memory; it simply walks this dedicated list, which is a much more efficient operation.

The following reading dives into the CPython source to show exactly how these structures are defined and used.

The Cycle Detection Algorithm

Now we arrive at the core of the garbage collector: the algorithm used to find unreachable cycles. This process, as described by Pablo Galindo Salgado (a CPython core developer), is a complex but elegant solution. Let's break it down into its main phases.

For this explanation, we'll use the linked-list example from the LINK article, where link1, link2, and link3 form a cycle, and an external variable A points to link1. This makes link1 reachable from the outside, while link2 and link3 are only reachable through the cycle.

Phase 1: Accounting for All References

The GC starts with the list of all container objects in the generation it's scanning.

1. Copy Reference Counts: The GC cannot safely modify the real reference counts (ob_refcnt) during its analysis. Instead, for each object in the list, it copies the value of ob_refcnt into a temporary field, gc_refs.

2. Subtract Internal References: The GC then traverses every object in its list again. For each object, it finds all other objects it refers to (its "children"). If a child is also in the list of objects being scanned, the GC decrements the child's gc_refs count.

The intuition here is crucial: this step "subtracts" all references that are internal to the group of objects being scanned.

• If an object's gc_refs drops to 0, it means all references to it came from within the cycle group. It is potentially garbage.
• If an object's gc_refs remains greater than 0, it means it has at least one reference from outside the group (like our variable A pointing to link1). This object is a candidate for being "reachable."

This first part of the algorithm is explained well in the following resources.

Phase 2: Identifying Truly Unreachable Objects

Having a gc_refs of 0 isn't enough to condemn an object. It could be part of a cycle that is attached to a reachable object. The next phase weeds these out.

The GC logically splits the objects into two lists: reachable and unreachable.

1. The algorithm iterates through the objects. Any object with a non-zero gc_refs is known to be reachable from outside and remains in the reachable list. The algorithm then transitively follows all references from this object. Any object it can reach is also "rescued" and moved (or kept) in the reachable list.

2. Any object with a gc_refs of 0 is tentatively moved to the unreachable list.

3. The key is the "rescue" operation. If a reachable object (like our link1) points to an object that was tentatively marked as unreachable (like link2), the GC moves link2 back into the reachable list. It then continues this process from link2 to see if it can rescue link3.

At the end of this phase, the unreachable list contains only those objects that belong to cycles completely isolated from the rest of the program.

The same resources from before continue to explain this phase beautifully.

Phase 3: Breaking the Cycles

Now that the GC has identified the garbage cycles, it must break them. It does this by calling a special C-level method on each object in the unreachable set called tp_clear.

The tp_clear function's job is simple: nullify all internal references the object holds.

• For a list, tp_clear clears all its elements.
• For a dict, it clears all key-value pairs.
• For a custom object instance, it clears its __dict__.

By severing these internal connections, the reference cycle is broken. The objects' reference counts immediately drop, and the standard reference counting mechanism takes over to deallocate the now-zero-count objects.

A complication arises if an object in the cycle has a __del__ method (a finalizer). In modern Python, the GC will call these finalizers. However, a finalizer could "resurrect" an object by creating a new external reference to it. If the GC detects this, it aborts the collection for the resurrected object and anything it refers to, ensuring program state remains consistent.

This final stage is detailed in the last part of the PyCon talk.

Conclusion

In this lesson, we demystified Python's cyclic garbage collector. You now have a deep, systems-level understanding of how CPython complements reference counting to provide robust, automatic memory management.

Here are the key takeaways:

• Purpose: The cyclic GC is a secondary mechanism designed specifically to detect and collect unreachable objects involved in reference cycles.
• Generational Strategy: It operates on generations (0, 1, 2) to remain efficient, focusing collection efforts on young, short-lived objects.
• Object Tracking: It only tracks container objects, which are linked together in a doubly linked list per generation via the PyGC_Head struct.
• Detection Algorithm: The GC uses a multi-phase algorithm that involves:
  1. Copying reference counts to a temporary gc_refs field.
  2. Subtracting internal references to find potential cycle members.
  3. Traversing from known-reachable objects to "rescue" any connected cycles.
• Cleanup: Isolated cycles are broken by calling each object's tp_clear method, which severs its internal references, allowing the standard reference counting mechanism to perform the final deallocation.

We have now covered the two pillars of memory management in CPython. This detailed model of how objects live, die, and relate to one another is fundamental. In our next lesson, we will build directly on this foundation to explore a common but often misunderstood operation: making copies of objects. We will learn to distinguish between shallow and deep copies using the copy module, an area where a clear mental model of object references is essential.