Cycles and the garbage collector
Cycles and the garbage collector
A cycle that leaks
Problem. Two cart items each keep a reference to the other. We delete both names. How could CPython ever free them, when each still has a reference?
New words
- reference cycle: objects that hold references to each other
- garbage collector: code that frees objects that counting cannot
The class Node below holds a reference to one other node, and it prints when CPython deallocates it.
import gc
class Node:
def __init__(self, name):
self.name = name
self.other = None
def __del__(self):
print("freed", self.name)
x = Node("x")
y = Node("y")
x.other = y
y.other = x
del x, y
print("cycle deleted")
cycle deleted
No freed line appears. After del x, y, no name reaches either node. Each node still holds the other, so each count stays at 1 and cannot reach 0.
CPython runs a second mechanism for this case, the cycle collector. The gc module calls it by hand. The count below comes from CPython 3.12. Another version can count other internal objects.
print("collected", gc.collect())
freed x
freed y
collected 2
The function gc.collect() returns the number of unreachable objects that it found.
NOTE: Reference counting frees most objects at once. The collector exists only for cycles, and CPython does not promise that it finds every one.
Recall. After a = Node("a"), a.other = a and del a, does freed a print before gc.collect() runs?
A toy collector
Problem. How could the toy heap find objects that only refer to each other?
The collector subtracts the references that heap objects hold to each other. A count left above zero comes from outside, such as a name. Those objects are alive.
- Copy every object's count into
outside. - For each list, subtract 1 from
outsidefor each item that it holds. - Mark every address with
outsideabove 0 as alive. - Mark everything that an alive list holds as alive.
- Remove every object that is not alive.
Build a cycle of two lists that hold each other. Use a fresh run of the counted toy heap from the previous note, so heap, namespace and addresses start empty and the lists sit at addresses 1000 and 1001.
first = allocate("list", [])
second = allocate("list", [first])
heap[first]["value"].append(second)
incref(second)
bind("x", first)
bind("y", second)
unbind("x")
unbind("y")
The following trace table shows both counts after each of the last five lines of the code above.
heap[1000]["refcount"] |
heap[1001]["refcount"] |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 2 | 2 |
| 1 | 2 |
| 1 | 1 |
Both counts stay at 1, so counting alone frees nothing.
def collect():
outside = {}
for address, record in heap.items():
outside[address] = record["refcount"]
for record in heap.values():
if record["type"] == "list":
for item in record["value"]:
outside[item] -= 1
pending = []
for address, count in outside.items():
if count > 0:
pending.append(address)
reachable = set()
while pending:
address = pending.pop()
if address in reachable:
continue
reachable.add(address)
record = heap[address]
if record["type"] == "list":
pending.extend(record["value"])
garbage = []
for address in heap:
if address not in reachable:
garbage.append(address)
for address in garbage:
del heap[address]
return len(garbage)
print(collect(), len(heap))
2 0
The following trace table shows outside for the two lists.
address |
heap[address]["refcount"] |
outside[address] after step 2 |
|---|---|---|
| 1000 | 1 | 0 |
| 1001 | 1 | 0 |
No count stayed above 0, so nothing was alive, and collect removed both lists.
Only container objects, which can hold references to other objects, take part in cycles. An integer or a string cannot form one.
In CPython: update_refs() in Modules/gcmodule.c copies the counts, as in step 1. Then subtract_refs() subtracts the references between tracked objects, as in step 2.
Recall. Build the two-list cycle again, but keep bind("x", first) in place. After collect(), which of 1000 and 1001 survive, and why?
When the collector runs
CPython sorts container objects into three generations by the number of collections that they survived. New objects start in generation 0. A survivor moves to the next older generation. The collector runs when allocations minus deallocations pass threshold0, and it examines younger generations more often than older ones.
import gc
print(gc.get_threshold())
(700, 10, 10)
These are the CPython 3.12 values. Other versions can print other values. The call gc.disable() turns off automatic collection, and reference counting continues. Disable the collector only when a program creates no cycles.
In CPython: Python 3.12 added immortal objects (PEP 683). An immortal object has a count that never changes, so CPython never deallocates it. None, True, False and the static types are immortal. Py_DECREF returns early for them. So on 3.12, sys.getrefcount(None) returns a very large number.
Recall. On 3.12, after items = [None] * 1000, does sys.getrefcount(None) rise by 1000? Explain.
Sources
- The Python Standard Library, gc: https://docs.python.org/3.12/library/gc.html
- The Python Standard Library, sys (getrefcount): https://docs.python.org/3.12/library/sys.html
- The Python Language Reference, Data model, Basic customization (
__del__): https://docs.python.org/3.12/reference/datamodel.html - PEP 683, Immortal Objects, Using a Fixed Refcount: https://peps.python.org/pep-0683/
- PEP 442, Safe object finalization: https://peps.python.org/pep-0442/
- CPython source,
Modules/gcmodule.c, 3.12 branch: https://github.com/python/cpython/blob/3.12/Modules/gcmodule.c - CPython source,
Include/internal/pycore_runtime_init.h, 3.12 branch: https://github.com/python/cpython/blob/3.12/Include/internal/pycore_runtime_init.h
Cards
Why does a two-node reference cycle stay in memory after both names are deleted?
Reveal
Each node holds a reference to the other, so each count stays at 1. Neither count can reach 0 by counting alone.
What does gc.collect() return?
Reveal
The number of unreachable objects that it found.
In CPython 3.12, what does gc.collect() return after these lines?
import gc
class Node:
def __init__(self):
self.other = None
a, b, c = Node(), Node(), Node()
a.other = b
b.other = c
c.other = a
del a, b, c
Reveal
3. The three nodes hold each other in a ring, and no name reaches any of them. Another version can count other internal objects too.
A cycle collector copies every object's reference count, then subtracts 1 for each reference that another tracked object holds. What does a count left above 0 mean?
Reveal
A reference comes from outside the group, such as a name. That object is alive, and so is everything it reaches.
Which objects can take part in a reference cycle?
Reveal
Container objects, which can hold references to other objects. An integer or a string cannot.
How does an object move to an older generation in CPython's collector?
Reveal
It survives a collection. New objects start in generation 0, and the collector examines younger generations more often.
What does gc.get_threshold() return on CPython 3.12?
Reveal
(700, 10, 10). Other versions can return other values.
Does gc.disable() stop reference counting?
Reveal
No. It turns off automatic cycle collection only. Reference counting continues.
What is an immortal object in CPython 3.12, and what does Py_DECREF do for one?
Reveal
An object whose count never changes, so CPython never deallocates it. None, True and False are examples. Py_DECREF returns early for it.