Garbage Collection

Garbage collection (GC) automatically manages the memory lifecycle of some objects. The term "garbage" here is typically determined by observable reference relationships within the language and runtime; it does not imply that the collector knows with certainty what the program will never use again. An object that is no longer useful but is still referenced by a global cache for a long time may still be retained.

When understanding GC, it is important to separate several dimensions: how reclaimable objects are identified, whether objects are moved, whether generational collection is used, whether the work is parallel or concurrent, and how the compiler reports references. These can be combined and are not mutually exclusive product categories.

Roots, Object Graphs, and Conservative Approximations

Tracing GCs traverse the object graph starting from root references. Roots may reside in thread stacks, registers, global slots, or runtime handles, but not every word in these regions is necessarily a pointer.

Precise GCs rely on type layouts and stack maps to identify reference slots; conservative GCs may treat values that look like addresses as potential references, thereby mistakenly retaining some objects and limiting safe movement strategies. Precise and conservative describe reference identification capabilities and do not directly determine whether generational or concurrent collection is used.

Reference counting maintains counts as references change and reclaims objects when the count reaches zero. It does not need to traverse the entire graph from roots every time, but unreachable cycles of mutually referenced objects will not naturally reach zero, usually requiring other mechanisms to handle cycles. One cannot define GCs as "all performing the same kind of root traversal."

Mark-Sweep: Identify Live Objects, Then Reclaim Unmarked Space

The marking phase traverses objects reachable from roots; the sweeping phase reclaims the space of unmarked objects based on marking information. Implementations can handle pages, spans, or allocation metadata, and do not necessarily scan the entire reserved address space byte by byte.

Non-moving sweeping does not change object addresses, which is convenient for certain external references and fixed address requirements, but leaves behind holes of varying sizes. Allocator size classes and free list management can mitigate fragmentation; "sufficient total free space" does not guarantee the ability to satisfy all contiguous large object allocations.

The cost of marking is determined not only by the byte size of live objects but also by the number of pointers, object layout, and locality. Tracing work can differ significantly between a large byte array and a dense pointer graph of the same size.

Copying and Compaction: Changing Object Addresses During Reclamation

The classic semi-space collector divides the allocation space into from-space and to-space, copying live objects to the target space, updating references, and then swapping the roles of the two spaces. The Cheney algorithm organizes a breadth-first scan using two pointers in the target space: scan and free. Newly copied objects are appended to free, and scan processes their references sequentially until they meet.

Forwarding information ensures that multiple references pointing to the same object result in only one copy and provides a unified way to find the new address. Reclaiming the original area indicates it is available for reallocation, not that it must be immediately returned to the operating system.

The simple form of semi-space collection reserves half the region as the copying target, but this ratio cannot be generalized as the overall utilization rate for all moving GCs. Region-based, generational, and compaction algorithms have different space strategies. Moving also requires handling internal pointers, FFI handles, and pinned objects; updating roots alone is not enough.

Ensuring scan and free Truly Traverse an Object Graph

Use integers to represent old object addresses: 10 is A, pointing to B and C; 20 is B, also pointing to C; 30 is C, with no child references. Additionally, 40 and 50 form an unreachable cycle. The only root is A. By unifying object sizes to one slot and keeping only pointer fields, the copying algorithm can be reduced to the following complete model.

heap = {10: [20, 30], 20: [30], 30: [], 40: [50], 50: [40]}


def collect(heap, roots):
    forwarding, copied, queue = {}, [], []

    def evacuate(old):
        if old not in forwarding:
            forwarding[old] = len(copied)
            copied.append(None)  # Reserve slot and establish forwarding first, then scan fields
            queue.append(old)
        return forwarding[old]

    new_roots = [evacuate(old) for old in roots]
    scan, trace = 0, []
    while scan < len(copied):  # len(copied) is free in this model
        old = queue[scan]
        copied[scan] = [evacuate(child) for child in heap[old]]
        scan += 1
        trace.append((scan, len(copied)))
    return new_roots, copied, forwarding, trace


roots, copied, moved, trace = collect(heap, [10, 10])
assert roots == [0, 0]  # Two roots maintain aliasing relationship
assert copied == [[1, 2], [2], []]
assert moved == {10: 0, 20: 1, 30: 2}
assert trace == [(1, 3), (2, 3), (3, 3)]
assert collect(heap, [40])[1] == [[1], [0]]  # Reachable cycles are also copied only once
assert collect(heap, [])[1] == []

This sequence reveals two responsibilities of forwarding: preventing duplicate copying and maintaining object identity. If A and B originally shared C, they must still share the same C after reclamation; they cannot each copy a separate instance and silently change visibility of modifications. Registering forwarding before scanning fields also allows reachable cycles to terminate.

The new addresses in the model are array indices; real collectors advance byte pointers based on actual object sizes and alignment, and must also handle insufficient capacity in the copying target. This model assumes the object graph remains unchanged during collection, without implementing concurrent barriers, weak references, finalizers, or internal pointers.

Why do two references copy a shared object only once?

scan and free differ because copying does not yet update fields. Pending to-space objects can retain old addresses until scanned. A and B must both refer to C’s one new slot; rooting D also demonstrates forwarding-before-scanning termination for the D/E cycle. Equal object slots are a teaching convention.

$$[0,\mathrm{scan})\text{scanned},[\mathrm{scan},\mathrm{free})\text{pending}$$

