Garbage Collection Strategies

A root set is the set of memory locations a running program can directly access without following a heap pointer: local variables on the stack, CPU registers, and global/static variables. An object is reachable if it is in the root set, or if it is pointed to by a field of another reachable object — i.e., reachability is the transitive closure of the "points-to" relation starting from the roots. The fundamental theorem of garbage collection is simple to state and easy to justify: any object not reachable from the roots can never again be read or written by the program, because the program has no way to construct a pointer to it out of thin air (in a type-safe, non-pointer-arithmetic language). Therefore reclaiming unreachable objects is always memory-safe. The four classical strategies differ in how they track or discover reachability:

• Reference counting maintains, for each object, a count of how many pointers currently reference it. When the count hits zero, the object is immediately unreachable from any live pointer and can be freed. This is a local, incremental approximation to reachability.
• Mark-sweep performs an explicit graph traversal (depth-first or breadth-first) from the roots, marking every object it visits, then sweeps the entire heap freeing anything unmarked. This computes reachability exactly, globally, but requires a full pass over the heap.
• Copying collection also traces from the roots, but instead of marking in place, it evacuates every live object into a second region, compacting them contiguously; the old region is then reclaimed as one contiguous free block.
• Generational collection is an optimization layered on top of mark-sweep or copying: it partitions the heap by object age, collects the young generation (where most garbage lives) far more often than the old generation, using the empirical weak generational hypothesis — most objects die shortly after allocation.

