Demystifying Garbage Collection Algorithms

Sylvain Tiset

18 min read

·

Sep 4, 2024

--

Listen

Share

A lot of programming languages are using a Garbage Collector (GC) to manage memory. In this article, we’ll see what is a GC, and the GC algorithms of some popular languages : Java, C#, Python and GoLang.

Press enter or click to view image in full size

What is a Garbage Collector?

Garbage collection is an automatic memory management feature used in some programming languages like Java, C#, Python, or GoLang to reclaim memory no longer used by the program.

A GC automates dynamic memory management through the following operations:

• Allocates memory from the operating system and returns it when no longer needed.
• Distributes memory to the application as requested.
• Identifies which portions of memory are still being used by the application.
• Reclaims unused memory, making it available for reuse by the application.

GC have performance metrics that are connected to each other:

• Memory Footprint represents the amount of memory required by the GC process to function effectively. A larger memory footprint for the GC algorithm reduces the available memory for the heap.
• Throughput refers to the amount of work completed within a specified time frame. The more throughput the GC algorithm is, the more memory footprint / time it uses.
• Latency is the time required to complete a request by the GC. A GC algorithm which is fast might not be throughput or can use a lot of memory.

How does Garbage Collection work in Java?

How does Garbage Collector knows an object can be deleted from the program?

Java uses a concept known as reachability to identify which objects in the heap memory are still in use and which are not. An object is said to be unreachable if it doesn’t contain any reference to it. Once an object is no longer reachable, it becomes eligible for garbage collection.

Here are the possible ways for an object to become unreachable:

• Nullifying the reference variable

Integer i = new Integer(7);
i = null; // the new Integer object is reachable via the reference in 'i'

• Re-assigning the reference variable

Test t1 = new Test("t1"); 
Test t2 = new Test("t2"); 
  
// t1 now referred to t2; t1 object can be reclaimed from memory
t1 = t2;

• An object created inside the method

void Test() 
{ 
    //object t1 inside method becomes unreachable when Test() removed 
    Test t1 = new Test("t1");  
}

• Island of Isolation: a group of objects that reference each other but are not referenced by any active object in the application

GFG t1 = new GFG();
GFG t2 = new GFG();

t1.i = t2;
t2.i = t1;

t1 = null;
t2 = null; // Now two objects are eligible for garbage collection

Press enter or click to view image in full size

How to trigger Java Garbage Collector?

There are two common ways of triggering the GC in Java:

• Automatic trigger when algorithm threasholds are reached.
• Explicit call of System.gc() method or Runtime.getRuntime().gc() method that suggest the JVM to initiate a GC cycle. However this is only a suggestion and the JVM may ignore it.

Java different GC algorithms

Java provides several garbage collectors, each one suited to match with a specific performance metric trade-offs:

• Parallel GC: Default GC algorithm in Java 8 and prior, focus on throughput using multiple threads.
• Serial GC: Focus on footprint, best usage for single-threaded environments or small applications.
• CMS (Concurrent Mark-Sweep) GC: Low-latency focus aiming to minimize pause times
• G1 (Garbage-First) GC: Default algorithm used from Java 9 onwards. It aims to balance throughput and latency.
• Z GC: Low-latency garbage collector designed for applications that require large heap sizes and minimal pause times.
• Shenandoah GC: Low-latency garbage collector similar to ZGC. It aims to minimize pause times by performing heap compaction concurrently with the application threads.
• Epsilon GC: No-op GC, meaning it does not perform any actual memory reclamation. It allocates memory but never frees it, allowing developers to measure the performance impact of GC in applications or to use it in environments where memory reclamation is handled externally.

Let’s review them into more details.

Understanding the Generational Heap structure

Let’s first look at how the heap is structured to understand how most GC works. Most GC use a generational heap structure, based on the following analysis that most objects are short-lived:

The generational heap structure divides the heap into several areas:

• Young Generation: Where new objects are allocated. It is further divided into eden space and survivor spaces:
• Eden Space: The area where new objects are created.
• Survivor Spaces (S0 and S1): Two smaller areas that hold objects that have survived at least one garbage collection.
• Old Generation (Tenured): Where objects that have survived multiple collections in the Young Generation are promoted.
• Permanent Generation: contains metadata required by the JVM to describe the classes and methods used in the application.

