Like attention, no more lost, your support means a lot to me!

🔥 Hi, I’m Chouchou. GitHub · Android-Notebook has been included in this article. Welcome to grow up with Chouchou Peng. (Contact information at GitHub)

directory

Front knowledge

The content of this article will involve the following pre/related knowledge, dear I have prepared for you, please enjoy ~

  • Java memory allocation model: the Java virtual machine | memory allocation model

  • Objects in the virtual machine: the Java virtual machine | object with a magnifying glass

  • Reference types: Java | reference type & finalizers mechanism

1. Overview of garbage collection

Garbage Collection (GC) is an automatic memory management mechanism. When objects in memory are no longer needed, they are automatically released to free up storage space.

Garbage collection is one of the most important features of the Java Virtual Machine, and it is also one of the most important interview questions. In practice, since GC consumes program running resources, more in-depth memory performance optimization also requires an understanding of the garbage collection mechanism.

Here are three questions to discuss when discussing garbage collection mechanisms. You can read the rest of the article with these questions in mind for clarity.

  • Reclaimed objects: Which objects/regions need to be reclaimed?
  • Timing of collection: When is the GC triggered?
  • The recycling process: How to recycle?

1.1 Concepts related to GC

In this section, we will list some of the most important concepts in GC:

concept describe
collector Represents the module in the program responsible for garbage collection
mutator Represents modules in the program other than collector
Incremental Collection Each GC only targets a portion of the heap, rather than the entire heap, greatly reducing pause times
Generational collection (Generational GC) One of the ways to realize incremental recovery is to divide the heap into new generation, old generation and eternal generation
Parallel Collection The collector has multiple garbage collection threads
Concurrent Collection Refers to a phase of garbage collection where the Collector thread and mutator can execute simultaneously.

This avoids the need to pause the Mutator thread while the Collector thread is working (stop-the-world)

1.2 Advantages and disadvantages of garbage collection

  • Advantages: There is no need to write delete/free operation for each new operation, and the program is not prone to memory leakage or overflow problems.

  • Risk: The garbage collector itself also consumes system resources (CPU resources/memory), increasing program pause times.

1.3 Performance index of GC algorithm

Before introducing the garbage collection algorithm, let’s define the performance metrics that evaluate the garbage collection method:

indicators define describe
Throughput Processing capacity per unit of time
throughput = Run user code time Garbage collection frequency ∗ Single garbage collection time Throughput = \frac{time to run user code} {garbage collection frequency * single garbage collection time}
Maximum pause time Refers to the maximum amount of time that a program is suspended for GC /
Space overhead Refers to the proportion of heap space that is available to the total heap Influencing factors: Object header size + reclamation algorithm
Access locality Indicates whether the collection method tends to access local memory Access to local memory makes it easier to hit the CPU cache line

Tip: If you do not understand the concept of “access locality”, you can think of quicksort and heap sort performance comparison, the former access locality is better.

2. Area of garbage collection management (collected objects)

According to the Java Virtual Machine Specification, the memory managed by the Java Virtual Machine includes the following areas:

Runtime data area Thread the exclusive describe
Program counter register private The memory address where the next bytecode instruction is stored
Java virtual machine stack private Store thread Stack frames



Stack frame contains: local variable table, operand stack, dynamic link, return address and other information
Local method stack private Store local method stack frames
The Java heap Shared The storage area for most objects
Methods area Shared Store type information, constants, class static variables, code cache even after compiler compilation, and so on

Not all areas managed by the Java VIRTUAL machine require garbage collection, and thread-exclusive areas are destroyed as the thread terminates without garbage collection. So the areas that the garbage collection mechanism needs to manage are:

  • Heap: garbage objects;

  • Method area: Obsolete constants and no longer used types.

3. How to determine the garbage object? (Timing of recycling)

There are two ways to determine whether an object is junk: reference counting & reachability analysis. According to the judgment method, the garbage collection algorithm described in the following paper can also be divided into reference counting type and trace type.

3.1 Reference Counting Algorithm (Reference Counting)

3.1.1 Determination method

When an object is allocated, an extra space is allocated to the object, which is used to record the number of references to the object. If there is a new reference to the object, the counter is incremented by one; When a reference no longer refers to the object, the counter decreases by 1. When the value of the counter is 0, the object is garbage.

3.1.2 advantages

  • 1, timeliness: when the object becomes garbage, the program can immediately perceive, immediately recycling; In the reachability analysis algorithm, it is not sensed until GC is performed.
  • 2. Short maximum pause time: GC can run alternately with applications.

3.1.3 shortcomings

  • 1. Frequent update of counter value: In most cases, the reference state of the object will be updated frequently, and the task of updating counter value will become onerous;
  • 2. Heap utilization reduction: the counter occupies at least 32 bits of space (depending on the machine bits), resulting in the heap utilization reduction;
  • 3. Complexity of implementation;
  • 4. (Fatal flaw) Unable to reclaim circular reference objects.

Error prone: Reference counting method is simple algorithm, difficult to implement.

3.2 Reachability Analysis

3.2.1 Determination Method

