13 Common Gc Algorithms the Background and Principles of Gc

13 Common GC Algorithms- The Background and Principles of GC #

GC is an abbreviation of the English term “Garbage Collection” and is commonly translated as “垃圾收集” in Chinese. Sometimes, for the sake of smoothness, “垃圾回收” (garbage recycling) is also used. Generally, “垃圾回收” and “垃圾收集” have the same meaning. In addition, GC also refers to “垃圾收集器” (Garbage Collector), which is the English expression for it. In this section, we will explain the commonly used GC algorithms in detail.

A digression on GC #

Let’s say we are in business and need warehouses to store goods. If all warehouses need to be built by the company itself, the cost would be too high and most people would find it difficult to manage, and the efficiency would not be great either. If cost control is not good, it would be difficult to make money. Therefore, modern society has a spirit of sharing and leasing, which significantly improves the utilization of resources in the whole society.

For example, in a supply chain, if Company A transfers goods to Company B, and Company B transfers goods to Company C, then each company’s own processing workshops and private warehouses can be likened to thread spaces. There will be corresponding assembly lines in the factory. Because the energy of each company/salesperson is limited, this private space cannot be infinitely large.

The public warehouse can be likened to the heap memory, which is much larger than the private space and is very convenient for other companies to store and retrieve goods. It can either be accessed directly or require a key to access through locking. It is obvious that this system needs to be effectively managed for the entire warehousing system to operate well. Warehouses that are no longer in use need to be notified that they are no longer needed, otherwise the company will continue to pay fees, which is essentially a waste of the company’s money and society’s resources. This is similar to memory deallocation.

It can also be likened to a shared workspace in a maker space. Workspaces (memory) are limited and fixed. Everyone can come and lease (apply for memory) and after acquiring ownership, they can use the workspace (memory). After using it, they return it to the management (system), and then others can come and lease and use it.

In this section, we will first briefly introduce the basic knowledge related to GC, and then introduce three common garbage collector implementations (Parallel/CMS/G1).

Manual Memory Management #

For students who have previous experience in C/C++ programming or an understanding of computer principles, it is easy to understand the concepts of “memory allocation” and “memory deallocation”.

During the execution of a computer program, there needs to be a place to store input parameters, intermediate variables, and calculation results. Through previous course learning, we know that these parameters will be stored in the stack memory.

However, if the system’s business processing code needs to use memory immediately, for example:

For example, I am a salesperson responsible for business negotiations with other companies. I need to keep an eye on the contracts after they are signed and decide when to return the warehouse. This is the case when using C/C++ programming, and we call it “manual memory management”.

When the company is small and the business is simple, this method is very flexible, and the salesperson has a lot of power. But if the company’s business scale expands and the business becomes more complex, the shortcomings of this approach will become apparent. Because it is also difficult for the salesperson to decide when to return the warehouse. Not returning it may waste resources, but returning it may be needed by another downstream company, which can result in complaints.

So C++ programmers are very cool, like the hand of God, everything is under control. But for companies that use C++ to develop their businesses, other departments may not be as cool.

This approach is called “manual memory management” in the computer field.

The drawback is that when multiple people have handled a warehouse, they may not remember whether this warehouse needs to be returned or if it has already been returned, resulting in chaotic warehouse management and conflicts among multiple parties using the warehouse.

Reference Counting #

After some discussion, the bosses decided to establish a department specifically for managing the warehouses. If anyone needs to use a warehouse, they have to apply to the warehouse department. As for when to release the warehouse, it will be managed by the warehouse itself, so the salespeople don’t have to worry about it.

The GC (Garbage Collector) is like this warehouse department. It is responsible for allocating memory and tracking the usage of this memory. It will release the memory when appropriate.

Thus, the warehouse department is established to manage these warehouses. How do they manage them?

First, they came up with a method called “reference counting”. When someone needs to use a warehouse, they would mark it as 1 with a counter. Whenever another operation needs to use it, they have to register it and increase the count by 1. After each operation is completed, the counter is decreased by 1. If the counter of a warehouse (memory used by an object) reaches 0, it means that no one is using this warehouse anymore, and we can return/release it whenever convenient. (Note: It is not efficient to release the warehouse immediately when the counter reaches 0. Instead, the system usually waits until a batch of warehouses is ready to be processed together, which is more efficient.)

However, if the operations become more complex and warehouses need to work together with dependencies:

At this point, simple reference counting will cause problems. Warehouses/objects with circular dependencies cannot be reclaimed, just like database deadlock, which is annoying. You cannot make it reach 0 by itself.

