Tracing Mark-Sweep Cycle¶
Traversal algorithm — instantiates Reachability-Guided Resource Reclamation
Traces every resource reachable from the declared roots, marks it live, then sweeps away everything the trace never touched.
Tracing Mark-Sweep Cycle decides liveness globally, by construction rather than by tally. Starting from the declared roots, it walks every reference it can follow and marks each resource it reaches; when the walk is exhausted, the marked set is exactly the resources still reachable, and everything else — however it came to be orphaned — is provably dead. A sweep over the full universe of resources then frees the unmarked. Because the verdict comes from actual reachability and not from a per-object count, this mechanism reclaims garbage no accounting scheme can see, including mutually-referencing cycles: a loop of dead objects is unreachable from the roots, so the trace simply never marks it. The cost is symmetrical to the strength — the work is a whole-graph traversal plus a whole-universe sweep, done as a batch.
Example¶
Consider a Git repository's object database. Its resources are commits, trees, and blobs; its roots are the refs — branch tips, tags, HEAD, and the reflog. When you run git gc, Git traces outward from every ref: each commit points to its tree and its parent commits, each tree to its blobs and subtrees, and Git marks every object it reaches. Suppose you deleted a feature branch a week ago; the commits that were only on that branch are no longer named by any ref, so the trace from the surviving refs never reaches them. When the mark phase finishes, those commits and any blobs unique to them are unmarked — and the sweep prunes them from the object store, shrinking the repository. Notice that Git did not track a count per object; it recomputed the entire reachable set from the roots and let the unreachable remainder fall away. The technique traces back to John McCarthy's original garbage collector for Lisp.[1]
How it works¶
The cycle has two phases. Mark: perform a transitive traversal (depth- or breadth-first) from the root set, setting a live bit on every resource visited; the set of marked resources is the reachable closure. Sweep: iterate over the entire resource universe and reclaim every resource whose bit is clear, then clear the bits for the next cycle. Liveness is decided by presence in the closure, so graph shape — chains, diamonds, cycles — is irrelevant; only reachability matters. In its basic form the whole cycle runs as a single batch while mutation is paused.
Tuning parameters¶
- Trigger threshold — how full or how old the resource set must get before a cycle runs. Frequent cycles keep the reclaimable backlog small but spend traversal cost often; rare cycles amortize better but let dead resources pile up.
- Traversal order and mark-stack size — depth-first is memory-light on the stack; explicit work-lists bound worst-case depth on pathological graphs.
- Sweep laziness — free everything in one pass, or sweep incrementally as reclaimed slots are next requested, spreading the sweep cost over subsequent use.
- Compaction — whether the sweep also relocates survivors to defragment. Compaction removes fragmentation but adds a relocation pass and pointer fix-ups.
When it helps, and when it misleads¶
Its strength is completeness: it reclaims everything genuinely unreachable regardless of graph structure, which is precisely the cycle-shaped garbage a local counter can never free. It needs no ownership discipline from the code that creates references. Its failure mode is the batch cost — a full trace is proportional to the live set and the sweep to the whole universe, so a naive full collection over a large heap produces a long stop-the-world pause. It also suffers floating garbage: a resource that dies just after being marked survives until the next cycle. The classic misuse is triggering full collections too aggressively on a big heap, trading memory headroom for latency spikes. The guarding discipline is to tune the trigger to the workload, and where pauses cannot be tolerated, to move the trace off the critical path rather than run it more often.
How it implements the components¶
resource_universe_boundary— the sweep must enumerate every managed resource to free the unmarked ones, so the mechanism is defined over a known, bounded universe.authoritative_root_set— the trace begins from the declared live roots (in the example, the repository's refs); reachability is defined relative to them.reachable_closure_record— the mark bits are the closure: the transitive set of resources reachable from the roots, recomputed each cycle.reclamation_policy— sweep-the-complement: whatever the closure did not cover is freed in one batch.
It maintains no candidate_reclamation_set as a standing quarantine — it frees the complement of the closure in place, whereas enumerating a reviewable candidate list is dry_run_reclamation_report's job — and it holds no synchronization_and_epoch_rule to run beside a live mutator, which is concurrent_collection_barrier's. edge_semantics_policy (strong versus non-owning edges) is weak_reference_registry's.
Against its nearest twin reference_counting: that mechanism decides from a local per-object count and cannot see cycles; this one decides from a global reachable closure and therefore can.
Related¶
- Instantiates: Reachability-Guided Resource Reclamation — supplies the complete, structure-agnostic reclamation verdict the archetype computes from roots.
- Sibling mechanisms: reference_counting · generational_collection · concurrent_collection_barrier · cycle_detection_pass · dry_run_reclamation_report · reachability_graph_visualization · lease_expiry_sweep · tombstone_then_delete · weak_reference_registry
Editorial Notes¶
Form Classification¶
Form family: Control, Automation & Runtime
Rationale: Tracing Mark-Sweep Cycle operates as a live operational control that automatically routes, enforces, adapts, or responds during execution because it traces every resource reachable from the declared roots, marks it live, then sweeps away everything the trace never touched.
Independent corroboration: The frozen evidence defines Tracing Mark-Sweep Cycle as 'Traces every resource reachable from the declared roots, marks it live, then sweeps away everything the trace never touched', so its operative form is Control, Automation & Runtime.
Nearest alternative: Protocol, Workflow & Routine — Tracing Mark-Sweep Cycle includes features of a repeatable ordered procedure or handoff sequence that coordinates action, but its defining operation is a live operational control that automatically routes, enforces, adapts, or responds during execution.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine introduces tracing from accessible roots followed by reclamation of unmarked list structures, the historical mark-and-sweep lineage. This directly supports computer science as the best-evidenced historical home of the operation—Traces every resource reachable from the declared roots, marks it live, then sweeps away everything the trace never touched.—while the alternates record adjacent lineages rather than mere domains of later use.
Related originating lineages:
- Engineering & Design — Engineering design, reliability, and systems-safety practice supplies a parallel or contributing lineage for the mechanism's defining operation: traces every resource reachable from the declared roots, marks it live, then sweeps away everything the trace never touched.
- Organizational & Management Science — Organizational management supplies a historically relevant adjacent lineage or formative practice for the operation—Traces every resource reachable from the declared roots, marks it live, then sweeps away everything the trace never touched.—but the researched evidence more directly locates the defining lineage in computer science.
- Systems Thinking & Cybernetics — Feedback, system boundaries, stocks, flows, and regulation supplies a distinct formative lineage for the mechanism's tracing mark sweep cycle logic.
Review resolution: The blind reviewers disagree on primary lineage (organizational_management versus computer_science). The defining operation is: Traces every resource reachable from the declared roots, marks it live, then sweeps away everything the trace never touched. The researched McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine introduces tracing from accessible roots followed by reclamation of unmarked list structures, the historical mark-and-sweep lineage. That is mechanism-specific evidence for computer science as the historical origin. Organizational management remains represented among the uncapped alternates where it contributes a genuine formative practice, but broad deployment or governance of the operation is not by itself evidence that the mechanism originated there. origin_mode=single_lineage records lineage; domain_reach=specialized separately records later applicability.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Researched adjudication after independent review; high confidence.
Sources consulted:
Notes¶
This mechanism is the substrate several siblings refine rather than replace: generational_collection restricts the trace to young resources most of the time, concurrent_collection_barrier lets the trace run beside a live mutator, and dry_run_reclamation_report runs the trace in simulation to preview its verdict.
References¶
[1] The mark-and-sweep collector was introduced by John McCarthy in his 1960 paper describing Lisp — the first automatic garbage collector, and still the reference design against which reachability-based reclamation is taught. withdrawn registry ↩