Garbage collection (GC) is the automatic reclamation of memory that a program no longer needs. Modern GC algorithms are central to many managed languages (Java, C#, Go, JavaScript, Haskell, etc.), and they also appear in hybrid or optional forms (ARC/RC in Swift/Obj‑C, Boehm GC for C/C++). This article is a deep dive into garbage‑collection algorithms: history, fundamental concepts, core and advanced algorithms, implementation techniques, performance tradeoffs, use cases, and future directions.
Table of contents
- Introduction and scope
- Historical milestones
- Fundamental concepts and terminology
- Tracing vs reference counting: conceptual comparison
- Core algorithms
- Reference counting
- Mark-and-sweep
- Mark-and-compact
- Copying collectors (Cheney)
- Generational collection
- Incremental and concurrent collectors
- Parallel collectors
- Real-time (hard real-time) collectors
- Region-based and arena allocation
- Conservative garbage collection
- Hybrid strategies
- Implementation details and engineering
- Root set discovery and stack scanning
- Tri-color invariant and barriers (write/read)
- Card marking and remembered sets
- Large object handling and humongous objects
- Compaction, fragmentation, pinning
- Finalizers, weak/soft/phantom references
- Interaction with OS (virtual memory, page faults, NUMA)
- Practical examples and pseudo-code
- Simple reference counting
- Mark-and-sweep (pseudocode)
- Cheney’s copying (pseudocode)
- Basic write-barrier examples
- Real-world collectors and language implementations
- Java HotSpot (Serial, Parallel, CMS, G1, Shenandoah, ZGC)
- .NET CLR GC
- Go runtime GC
- CPython (reference counting + cycle collector)
- Boehm conservative GC
- V8 and JavaScript engines
- Functional language GCs (GHC)
- Swift/Obj‑C ARC
- Metrics and evaluation: throughput vs latency vs footprint
- Tuning strategies and heuristics
- Limitations, safety, and security considerations
- Future directions and research trends
- Practical guidance: choosing/designing a GC for different workloads
- Summary
Introduction and scope Garbage collection relieves programmers from managing memory explicitly (malloc/free, free()). A GC’s role is to detect unreachable objects and reclaim their storage while balancing tradeoffs: throughput (compute time dedicated to GC), latency (pause times/duration), memory footprint, fragmentation, and implementation complexity. This article covers classic algorithms, their modern variants (parallel, concurrent, generational), implementation techniques (barriers, remembered sets), and practical considerations for production systems.
Historical milestones
- 1960s – John McCarthy proposed an automatic memory management scheme for Lisp; mark-and-sweep-like ideas appeared early.
- 1969–1970 – Cheney’s algorithm for copying collection (nonrecursive compaction) introduced.
- 1970s – Reference counting and cycle issues were studied and practical improvements proposed.
- 1970s–1980s – Tri-color abstraction and on-the-fly/incremental GC (Dijkstra et al.) established formal invariants for concurrent collectors.
- 1990s–present – Generational collection and parallel/concurrent collectors became mainstream for multi-core servers and low-latency workloads.
- 2010s–present – Large-heap, low-latency collectors (G1, Shenandoah, ZGC) with concurrent compaction and region-based heaps.
Fundamental concepts and terminology
- Heap: region of memory used for dynamic allocation.
- Root set: references directly accessible from program state (global/static variables, CPU registers, stack frames, thread-local storage).
- Live (reachable) objects: reachable from root set via chains of references. Anything else is garbage.
- Tracing collector: identifies live objects by tracing from roots and marks reachable objects.
- Reference counting: each object maintains a count of inbound references; count reaching zero triggers deallocation.
- Mark-and-sweep: trace to mark live objects then sweep to reclaim unmarked objects.
- Copying collector: moves live objects to a new space (evacuation), leaving behind compacted memory.
- Compaction: moving objects to reduce fragmentation and improve locality.
- Fragmentation: free memory scattered into small blocks; internal vs external fragmentation.
- Pause time: time the mutator (application threads) is stopped for GC (stop-the-world).
- Throughput: fraction of total time devoted to application vs GC.
- Tri-color invariant: abstraction for incremental GC partitioning objects into white (unvisited), gray (discovered but children not processed), black (processed).
- Barriers: code emitted on field reads/writes to maintain invariants in concurrent/incremental collectors.
Tracing vs reference counting: conceptual comparison
- Tracing (mark-based): Pros: detects arbitrary cycles, can compact memory and reduce fragmentation, typically requires less per-object overhead. Cons: can require stop-the-world pauses or complicated concurrent algorithms and write-read barrier overhead.
- Reference counting (RC): Pros: reclamation is immediate and incremental, simple to implement, low latency for single-threaded contexts. Cons: per-object metadata overhead (reference count), cost of updating counts on every pointer write, inability to reclaim cyclic structures without extra mechanisms, concurrency complexity.
Core algorithms
Reference counting Description:
- Each object has a counter for number of references to it.
- On assignment of a pointer, increment the new target’s count and decrement the old target’s count; when any decremented count hits zero, object is reclaimed, and its outgoing references are decremented recursively (cascading deallocation).
Pseudocode (simplified): `` function assign(slot, obj): old = slot.value if obj != null: obj.count += 1 slot.value = obj if old != null: old.count -= 1 if old.count == 0: finalizeandfree(old) ``
Pros:
- Deterministic reclamation time; low-latency deallocations.
- Good for real-time or incremental reclamation.
Cons:
- Cannot collect cycles without cycle-detection algorithms (trial deletion, periodic cycle collector).
- Per-write overhead: O(1) updates for each pointer write (can be expensive).
- Concurrency requires atomic inc/dec or locks; contention on counts.
Practical uses:
- CPython uses RC for immediate deallocation, supplemented by a cycle detector for container cycles.
- Swift/Obj‑C use ARC (Automatic Reference Counting) which is compile-time assisted RC with runtime support.
Mark-and-sweep Description:
- Stop-the-world (classically) tracing collector. Two phases: mark (trace from roots marking reachable objects); sweep (scan heap and reclaim unmarked objects).
- Optionally followed by a compaction phase to eliminate fragmentation.
Pseudocode: ``` function collect(): markphase() sweepphase()
function mark_phase(): for root in roots: if not root.marked: mark(root)
function mark(obj): obj.marked = true for child in obj.fields: if not child.marked: mark(child)
function sweep_phase(): for each object in heap: if not object.marked: free(object) else: object.marked = false // reset for next GC ```
Pros:
- Handles cycles naturally.
- Low per-allocation overhead.
Cons:
- Stop-the-world pauses (unless made incremental/concurrent).
- Sweep can leave fragmentation unless compacted.
Mark-compact
- Variation: after marking, relocate live objects to compact heap, then update references. Eliminates fragmentation but moving objects requires updating all references to moved objects (via forwarding pointers or two-pass updates, or using card-marking remembered sets to limit updates).
Copying collectors (Cheney’s algorithm) Description:
- Divide heap into two semispaces: from-space and to-space. Allocate in from-space sequentially. When from-space fills, copy live objects to to-space by breadth-first forwarding, then swap spaces.
- Cheney’s algorithm is non-recursive and uses a scanning pointer: copied objects are scanned to copy their children.
Pseudocode (high-level): ``` scan = to-space.start free = to-space.start
copyroot(root): if root.forwarding is set: return root.forwarding new = free copyobject(new, root) root.forwarding = new free += object_size return new
while scan < free: for each field in objectat(scan): if field != null: field = copyroot(field) scan += object_size(scan) ```
Pros:
- Compaction is natural (to-space is compact).
- Allocation is pointer bump (very fast).
- No fragmentation.
Cons:
- Requires double memory (unless semi-space is resized; but generational copying avoids full doubling).
- Copying overhead for live objects.
- Not well-suited for large heaps without generational techniques.
Generational collection Core idea:
- Most objects die young (weak generational hypothesis). Partition heap into generations, typically nursery (young) and tenured (old). Do frequent minor collections on nursery (fast copying), occasional major collections on tenured space.
- Track intergenerational pointers from old to young using write barriers and remembered sets; roots include old->young pointers.
Pros:
- Good throughput and low pause times for many workloads: most collections are minor and fast.
- Fast allocation (bump-pointer in nursery).
Cons:
- Complexity (barriers, remembered sets, promotion policies).
- Workloads with long-lived short-lived objects or huge volumes of promoted objects can defeat benefits.
Incremental and concurrent collectors Motivation:
- Long stop-the-world pauses unacceptable; design collectors that run concurrently with mutator to reduce pause times.
Key techniques:
- Tri-color abstraction to maintain correctness during concurrent marking: objects are white (unprocessed), gray (discoverd but children not yet processed), black (fully processed).
- Barriers (write barriers and read barriers) to ensure that program modifications do not invalidate collector invariants.
- Snapshot-at-the-beginning (SATB) and incremental update approaches to implement consistent concurrent marking.
Types:
- Concurrent mark-sweep (CMS): concurrent marker, stop-the-world remarking, concurrent sweep. Requires avoidance of fragmentation via either mark-compact later or acceptance of fragmentation.
- Concurrent compacting (Shenandoah/ZGC): concurrent evacuation/compaction using region-based heaps and remembered sets; aims to keep pause times low and independent of heap size.
Pros:
- Low and predictable pause times.
- Good for interactive or low-latency servers.
Cons:
- Overheads from barriers (some percentage of mutator time).
- Complexity and corner cases (e.g., object pinning, integration with native code).
Parallel collectors
- Utilize multiple CPU cores to parallelize marking, copying, and sweeping. Most modern server-class GCs do this.
- E.g., Java's Parallel GC (throughput collector), parallel GCs in GHC, .NET parallel GC during stop-the-world phases.
Real-time collectors
- Guarantee upper bounds on pause times (hard real-time). Approaches include micro‑scheduling GC work interleaved with mutator and incremental compaction.
- Examples: Metronome (IBM research), real-time enhancements to Java (Real-Time Specification for Java) use scoped memory or specialized collectors.
- Typically incur higher overhead for strict guarantees.
Region-based and arena allocation
- Memory is allocated in arenas or regions: allocation is fast, deallocation occurs by freeing the whole region en masse.
- Useful for scoped lifetimes (function stack-like lifetimes), efficient where object lifetimes are similar.
- Regions may be combined with GC for objects escaping region lifetimes.
Conservative garbage collection
- For languages like C/C++, where pointer metadata is not available, conservative GC scans memory and treats any ...