1. Memory sets and card tables

In order to solve the problems caused by cross-generation references, the garbage collector built a data structure called Remembered Set in the new generation to avoid the whole old generation being included in GC Roots scanning. In fact, it is not only the new generation and the old generation that have the problem of intergenerational citation.

1.1 the memory set

A memory set is used to record Pointers from non-collection regions to objects in the collection Region. G1 maintains a memory set for each Region and records the addresses of other regions that reference objects in the Region. Full heap scan is not required for garbage marking.

1.2 the card table

A Card table records which objects in a Region are referenced by other regions. A Card table is an array. Each element corresponds to a memory block of a specific size in its identified memory Region, which is called a Card Page. In general, the card page size is the number of bytes to the NTH power of 2.

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) object in the card page, the value of the array element of the corresponding card table is marked as 1, which is called the element becomes Dirty. If there is no such element, it is marked as 0. When garbage collection occurs, it is easy to determine which card page memory blocks contain cross-generation Pointers by screening out the dirty elements in the card table and adding them to GC Roots for scanning.

2. Write barriers

The JVM maintains the pointing relationship of object reference Pointers through write barriers, which assign the address value of the moved object to the referenced object when an object is moved.

Write barriers can be thought of as an AOP aspect of the “assignment of a reference type field” action at the virtual machine level. When a reference object is assigned, an Around notification is generated for the program to perform additional actions, that is, before and after the assignment is covered by the write barrier.

3. Incremental collection and original snapshot

Theoretically, the reachability analysis algorithm requires that the whole process is based on a snapshot that can guarantee consistency. In the concurrent garbage marking, the user thread may re-reference the unmarked object, so it is necessary to re-mark and update the marked object to prevent the object from being deleted by mistake.

3.1 Three-color marking

The objects encountered in the process of traversing the object graph are marked in the following three colors according to the condition “visited or not” :

  • White: indicates that the object has not been accessed by the garbage collector. Obviously, at the beginning of the reachability analysis, all objects are white. If at the end of the analysis, all objects are still white, that is, they are unreachable.

  • Black: Indicates that the object has been accessed by the garbage collector and that all references to the object have been scanned. The black object indicates that it has been scanned, and it is safe and survivable. If there is another object reference pointing to the black object, there is no need to scan again. A black object cannot point directly to a white object (without passing the gray object).

  • Gray: Indicates that the object has been accessed by the garbage collector, but at least one reference to the object has not been scanned.

During concurrent garbage tagging, it is possible for unmarked objects to be re-referenced, resulting in two solutions: Incremental Update and Snapshot At The Beginning (SATB).

  • Incremental update: When a black object inserts a new reference to a white object, the newly inserted reference is recorded. After the concurrent scan, the black object in these recorded reference relationships is scanned again. This can be simplified to say that a black object becomes a gray object as soon as a new reference to a white object is inserted.

  • Original snapshot: When a gray object wants to delete a reference to a white object, the reference to be deleted is recorded. After the concurrent scan, the gray object in these recorded reference relationships is scanned again. This can also be simplified to mean that the search is based on a snapshot of the object graph at the moment when the scan begins, whether the reference relationship is deleted or not.

4.G1

The Garbage First(G1 for short) collector is a milestone in the history of Garbage collector technology. It pioneered the idea of local collection-oriented design and region-based memory layout.

The region-based heap memory layout pioneered by G1 enables it to reclaim only a portion of the pair of memory regions at a time. Although the G1 is designed to follow the generational collection theory, but the layout of the heap memory with other collectors have very obvious difference: the G1 is no longer insist on fixed size, and a fixed number of generational division, but the size of the Java heap is divided into multiple consecutive equal independent Region (Region), each Region can according to need, as new Eden space, Survivor space, or old time space of the generation.

The G1 collector tracks the “value” of garbage accumulation in each Region, which is the amount of space collected and the experience of how long it takes to collect, and then maintains a list of priorities in the background based on the allowable collection pause times (using the parameter -xx :M) AxGCPauseMillis specifies, default is 200 milliseconds), which prioritises regions with the highest return value.

Regions also have a special Humongous Region, which is used to store large objects. Most of G1’s behaviors treat Humongous regions as part of the old era.

The use of memory sets avoids the whole heap as GC Roots, but the application of memory sets in G1 collector is actually much more complicated. Each Region maintains its own memory set, which records the Pointers of other regions to it and marks which card pages these Pointers fall within.

How to ensure that the collector thread and the user thread run without interfering with each other in the concurrent marking stage, the CMS collector adopts incremental update algorithm, while G1 collector is implemented by the original snapshot (SATB) algorithm. In addition, the effect of garbage collection on the user thread is also reflected in the allocation of memory for newly created objects during the collection process. For the program to continue running, new objects must be continuously created. G1 designs two Pointers named Top at M Ark Start (TAM S) for each Region to divide part of the Region space for the allocation of new objects in concurrent reclamation. The addresses of newly allocated objects must be above these two Pointers. By default, they are alive and not included in the collection scope.

