Garbage Collection

Programs store data in dynamic memory (the heap). Managing this memory involves allocating blocks when data is created and releasing them when the data is no longer needed.

In languages with manual memory management (such as C and C++), engineers must explicitly request heap space using calls like malloc() and free it using free(). This approach offers high performance, but it is highly error-prone:

• Memory Leaks: Occur when data is no longer used but free() is never called, causing the application to gradually exhaust system memory.
• Dangling Pointers: Occur when memory is freed while a pointer still references its address. Dereferencing this pointer triggers undefined behavior or segmentation faults.
• Double Free: Occurs when code attempts to deallocate the same pointer address twice, corrupting the memory allocator's internal metadata.

Garbage collection (GC) is the automatic management of dynamic memory. The runtime environment includes a background system that automatically detects and reclaims heap blocks that are no longer accessible by the application, resolving these safety risks.

---

The most direct approach to automatic memory management is Reference Counting. Every object on the heap is allocated with an implicit metadata counter tracking how many references point directly to it.

The mechanics follow simple updates:

• When a reference to an object is copied, its counter is incremented.
• When a reference falls out of scope or is reassigned, its counter is decremented.
• If the counter drops to 0, the object is immediately deallocated, and the counters of any other objects it referenced are decremented in turn.

This model is similar to tracking mugs in a shared office. If you write a tally mark on a board whenever someone takes a mug to their desk, you know exactly when the last person brings a mug back. Once the active user count is 0, the mug can be washed and returned to the cupboard immediately.

Pros and Cons

• Pros: Reclaims memory instantly when it is no longer needed. This prevents large memory build-ups and avoids the long, unpredictable pauses associated with other garbage collection models.
• Cons: Modifying counters on every reference update adds significant execution overhead, particularly in multi-threaded environments where counters must be updated using slow, atomic hardware operations.
• The Cyclic Reference Problem: Reference counting cannot resolve cyclic dependencies. If Object A points to Object B, and Object B points to Object A, their reference counts will never drop to 0, even if both become completely disconnected from the rest of the application. This causes a memory leak that must be solved using weak references or auxiliary tracing sweeps.

---

Instead of tracking every reference update in real time, tracing garbage collection operates periodically. The garbage collector runs at designated intervals, tracing object reference paths starting from application entry points (roots).

This approach can be compared to a professional cleaning service. Instead of running to the dumpster with every single piece of trash the moment it is created, you place discardable items in bins. The cleaning service arrives once a week, walks through the rooms you actually use (roots), labels items in those rooms as "keep" (marking), and then empties the wastebaskets containing everything else (sweeping).

Tracing GC uses three primary phases:

1. Mark Phase: The collector starts at root references (such as CPU registers, active stack frames, and global variables) and traverses the object graph. Every reachable object is flagged as "live".
2. Sweep Phase: The collector scans the entire heap space. The memory blocks of any objects not flagged as "live" are unlinked and returned to the allocator's free list.
3. Compact Phase: The collector relocates surviving live objects to a contiguous section of the heap. This resolves memory fragmentation, allowing the allocator to use simple bump-allocation for future requests.

---

Tracing the entire heap on every garbage collection cycle is inefficient, especially as the application's memory footprints grow. To optimize this, modern garbage collectors rely on the generational hypothesis: most objects die young.

In real-world applications, the majority of allocated objects are short-lived (such as temporary variables used inside a loop or request-scoped variables in a web handler). Objects that survive several collection cycles tend to remain active for a long time.

To leverage this, the heap is divided into distinct generations:

• Ephemeral Space (Young Generation): Contains newly allocated objects. This space is subdivided into the Eden space and two Survivor spaces. Most collection runs (minor GCs) only scan this young space. Surviving objects are copied between the survivor spaces before being promoted.
• Tenured Space (Old Generation): Stores objects that have survived multiple minor GC cycles. This space is scanned less frequently during major GCs (or full GCs), reducing execution pauses.

---

To perform garbage collection concurrently alongside active application threads, modern runtimes use the tri-color marking abstraction. Objects on the heap are categorized into three logical colors:

• White: Unvisited objects. These are candidates for deletion.
• Grey: Visited objects whose immediate child references have not yet been evaluated. These are queued for processing.
• Black: Visited objects whose child references have been fully evaluated. These are confirmed live and will not be swept.

The collection loop proceeds by popping a grey object from the queue, marking its white child references as grey, and marking the parent object as black. This loop runs until no grey objects remain in the queue.

The Concurrent Invalidation Problem and Write Barriers

If the collector runs concurrently with application threads, the application might modify references during the sweep. For example, if a thread updates a black object to point to a white object, and deletes the only reference to that white object from any remaining grey objects, the collector will never visit the white object. The white object remains white, and the collector will delete it, causing a critical memory corruption bug.

To prevent this, concurrent collectors enforce a write barrier. This hook intercepts runtime reference modifications. If the application attempts to point a black object to a white object, the write barrier intercepts the update and promotes the white object to grey, ensuring it is scanned and preserved.

---

As objects of varying sizes are allocated and deallocated over time, the heap memory space becomes fragmented. A fragmented heap has plenty of total free memory, but that memory is split into tiny, non-contiguous gaps. If the application attempts to allocate a new object that is larger than any of the individual gaps, the allocation fails, triggering an Out-Of-Memory (OOM) error.

Runtimes mitigate fragmentation using three strategies:

• Free Lists: The allocator maintains lists of free memory blocks categorized by size. When an allocation request is made, the allocator checks the free list to find a block that matches the requested size.
• Compaction Phase: The garbage collector physically copies surviving objects to a contiguous region of the heap, consolidating all free space into a single block. This requires updating all pointer references throughout the application.
• Bump Allocators: If compaction is used, new memory can be allocated using a single pointer (the "bump" pointer). To allocate space, the allocator checks if the gap between the pointer and the end of the heap is large enough, allocates the memory, and increments (bumps) the pointer, executing in O(1) time.

---

Modern languages use garbage collectors that are optimized for their specific runtime environments and trade-offs:

• Go: Go uses a concurrent, tri-color mark-and-sweep collector. It is optimized for low latency, aiming for Stop-The-World (STW) pauses of less than one millisecond. Go relies heavily on compiler escape analysis to allocate variables on the stack rather than the heap whenever possible, reducing overall GC pressure.
• Java (G1 / ZGC): The Java Virtual Machine (JVM) supports several garbage collectors. The Garbage-First (G1) collector divides the heap into regions and focuses sweeps on the regions containing the most dead objects. The newer ZGC is a scalable, low-latency collector designed to handle multi-terabyte heaps with STW pauses that do not exceed 10 milliseconds, using load barriers to track object relocations.
• V8 (JavaScript): Google's V8 engine uses a generational collector. The young generation is managed by a Scavenger algorithm that copies live objects between survivor spaces, while the old generation is managed by a mark-sweep-compact collector.

---

• The Garbage Collection Handbook: The Art of Dynamic Memory Management — The definitive guide to garbage collection history and algorithms.
• Go's Garbage Collector Guide — Detailed explanation of Go's concurrent collector design and tuning knobs.
• An Introduction to ZGC — Architectural overview of Java's low-latency, scalable garbage collector.
• V8 Garbage Collection Internals — A technical write-up detailing how the V8 engine manages memory.