Generational: Scan Long-Lived Objects Less Frequently

The weak generational hypothesis is that a large number of objects in many programs die quickly. If this hypothesis fits the workload, frequent collection of small young generations can reduce repeated scanning of long-lived objects. Promotion thresholds, generations, and per-generation algorithms are implementation-defined; young generations do not need to follow uniform sizes or collection counts.

Card tables typically record potential changes with granularity of small memory regions, while remembered sets can use finer object or reference slot representations. They inform young generation collection about which old objects might provide entries, without needing to scan the entire old generation.

If a program has many long-lived objects, frequent cross-generation writes, or young objects that promote quickly, the additional recording and copying costs of generational collection may diminish its benefits. Generational collection is a load-based optimization, not a mandatory phase for all GCs.

Parallel, Concurrent, and Incremental Are Not Synonyms

Parallel means multiple collection threads work together, while the application may still be paused; concurrent means the collector and application mutators execute simultaneously; incremental means splitting the work into smaller steps. These dimensions can appear simultaneously.

Mark-Sweep or copying can be used in both stop-the-world and concurrent schemes under supporting protocols. Concurrency may still require brief pauses to establish root views, transition phases, or complete cleanup; it cannot be directly called "application never pauses."

Barriers: Maintaining Information Required by Specific Algorithms

The three-color abstraction divides objects into white (not yet discovered), gray (discovered, pending scan), and black (scanned). Under the simple strong three-color invariant, black objects are not allowed to point to unprotected white objects; concurrent modifications change the graph, so barriers and work queues are needed to maintain correctness.

For example, the collector has already scanned A, the application subsequently writes a reference to B into A, and B's last pending scan path was previously removed. Without corresponding protection, B might still be referenced by the application but not marked.

Insertion barriers can record newly written references; deletion barriers or SATB-style barriers can preserve overwritten old references; mixed barriers combine different actions. Different algorithms maintain different invariants, so they cannot all be abbreviated as if black then gray.

Generational barriers mainly record cross-generation references, concurrent marking barriers protect tracing correctness, and read barriers for moving collectors may also handle forwarding. Choosing between read or write barriers first depends on algorithmic requirements; read/write frequency affects cost but does not solely determine the correct solution.

Go's official GC guide describes its concurrent, non-moving tracing collector; the runtime write barrier source code explains the purpose of mixed barriers. It cannot serve as a generic generational example of "young generation copying, old generation sweeping." Go GC Guide, Go Write Barrier Implementation Notes

Who discovers a white object newly referenced by black?

Fix one incremental-update model rather than generalizing every barrier to one rule. Adding A→B after scanning A needs new marking work if B is white. Link it before deleting G→B to remove the old gray path. With the insertion barrier, B itself is already gray, so the work survives removal of the old path.

What the Compiler Must Provide

Safepoints do not need to exist only at function calls or loop headers; implementations can also support restricted asynchronous pause mechanisms. The compiler must also prove compliance with specific algorithms when eliminating a barrier; "object just allocated" is not a universal reason to omit all barriers. LLVM treats these collaboration requirements as part of the GC integration interface. LLVM GC Documentation

Cost and Lifecycle Quick Reference

Increasing heap budget often reduces collection frequency but increases resident memory; reducing pause times may shift more work to mutator barriers and concurrent CPU usage; moving improves compactness but increases copying and reference updating costs. Evaluation should simultaneously observe allocation rate, live set, GC CPU, pause distribution, and peak memory.

GC does not replace timely release of files, locks, or connections. The timing of finalizer execution is generally unsuitable for mandatory business cleanup that must be completed on time; explicit lifecycle mechanisms provided by the language should be used instead.

Separating "Frequency" and "One-Time Workload" Using a Constrained Budget Model

Assume the live set after each collection is fixed at 100 MiB, the next collection is triggered when heap usage reaches 200 MiB, and the application continuously allocates at 50 MiB/s. The allocatable remainder is 100 MiB, and the idealized collection interval is 2 seconds. If the threshold is changed to 300 MiB, the remainder is 200 MiB, and the interval becomes 4 seconds; this does not directly prove that a single pause is shortened.

from fractions import Fraction
live, allocation_rate = 100, 50  # MiB, MiB/s
intervals = [Fraction(limit - live, allocation_rate) for limit in (200, 300)]
assert intervals == [2, 4]
# Assume each collection round consumes a fixed 0.1 CPU seconds tracing the same live graph
cpu_per_second = [Fraction(1, 10) / interval for interval in intervals]
assert cpu_per_second == [Fraction(1, 20), Fraction(1, 40)]

The above amortized workload drops from 0.05 CPU seconds per second to 0.025 CPU seconds per second, which is the conclusion of the "fixed cost per round, only changing frequency" model. Real runtimes start concurrent marking early, roots and live sets change, and allocation assistance, promotion, or memory pressure may occur, so these two numbers cannot be directly used as product performance predictions.

If pauses are still long, further identify whether root scanning, copying live objects, or the cleanup phase dominates; if total CPU is high but pauses are short, it may be frequent collection or a large amount of concurrent work. Only by placing per-round duration, rounds per second, and application throughput together can one determine which cost is solved by increasing the heap budget. Go GC Cost Model

References

• Go GC Guide.
• Go mbarrier.go.
• LLVM: Garbage Collection.

Keywords: GC, tracing, reference counting, root map, mark-sweep, copying, generational, remembered set, barrier, safepoint