Garbage Collection: How Automatic Memory Works

Automatic memory management changes who decides when storage can be reused. A program allocates objects, connects them into a graph, drops some connections, and keeps running. The garbage collector (GC) must distinguish objects the program may still observe from objects that have become impossible to reach, then recover the latter safely.

This is a live systems problem. Application threads mutate the graph while the collector inspects it. Compaction improves locality but requires every reference to move correctly. Low average pause time can also conceal damaging tail pauses. Understanding GC means understanding these tradeoffs.

Reachability defines liveness #

Most managed runtimes model the heap as a directed object graph. An edge exists when one object contains a reference to another. Collection starts from roots: references known to be immediately usable by running code, such as local variables in active stack frames, static or global fields, CPU registers described by stack maps, runtime handles, and some native interop references.

An object is live if a path from any root reaches it. Let R0 be the root set and refs(x) be the objects referenced by x. The reachable set is the least fixed point:

Tracing stops when $R_{n+1} = R_n$. Every allocated object outside the final set is garbage:

Request and Buffer form a cycle, but they remain live because the stack reaches them. Detached node and Listener also form a cycle, yet neither has a path from a root, so a tracing collector can reclaim both. The collector does not ask whether an object is useful in a business sense. A forgotten cache entry is reachable and therefore live even if the application will never intentionally read it again.

Tracing and reference counting solve different problems #

Reference counting stores the number of incoming references to each object. Adding an edge increments the count; removing one decrements it. At zero, the object can be destroyed immediately, and releasing its outgoing edges may cascade. This gives predictable reclamation in systems such as Swift ARC, Python, and C++ smart pointers.

Its blind spot is a cycle. If A points to B and B points to A, each count stays positive after external references disappear. Python adds a cycle detector; weak references and ownership rules can also break cycles. Counting adds work to reference assignments, sometimes including atomic operations across threads.

Tracing starts at roots and discovers the live graph. Cycles need no special case: an unreachable cycle is simply never marked. Tracing usually amortizes work into collection phases and can move objects, but it introduces pauses or concurrent coordination.

Neither family eliminates ownership. File descriptors, sockets, locks, GPU buffers, and transactions should have deterministic lifetimes through using, defer, finally, or explicit close. A finalizer runs at an unspecified time, may never run before process exit, and can delay reclamation by at least one collection cycle.

Mark, sweep, compact, and copy #

A basic mark-sweep collector marks every object found from roots, then sweeps unmarked blocks into free lists. Objects keep stable addresses, but allocation can leave fragmented holes. Sweep cost may follow heap capacity rather than live data.

Mark-compact marks live objects, slides them together, and updates references. It enables pointer-bump allocation and improves locality, but moving live bytes is expensive. Runtimes may compact only fragmented regions.

A copying collector copies each reachable object from a source to a destination space and records a forwarding address. The source then becomes free and survivors are compact. Cost follows live data, but copying needs bandwidth and destination capacity.

The useful cost model is not merely “GC is expensive.” If live_bytes survive a copying pass with memory bandwidth copy_bandwidth, a lower bound for movement is approximately:

Reducing allocation may lower collection frequency, while reducing long-lived state lowers the work of major collections. Those are different optimizations.

A small generational tracing collector #

Real collectors encode object layouts, coordinate threads, scan registers, and maintain regions. This pseudocode keeps the central rules: roots seed tracing, a full collection scans everything, a minor collection scans young objects from roots and remembered old objects, and a write barrier records every old-to-young edge.

WRITE(source, target):
    source.fields.add(target)
    if source.old and target.young:
        remembered.add(source)       // write barrier

TRACE(seeds, eligible):
    work = stack(seeds)
    while work is not empty:
        object = work.pop()
        if object is unmarked and eligible(object):
            object.marked = true
            work.pushAll(object.fields)

FULL_COLLECT(roots):
    TRACE(roots, every_object)
    reclaim every unmarked object; clear remaining marks

MINOR_COLLECT(roots):
    seeds = young references in roots
    seeds += young references from remembered old objects
    TRACE(seeds, young_objects_only)
    reclaim unmarked young objects
    age survivors; promote objects past the age threshold

Without the barrier, a minor collection could reclaim a young object still referenced by an old one. The remembered set summarizes where cross-generation edges originate. Production runtimes often use card tables: a write dirties an address range, and the collector rescans objects in dirty cards.

Generations, pauses, and concurrent work #

The generational hypothesis says most newly allocated objects die young. Temporary strings, request wrappers, iterator results, and intermediate arrays often disappear before the next few collections. A generational collector allocates them in a nursery and collects that small area frequently. Survivors age and eventually promote to an old generation collected less often.

This is an optimization, not a semantic rule. Workloads with many medium-lived objects can survive several nursery passes and then die soon after promotion, causing premature promotion and pressure in the old generation. A nursery that is too small collects frequently; one that is too large may produce longer minor pauses. Promotion thresholds and region sizing therefore depend on the observed lifetime distribution.

Collectors also differ in how they coordinate with application threads, often called mutators:

• A stop-the-world collector pauses mutators while tracing or relocating. It is simpler and may maximize throughput for batch jobs.
• An incremental collector divides work into short slices, reducing individual pauses at the cost of barriers and bookkeeping.
• A concurrent collector marks or sweeps while mutators run. It still needs brief synchronization pauses and enough CPU headroom to keep up.
• A mostly concurrent compacting collector may relocate selected regions while using forwarding pointers, read barriers, or short evacuation pauses.

Concurrency creates a snapshot problem. Suppose the collector has scanned object A; the application then stores a pointer from A to an unmarked object B and removes the only other path to B. A collector unaware of that mutation could reclaim a live object. Barrier strategies preserve an invariant: incremental-update barriers shade newly installed references, while snapshot-at-the-beginning barriers record overwritten references so the collector observes the logical starting graph.

Leaks, metrics, tuning, and misconceptions #

A garbage-collected program can absolutely leak memory. A leak is unwanted retention, not merely unreachable storage that has not yet been collected. Unbounded maps, event listeners never removed, timers capturing large closures, queue backlogs, accidental globals, and caches without eviction all keep paths from roots to data. The GC is correct to preserve them.

Heap snapshots answer “what retains this object?” through dominator trees and retaining paths. Allocation profiles answer “where is memory being created?” A single snapshot can mislead because a healthy heap naturally grows between collections. Compare snapshots after equivalent full-GC points or inspect trends over repeated workload cycles.

Useful operational signals include:

One practical pressure estimate is:

If allocation_headroom stays negative, increasing the heap only delays failure. If the live set is stable but pauses are frequent, a larger nursery may help. If major pauses move too many live bytes, reducing retained state or choosing a concurrent collector may matter more. If GC CPU is high because short-lived allocation is extreme, remove allocation from hot paths only after a profile proves it significant.

Common misconceptions lead directly to bad tuning:

• “GC removes all memory bugs.” It prevents many use-after-free and double-free errors, but not retention leaks, native-memory corruption, or resource leaks.
• “Calling GC manually fixes a leak.” It may clarify a measurement; it cannot sever a reachable path.
• “A larger heap is always faster.” It can reduce frequency but increase major-cycle work, footprint, and worst-case pause time.
• “Zero allocations is the goal.” Allocation can be extremely cheap with bump pointers. Optimize latency, throughput, and footprint, not a ritual counter.
• “Finalizers are destructors.” Their timing and ordering are nondeterministic, so correctness must not depend on them.

Takeaways #

• Reachability from roots, not intuition or cycle membership, defines liveness in a tracing collector.
• Reference counting offers prompt reclamation but needs help with cycles; tracing naturally reclaims unreachable cycles.
• Mark-sweep preserves addresses, compaction improves density, copying makes cost follow survivors, and generations exploit common lifetime patterns.
• Write barriers are correctness mechanisms that let collectors skip or concurrently inspect parts of a changing graph.
• Concurrent collectors reduce pauses but do not abolish synchronization, CPU cost, or memory overhead.
• Managed memory can still leak through unwanted reachable paths; retaining paths and post-collection live-set trends expose them.
• GC tuning is workload tuning. Measure allocation, survival, promotion, pauses, and collector CPU before changing heap sizes or algorithms.