Fix the experiment boundary
Build a model that keeps exactly the vertices reachable from a specified root set. It uses only Python 3.12 standard facilities and never manipulates the process's actual heap. Strings identify objects; lists of strings represent outgoing references. We are not measuring how Python collects the dictionary used to hold this model. Read the reachability guide first and be ready to explain traversal from roots.
The questions are whether an unreachable cycle disappears, shared targets are expanded only once, and an added root changes the result. Pauses, generations, concurrent mutation, and object movement are outside the experiment. Report this as a test of marking and reclamation on a fixed graph. Removing a dictionary entry is also different from returning physical storage to the operating system.
Predict the sets before running
Object a refers to b and c, while b also refers to c. Object c points back to a, so this component contains both sharing and a cycle. Objects d and e form a separate cycle. A cache retains a payload. With only a as a root, the expected live set is a, b, and c; d, e, cache, and payload are candidates for reclamation. Write these sets before consulting the assertions.
Adding b as another root changes nothing because b was already reachable. Adding cache instead brings both cache and payload into the live set. An empty root set reaches nothing. These inputs test the meaning of reachability, not execution speed. Follow how the visited set prevents repeated expansion when c is reached through two different paths.
Save the program and run every assertion
Save the program as gc_model.py and run python3.12 gc_model.py. The mark function only traces. The collect function constructs a fresh dictionary containing the marked vertices. Because the input is not mutated, the same heap can be compared under different root sets. A reference to an absent identifier raises ValueError rather than being silently ignored; otherwise a malformed graph could be mistaken for a collection result.
The output lists a, b, and c as live and cache, d, e, and payload as reclaimed, followed by GC graph assertions passed. Sorting stabilizes presentation; traversal order is not a correctness condition. All assertions were executed successfully with Python 3.12.14. The observed values are identifier sets, not byte counts, elapsed times, or statistics from a real collector.
heap = {
'a': ['b', 'c'],
'b': ['c'],
'c': ['a'],
'd': ['e'],
'e': ['d'],
'cache': ['payload'],
'payload': [],
}
def mark(heap, roots):
pending = list(roots)
live = set()
while pending:
obj = pending.pop()
if obj not in heap:
raise ValueError('dangling reference: ' + obj)
if obj in live:
continue
live.add(obj)
pending.extend(heap[obj])
return live
def collect(heap, roots):
live = mark(heap, roots)
return {obj: list(refs) for obj, refs in heap.items() if obj in live}
assert mark(heap, {'a'}) == {'a', 'b', 'c'}
assert mark(heap, {'a', 'b'}) == {'a', 'b', 'c'}
assert mark(heap, {'a', 'cache'}) == {'a', 'b', 'c', 'cache', 'payload'}
assert mark(heap, set()) == set()
remaining = collect(heap, {'a'})
assert set(remaining) == {'a', 'b', 'c'}
assert remaining == collect(remaining, {'a'})
assert set(heap) == {'a', 'b', 'c', 'd', 'e', 'cache', 'payload'}
try:
mark(heap, {'missing'})
except ValueError as error:
assert str(error) == 'dangling reference: missing'
else:
raise AssertionError('invalid root accepted')
print('live:', sorted(remaining))
print('reclaimed:', sorted(set(heap) - set(remaining)))
print('GC graph assertions passed')Explain termination using the loop invariant
The pending worklist holds references still requiring inspection. Every vertex in live has been discovered through a path from a root. Once a vertex enters live, removing it from pending again does not expand its outgoing edges. A finite heap therefore cannot force endless expansion through a cycle. Trace the edge from c back to a to see the condition in action.
Sharing can still put duplicate identifiers into pending. The implementation does not promise a duplicate-free worklist; it promises that an already visited vertex is not expanded again. Under the usual assumptions about dictionary and set operations, marking is understood in terms of O(V + E) work for vertices and edges. Collection additionally scans the heap dictionary. Tiny execution times do not establish general pause behavior.
Separate changed expectations from invalid input
Add d to c's outgoing references. The first original assertion should fail: a now reaches c, d, and e. That failure does not show a defect in marking. The input changed while the expected set did not. Update the prediction to a, b, c, d, and e and revise the reclaimed set accordingly. Cache and payload remain unreachable.
The final test deliberately supplies a missing root and requires ValueError. Merely reaching a success message is insufficient; rejection of malformed input is part of the contract. Our model assumes the graph stays fixed throughout marking and collection. Supporting mutation during traversal requires another rule defining the heap view being collected. Appending to reference lists while traversing them would not, by itself, implement a concurrent collector.
Add a monotonicity check for roots
On the same fixed heap, adding roots cannot make a previously reachable vertex unreachable. Add an assertion that mark(heap, {'a'}) is a subset of mark(heap, {'a', 'cache'}). The important condition is that no heap edges change between the two calls. Changing roots and removing edges at the same time no longer tests this simple property. This extension checks a relationship between results rather than duplicating one expected list. It also provides a small example of why a comparison should change only the condition named in its explanation.
Exercise and worked answers
First explain why collecting twice with the same roots gives the same graph. The first collection removes only unreachable vertices and preserves the paths among survivors. A second pass therefore has nothing further to remove. Next explain the assertion that the original heap still contains every initial key. It protects comparisons from accidental mutation of their shared input.
Finally add cache to the roots and ask whether declaring the payload useless makes it collectible. It does not in this model: the reference path remains. Your record should contain changed edges, roots, predicted live sets, observed results, and the Python version. Distinguish the unreachable cycle that disappeared from the reachable cycle that survived. “A cycle was collected” alone leaves out the reason that determined the result.