Generational Cyclic Garbage Collection

While reference counting is deterministic and instant, it has one fatal architectural flaw: it cannot detect or collect cyclic references.

When two or more container objects reference each other ($A \to B \to A$), their reference counts remain positive ($r(A) \ge 1, r(B) \ge 1$) even after all external variable references have been deleted. Without a secondary cleanup mechanism, these orphaned cycles would leak memory permanently.

To solve this, CPython incorporates a Generational Cyclic Garbage Collector dedicated to discovering and reclaiming unreachable reference cycles.

1. The Reference Cycle Problem#

Consider two simple objects holding references to each other:

When you execute del a and del b:

1. The external variable pointers a and b vanish.
2. The reference count of each node drops from 2 to 1 ($r(A) = 1, r(B) = 1$).
3. Because neither refcount reached zero, neither deallocator fires!
4. The two nodes are now completely inaccessible from your program, floating in RAM as permanent memory leaks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gc

class Node:
    def __init__(self, name: str):
        self.name = name
        self.partner = None

# Disable GC temporarily to demonstrate the leak
gc.disable()

# Create cyclic references
a = Node("A")
b = Node("B")
a.partner = b
b.partner = a

# Delete root variables
del a
del b

# Memory is leaked! But gc.collect() can find and clean it:
unreachable_count = gc.collect()
print(f"Cyclic GC collected {unreachable_count} unreachable objects!")

2. Container Tracking & PyGC_Head#

Atomic primitives like integers, floats, and strings cannot form reference cycles because they cannot hold references to other objects.

Therefore, CPython optimizes performance by excluding atomic types from the cyclic garbage collector entirely! Only container types (lists, dicts, sets, tuples, custom classes) with the Py_TPFLAGS_HAVE_GC flag are tracked.

When a container object is allocated, CPython prepends a PyGC_Head struct directly before the PyObject header in RAM:

The gc_next and gc_prev pointers link all tracked container objects into a doubly-linked circular ring.

3. The Three Generations: $G_0, G_1, G_2$#

CPython's cyclic collector is grounded in the Weak Generational Hypothesis: most objects created by a program die very young (temporary loop variables, transient function arguments, intermediate strings).

To avoid scanning every container object in RAM on every sweep, CPython partitions tracked containers into three generations:

Collection Thresholds#

CPython tracks collection counts via thresholds $(T_0, T_1, T_2)$, default (700, 10, 10):

1. Generation 0: Swept whenever net container allocations (allocations minus deallocations) exceed $T_0 = 700$.
2. Generation 1: Swept whenever Generation 0 has been collected $T_1 = 10$ times.
3. Generation 2: Swept whenever Generation 1 has been collected $T_2 = 10$ times (full collection).

Objects that survive a collection sweep are promoted to the next older generation. Long-lived objects (like loaded module dictionaries or caches) quickly settle in Generation 2, exempting them from frequent GC scans.

4. Inspecting the GC Subsystem#

You can inspect and tune the garbage collector dynamically via the gc module:

1
2
3
4
5
6
7
8
9
10
11
import gc

# Inspect current thresholds: (700, 10, 10)
print(f"GC Thresholds (T0, T1, T2): {gc.get_threshold()}")

# Inspect current generation allocation counters: (count0, count1, count2)
print(f"Current GC Counters: {gc.get_count()}")

# Force an immediate full collection of all generations
collected = gc.collect()
print(f"Objects collected: {collected}")

5. Concept Verification#

Test your understanding of the cyclic garbage collector: