Learning JVM garbage collection is inseparable from the trace garbage collection algorithm, the existing mainstream Java virtual machines are using the trace garbage collection algorithm. In contrast to reference-counting garbage collection, tracing garbage collection algorithms adopt an indirect collection strategy, that is, this strategy does not directly look for the garbage itself, but first looks for which objects are alive, and then determines that all the remaining objects are garbage objects. The tracking recovery algorithm itself includes three recovery strategies: Mark-sweep, mark-copy and Mark-compact. In a real collector, different recovery strategies must be adopted according to different situations of objects by partitioning or generation. In response to these situations, a number of related basic concepts are presented.

Tracing recovery algorithm Recovery policy

Tracing recovery algorithm itself includes three recovery strategies: Mark-sweep, Mark-copy and Mark-compact. All of these three strategies have one thing in common, that is, Mark. The process of this marking was described in the previous article (JVM learning-GC determination of object survival), and the reachability analysis algorithm is not outlined in this article.

Mark-sweep algorithm

Mark-sweep algorithm is a typical non-mobile recovery algorithm, which is the basis of all tracking recovery algorithms. Other algorithms are improved based on the shortcomings of Mark-sweep algorithm.

The principle of

After the marking process is complete, unmarked objects are recycled.

The advantages and disadvantages

Advantages: 1. Throughput of mark-sweep algorithm (throughput is the ratio of the time the processor spends running user code to the total elapsed time of the processor, throughput = running user code time/(running user code time + running garbage collection time)) is high; 2. Mark-sweep algorithm is relatively efficient in space utilization. It does not need to allocate extra space to Copy objects as mark-copy algorithm does, nor does it need to set reference counters for each object as reference counting algorithm does. Disadvantages: 1. The execution efficiency of Mark-sweep algorithm is not stable; 2. During the process of mark-sweep algorithm, a large amount of fragmented space will be generated. Too much fragmented space will cause that the program cannot find a large enough continuous space when allocating objects at runtime, leading to another garbage collection in advance;

Mark-copy algorithm

Mark-copy algorithm is referred to as replication algorithm. In order to solve the problem of low efficiency of Mark-sweep algorithm when it faces a large number of recoverable objects.

Half region replication principle

The basic copy collector divides the heap into two equally sized halves, the source space and the target space. Each time the program runs, only the source space is used to allocate the object’s memory. When the source space is insufficient, the garbage collection is carried out, the roles of the two half regions are swapped, and then the surviving objects are moved to one end of the other half region. Finally, the garbage collection half region memory is cleared.

Advantages and disadvantages of half – partition replication

Advantages: 1. Half-zone replication improves the efficiency of garbage collection; 2. Semi-regional replication reduces the birth of fragmented space; Disadvantages: 1. Half-partition replication reduces the original available memory by half;

Appel recycling principle

Appel collection is an adaptive generation strategy proposed for standard ML. In ML language, less than 2% of objects can survive after a collection. Appel collection is formally designed for this situation. Appel recycling strategy divides the space into three parts: In the HotSpot VIRTUAL machine, the new generation collector changes the new generation into Eden space and the replication reservation into two smaller Survivor Spaces. During the program run, only Eden and one Survivor space are used for allocating memory each time. When garbage collection occurs, The surviving objects are copied to the remaining Survivor and the other two Spaces are zeroed out (the ratio of Eden to Survivor is 8:1 in the HotSpot virtual machine). When Survivor space is insufficient to accommodate a Minor GC, other memory regions (mostly older generations) are relied on for allocation guarantees, and objects that do not have enough space go directly to other regions.

Advantages and disadvantages of Appel recycling

Advantages: 1. Appel reclamation can dynamically adjust the size of the replication retention zone; Disadvantages: 1. There must be other space for space guarantee;

Mark-compact algorithm

The biggest problem of mark-sweep algorithm, which is a non-mobile collection algorithm, is that it will generate fragmented space, and mark-compact algorithm is a solution proposed to reduce memory fragmentation.

The principle of

