Garbage Collection Algorithms

In modern managed runtime environments, garbage collection (GC) is the silent engine that automates memory management. By identifying and reclaiming memory occupied by objects that are no longer in use, GC liberates developers from the complexities and risks of manual memory allocation and deallocation—tasks that, if handled incorrectly, lead to memory leaks and dangling pointers.

To implement an effective garbage collector, the system must first solve a fundamental question: "Which objects are garbage?" There are two primary methodologies used to answer this.

• Reference Counting: Each object maintains a counter representing the number of references pointing to it. When a new reference is created, the count increments; when a reference is destroyed or reassigned, the count decrements. Once the count hits zero, the object is immediately eligible for reclamation. While simple and responsive, this method struggles with circular references (where two objects reference each other, preventing their counts from ever reaching zero) and incurs significant overhead due to constant counter updates.
• Reachability Analysis: This is the standard approach used by modern runtimes like Java and C#. Instead of counting references, the system starts from a set of "root" objects known as GC Roots (such as local variables in stack frames, static variables, and JNI references). The collector traverses the entire object graph via these roots. Any object that cannot be reached through this chain of references is deemed unreachable and, therefore, garbage. This method effectively solves the circular reference problem.
  Once the system can identify garbage, it must decide how to reclaim that memory. Several classic algorithms serve as the foundation for modern collectors.

Mark-Sweep Algorithm

The Mark-Sweep algorithm is the most straightforward approach, operating in two distinct phases:

1. Mark Phase: The collector traverses the object graph starting from the GC Roots and marks all reachable (live) objects.
2. Sweep Phase: The collector performs a linear scan of the heap, reclaiming the memory occupied by any object that was not marked during the first phase.

While simple to implement and efficient because it does not move objects, Mark-Sweep suffers from memory fragmentation. As objects are cleared from various locations in the heap, they leave behind small, non-contiguous gaps. Over time, these "holes" may become so small that the system cannot allocate a large new object, even if the total free memory is sufficient, triggering premature and frequent GC cycles.

Copying Algorithm

To solve the fragmentation issue, the Copying algorithm divides the available memory into two equal-sized regions. Only one region is used for active allocation at any given time. When the active region becomes full, the collector identifies all live objects and copies them into the second, empty region. The first region is then wiped entirely.

• Pros: It completely eliminates fragmentation. Since live objects are packed together in the new region, allocation is extremely efficient—it only requires moving a pointer (often called "bump-the-pointer" allocation).
• Cons: It is inherently inefficient in terms of space, as 50% of the memory remains idle at all times. Furthermore, if most objects are still alive, the cost of copying them becomes prohibitively high.

Because of these characteristics, the Copying algorithm is ideal for scenarios where most objects are short-lived. This is why modern JVMs use it for the Young Generation, dividing the space into an Eden area and two Survivor spaces (typically in an 8:1:1 ratio) to minimize wasted space while maintaining high efficiency.

Mark-Compact Algorithm

The Mark-Compact algorithm is designed for the "Old Generation," where objects tend to be long-lived and the cost of copying them (as in the Copying algorithm) would be too high. It works similarly to Mark-Sweep but adds a third phase:

1. Mark Phase: Identify all live objects.
2. Compact Phase: Instead of just clearing the dead objects, the collector slides the live objects to one end of the memory space, closing the gaps.
3. Sweep Phase: The remaining space at the end of the heap is treated as a single, contiguous block of free memory.

This approach provides both high space utilization and zero fragmentation. However, the compaction process is computationally expensive because the collector must update every single reference pointing to the moved objects, often resulting in longer Stop-The-World (STW) pauses.

The Generational Collection Strategy

Most modern garbage collectors do not rely on a single algorithm. Instead, they employ Generational Collection, a strategy based on the "Weak Generational Hypothesis": the observation that most objects die young.

By dividing the heap into different generations, the system can apply the most efficient algorithm to each:

• Young Generation: Designed for short-lived objects. It uses the Copying algorithm to perform frequent but very fast "Minor GCs."
• Old Generation: Designed for long-lived objects that have survived multiple collection cycles. It uses Mark-Sweep or Mark-Compact to perform "Major" or "Full GCs," which are less frequent but more resource-intensive.

As objects survive successive Minor GC cycles, their "age" increases. Once an object reaches a specific threshold (for example, 15 in the HotSpot JVM), it is promoted to the Old Generation.

public void process() {
    // This object is local to the method; it will likely die in the Young Gen
    byte[] temp = new byte[1024 * 1024]; 
    
    // This object is assigned to a long-lived field; it will eventually be promoted to the Old Gen
    this.cache = new byte[64 * 1024 * 1024];  
}

Advanced Techniques: Concurrent Collection

To minimize the latency caused by "Stop-The-World" pauses, modern collectors like CMS (Concurrent Mark Sweep), G1 (Garbage First), and ZGC attempt to perform much of the collection work concurrently with the application threads.

To manage this, they often use the Tri-color Marking model:

• White: Objects that have not been visited yet (candidates for collection).
• Gray: Objects that have been visited, but their internal references have not yet been fully scanned.
• Black: Objects that have been fully scanned and are confirmed to be live.

A major challenge in concurrent collection is that the application (the "mutator") might change object references while the collector is marking them. This could lead to a "lost object" scenario where a live object is accidentally marked as white and reclaimed. To prevent this, collectors use Write Barriers—small pieces of logic injected into the code during reference assignments. These barriers use techniques like Incremental Update or SATB (Snapshot-At-The-Beginning) to ensure that any changes to the object graph are captured and accounted for during the marking phase.

Summary Comparison

Understanding these fundamental algorithms is essential for anyone looking to master JVM tuning, diagnose memory leaks, or optimize application performance in high-throughput, low-latency environments. The choice of a garbage collector should always be driven by the specific lifecycle of the application's objects and its tolerance for pause times.