Starting from the GC Root node (GC Root), the reference chain is formed according to the reference relationship. An object is alive if it exists in a chain of references to GC Root, garbage otherwise. In Java, GC Root consists of:

  • 1. Objects referenced in the Java virtual machine stack (i.e. local variables in the stack frame);
  • 2. Objects referenced in the local method stack;
  • 3. Objects referenced by class static variables in the method area;
  • 4. Objects referenced in the method area constant pool;
  • 5. Objects held by synchronized keyword;

3.2.2 advantages

  • 1. Recycle reference objects;
  • 2. Simple implementation.

3.2.3 shortcomings

  • 1. Long maximum pause times: during GC, the entire application stops (stop-the-world, STW);
  • 2. Garbage collection is not timely: garbage objects cannot be sensed until GC is performed;

3.3 summary

methods advantages disadvantages
Reference counting 1. Timeliness

2, the maximum pause time is short		 1. The counter value is updated frequently

2. Heap utilization is reduced

3. Complexity of implementation

Unable to reclaim circular reference object
Accessibility analysis 1. Recycle reference objects

2. Simple implementation		 1, the maximum pause time is long

2, recycling is not timely

Because reference counting GC has the fatal flaw of “not being able to reclaim circular reference objects”, trace GC is still dominant in the industry implementation, and I will focus on trace GC later.

4. Garbage Collection algorithm (recycling process)

In principle, garbage collection algorithms can be divided into the following four basic algorithms, other garbage collection algorithms are actually improvements or combinations of basic algorithms.

time Early adopters algorithm category
In 1960, John McCarthy, the father of Lisp Mark-clean algorithm The track type
In 1960, George E. Collins Reference counting algorithm Reference counter
In 1969, Fenichel Replication algorithm The track type
In 1974, Edward Lueders Mark-collation algorithm The track type

In practice, most modern garbage collectors use the generational collection model, which is based on the following empirical premises:

  • 1. Most of the objects die overnight and cannot survive the first garbage collection;
  • 2. Objects that have survived multiple garbage collections are often harder to recycle.

Based on the above factual experience, virtual machines often use the design idea of static and static separation: new objects and old objects that are difficult to recycle are stored in different areas, new objects are stored in the new generation, and objects that are difficult to recycle are stored in the old era. Different garbage collection algorithms are adopted according to the characteristics of different regions.

— Picture quoted from Internet

  • 1. New generation: Objects in the new generation have a low survival rate. As long as they pay a small amount of replication cost, they can complete the recovery process.

  • 2. Old generation: Objects in old generation have a high survival rate and no extra space for allocation guarantee, so “mark-clean” or “mark-tidy” algorithms are selected.

4.1 Mark-Sweep Algorithm

4.1.1 Algorithm recycling process

The recovery process of mark-clean algorithm is divided into two stages:

  • Mark phase: Walks through the heap to Mark garbage objects (or live objects);

  • Sweep phase: Walks through the heap, linking garbage objects in chunks to the free list.

4.1.2 advantages

Simple implementation;

4.1.3 shortcomings

  • 1. Unstable execution efficiency: The more objects in the Java heap, the more time-consuming the process of marking and cleaning may be;
  • Fragmentation: The collection process will gradually generate many small fragments of fragmented memory. When the fragments are insufficient to allocate object memory, another GC for Alloc will be triggered.

4.2 Copying Algorithms

4.2.1 Algorithm recycling process

The key points of the recovery process of the replication algorithm are as follows:

  • 1. Divide the heap into two Spaces of the same size: from and to;
  • 2. Object memory allocation only uses the FROM area. When the FROM area is full, all surviving objects are copied to the TO area.
  • 3. Swap Pointers to and from after replication.

– pictures reference weread.qq.com/web/reader/… The Deng Fan flat

4.2.2 advantages

  • 1. Fast allocation of objects: A free block is a contiguous memory space that does not need to traverse the free list as mark-clean algorithms do;
  • 2. Avoid memory fragmentation: Live and newly allocated objects are compressed to one side of the tospace, avoiding a lot of small memory that is not contiguous.

Holdings shortcomings

  • 1. Low heap utilization: only half of the heap can be used when the heap is bisected, and the maximum heap utilization is only 50%.

4.2.4 improvement

  • 1. The New generation is divided into: one Eden area and two Survivor areas, with a corresponding ratio of 8:1:1;
  • 2. Objects are allocated only in Eden zone. When Eden zone is full, all the surviving objects in Eden zone and from Survivor zone are assigned to To Survivor zone;
  • 3. After replication is complete, swap Pointers to from Survivor and to Survivor.

After the improvement, the heap utilization rate is up to 90%.

4.3 Mark-Compact Algorithm

4.3.1 Algorithm recycling process

The essential difference between mark-clean and mark-tidy algorithms is whether objects are moved. The recovery process of mark-collation algorithm is mainly divided into two stages:

  • The Mark phase: walks through the heap, marking out garbage objects (this step is the same as the mark-clean algorithm);

  • The Compact phase: Move (compress) all living objects to one end of the heap and then clean up memory directly beyond the boundary.

– pictures reference weread.qq.com/web/reader/… The Deng Fan flat