The PermGen was removed and replaced by Metaspace, which is managed separately from the heap, which avoid some OutOfMemory errors.

Press enter or click to view image in full size

Press enter or click to view image in full size

By convention:
Full GC clean the entire heap (both Young and Old spaces)
Major GC works on the Old space
Minor GC works on the Young space

Parallel GC

The parallel GC works the following:

1. New objects are allocated in the Eden space.
2. When the Eden fills up, a Minor GC is triggered, using multiple threads to reduce the time spent on garbage collection, which increases the application’s overall throughput.
3. Unreachable objects are removed from Eden, while live objects from Even and Survivor are moved to Survivor (from S0 to S1 or vice versa).
4. Objects that survive several minor GC are promoted to the Old Generation.
5. On a Major GC trigger, GC marks all live objects in the Old Generation, perform a compaction phase to reduce memory fragmentation, and then clean up the memory occupied by dead objetcts. The Major GC is done less frequently as Minor GC as it is more time consuming.

Here is the general GC process ilustrated:

The number of threads used by the Parallel GC can be tuned by using JVM flags like -XX:ParallelGCThreads=N, where N is the number of threads you want to allocate for garbage collection.

The Parallel GC is often prefered in applications where throughput is more critical than low pause times. It’s suitable for environments where predictable high performance is required, and occasional longer pause times are acceptable.

Serial GC

The key characteristic of the Serial GC is that it is single-threaded. Both Minor and Major GC are performed using a single thread, which means that the entire application is paused during garbage collection. This pause is often referred to as a stop-the-world (STW) pause because all application threads are halted until the garbage collection completes.

Apart from that, Serial GC algorithm is the same as Parallel GC (except for the number of threads used).

The Serial GC is most suitable for:

• Small applications or those with small heaps, where the simplicity of the Serial GC results in minimal garbage collection overhead.
• Single-threaded applications or environments where the application does not require high throughput or low latency.
• Environments with limited resources where the simplicity and low footprint of the Serial GC are beneficial.

Concurrent Mark-Sweep GC

CMS GC uses the same heap structure as the parallel and serial GC. To collect memory on minor GC on young generation, the same algorithm as parallel GC is applied. The difference comes in the major GC.

The CMS major GC consists of the following phases:

1. Initial Mark: A stop-the-world operation that scans the old generation to mark the objects reachable from the root.
2. Concurrent Mark: After the initial mark, the CMS collector continues to trace and mark live objects concurrently, while the application is running.
3. Concurrent Pre-clean: CMS attempts to clean up some of the objects that became unreachable during the concurrent mark phase. This phase runs concurrently with the application to reduce the amount of work that needs to be done during the next stop-the-world phase.
4. Remark: A stop-the-world operation that ensures that any objects that were missed during the concurrent mark phase (because they were modified during marking) are correctly marked.
5. Concurrent Sweep: During this phase, CMS sweeps through the Old Generation, reclaiming the memory occupied by dead objects. This phase runs concurrently with the application.

Press enter or click to view image in full size

One limitation of CMS is that it does not compact the heap, which can lead to memory fragmentation over time.

If the heap becomes too fragmented, or if CMS fails to keep up with the allocation rate, a Full GC may be triggered as a backup algorithm. This is a stop-the-world event where the entire heap is collected and compacted, which can lead to longer pauses.

Note that CMS GC has been deprecated starting from Java 9, and completely removed in Java 14.

To sum up, CMS GC is designed to minimize pause times by performing most of its garbage collection work concurrently with the application’s execution. It is especially suited for applications requiring low latency. However, CMS has some limitations, such as potential heap fragmentation and increased CPU usage which led to its deprecation in favor of newer garbage collectors like G1 and ZGC that will be presented just below.

Garbage-First GC

Unlike traditional generational garbage collectors that divide the heap into large contiguous spaces for Young and Old generations, G1 divides the heap into many smaller regions. These regions are of equal size and can be dynamically assigned as either part of the Young Generation, Old Generation, or a special Humongous Region (for large objects). Note that the regions are not required to be contiguous like other garbage collectors.

Here is an illustration of the heap memory when using G1:

A Humongous region exists when an object’s size is larger than 50% of the region’s size. The humongous regions can be stored as a set of contiguous regions.