A collector must also solve the root enumeration problem (finding all roots precisely, which requires either conservative scanning or compiler-generated stack maps) and the write barrier problem (detecting when a pointer store creates a new reference that crosses a generational or concurrent boundary, so the collector's bookkeeping stays correct).

Reference counting

Every object carries a count of incoming references. The count is incremented when a new pointer to the object is created and decremented when a pointer is destroyed (variable goes out of scope, field is overwritten, container is cleared). When the count reaches zero, the object is freed immediately, and — critically — freeing it must recursively decrement the counts of everything it points to, since those pointers just disappeared too. ``` function IncRef(obj): if obj != null: obj.refcount += 1 function DecRef(obj): if obj == null: return obj.refcount -= 1 if obj.refcount == 0: for each field f in obj.fields: DecRef(f) // recursively drop children Free(obj) // return memory to allocator function AssignPointer(slot, newObj): IncRef(newObj) // do this FIRST oldObj = slot slot = newObj DecRef(oldObj) // then drop the old value ``` The order in `AssignPointer` matters: incrementing the new target before decrementing the old one correctly handles the edge case `slot := slot` (self-assignment), where decrementing first could free the very object being assigned.

Why cycles break it. Two objects `A` and `B` that point only to each other, with no external reference, each have `refcount = 1` forever — they are unreachable from the roots but their counts never hit zero. Pure reference counting leaks all cyclic garbage. Production systems (CPython, Swift ARC) bolt on a periodic cycle collector, essentially a mini mark-sweep restricted to candidate objects whose refcount was decremented but not to zero.

Mark-sweep

Mark-sweep works in two explicit phases and requires stopping the program (a "stop-the-world" pause) so the object graph does not mutate mid-traversal. ``` function MarkSweepGC(): // Phase 1: Mark — traverse from roots, marking every reachable object for each root r in Roots(): Mark(r) // Phase 2: Sweep — scan the whole heap, freeing unmarked objects for each obj in HeapObjects(): if obj.marked: obj.marked = false // reset for next cycle else: Free(obj) function Mark(obj): if obj == null or obj.marked: return // base case: null or already visited obj.marked = true for each field f in obj.fields: Mark(f) // recurse into children ``` The `if obj.marked: return` check is what turns an unbounded graph traversal into one bounded by the number of objects: it prevents infinite recursion on cycles and prevents revisiting shared subgraphs. In practice the recursive `Mark` is replaced by an explicit worklist/stack to avoid overflowing the call stack on deep object graphs.

Why sweeping is needed even though marking found the garbage: marking only identifies live objects; the sweep phase is what actually walks the whole heap's allocation records to return dead ones to the free list. This full-heap scan is mark-sweep's main cost, and it leaves the freed space scattered in place (fragmentation), which can make a large contiguous allocation fail even when total free memory is sufficient.

Copying collection

A copying collector (the classic instance is Cheney's algorithm) splits the heap into two equal halves, from-space and to-space. Only from-space is used for allocation between collections. A collection copies every reachable object into to-space, then swaps the roles of the two halves. ``` function CheneyCopy(): scan = free = ToSpaceStart() for each root r in Roots(): r = Forward(r) // copy roots, fix up pointers while scan < free: obj = ObjectAt(scan) for each field f in obj.fields: f = Forward(f) scan = scan + Size(obj) swap(FromSpace, ToSpace) // to-space becomes from-space return free // new allocation pointer function Forward(ptr): if ptr == null: return null if IsForwarded(ptr): return ForwardingAddress(ptr) // already copied — reuse newAddr = free Copy(ptr, newAddr, Size(ptr)) SetForwardingAddress(ptr, newAddr) // leave a "moved-to" pointer free = free + Size(ptr) return newAddr ``` The elegance here is the forwarding pointer: when an object is copied, its old from-space slot is overwritten with the address of its new location. Any later pointer that targets the same old object detects this and simply redirects, so shared objects are copied exactly once and cycles terminate naturally (the second time you reach an already-forwarded object, you stop). The `scan`/`free` two-pointer technique is a breadth-first traversal implemented without extra stack or queue memory — the to-space itself, between `scan` and `free`, acts as the worklist.

Why this gives free compaction: live objects are packed contiguously into to-space in the order visited, with no gaps, so fragmentation is eliminated as a side effect, and allocation afterward is just bumping a pointer.

Generational collection

The weak generational hypothesis observes that in most programs, the large majority of objects die within a few kilobytes of allocation (temporary strings, loop-local structures), while a small minority survive indefinitely (top-level data structures, caches). A generational collector partitions the heap into a small young generation and a larger old generation, and collects the young generation far more frequently. ``` function AllocateGenerational(size): obj = BumpAllocate(YoungGen, size) if obj == null: MinorGC() obj = BumpAllocate(YoungGen, size) if obj == null: MajorGC() // fallback if minor GC insufficient obj = BumpAllocate(YoungGen, size) return obj function MinorGC(): roots = StackAndGlobalRoots() + RememberedSet() // old->young pointers too! CopyReachable(from=YoungGen, to=Survivor, roots=roots) PromoteSurvivorsAboveThreshold(to=OldGen) ResetYoungGen() function WriteBarrier(obj, field, value): field = value if IsOld(obj) and IsYoung(value): RememberedSet.add(obj) // record cross-generational pointer ``` The subtlety that makes this correct is the <strong>remembered set</strong> and its accompanying <strong>write barrier</strong>: a young object can be reachable only* through a pointer stored in an old object (e.g., a long-lived cache holding a reference to a freshly-allocated value). If a minor collection only scanned the stack/global roots, it would incorrectly free that young object. The write barrier intercepts every pointer store that creates an old-to-young reference and records it, so the remembered set can be added to the root set during a minor collection — letting the collector scan a small fraction of the old generation instead of all of it.

Reference counting. Time per pointer write is $O(1 + k)$ amortized, where $k$ is the size of the object subtree freed if the count drops to zero (in the worst case a long chain of decrements cascades, e.g. freeing a linked list of length $n$ costs $O(n)$ in that single operation, though the total work across the list's lifetime is still $O(n)$ once). There is no separate global "GC pause" — cost is spread across every mutation, which is good for latency-sensitive code but bad for throughput (every single pointer store pays overhead, cache-unfriendly since it touches the target object's header). Correctness: the invariant maintained is `refcount(obj) = |{pointers currently referencing obj}|`, kept exact by pairing every pointer store with an increment/decrement. Since a zero count means no live pointer exists anywhere in the currently-reachable graph, freeing is always safe — except for cycles, which are a fundamental blind spot: no local counter can detect that a whole strongly-connected component is globally unreachable. This is not a bug to be patched but a mathematical limitation of purely local reference counts.

Mark-sweep. Mark phase: $O(L)$ where $L$ is the number of live objects and edges (each object and pointer visited once, guarded by the `marked` check). Sweep phase: $O(H)$ where $H$ is total heap size (every object, live or dead, is visited once). Total: $O(L + H)$ time, $O(1)$ extra space beyond a mark bit per object (or a worklist bounded by heap size if implemented iteratively). Correctness: `Mark` computes exactly the set reachable from roots via a standard graph reachability traversal; termination follows because each object is marked at most once (the `if obj.marked: return` check), so the recursion visits each of the $H$ objects at most once — a strict decrease in "unmarked objects remaining" bounds the recursion depth by $H$. Anything left unmarked after this exact fixpoint computation is, by the fundamental theorem, genuinely garbage.

Copying collection. Time: $O(L)$ — only live objects are ever touched (dead objects are implicitly discarded by never being copied), which is strictly better than mark-sweep's $O(L+H)$ when the heap has substantial garbage. Space: requires 2× the maximum live-object footprint, since to-space must be able to hold everything from-space could contain — this is the fundamental tradeoff, trading memory for speed and automatic compaction. Correctness: the forwarding-pointer scheme guarantees each live object is copied exactly once (subsequent visits see `IsForwarded` and redirect), and the scan/free two-finger invariant — everything before `scan` has had its fields forwarded, everything between `scan` and `free` is copied but not yet scanned, everything after `free` is untouched to-space — is a standard breadth-first-traversal invariant that terminates because `free` only grows and is bounded by total live size $L$.

Generational collection. A minor GC costs $O(\text{live objects in young gen})$, typically tiny and sub-millisecond, because the young generation is small by design and most objects there are already dead (so a copying collector is typically used for it — dead objects cost nothing). Major (full-heap) GCs are rarer and pay the full $O(L_{old} + H_{old})$ or $O(L_{old})$ cost depending on the underlying algorithm chosen for the old generation. Correctness hinges on the write barrier being triggered on every store that could create an old→young pointer; if even one such store is missed, the remembered set becomes incomplete, and a minor GC can incorrectly free a young object still reachable through the old generation — this is why write barriers are inserted by the compiler/runtime on every heap pointer write, not just "most" of them, and why unsafe/manual memory tricks in managed languages (e.g., raw pointer casts) are dangerous exactly at this boundary.

Overall honesty about tradeoffs: no strategy dominates. Reference counting gives immediate, incremental reclamation and good locality of destruction (useful for closing files/sockets promptly) but leaks cycles and taxes every mutation. Mark-sweep handles cycles and needs no extra heap space but fragments memory and pauses proportional to heap size. Copying eliminates fragmentation and is proportional only to live data, but doubles memory footprint. Generational collection reduces average pause time dramatically but adds write-barrier overhead to every old-to-young store and still needs an occasional expensive major collection.

Consider a small object graph built by this pseudocode: ``` Root -> A -> B -> C A -> D B -> A // creates a cycle A <-> B E (unreachable, was assigned null last statement) ``` Suppose initial refcounts (assuming a reference-counting collector) are: `A=1` (from Root), `B=2` (from A and... wait, from A only, plus itself in the cycle back-edge counts toward A not B) — let's trace precisely.

At step 7, `E` is correctly and immediately reclaimed by reference counting — this is RC's strength. But at step 7, even though `A`, `B`, `C`, `D` are now entirely unreachable from Root, their counts never reach zero: `A` is held alive by `B.back`, and `B` is held alive by `A.next`. Pure reference counting leaks all four objects permanently. Now run mark-sweep starting fresh from the same final state (Root is null, but suppose we still have a separate live root `Keep -> C` directly, to make the example non-trivial and show partial reclamation): ``` Roots = { Keep } Keep -> C A -> B -> C B -> A (cycle, but A/B unreachable from Keep) A -> D ```

Mark-sweep correctly reclaims the `A ↔ B` cycle and the now-unreachable `D`, because it computes reachability globally from the true roots rather than relying on local counts — this is precisely the cycle problem reference counting cannot solve, resolved by exact graph traversal. Finally, tracing copying collection on the same `Keep -> C` state: the collector visits only `Keep` and `C` (2 objects), copies both into to-space, and never even touches `A`, `B`, `D` — they simply vanish along with all of from-space when the halves swap. This shows copying's key efficiency property: work is proportional to the 2 live objects, not the 4 total heap objects, whereas mark-sweep did $O(4)$ work in its sweep phase touching every object including the dead ones.

Reference counting itself traces back to early Lisp implementations and was formalized alongside George Collins's 1960 work on compacting collectors; the "cycle problem" was recognized almost immediately as RC's Achilles' heel, motivating decades of hybrid cycle-detection schemes still used in Python and Swift today. Copying collection, Cheney's 1970 non-recursive reformulation of earlier semi-space ideas, made compaction practical without a call stack proportional to heap depth — a genuinely clever reuse of the to-space itself as the traversal worklist. Generational collection, crystallized by David Ungar's 1984 work on Smalltalk, turned an empirical observation about object lifetimes into one of the most impactful performance optimizations in managed runtime history, cutting typical GC pause times by an order of magnitude and enabling today's low-latency JVM and CLR collectors (G1, ZGC, Shenandoah).

Every major managed-language runtime embeds a descendant of these algorithms. The JVM's G1 and ZGC collectors are generational, mostly-copying collectors tuned for sub-millisecond pauses on multi-gigabyte heaps used by enterprise servers and Android's ART runtime. The .NET CLR uses a generational mark-compact collector with three generations plus a large-object heap handled separately to avoid copying huge arrays. Python's CPython interpreter uses reference counting as its primary mechanism (giving deterministic, immediate destructor calls that Python programmers rely on for closing files) layered with a periodic generational cycle-detector to catch reference cycles. Go's runtime uses a concurrent, non-generational mark-sweep collector specifically designed to minimize stop-the-world pauses for low-latency network services. JavaScript engines (V8, SpiderMonkey) use generational copying collectors for the young generation ("scavenger") combined with incremental/concurrent mark-sweep-compact for the old generation, directly enabling the responsiveness of modern web applications. Even outside managed languages, Objective-C/Swift's ARC (Automatic Reference Counting) is a compiler-inserted, static version of the reference-counting algorithm described here, used throughout iOS and macOS application development. Understanding these strategies is a direct prerequisite to understanding how Virtual Machines and Bytecode execute managed programs, since the GC is typically as deeply integrated into a VM's runtime loop as the bytecode interpreter itself, and both depend on the allocator concepts from Heap Management and Dynamic Allocation and the broader question of Memory Safety that automatic collection is designed to guarantee.

Ask the tutor: How would you design a write barrier and remembered set for a concurrent generational collector where mutator threads run simultaneously with the collector?