Collect unreachable objects by tracing the graph

Prerequisites: Pointers, object graphs, and basic graph traversal.

Learning objectives

• Identify roots and reachable heap objects.
• Trace mark-and-sweep on a graph containing a cycle.
• Explain why collection does not replace explicit resource management.

Reachability is a graph property

Model allocated objects as vertices and references between them as directed edges. Roots are references available directly to the running program, such as live stack or register references and relevant global variables. A tracing collector retains every object reachable from the roots. An unreachable object cannot be accessed through the modeled references and is eligible for reclamation.

Reachable does not mean useful to the application. A forgotten global list can retain a million obsolete objects, and a correct collector must keep them because they remain reachable. This is a logical memory leak caused by retention, even though the runtime prevents access to reclaimed storage.

Trace a cycle precisely

Suppose the roots reference A. A references B, B references C, and C references B. Separately, D and E reference each other but have no path from a root. Marking begins with A and discovers B and C. The reachable cycle B↔C is retained. The unreachable cycle D↔E is not marked and can be reclaimed.

heap = {'A': ['B'], 'B': ['C'], 'C': ['B'],
        'D': ['E'], 'E': ['D']}
marked, pending = set(), ['A']
while pending:
    obj = pending.pop()
    if obj in marked:
        continue
    marked.add(obj)
    pending.extend(heap[obj])
assert marked == {'A', 'B', 'C'}
assert set(heap) - marked == {'D', 'E'}

A simple mark-and-sweep collector first marks reachable objects, then examines allocated objects and reclaims unmarked ones. It must reset or otherwise manage marks for later collections. This code models graph reachability only; it is not a complete allocator or concurrent collector.

Implementation choices carry obligations

Basic reference counting tracks incoming references and reclaims an object when its count reaches zero. The isolated D↔E cycle can keep both counts nonzero despite being unreachable, so basic reference counting alone does not collect every cycle. Runtimes may add cycle detection or use tracing alongside it.

A moving collector can compact live objects and improve allocation locality, but all relevant references must be found and updated or safely handled. Conservative identification, foreign-function interfaces, and pinned objects complicate movement. Concurrent and incremental collectors reduce some pauses by coordinating collection with program mutation, typically requiring barriers and carefully maintained invariants.

Finally, memory reclamation is different from prompt release of files, sockets, locks, or transactions. Collection timing may be unpredictable, and finalization order may be restricted. Use explicit scoped cleanup or the language’s resource-management mechanisms when timely release matters. To investigate memory growth, inspect root paths and retained object graphs rather than assuming that running the collector more often can free objects the program still references.

Primary reading

• Memory Organization and Garbage Collection (Cornell University, CS312).

Practice problem

In the shown graph, remove the root reference to A and add a root reference to E. Determine the live and collectible objects. Explain why the cycle D↔E is now retained and the cycle B↔C is not. Then explain why a reachable but obsolete cache entry may still cause memory growth.

Worked solution

With E as the only root, traversal marks E and follows its edge to D, then follows D back to E without discovering any further objects. Live objects are therefore {D,E}. Objects A, B, and C are unreachable from the root set and are collectible, even though B and C still reference each other. A cycle neither guarantees retention nor guarantees collection; reachability from roots decides the result for tracing collection. A cache entry reachable through a global cache remains part of the root-reachable graph even when the application no longer benefits from it. The collector cannot infer the intended eviction policy. The program must remove or weaken the retention path according to a deliberate cache policy before collection can reclaim the entry.

Check your understanding

Which objects can a tracing collector reclaim?

• Every object in a cycle.
• Objects unreachable from the modeled roots.
• Every object older than one second.
• Only objects with zero internal references.

Explanation

Tracing follows root reachability, including through cycles.

Why can basic reference counting retain an unreachable cycle?

• The cycle’s objects can keep one another’s counts above zero.
• Reference counts cannot represent integers.
• Every cycle is always reachable from a root.
• Tracing collectors prohibit loops.

Explanation

Internal references remain even after all external paths disappear.

Primary reading

• Memory Organization and Garbage Collection: Cornell University, CS312

Open the study and save your work →