New objects are still allocated in the Eden regions. When Eden regions fill up, a minor GC is triggered, moving live objects from Eden to Survivor regions or promoting them to Old regions if they have survived enough collection cycles. No cleanup is done at this stage. The minor GC is done in parallel using multiple threads.

When the initiating heap occupancy threshold is reached, the second phase of G1 algorithm takes place. During the concurrent marking phase, G1 begins to determine which objects in the Old Generation are still live. During this period, regular young collections (normal minor GC) may still occur. The concurrent marking process concludes with two key stop-the-world pauses:

• Remark: This pause finalizes the marking process, ensuring that all reachable objects are marked. It also handles tasks like global reference processing, class unloading, and reclaiming completely empty regions.
• Cleanup: During this pause, G1 identifies regions with the most garbage and decides which ones will be collected in the next mixed collection.

The final step is the mixed GC: G1 not only collects the Young Generation regions but also selectively evacuates live objects from Old Generation regions. The goal is to reclaim memory from Old Generation regions that have a high percentage of garbage. This phase continues with multiple Mixed collections until G1 determines that further evacuations would not provide enough benefit. After the space-reclamation phase ends, G1 restarts the cycle with another young-only phase.

If, during the marking process or any other part of the cycle, the application runs out of memory or G1 cannot reclaim enough space, it may trigger a Full GC. This is a stop-the-world event that performs a full heap compaction, similar to parallel GC algorithm, to recover as much memory as possible.

Here is an overview of the G1 collection cycle:

One of the key features of G1 is its ability to provide predictable pause times. A target maximum pause time can be specified using the JVM option -XX:MaxGCPauseMillis=200, and G1 will adjust its behavior to meet this goal as closely as possible.

G1 is well-suited for large, complex applications where both performance and low-latency garbage collection are critical.

Z GC

The Z Garbage Collector (ZGC) is a modern, low-latency garbage collection algorithm introduced in Java 11 as an experimental feature.

Unlike all other Java GC algorithms, Z GC doesn’t use the generational heap structure. As G1 GC, Z GC uses regions where the heap is divided into many small, equal-sized Z-Pages. Z-Pages can be dynamically created and ​destroyed.

The algorithm works like this:

1. Marking: Z GC begins by marking concurrently with the application, all live objects in the heap.
2. Compaction and Relocation: After marking, Z GC starts relocating (or compacting) live objects to new regions in the heap.
3. Remapping References: After objects are relocated, Z GC remaps all object references to point to their new locations.

How does Z GC can do that?

Z GC uses two concepts called colored pointers and load barriers. Colored pointers enables ZGC to find, mark, locate, and remap the objects. Here is an illustration of colored pointers, used to reference heap objects:

Press enter or click to view image in full size

• 42 bits address the object itself
• Marked1 and Marked0 bits mark objects for garbage collection
• The single Remapped bit enables an object to be marked as not pointing to into the relocation set
• Finilizable bit marks that an object can only be reachable through a finalizer
• 18 bits are reserved for future use

The use of two bits (marked0 and marked1) in Z GC’s colored pointers allows the garbage collector to efficiently manage multiple concurrent or successive marking cycles.

Load barriers are special instructions inserted into the application code by Z GC. Every time an object reference is accessed, the load barrier checks and potentially updates the reference using the colored pointers, ensuring that it points to the correct, potentially relocated, object.

To use this experimental algorithm, you can apply the following option:

-XX:+UnlockExperimentalVMOptions -XX:+UseZGC

In summary, Z GC is a low-latency GC algorithm designed for large heaps and applications requiring minimal pause times. It achieves this by performing most of its operations concurrently with application execution, using a region-based heap and a load barrier mechanism to manage object references.

Shenandoah GC

This experimental feature has been introduced in Java 12. Shenandoah divides the heap into small, equal-sized regions, similar to the G1 GC. However, unlike G1 Shenandoah doesn’t divide the heap area into generations.

Press enter or click to view image in full size

The Shenandoah GC algorithm works as follow:

1. Marking: most of the work is done concurrently to mark all reachable objects in the heap, however, a start phase and a final mark phase are done in stop-the-world mode to ensure completeness.
2. Cleanup: Shenandoah concurrently cleans up the memory, reclaiming regions that are found to be completely free of live objects.
3. Evacuation: Shenandoah moves live objects from regions with a high proportion of garbage to other regions, freeing up large chunks of memory. This is done concurrently, without stopping the application.
4. Update References: After objects are moved, Shenandoah updates concurrently all references to point to the new locations of the moved objects.
5. Cleanup: Shenandoah reclaims the memory from regions that are now empty after evacuation. This is done concurrently, without stopping the application.