4.3.2 advantages

  • 1, avoid memory fragmentation, high heap utilization, higher throughput;
  • 2. Fast allocation of objects: A free block is a contiguous memory space that does not need to traverse the free list as mark-clean algorithms do;

4.3.3 shortcomings

  • 1. Moving objects takes more time than cleaning them, resulting in longer STOP-the-world GC pauses.

5. Concurrent reclamation

5.1 stop – the – world phenomenon

In standard garbage collection algorithms, all user threads (mutators) are suspended during the tag-clean/collate/copy process of the garbage collector to ensure that all garbage objects are completely cleaned up.

But this approach can lead to the virtual machine throughput degradation (throughput = garbage collection to run user code time frequency ∗ throughput single recycling time = \ frac {user code running time} {* single recycling garbage collection frequency time} throughput ∗ = garbage collection frequency single recycling time running user code).

5.2 CMS Garbage Collector

CMS (Concurrent Mark Sweep), a garbage collector that allows collecting threads to run concurrently with user threads, has been developed to minimize the pause time of garbage collectors on systems that seek to respond quickly.

The main working process of the CMS garbage collector is divided into four steps:

  • Initial tag (stop-the-world) : tag only objects that are directly referenced by GC Root. This process is slow because there are relatively few GC roots.

  • 2. Concurrent marking (time consuming) : Continue traversing objects on the GC Root reference chain. This process is time-consuming, so concurrent processing is used.

  • 3. Re-marking (stop-the-world) : In order to correct the reference relationship changes caused by the user thread during concurrent marking, the user thread needs to be paused for re-marking;

  • 4. Concurrent cleanup (Time-consuming) Because the object cleanup process is time-consuming, concurrent processing is adopted.

— Picture quoted from Internet

5.3 Advantages of CMS

  • 1. Shorten the stop-the-world time of the system and improve the throughput;

5.4 Disadvantages of CMS

  • 1. CPU sensitivity: The system as a whole will occupy more CPU resources if the concurrent policy is adopted.
  • 2. Floating garbage: Because the user thread is still running during concurrent cleaning, CMS cannot recycle the garbage generated by the user thread at this stage. This part of garbage is called “floating garbage”. Due to the existence of floating garbage, the garbage collector needs to reserve some space to allow the generation of floating garbage. If the space reserved is not enough to store floating garbage, a Concurrent Mode Failure will occur. In this case, a non-concurrent cleaning solution needs to be started temporarily to replace the CMS.
  • 3, memory fragmentation: the use of mark-clean algorithm, memory fragmentation will be generated.

6. Summary

  • 1. Performance indicators of garbage collection algorithm mainly include: throughput, maximum pause time, heap utilization, access locality. In the process of understanding garbage collection mechanism, we can take “the object of recycling” & “the timing of recycling” & “the process of recycling” to understand;

  • 2. Garbage collection mechanism management area includes heap and method area;

  • 3. Algorithms for judging garbage objects are divided into reference counting algorithm and reachability analysis algorithm, each of which has its own advantages and disadvantages.

  • Garbage collection algorithms can be divided into four basic algorithms: reference counting algorithm, mark-clean algorithm, mark-collation algorithm and copy algorithm. Other garbage collection algorithms are improvements or combinations of the underlying algorithms. For example, the mainstream VIRTUAL machine garbage collection algorithm adopts generational recycling model: that is, the copying algorithm is used in the new generation (low survival rate of objects), while the “mark-clean” or “mark-tidy” algorithm is used in the old generation (high survival rate of objects and no extra space for allocation guarantee).

  • 5. In standard garbage collection algorithms, the garbage collection process is stop-the-world. Using concurrent collection can reduce system pause times and provide throughput.

The resources

  • Debug ART Garbage Collection — Android Developers
  • Understanding Android in Depth: Java Virtual Machine ART (Chapter 14). By Fanping Deng
  • In Depth understanding the Java Virtual Machine: Advanced JVM features and Best Practices (3rd edition) (chapters 2 and 3). By Zhiming Chou
  • Algorithms and Implementation of Garbage Recycling. By [Japan] Nakamura Narayo, [Japan] Aikawa Mitsu
  • “Android Mobile Performance Combat” (Chapter 2) — Tencent SNG special test team
  • GC Debug Logs for Dalvik and ART Virtual Machines. By Gityuan bytedance
  • Let’s talk about Java Garbage Collection from start to finish. By Nie Xiaolong (Alibaba)
  • How are Garbage Collection Algorithms Designed? — Qi Guang (Ali Baba
  • How has garbage Collector Evolved? — Qi Guang (Ali Baba
  • “Alipay Client Architecture analysis: Android Client Startup Speed Optimization of the” Garbage Recycling “– Xinxian (Alibaba)
  • Meituan’s Exploration and Practice on ZGC — Wang Dong, Wang Wei (Meituan)
  • ART Virtual Machine on Android by Qiang Bo (Huawei)
  • Dalvik VIRTUAL Machine on Android by Qiang Bo (Huawei)

Creation is not easy, your “three lian” is chouchou’s biggest motivation, we will see you next time!