After marking, all marked objects are moved to one end of the memory space, and memory outside the boundary is zeroed out.

The advantages and disadvantages

Advantages: 1. Reduced memory fragmentation; 1. In the case of a large number of objects surviving, the efficiency is higher than the replication algorithm; Disadvantages: 1. The Compact process is tedious, and most algorithms need to traverse The memory for many times, and STW(Stop The World) time is longer than Sweep time;

Personal understanding of mark-compact algorithm throughput: Algorithmically, mark-compact algorithms generally traverse the heap multiple times, so the throughput of mark-compact is not as good as that of Mark-sweep. However, for the whole system, Mark-sweep algorithm belongs to the non-moving recovery algorithm. The non-moving recovery algorithm has an obvious disadvantage that it is more complex in allocating memory, and other means of allocating space can only be used for a large amount of fragmented space (such as: Partition idle allocation linked list), and allocating memory is the most frequent operation during the running of the program, so the throughput of the mark-compact algorithm is better than that of the Mark-sweep algorithm in the system throughput.

Three color algorithm

In the marking process, the tricolor algorithm is the invariant observed by all valuers and recyclers.

Three color algorithm principle

As it traverses the object graph, the collector marks all visited objects in three colors based on whether they were visited.

  • White: The object is not yet reachable by the collector. At the beginning of the collection cycle, all objects are white. At the end of the collection cycle, all white objects are unreachable.
  • Gray: Indicates that the object has been scanned by the collector, but one or more references to the object have not been scanned.
  • Black: The object has been scanned by the collector and all references have been scanned. A black object can never point directly to a white object and will never be scanned again by the collector unless the color changes.

The collector starts from the white root node and gradually turns the objects of the object graph into gray and then black. When all traversal is complete, all reachable nodes turn black and unreachable nodes remain white.

Object loss problem

Object loss problems occur when both conditions occur at the same time

  • The assignor inserts one or more new references from the black object to the white object;
  • The assignor removes all direct or indirect references from the gray object to the white object.

Weak tri-color invariants and strong tri-color invariants

Weak tri-color invariants and strong tri-color invariants are used to deal with object loss.

  • Weak tricolor invariant: all white objects referenced by black are protected by grey (grey protection: white objects are directly or indirectly referenced by grey objects). The weak tri-color invariant breaks condition two of the object loss condition.
  • Strong tri-color invariant: There is no pointer to a black object to a white object. Strong trichromatic invariants break condition one of object loss conditions.

Solution to the tricolor problem when concurrency

Incremental updating

Incremental updates break the first condition. When a black object inserts a new reference to a white object, the newly inserted reference is recorded. After the concurrent scan is completed, the black object in the recorded reference relationship is scanned again.

Original Snapshot (SATB)

Raw snapshot (SATB) breaks the second condition. When a gray object deletes a reference to a white object, the reference to be deleted is recorded. After the concurrent scan, the gray object in the reference to be deleted is scanned again.

How GC is implemented

In the traceable garbage collection algorithm, the first step is to Mark the object with the reachability analysis algorithm. In the reachability analysis algorithm, the first step is to determine the Root Set. How to determine the Root Set affects the GC implementation.

Conservative type GC

If the JVM chooses not to record the type of every data in memory, then the JVM cannot distinguish between data at a location in memory that should be read as a reference type and another data type. In this case, the GC implemented is a “Conservative GC.” During GC, the JVM starts scanning memory from some known location (i.e., the JVM stack), and sees each number as “does it look like a pointer to the GC heap” in the same way that upper and lower bounds are checked, checked, etc.

Semi-conservative GC

The JVM can choose not to record type information on the stack, but on the object. In this way, the stack scan is still the same as Conservative GC, but when an object in the GC heap is scanned with enough type information, the JVM is able to determine exactly where the data in the object is a reference type. This is The semi-conservative GC, also known as ConserVative With Respect To The Roots.

Accurate type GC