This situation is called “memory leak” in computers. The ones that should be released are not released, and the ones that should be reclaimed are not reclaimed.

If the dependencies become more complex, the computer’s memory resources may be full or insufficient, which is called “memory overflow”.

So we know that reference counting has some flaws. Is there a solution? As the saying goes, where there’s a will, there’s a way. I’ll find someone specifically to deal with circular counting. If one person is not enough, then two… But what if there are thousands or even billions of warehouses? It can still be solved, although it may take more time.

Platforms/languages like Perl, Python, and PHP use reference counting (of course, they have made some optimizations, so generally, you don’t have to worry too much). Moreover, each language has its own suitable scenarios, so it’s good for a language to focus on doing its own thing.

The first generation of automatic garbage collection algorithm uses reference counting. It only needs to remember the number of references for each object. When the reference count becomes 0, this object can be safely reclaimed. A well-known example is the shared pointer in C++.
The second generation of garbage collection algorithm is called “reference tracing”. Various garbage collection algorithms used by JVM are based on reference tracing.

Now let’s take a look at the garbage collection method used in JVM.

Mark and Sweep Algorithm #

Garbage Collection Process and Memory Pool Division #

In the previous section, we discussed the need to search for all objects and their reference relationships in the reference count approach. Now, let’s see how to find all objects and mark them. This section mainly explains this process.

In order to traverse all objects, the JVM defines what is called garbage collection roots precisely.

There is a class of very specific objects called Garbage Collection Roots, which include:

Local variables
Active threads
Static fields
JNI references
Other objects (to be introduced later)

The JVM uses the Mark and Sweep algorithm to track all reachable objects (i.e. live objects) and ensure that the memory occupied by all unreachable objects can be reused. This process includes two steps:

Marking: Traverse all reachable objects and categorize them in native memory.
Sweeping: This step ensures that the memory occupied by unreachable objects can be reused when allocating memory afterwards.

The JVM contains various GC algorithms, such as Parallel Scavenge, Parallel Mark+Copy, and CMS. They differ in implementation, but theoretically, they all use the two steps mentioned above.

The most important advantage of the mark and sweep algorithm is that it no longer results in memory leaks due to circular references.

Mark and Sweep is the most classic garbage collection algorithm. When applying this theory to practical use, there are many optimizations and adjustments that need to be made to adapt to specific environments. Later, we will go through a simple example to see how to ensure that the JVM can continuously allocate objects safely.

However, the disadvantage of this approach is that during garbage collection, all threads of the application must be suspended. If not suspended, the reference relationships between objects will continue to change, making it impossible to perform statistics. This situation is called STW pause (Stop The World pause), which temporarily stops the application to allow the JVM to perform memory cleanup. If we consider the environment in the JVM as a world, it is like the time in the entire world suddenly freezes as we often see in movies. There are many reasons that can trigger STW pause, with garbage collection being the most common one.

Fragmentation #

Every time the sweeping process is executed, the JVM must ensure that the memory occupied by unreachable objects can be reclaimed and reused. At this time, it is just like removing some chess pieces from a Go board, leaving behind some scattered empty spaces. However, this can (eventually) lead to memory fragmentation (similar to disk fragmentation), which can cause two problems:

Writing operations become more time-consuming because it becomes difficult to find a large enough free memory space (there is no entire empty space on the chessboard).
When creating new objects, the JVM allocates memory in continuous blocks. If the fragmentation problem is severe, an allocation error may occur when there is no free segment that can accommodate the newly created object.

To avoid this kind of problem, the JVM must ensure that the fragmentation problem does not get out of control. Therefore, during the garbage collection process, not only marking and sweeping are performed, but also a “memory compaction” process is executed. This process arranges all reachable objects in order to eliminate (or reduce) fragmentation. It is just like gathering the remaining chess pieces on the board together, leaving enough empty space. The diagram below illustrates this process:

Note:

References in the JVM are an abstract concept. If the GC moves an object, it will modify all references pointing to that object (in the stack and heap).

Moving/copying/promoting/compressing is usually an STW process, so modifying object references is a safe operation. However, updating all references may affect the performance of the application.

Generational Hypothesis #

As mentioned earlier, performing garbage collection requires stopping the entire application. Obviously, the more objects there are, the longer it takes to collect all garbage. But can we only deal with a smaller memory area? To explore this possibility, researchers found that most recyclable memory in a program can be classified into two categories:

Most objects are no longer used quickly and have a short lifespan.
There is a part that is not immediately useless, but also does not last for too long.

These observations formed the Weak Generational Hypothesis, which means that we can classify objects based on their different characteristics. Based on this hypothesis, the memory in the VM is divided into Young Generation and Old Generation. Sometimes, the old generation is also referred to as Tenured.

