Cycle Detection Pass¶
Graph analysis — instantiates Reachability-Guided Resource Reclamation
Finds groups of resources that keep each other alive by mutual reference yet are collectively unreachable — the cycles a reference count can never free.
Cycle Detection Pass exists to recover one specific class of garbage: resources that hold each other alive in a loop but are, as a group, unreachable from anything outside the loop. A reference count can never free such a group, because each member's count is propped up by another member. This pass finds those self-sustaining islands. Rather than trace the entire universe from the program's roots, it works locally over the suspect subgraph — resources whose counts are nonzero but might be sustained only from within a cycle — and asks a sharper question than "is this reachable?": "would this resource's count survive if we ignored the references coming from its own group?" What fails that test is an unreachable cycle. It is a targeted supplement, not a general collector.
Example¶
CPython manages memory primarily by reference counting, which frees most objects promptly but is blind to cycles. Build a two-node loop — a parent object whose attribute points to a child, and a child whose .parent points back — then drop every external name for both. Each still has a reference count of one, contributed entirely by the other, so neither is freed and the pair leaks. CPython's cyclic garbage collector is the cycle detection pass that reclaims them. Periodically it examines the container objects that could participate in cycles, computes for each a hypothetical count with all intra-group references subtracted out, and finds that both the parent and the child would drop to zero once their mutual references are discounted — while any object still supported by a reference from outside the suspect set stays alive and anchors the reachable region. The parent/child pair is exposed as an unreachable cycle and collected; a sibling object still held by a live variable is untouched.
How it works¶
The pass restricts attention to resources that can form cycles (typically containers) and reads their references among one another. Using trial deletion,[n1] it computes each candidate's reference count minus the references originating from within the candidate set. Resources whose count remains positive are supported from outside — they are the reachable anchors — so it marks outward from them; whatever the marking does not reach is a genuinely unreachable cycle and is collected. The scope is the suspect subgraph, never the whole heap: it presumes an underlying counter has already reclaimed everything acyclic and only the loops remain to be swept up.
Tuning parameters¶
- Invocation cadence — how much allocation-minus-deallocation churn accrues before a pass runs. Frequent passes bound the memory a leaked cycle can hold; infrequent passes cut the graph-scanning overhead.
- Suspect scope — which resource types are even considered (only those capable of holding references worth tracing). Narrowing the scope makes each pass cheaper but risks missing exotic cycle carriers.
- Generational partitioning of the pass — bucketing candidates by how many passes they have survived, so long-lived containers are re-examined less often.
- Finalizer handling — whether resources carrying finalizers inside a cycle are collected, deferred, or reported, since their teardown order is ambiguous.
When it helps, and when it misleads¶
Its strength is precise: it recovers exactly the leak class a local counter structurally cannot, and it does so without paying for a full-universe trace. It misleads when treated as a primary collector — it presumes a counter has already done the bulk of the work, and run alone it is neither complete nor efficient. Its honest costs are the expense of scanning the container graph and the genuine ambiguity of collecting cycles that contain finalizers, whose teardown order is undefined and whose resurrection is possible. The classic misuse is assuming reference counting alone suffices and never scheduling the pass, so a service leaks slowly through cyclic structures until it exhausts memory in production. The guarding discipline is to run it as a routine backstop to the counter and to keep finalizer semantics for cyclic resources explicit rather than incidental.
How it implements the components¶
reference_and_dependency_graph— it reads the reference edges among suspect resources, both inbound and outbound, as its raw material.reachable_closure_record— it computes a local closure: which suspects remain externally supported (and thus reachable), marking outward from them.candidate_reclamation_set— the suspects left unreached after trial deletion are the reclamation set: the unreachable cycles.
It consults no authoritative_root_set and does not trace the whole heap from the program's declared roots — that general reachability computation is tracing_mark_sweep_cycle's — and it does not perform the eager per-object reclamation_policy at count-zero, which is reference_counting's.
Against its nearest twin tracing_mark_sweep_cycle: that mechanism traces the entire universe from the roots; this one examines only the suspected-cyclic subgraph — objects with nonzero counts that might be sustaining themselves — and discounts intra-group references rather than starting from roots.
Related¶
- Instantiates: Reachability-Guided Resource Reclamation — supplies the recovery step for the one leak class local counting cannot reach.
- Consumes: reference_counting — it exists to clean up the cycles that mechanism structurally leaves behind.
- Sibling mechanisms: tracing_mark_sweep_cycle · generational_collection · concurrent_collection_barrier · dry_run_reclamation_report · lease_expiry_sweep · reachability_graph_visualization · tombstone_then_delete · weak_reference_registry
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Cycle Detection Pass operates as a computation, comparison, model, or analytic representation used to infer, estimate, or choose because it finds groups of resources that keep each other alive by mutual reference yet are collectively unreachable — the cycles a reference count can never free.
Independent corroboration: The frozen evidence defines Cycle Detection Pass as 'Finds groups of resources that keep each other alive by mutual reference yet are collectively unreachable — the cycles a reference count can never free', so its operative form is Analysis, Modeling & Optimization.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Programming-language runtime research cohered cyclic garbage-collection passes that detect reference groups sustained only by internal links and reclaim them without disturbing externally reachable objects.
Review outcome: Independent reviewer agreement; high confidence.
Notes¶
This pass is meaningful only as the partner of reference_counting: the counter reclaims all acyclic garbage promptly, leaving cycles as the sole residue for this pass to sweep. Read alone, it looks like a worse mark-sweep; read as a backstop, it is the missing half of a counting collector.
[n1] Trial deletion — the technique at the heart of Bacon and Rajan's cycle-collection algorithm: hypothetically remove a candidate's internal references and observe whether its count would fall to zero, which reveals a group sustained only by its own internal loop. ↩