The so-called accuracy of “accurate GC” is the key to “type”, that is to say, given a certain piece of data at a certain position, it is necessary to know what its exact type is, so that the meaning of data can be reasonably interpreted. The GC is concerned with whether the data is a pointer or not. This data is not only the data on the objects in the GC heap, but also the data in the active record (stack + register).

The theory of generational collection is relevant

Tracking garbage collection algorithms are very efficient at collecting small amounts of garbage, especially copy-collection algorithms. However, the existence of long-lived objects will affect the efficiency of recycling. In this case, partition is adopted to make long-lived data pile up to one side, so that the replication recovery algorithm can greatly improve the efficiency of young data. In the real commercial garbage recycling, most of them adopt the generation theory. Even though G1 collector serves as the collector of the whole region, the generation concept is still used in the region.

Generation collection theory

The theory of generational collection is based on two generational hypotheses:

  • Weak generation hypothesis: Most objects are ephemeral. This hypothesis has been proven in different programming languages and paradigms;
  • The strong generational hypothesis: subjects who live longer are less likely to die. This hypothesis has less evidence, but still makes sense for large object recycling.

Together, these two hypotheses underlie the consistent design principle of several common garbage collectors: the collector should divide the heap into different regions and then allocate the collection objects to different regions based on age.

In addition, the new generation object can be completely referenced by the old age object. If such references are generated, the whole old age needs to be traversed to determine the accuracy of the reachability analysis, which brings great performance burden to the memory reclamation, so another hypothesis is proposed

  • Cross-generation citation hypothesis: Cross-generation citation is very rare compared to same-generation citation.

Remembered Set and Card Table

For cross-generation references, the current solution is memory sets and card tables. Remembered Set is an abstraction, and Card Table can be a form of Remembered Set. The Remembered Set is an abstract data structure used to record the collection of Pointers from the non-collection part to the collection part when partial GC is implemented. 1. Record accuracy (in fact, whether remembered set or card table, record accuracy has a large choice) :

  • Word granularity: Accuracy to one machine Word per record. This word contains cross-generation Pointers.
  • Object granularity: Each record is accurate to one object. This object has fields containing cross-generation Pointers.
  • Card granularity: Each record is accurate to a large memory area. Objects in this region contain cross-generation Pointers.

(There are also many types of granularity, you can imagine)

Data structures Remembered Set: this is achieved using Pointers (object Pointers or word Pointers), for example

struct RememberedSet {  
  Object* data[MAX_REMEMBEREDSET_SIZE];  
}; 
Copy the code

Card Table: Use an array of bytes to record cards. Each Card pair should have one bit or one byte in the array, for example

struct CardTable {  
  byte table[MAX_CARDTABLE_SIZE];  
};  
Copy the code

Each element of the byte array Card table corresponds to a block of memory of a specific size in its identified memory area, which is called a “Card Page”. Generally, the size of the Card Page is 2 to the NTH power of bytes. The memory of a card page usually contains more than one object. As long as there is a cross-generation pointer in the field of one or more objects in the card page, the identity of the array element of the corresponding card table is changed to 1, which is called the element becomes dirty, and it is marked as 0 if there is no such element. As long as the dirty elements are filtered out during garbage collection, the dirty elements are added to the Root Set and scanned.

Age of object

In the HotSpot VIRTUAL machine of the JVM, the age of the object is placed in the object header, and each time the object undergoes a recycle, the age is increased by one, up to 15. Object assignment rules and promotion old age rules:

  1. Objects are allocated in Eden first
  2. Big object goes straight to the old age
  3. The long-lived object enters the old age
  4. Dynamic object age judgment (The virtual machine does not always require the object age to reach the specified promotion age (MaxTenuringThreshold) to be promoted to the old age. If the sum of all object sizes of the same age in the Survivor space is greater than half of the Survivor space, Objects older than or equal to this age can enter the old age without waiting until MaxTenuringThreshold.
  5. Space allocation guarantee

This article uses in-depth Understanding of Java Virtual Machine, The Garbage Collection Handbook and RednaxelaFX’s articles for reference and study