This is the first day for me to participate in the Genwen Challenge in November. Please check the details of the event: # 2021 Last Genwen Challenge, gameplay upgrade with many prizes, new experience waiting for you.

This article is the pre-knowledge of the following algorithm, after all, to understand the basis of algorithm logic, is to understand the concept

structure

object

Composition:

  • Header: Stores some basic information about the object, such as size, type, etc. Its address also represents the address of the object, similar to the first address of an array
  • Domain: The accessible part of an object that can hold various data and Pointers to other objects (headers to other objects)

classification

  • Active objects: Objects that can be referenced by the mutator (described below)
  • Inactive objects: Objects that cannot be referenced by the mutator, which are objects to be GC, called garbage

mutator

This is an action that changes the reference relationship of objects in the GC. It can be likened to a new operation, which creates a new object. The mutator can allocate memory to prepare for the new object, or change the direction of Pointers in the object’s domain

Other structures

  • Heap: The space in which objects are stored during program execution
  • Root: The starting point of a pointer to an object
  • Block: When mutator, a block of memory separated from the heap
  • Allocation: Method of selecting a block from the heap for the mutator

Algorithm to evaluate

How do you determine if a GC algorithm is good? There are several aspects

  • Throughput: The processing capacity per unit time can be calculated by: heAP_size /GC time for example

Throughput in the figure above = heap size /(A+B+C), where A,B, and C are three GCS

  • Maximum pause time: The maximum time the Mutator is paused for GC

As you can see from the above figure, the mutator will pause when GC is triggered, so it can also be interpreted as the maximum time required for a single GC. In the figure, B is the longest, so the maximum pause time is B

  • Heap efficiency

There are two aspects, one is the head of the object, in the object, the larger the head, the more information, the more convenient to find it, but the efficiency will be reduced, because the head is large, the size of the object remains the same, the number of objects can be generated will be reduced

The second is the utilization rate. The better the algorithm is, the higher the utilization rate of the heap will be, of course, but the corresponding GC will be more difficult. Although the analogous hash algorithm can maximize the utilization of array space through mapping, the array arrangement is very irregular. The same is true in the heap, where similar objects may be distributed all over the heap, making it difficult to find them all

  • Some objects will be generated or destroyed together due to strong correlation. For example, boyfriend leads to girlfriend. It is better to put these objects in a close place, so that they can be generated and removed easily

So, our GC algorithm is looking for greater throughput, smaller maximum pause times, appropriate utilization, and maximum locality

Now that you have everything you need to learn about GC, let’s learn about GC algorithms

From the beginning of this article, GC algorithm will continue to update, GC algorithm is the interview Java must ask knowledge, at the same time, in C, C ++ this need manual GC language, but also need to master the algorithm, come on!

I am Komatsu, programmer in 1998, in addition to Android development, I also adhere to the daily problem solution in B station, if you also want to improve the algorithm, you can pay attention to oh B station daily problem