Globally, the phases of Shenandoah GC algorithm looks like this:

Press enter or click to view image in full size

The main specificity of Shenandoah GC is the use of Brooks pointers. Brooks pointers can track the location of objects. When an object is moved during the concurrent evacuation phase, its original location contains a forwarding pointer to the new location. This ensures that any references to the object are automatically redirected to the correct location, even if they haven’t been updated yet.

To use this experimental algorithm, you can apply the following option:

-XX:+UnlockExperimentalVMOptions -XX:+UseShenandoahGC

In short, Shenandoah GC is a region-based garbage collector that minimizes pause times by performing most garbage collection tasks concurrently with application execution. It is particularly suited for applications requiring predictable and ultra-low latency, and it effectively manages large heaps by performing concurrent compaction and evacuation.

Epsilon GC

Used for performance testing, development, this GC was introduced in Java 11. Basically, this GC just allocates memory but never reclaims it. When application exhausts the available heap space, the JVM will throw an OutOfMemoryError and just terminate. As there is no memory management at all, there is no pauses nor memory clean up nor compacting. This makes it straightforward to understand the true impact of the selected GC algorithm on the application.

To use this experimental algorithm, you can apply the following option:

-XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC

There are also other rare use cases where this GC algorithm can be useful:

• Short-lived Applications: In scenarios where an application runs for a very short period and does not need to reclaim memory, Epsilon GC can be used to avoid the overhead of garbage collection.
• External Memory Management: In some cases, memory management might be handled by an external system, making the JVM’s garbage collection redundant.

How does Garbage Collection work in C#?

Heap Structure

In C#, the GC operates on the managed heap, a block of memory reserved for the application by the .NET runtime. When an application creates a new object, memory is allocated from the managed heap.

Objects larger than 85 000 bytes are allocated in a special area of the heap called the Large Object Heap (LOH). The LOH is not compacted as often as other parts of the heap, leading to possible fragmentation. The GC collects the LOH less frequently because it is more expensive to compact.

The managed heap is divided into three generations:

• Generation 0: This is where newly created objects are allocated.
• Generation 1: Objects that survive a Gen 0 garbage collection cycle are promoted to Gen 1.
• Generation 2: Objects that survive a Gen 1 garbage collection cycle are promoted to Gen 2. This is were long-live objects are.

Triggering Garbage Collection

There are several ways to trigger the GC:

• Generation threashold: This is the most common trigger. When a Generation is full, the GC will attempt to reclaim memory by collecting unused objects.
• Memory pressure: If the system is low on memory, the GC may be triggered to free up space.
• Explicit call: Although not recommended, developers can force a GC collection using GC.Collect().

Garbage Collector Process

1. Marking: The GC begins by identifying all objects that are still reachable from the application by traversing the object graph from the root.
2. Sweeping: Unmarked objects are reclaimed by the GC.
3. Relocating: The references of all objects identified as live are updated to point to their new locations, where the objects will be moved during the compacting phase.
4. Compaction: The remaining live objects are compacted to free up contiguous blocks of memory. This takes care on promotion, where objects that survive a garbage collection cycle are promoted to the next generation.

Threads management with Background Garbage Collection

Starting from .NET Framework 4.5, background GC replaces concurrent GC. In background GC, generations 0 and 1 are collected as needed while a generation 2 collection is in progress. This type of GC is carried out on one or more dedicated threads, depending on whether it’s workstation or server GC, and is specifically used for generation 2 and LOH collections.

• Workstation GC: Optimized for single-user applications (like desktop apps).

• Server GC: Optimized for multi-threaded, high-throughput server applications (like web servers). It uses multiple threads for garbage collection.

Background GC optimizes the pauses duration, as shown by the following schema:

Press enter or click to view image in full size

Managing Objects Outside the Managed Heap

Until now only objects in the managed heap were handled. However, in C#, there are some objects that require manual memory management. Unmanaged resources include system resources, file access, or database connections.

There are three ways to manage these ressources:

• Using the Dispose method of the IDisposable interface. This method should contain the code responsible for explicitly freeing the memory of unmanaged resources.
• Create a destructor (with the ~ symbol), which will be called automatically when the garbage collector runs.
• Using the using keyword, to be sure that the object will be destroyed, as Dispose is automatically called when exiting the block.

How does Garbage Collection work in Python?

Python’s garbage collection is based on reference counting and a cyclic garbage collector. Let’s see how it works.

Reference Counting

Each object has a reference count, a Python object’s reference count is incremented whenever the object is referenced, and it’s decremented when an object is dereferenced. When it reaches zero, the memory is freed.

Press enter or click to view image in full size

It’s possible to see the reference count of objects with the following code line:

sys.getrefcount(a)

Cyclic Garbage Collector

Reference counting works fine on most objects. However, it cannot handle cyclic references on its own, such as those illustrated below:

The cyclic GC periodically scans objects and identifies groups of objects that are only reachable by one another and are not accessible from outside the cycle (ie. from the root). Once identified, the cyclic GC breaks the cycle by deallocating these objects. This is the Mark and Sweep algorithm illlustrated below:

Press enter or click to view image in full size

Python’s cyclic GC is generational, organized like this:

• Generation 0: New objects are placed here. It’s collected most frequently.
• Generation 1: Objects that survive a collection in Generation 0 move here.
• Generation 2: Objects that survive collections in Generation 1 move here. It’s collected the least frequently.

Here’s the process of generational GC in Python:

Press enter or click to view image in full size

How is GC triggered?

• Reference counting is automatically triggered when reference count reaches 0.
• Cyclic GC is triggered automatically when a threashold is reached. Each generation as a specific threashold.

import gc
gc.get_threshold() # Gets the threshold for each generation
gc.get_count() # Gets the count of objects for each generation

• Manually, by calling gc.collect(generation=2, full=True)

import gc
gc.collect()  # Collects all generations
gc.collect(0, False)  # Collects only generation 0

In Python, the reference counting algorithm cannot be disabled, whereas Cyclic GC is optional and can be disabled.

import gc
gc.disable() # Disable garbage collection
gc.enable() # Enable garbage collection

A world about threads

Python uses the Global Interpreter Lock (GIL) to ensure that only one thread executes Python bytecode at a time, even in a multi-threaded environment. During reference counting, GIL ensure the operation is performed atomically. When cyclic GC runs, it pauses other threads by acquiring the GIL, making the entire garbage collection process thread-safe. It also means that GC pause all other Python threads when it runs.

How does Garbage Collection work in GoLang?

In GoLang, GC is concurrent, minimizing stop-the-world pauses, tricolored, and based on Mark and Sweep algorithm. Let’s look at it in details.

Tri-colored Mark and Sweep

The term tri-color refers to the marking algorithm used by Go’s GC, which categorizes objects into three distinct states: white, grey, and black.

• White objects: These are objects that the GC has not yet examined. They may or may not be reachable from the roots.
• Grey objects: These are objects that the GC has identified as reachable from the roots, but their descendants objects have not yet been processed.
• Black objects: These are objects that the GC has fully processed, meaning both the object itself and all its descendants have been identified as reachable.

At the beginning of the marking phase, all objects are marked white, indicating they are candidates for reclamation. Root objects are then marked grey, signifying they are active but their referenced objects haven’t been processed yet. The garbage collector processes these grey objects, marking their descendants grey and turning the original objects black. This continues until no grey objects remain. At the end, all live objects are black, and the remaining white objects are identified as garbage and can be collected in the sweep phase.

Here is a schema of marking step using tricolored Mark and Sweep:

Write Barriers

This mechanism ensures that the properties of the tri-color abstraction are preserved during the execution of the algorithm. When a pointer to a white object is assigned to a black object, the garbage collector automatically marks the white object as grey, preventing it from being collected too early.

Triggering Garbage Collector

The garbage collector is automatically triggered based on the amount of allocated heap memory. The Go runtime dynamically adjusts the frequency of GC runs based on the current memory usage and the program’s allocation patterns. It’s possible to control the GC’s behavior to some extent using environment variables like GOGC, which sets the percentage growth of the heap that triggers the next garbage collection.

Hoping Garbage Collectors have no more secrets to you in any of these languages. If you liked the article, feel free to clap it, comment it or share it. To stay updated with my content, you can follow me on Medium.