G1 Garbage collection process:

  • Initial M arking: Simply mark objects that GC Roots can associate directly with, and modify the value of the TAMS pointer so that the next phase of user threads running concurrently will allocate new objects correctly in the available regions. This phase requires the thread to pause, but it is very short, and it is done synchronously during the Minor GC, so the G1 collector actually has no additional pauses during this phase.

  • Concurrent M arking: Performs a reachability analysis of objects in the heap starting with the GC Root, recursively scanning the entire heap object graph for objects to be reclaimed. This phase is time-consuming but can be performed concurrently with user programs. When the object graph scan is complete, it is also necessary to reprocess the objects recorded by SATB that have reference changes at the time of concurrency.

  • Final M arking: Another short pause is made on the user thread to process the last few SATB records that remain after the end of the concurrent phase.

  • Live Data Counting and Evacuation: responsible for updating statistics for regions, ordering the collection value and cost of each Region, creating a collection plan based on the user’s expected pause time, freely selecting any number of regions to form a collection, and then copying the live objects of the part of the Region that decides to be recycled to an empty one Region, and clear all space of the old Region. The operation here involves the movement of the living object, which must suspend the user thread, and is done in parallel by multiple collector threads.

Disadvantages of the G1:

G1 consumes at least 10% to 20% of the Java heap’s additional memory to keep the collector working. G1 has a higher Footprint than CMS in terms of both garbage collection and additional execution load at runtime.

In addition to using post-write barriers for the same (but more cumbersome) card table maintenance operations in G1, pre-write barriers are needed to track pointer changes during concurrency in order to implement the raw snapshot search (SATB) algorithm.

5.ZGC

ZGC: Both want low latency that can limit gc pauses to less than 10 milliseconds at any heap size with as little impact on throughput as possible

The ZGC collector is a garbage collector based on Region memory layout, with (for now) no generation, and uses techniques such as read barriers, dye Pointers, and memory multiple mapping to implement concurrent mark-collation algorithms with low latency as the primary goal.

  • 1.ZGC also uses region-based heap memory layouts, but unlike them,ZGC’s regions are dynamic — dynamically created and destroyed, as well as dynamically sized regions. There are large, medium and small three types of capacity

    • Small Region: with a fixed capacity of 2 MB, it is used to store Small objects smaller than 256KB.
    • Edium Region: a medium Region with a fixed capacity of 32 MB. It is used to place objects larger than 256KB but smaller than 4 MB.
    • Large Region: the capacity of a Large Region is not fixed and can change dynamically. However, the value must be a multiple of 2 MB. It is used to place Large objects of 4MB or larger. Each large Region holds only one large object,

  • 2. Dye pointer

A signature design of the ZGC collector is its use of the dye pointer technique, which typically stores information about the object’s hash code, generational age, lock record, whether it was moved, and so on, in the object header.

Only the reference relation of an object can determine its survival. All other attributes of the object cannot affect its survival. The HotSpot VIRTUAL machine’s several collectors have different implementations of tags, from recording the tags directly on the object (as in Serial) to recording the tags on data structures independent of the object (as in G1). Shenandoah uses a 1/64th of heap memory, called BitM The ap structure records the markup information), while the ZGC’s coloring pointer is the most direct and purest, recording the markup information directly on the pointer to the reference object

The dyeing pointer technology of ZGC extracts the four high bits of the symbol to store the four mark information. With these flag bits, the VIRTUAL machine can directly see the tricolor flag state of the reference object from the pointer, whether it is in the reallocation set (that is, moved), and whether it can only be accessed by finalize() method

The specific process of ZGC:

  • Concurrent Mark: A Concurrent Mark is a stage of reachability analysis traversing the object graph, with brief pauses. ZGC marks objects on Pointers rather than objects. The marking phase updates the M arked 0 and M arked 1 bits in the dye pointer.

  • Concurrent Prepare for Relocate: This stage will determine which regions are to be relocated based on specific query conditions.

  • Concurrent Relocate: A central stage in the ZGC execution process is to copy live objects in a relocation set to a new Region and maintain a Forward for each Region in the relocation set Table), records the steering relationship from the old object to the new object. Benefited from dyeing pointer support, can only from ZGC collector on a clear reference whether an object in the redistribution of set, if the user thread as concurrent access to the concentration of the redistribution of object, the visit will be intercepted by the preset memory barrier, then immediately turn according to the Region of the published records to forward the access to the new copy of objects, and the same Update the value of the reference so that it points directly to the new object.

  • Concurrent remapping (Concurrent Remap) : heavy mapping does is fixed point to redistribution in the whole heap concentrated all the old object references, ZGC cleverly maps the concurrent heavy phase of work to do, to merge into the concurrent marks in the next garbage collection cycle stages to complete, anyway, they are object to iterate over all, this merger has saved a traverse object graph overhead. Once all Pointers have been corrected, the forwarding table that records the relationship between the old and new objects can be released.

ZGC Also limits the rate of object allocation will not too high, it can sustain can imagine the following scenario to understand ZGC this disadvantage: ZGC ready to do to a big pile of a complete concurrent collection, assuming that the whole process lasted for more than ten minutes, please do not confuse readers concurrent pause time and time, ZGC state Flag is pause time not more than 10 milliseconds), in this Over time, due to the high rate of object allocation in the application, a large number of new objects are created, which are difficult to fit into the tag range of the current collection and are usually treated as all living objects — even though most of them are dead and alive, resulting in a large amount of floating garbage.