How Python Garbage Collection Works Internally: A Deep Dive

What is Garbage Collection in Python?

Garbage collection is a secondary memory management mechanism in Python (specifically CPython) designed to reclaim memory from objects that reference counting can’t handle—namely, those trapped in cyclic references . A cyclic reference occurs when objects reference each other (directly or indirectly), preventing their reference counts from reaching zero even when they’re no longer accessible from the program.

Python’s garbage collector, implemented in the gc module, periodically scans memory to identify and free these unreachable objects, complementing the immediate deallocation provided by reference counting.

Why Garbage Collection is Needed

Reference counting is fast and predictable but has a key limitation: it can’t detect cycles . Consider this example:

Copy codelist1 = [] 
list2 = [] 
list1.append(list2) # list1 references list2 
list2.append(list1) # list2 references list1 
del list1, list2 # Both still have refcount = 1 due to the cycle

After del list1, list2, no variable points to these lists, but their reference counts remain 1 because they reference each other. Without garbage collection, this memory would leak. The GC detects such cycles and frees the memory.

The Internal Architecture: Generational Garbage Collection

Python’s garbage collector uses a generational garbage collection algorithm, which divides objects into generations based on how long they’ve survived. This approach optimizes performance by focusing on newly created objects, which are more likely to become garbage, while minimizing checks on long-lived objects.

The Three Generations

• Generation 0 : Newly created objects.
• Generation 1 : Objects that survive one GC cycle from Generation 0.
• Generation 2 : Long-lived objects that survive multiple GC cycles.

Why Generations?

• Observation : Most objects die young (e.g., temporary variables in functions), while a few persist longer (e.g., global data structures).
• Efficiency : Checking only young objects (Generation 0) frequently and older generations less often reduces overhead.

Each generation has a list of objects tracked by the GC, stored in a doubly linked list for efficient traversal and updates.

How Garbage Collection Works Internally

The garbage collector operates in two main phases: cycle detection and memory reclamation . Here’s a step-by-step breakdown:

1. Tracking Objects

• The GC only tracks container objects that can hold references to other objects (e.g., lists, dictionaries, sets, custom classes). Simple types like integers, strings, and tuples (immutable) can’t form cycles and are left to reference counting.
• When a container object is created, it’s added to Generation 0 with a gc_refs field (a copy of its reference count) in its GC-specific header.

2. Triggering Garbage Collection

The GC runs:

• Automatically : When the number of allocations minus deallocations in Generation 0 exceeds a threshold (default: 700).
• Manually : Via gc.collect().
• The threshold can be adjusted with gc.set_threshold(threshold0, threshold1, threshold2).

When triggered, the GC starts with Generation 0. If needed, it propagates to higher generations (a process called a full collection ).

3. Cycle Detection Algorithm

The GC uses a mark-and-sweep-like algorithm to identify unreachable cycles:

1. Copy Reference Counts : For each object in the generation being collected, the GC copies its ob_refcnt (reference count) to gc_refs.
2. Subtract Internal References : For each object, the GC traverses its references (e.g., list elements) and decrements the gc_refs of referenced objects within the same generation. This simulates removing internal references within the cycle.
3. Identify Unreachable Objects : Objects with gc_refs > 0 are reachable from outside the generation (e.g., from the stack or globals) and survive. Objects with gc_refs == 0 are unreachable and part of a cycle.
4. Handle Survivors : Reachable objects (and their referenced objects) are moved to the next generation (e.g., Gen 0 → Gen 1).

4. Memory Reclamation

• Unreachable objects (those with gc_refs == 0) are deallocated:
  • Their destructors (__del__) are called if defined.
  • Their memory is returned to the Python Memory Manager’s free lists.
• The doubly linked list of tracked objects is updated to remove collected objects.

Example Internals

For the cycle list1 → list2 → list1:

• Initial state: list1.ob_refcnt = 1, list2.ob_refcnt = 1.
• GC copies: list1.gc_refs = 1, list2.gc_refs = 1.
• Subtract references: list1 references list2 (decrement list2.gc_refs to 0), list2 references list1 (decrement list1.gc_refs to 0).
• Result: Both have gc_refs = 0, so they’re collected.

Generational Collection in Action

Thresholds and Frequency

• Generation 0 : Collected when allocations exceed 700 (default).
• Generation 1 : Collected after 10 Generation 0 collections.
• Generation 2 : Collected after 10 Generation 1 collections.
• These counters are maintained in the gc module’s internal state.

Example

Copy codeimport gc 
    
gc.set_debug(gc.DEBUG_STATS) # Enable GC logging 
for i in range(1000): 
    lst = [] 
    lst.append(lst) # Self-referential cycle 
print(gc.collect()) # Forces collection, outputs stats

• After ~700 cycles, Generation 0 triggers a collection.
• Surviving objects move to Generation 1, and the process repeats.

Interaction with Reference Counting

• Complementary Roles : Reference counting handles immediate deallocations (refcount → 0), while GC handles cycles.
• Reference Count Updates : When the GC breaks a cycle, it adjusts ob_refcnt to allow deallocation via the Memory Manager.
• del Caveats : If an object in a cycle has a __del__ method, the GC leaves it as “uncollectable” to avoid unpredictable behavior:

  Copy codeclass MyClass:
      def __del__(self):
          print("Deleted")
  
  a = MyClass()
  b = MyClass()
  a.ref = b
  b.ref = a
  del a, b  # Cycle remains uncollected due to __del__
  print(gc.garbage)  # Lists uncollectable objects

Manual Control and Debugging

The gc module provides tools to interact with the garbage collector:

• gc.enable() / gc.disable(): Toggle automatic GC.
• gc.collect(generation): Force collection of a specific generation (0, 1, or 2).
• gc.get_stats(): Retrieve collection statistics.
• gc.set_debug(gc.DEBUG_LEAK): Log detailed info about uncollectable objects.

Example:

Copy codeimport gc

gc.disable()  # Turn off automatic GC
lst = []
lst.append(lst)
del lst
gc.collect()  # Manually collect, returns 1 (one object freed)

Performance and Optimization

• Overhead : GC adds runtime cost, but the generational approach minimizes it by focusing on young objects.
• Tuning : Adjust thresholds for long-running apps with gc.set_threshold() to balance memory usage and performance.
• Avoid Cycles : Minimize cyclic references to reduce GC workload.

Conclusion

Python’s garbage collector is a finely tuned system that ensures memory is reclaimed from cyclic references, complementing reference counting’s immediate deallocations. By using a generational approach and a cycle-detection algorithm, it efficiently identifies and frees unreachable objects while keeping overhead low. Understanding its internals—from generation tracking to reference subtraction—empowers developers to optimize memory usage and debug complex memory issues effectively.