Splitting into these two separately cleanable areas allows us to use different algorithms to greatly improve the performance of GC based on the different characteristics of objects.

However, there is no such thing as a free lunch, so this method is not without any problems. For example, objects in different generations may reference each other and become “de facto” GC roots when collecting a specific generation.

Of course, it should be emphasized that the generational hypothesis does not apply to all programs. The generational GC algorithm is specifically optimized for objects with the characteristics of “dying quickly” or “living for a long time”. At this time, managing objects that do not live for long becomes very embarrassing.

Memory Pool Division #

The memory pool allocation in the heap is also similar. The difficult part to understand is how garbage collection works in each memory pool. Please note that different GC algorithms may have different implementation details, but the concepts introduced in this chapter are consistent.

Eden Space #

Eden Space, also known as the Eden region, is a region in memory used to allocate newly created objects. Since multiple threads usually create multiple objects concurrently, the Eden region is divided into multiple Thread Local Allocation Buffers (TLABs). By using this buffer division, most objects are directly allocated by the JVM in the corresponding thread’s TLAB to avoid synchronization with other threads.

If there is not enough memory space in the TLAB, the object will be allocated in the shared Eden Space. If there is still not enough space in the shared Eden Space, a young generation GC is triggered to free up memory space. If there is still not enough free memory space in the Eden Space after GC, the object will be allocated in the old generation space.

During garbage collection in the Eden Space, the GC traverse through all objects reachable from roots and mark them as live objects.

We have mentioned that there may be references from objects in other generations to the objects in the Eden Space. To handle this, a method is needed to mark all references from other generations to the Eden Space. The JVM uses card marking as a technique: it only needs to remember the approximate locations of “dirty” objects in the Eden Space, which may have references from objects in the old generation. For more details, please refer to Nitsan’s Blog.

After the marking phase is complete, all live objects in the Eden Space are copied to the survivor space. The entire Eden Space can then be considered empty and used to allocate new objects. This method is called “Mark and Copy”: live objects are marked and then copied to a survivor space (note that it is copying, not moving).

Readers may wonder why copying instead of moving?

Survivor Spaces #

Next to the Eden Space are two survivor spaces called from space and to space. It is important to emphasize that at any time, one of the survivor spaces is empty.

The empty survivor space is used to store the collected objects in the next young generation GC. All live objects in the young generation (including the objects in the Eden Space and the non-empty “from” survivor space) are copied to the “to” survivor space. After the GC process is complete, the “to” survivor space contains objects, while the “from” survivor space does not contain any objects. The roles of the two survivor spaces are then switched, with the “from” space becoming the “to” space and vice versa.

The live objects are copied between the survivor spaces multiple times until the survival time of certain objects reaches a certain threshold. The generational theory assumes that objects that survive for a longer time are likely to survive for an even longer time.

These “older” objects are promoted to the old generation. When promoting, the objects in the survivor space are no longer copied to another survivor space, but are moved to the old generation and remain there until they become unreachable objects.

To determine if an object is “old enough” to be promoted to the old generation, the GC module tracks the number of times each object in the survivor space has survived. After each generational GC is completed, the age of live objects increases. When the age exceeds the tenuring threshold, the objects are promoted to the old generation.

The specific tenuring threshold is dynamically adjusted by the JVM, but it can also be specified using the -XX:+MaxTenuringThreshold parameter. If you set -XX:+MaxTenuringThreshold=0, live objects will be promoted to the old generation without being copied between survivor spaces during GC. In modern JVMs, this threshold is set to a default value of 15 GC cycles. This is also the maximum value allowed in the HotSpot JVM.

If there is not enough space in the survivor space to store the live objects in the young generation, promotion may occur earlier.

Old Generation #

The garbage collection (GC) implementation in the old generation is much more complicated. The old generation memory space is usually larger, and the probability of garbage objects inside it is smaller.

The frequency of old generation GC is much lower compared to the young generation. Additionally, because the majority of objects in the old generation are expected to be alive, the mark and copy algorithm is no longer used. Instead, objects are moved to minimize memory fragmentation. The cleaning algorithm for the old generation space is usually based on the following steps:

Mark all objects reachable from GC roots using a marked bit.
Delete all unreachable objects.
Compact the contents of the old generation space by copying all live objects and storing them consecutively starting from a certain point in the old generation space.

Based on the above description, it is necessary to explicitly compact the old generation in order to avoid excessive memory fragmentation.

Permanent Generation #

