Garbage Collection

Why have garbage collection?

Manual memory management is correct only when you free every allocation exactly once at the right time. Mistakes:

• Memory leak. Forget to free → memory accumulates → process eventually crashes.
• Use-after-free. Free, then access → undefined behavior, crash, or exploitable security vulnerability.
• Double-free. Free the same allocation twice → heap corruption.
• Dangling pointer. Pointer to freed memory accessed elsewhere → reads garbage or crashes.

These bugs are subtle, common, and the source of countless CVEs in C and C++ codebases. GC eliminates them entirely — the runtime knows exactly when something becomes unreachable and reclaims it. The cost is some runtime overhead and (historically) pause times.

Reachability — the foundation

An object is "reachable" if you can get to it via references starting from the root set:

• Local variables on each thread's stack.
• Global variables.
• CPU registers and active call frames.
• Some platform-specific roots (JIT code references, weak global tables).

Anything reachable from the roots must be kept alive. Anything not reachable can never be accessed by the program again — safely freeable.

The trick — tracing reachability efficiently and concurrently with the running application.

Basic GC algorithms

Algorithm	How it works	Pros	Cons
Reference counting	Each object tracks ref count; freed when count = 0	Immediate cleanup, predictable	Misses cycles; per-assignment overhead
Mark-and-sweep	Mark live objects from roots; sweep frees unmarked	Handles cycles; conceptually simple	Stop-the-world pauses; fragmentation
Mark-and-compact	Mark, then move live objects together to defragment	No fragmentation; fast bump allocation	Compacting is expensive; needs barriers
Copying (semi-space)	Two heap halves; copy live objects to other half	Cheap allocation; auto-defragmenting	Wastes 50% of heap; bad for long-lived data
Generational	Young gen collected often; old gen rarely	Exploits "most die young"; mostly cheap	Cross-generation references need write barriers
Concurrent / incremental	GC and app run interleaved	Low pause times	Higher CPU overhead, complex

Most modern GCs combine techniques — generational + concurrent + compacting. Java's G1, ZGC, and Shenandoah are all such hybrids; Go's GC is concurrent non-generational tri-color mark-and-sweep.

The generational hypothesis

Empirical fact across thousands of programs — most objects die young. Specifically:

• ~95% of new allocations are unreachable within milliseconds.
• The remaining 5% include long-lived data (caches, configuration, server-state).
• Old objects rarely become garbage; they "live forever" relative to the GC cycle.

Generational GC organizes the heap into:

• Young generation (eden). New allocations go here. Collected frequently — every few hundred ms. Most of the heap visited is dead, so collection is cheap (live objects are quickly copied out, the rest is bulk-cleared).
• Survivor space(s). Objects that survived 1-2 young collections. Promoted to old gen if they survive more.
• Old (tenured) generation. Long-lived objects. Collected rarely (every minute or so), but each collection is expensive (large heap to scan).

The young gen makes the common case fast; old gen is the rare case that takes longer. Net result — total GC time is much lower than non-generational across realistic workloads.

Java GC family — choose your tradeoff

GC	Type	Pause goal	Best for
Serial	Single-threaded stop-the-world	Doesn't matter — small heaps only	Tiny apps, low-throughput
Parallel (Throughput)	Multi-threaded stop-the-world	Maximum throughput, longer pauses OK	Batch jobs, no SLA on latency
G1	Region-based, mostly concurrent, generational	~100ms typical	General-purpose, default since Java 9
ZGC	Region-based, fully concurrent, scalable to TBs	Sub-10ms regardless of heap size	Latency-critical large-heap apps
Shenandoah	Concurrent compacting	Sub-10ms	Same niche as ZGC; OpenJDK alternative
Epsilon	No-op (allocates, never collects)	N/A	Performance testing, short-lived processes

For new Java apps in 2025, the choice is usually G1 (default, well-tuned) or ZGC (when latency matters more than CPU efficiency).

Reference counting in CPython, Swift, Objective-C

Each object has a refcount — incremented on new references, decremented when references go away. When the count drops to 0, the object is freed immediately.

# CPython conceptually does this on every assignment:
a = [1, 2, 3]    # list refcount = 1
b = a            # list refcount = 2 (b also references it)
a = None         # list refcount = 1
b = None         # list refcount = 0 → list freed

Pros — immediate, deterministic cleanup. No pauses. Memory released as soon as it's not needed.

Cons — cycles. a = [b]; b = [a] — refcounts never reach 0 even after both a and b go out of scope. Solutions:

• Cycle collector (CPython has one — runs periodically to find unreachable cycles).
• Weak references — programmer marks one direction of the cycle as "weak" so it doesn't increment refcount. Used in Swift's ARC.
• No support — early Objective-C and naive reference counting just leak.

Reference counting also has runtime cost — every reference assignment touches the refcount. In hot allocation paths, this overhead can exceed mark-and-sweep's amortized cost. Tracing GC wins on throughput; refcounting wins on latency predictability.

When GC behavior matters

• Latency-sensitive services. Trading systems, real-time audio, game engines, video processing — even a 10ms pause is unacceptable. Tune GC carefully or use a low-pause GC (ZGC, Shenandoah) or move to manually-managed languages (Rust, C++).
• High-allocation-rate workloads. Generational GC excels when most allocations die young. If your workload allocates many long-lived objects, tune the survivor sizes and old-gen capacity to match.
• Memory-constrained environments. Embedded systems, mobile, FaaS containers. Less heap means more frequent collections; pick a GC that doesn't waste memory on overhead (e.g., copy GC requires 2× heap).
• Long-running services with steady-state allocation. Tune for old-gen capacity and concurrent collection threshold to avoid full stop-the-world collections.

Alternatives — manual, ownership, escape analysis

• Manual (C, C++). Programmer is responsible for malloc/free. Maximum performance and predictability; maximum bug surface.
• RAII (C++). Resources tied to object lifetimes; destructors run automatically. Smart pointers (unique_ptr, shared_ptr) extend this for heap allocation. shared_ptr is reference counting; unique_ptr is single-owner.
• Ownership (Rust). Compile-time enforcement of borrow rules — every value has exactly one owner; references must follow strict aliasing rules. No GC needed; no leaks possible (assuming Drop is correctly implemented). Rivals manual C with safety guarantees.
• Escape analysis (some JVMs, Go). Compile-time detection that an allocation never escapes a function — replace with stack allocation. Eliminates GC pressure for the most common case (short-lived locals).

Common GC issues

• Memory leaks via accidental references. Caches, listener lists, observer patterns — anything that holds strong references to objects beyond their useful lifetime. The GC can't reclaim them; they're "reachable but useless." Use weak references for caches and explicit cleanup.
• Long pauses surprising production. Your dev test had a 100MB heap; production has 10GB. The full GC pause grows with heap size. Always test with production-realistic heap sizes and allocation rates.
• Allocation-rate spikes triggering GC storms. A burst of allocations forces frequent young collections; if survivors-to-old-gen overflow, you get long old-gen pauses. Profile and tune.
• Finalizers / destructors with side effects. Don't rely on them to run promptly (or at all). Java finalize() and Python __del__() run when the GC sees fit. For deterministic cleanup, use try/finally, with-statements, or Closeable patterns.
• Reference counting + cycles. CPython has a cycle collector; Swift requires you to use weak references. Forgetting to break cycles in Swift is the canonical iOS memory leak.
• Excessive boxing in JIT-compiled languages. Java and C# autobox primitive values into wrapper objects in some contexts — each box is a heap allocation. Avoid in hot loops; prefer primitive arrays over Integer[].