Before Java 8, there was a special space called the “permanent generation” or “Perm Gen”. This space stored metadata such as class information. Additionally, other data and information were also stored in this area, including interned strings and more.

In reality, this caused a lot of trouble for Java developers because it was difficult to calculate how much memory this area would actually require. The result of inaccurate predictions was often the occurrence of errors like java.lang.OutOfMemoryError: Permgen space. Unless OutOfMemoryError was actually caused by a memory leak, the only solution was to increase the size of the permgen space. For example, the following example sets the maximum permgen space size to 256 MB:

-XX:MaxPermSize=256m

Metaspace #

Since estimating the required space for metadata was so complex, Java 8 introduced a replacement for the permanent generation called “Metaspace”. From then on, many miscellaneous objects in Java were placed in regular heap memory.

Of course, information like class definitions is still loaded into Metaspace. The Metaspace is located in native memory and no longer affects regular Java objects. By default, the size of Metaspace is only limited by the available native memory of the Java process. This means that the program will no longer encounter java.lang.OutOfMemoryError: Permgen space errors due to loading a few extra classes/JAR files. However, it’s important to note that this unrestricted space is not without its consequences. If Metaspace gets out of control, it can lead to severe performance-impacting memory swapping or even failure in native memory allocation.

To avoid such worst-case scenarios, the size of Metaspace can be limited using the following syntax, for example, to limit it to 256 MB:

-XX:MaxMetaspaceSize=256m

Garbage Collection #

Although the implementation details of various garbage collectors may vary, garbage collectors generally focus on two things:

Finding all live objects
Discarding the rest, i.e., dead objects and objects no longer in use.

In the first step, all live objects are recorded through a process called marking in garbage collection.

Marking Reachable Objects #

In modern JVMs, all garbage collection algorithms start by identifying all live objects. The following diagram illustrates this process:

First, certain objects are designated as Garbage Collection Roots (GC roots), including:

Local variables and input parameters in the currently executing method
Active threads
Static fields of all classes in memory
JNI (Java Native Interface) references

Next, the garbage collector traverses the entire object graph in memory, starting from the GC roots and following direct references as well as references through object fields. All objects that the GC visits are marked as live objects.

Live objects are represented in the diagram with a blue color. After the marking phase is completed, all live objects have been identified. The remaining objects (gray data structures in the diagram) are unreachable from the GC roots and are considered garbage. The GC will remove these unreachable objects in the subsequent phases.

During the marking phase, there are a few things to note. To traverse all object reference relationships, all application threads need to be paused. This is because without pausing, it is not possible to track the constantly changing reference graph. This scenario is known as a Stop The World pause, and safe points are the points where threads can safely be paused so that the JVM can focus on performing the cleanup. Various factors can trigger safe points, and currently, GC is the most common reason for triggering safe points.

The duration of the pause in this phase is not directly related to the size of the heap or the total number of objects. It is determined by the number of live objects. Therefore, increasing the size of the heap does not directly affect the time taken for the marking phase.

After the marking phase, the GC proceeds to the next step, which is removing the unreachable objects.

Removing Unused Objects #

Different garbage collection algorithms have slight variations in how they remove unreachable objects, but they can generally be categorized into three types: sweeping, compacting, and copying. The next subsection will elaborate on these algorithms.

Sweeping #

The idea behind the Mark and Sweep algorithm is simple: simply ignore all garbage. In other words, after the marking phase is completed, the memory space occupied by the unreachable objects is considered free and available for allocating new objects.

This algorithm requires maintaining a free list to record all available free regions and their sizes. Maintaining the free list adds overhead to object allocation. There is also another weakness: even if there is a lot of free memory, there may not be a region large enough to accommodate the object being allocated, leading to allocation failure (in Java, this is an OutOfMemoryError).

Compacting #

The Mark-Sweep-Compact algorithm overcomes the drawbacks of the mark-sweep algorithm by moving all marked (live) objects to the beginning of the memory space.

The corresponding drawback is an increase in the pause time of GC. This is because all objects need to be copied to another location and the references pointing to these objects need to be updated.

The advantage of this algorithm is evident: after compaction, allocating new objects becomes simple, as it only requires pointer bumping. Using this algorithm ensures that the remaining capacity of the memory space is always clear and does not cause memory fragmentation issues.

Copying #

The Mark and Copy algorithm and the Mark and Compact algorithm are very similar in that both move all live objects. The difference is that the Mark and Copy algorithm moves the memory to another space called the survivor space. The advantage of the Mark and Copy algorithm is that marking and copying can be performed simultaneously. The downside is that it requires an additional memory space to store all live objects.

In the next section, we will introduce specific GC algorithms and implementations in the JVM.