Java-bang focuses on system architecture, high availability, high performance, high concurrency technology sharing
As a PhD student, I wrote a dynamic analysis of the statistical life cycle of Java objects and used it to run some benchmarks.
The results of some of these programs confirm the assumption of many researchers that most Java objects survive only for a short time, and the few that survive survive for a long time.
(Histogram of Java object life cycle in PMD, red represents objects optimized for escape analysis)
I mention this assumption because it gives rise to the idea of generational recycling in the Java virtual machine. In simple terms, the heap space is divided into two generations, called Cenozoic and old age. The new generation is used to store new objects. When an object survives long enough, it is moved to the old age.
Java virtual machines can use different reclamation algorithms for different generations. For the new generation, we assume that most Java objects live only for a short period of time, so it is possible to frequently use a shorter garbage collection algorithm so that most of the garbage can be collected in the new generation.
For the old age, we suspect that most of the garbage has already been recycled in the new generation, and that objects in the old age have a high probability of surviving. When a collection for older generations is actually triggered, the assumption is wrong or the heap has run out of space.
At this point, the Java virtual machine often needs to do a full heap scan, which takes time and costs nothing. (Of course, modern garbage collectors have evolved in parallel collections to avoid this full heap scan.)
In today’s post we look at Minor GC for the new generation. First, let’s look at exactly how the heap is divided in the Java virtual machine.
Heap partitioning for the Java virtual machine
As mentioned earlier, the Java Virtual machine divides the heap into new generation and old generation. The Cenozoic generation is divided into Eden region and two Survivor regions of the same size.
Taken by default, the Java virtual machine is a kind of dynamic allocation strategy (corresponding to the Java virtual machine parameters – XX: + UsePSAdaptiveSurvivorSizePolicy), according to the rate of generated objects, And the use of Survivor zone dynamically adjusts the ratio of Eden zone to Survivor zone.
Of course, you can fix this ratio with the -xx :SurvivorRatio parameter. Note, however, that one of the Survivor zones is always empty, so the lower the ratio, the higher the wasted heap space.
Generally speaking, when weWhen the new directive is called, itA block of memory is allocated in the Eden area as a storage object. Due to theThe heap space is shared by threads, so directly delimiting space here requires synchronization.
Otherwise, it is possible for two objects to share the same memory. If you remember the “parking space” analogy I used in the previous two posts, this is the equivalent of two drivers (threads) parking in the same spot at the same time and causing a scratch.
The Solution for the Java virtual machine is to pre-apply for multiple parking Spaces for each driver and only allow that driver to park in his or her own parking space. So what happens when the driver runs out of parking space (assuming the driver valets)?
The answer is: Just apply for more parking Spaces. This technique is called TLAB (Thread Local Allocation Buffer, which corresponds to the VM parameter -xx :+UseTLAB, enabled by default).
Specifically, each thread can request a contiguous chunk of memory, say 2048 bytes, from the Java virtual machine as a thread-private TLAB.
This operation requires locking, and the thread maintains two Pointers (actually more, but only two are important), one to the beginning of free memory in the TLAB and one to the end of the TLAB.
The new instruction, then, can be implemented directly by bump the pointer, which adds the requested number of bytes to the pointer to the free memory location.
I'm guessing there will be comments asking why bump the pointer isn't translated as a pointer bump. Just to explain, in English we usually omit the up in bump up the pointer. Bump in this context should mean "to raise." Another example is bump the version number when we release a new version of software.Copy the codeIf the value of the free memory pointer is still less than or equal to the pointer pointing to the end after addition, the allocation is successful. Otherwise, TLAB does not have enough space for this new operation. At this point, the current thread needs to re-apply for a new TLAB.
What happens when Eden runs out of space? At this point, the Java virtual machine triggers a Minor GC to collect the new generation’s garbage. The objects that survive are sent to the Survivor zone.
As mentioned above, there are two Survivor zones in the new generation, and we use from and to to refer to them respectively. The Survivior region directed by to was empty.
When a Minor GC occurs, surviving objects in the Eden region and Survivor region pointed to by FROM are copied to Survivor region pointed to by TO, and the FROM and TO Pointers are swapped to ensure that the next Minor GC, The Survivor zone to points to is still empty.
The Java virtual machine records how many times objects in the Survivor zone are copied back and forth. If an object is copied 15 times (corresponding to the VM parameter -xx :+MaxTenuringThreshold), the object will be promoted to the old age. In addition, if a single Survivor zone is already 50% occupied (corresponding to the vm parameter -xx :TargetSurvivorRatio), objects with higher replication times will also be promoted to the old age.
In summary, when a Minor GC occurs, we apply a mark-copy algorithm to promote the old Survivor from the Survivor region to the old age, and then copy the remaining Survivor and Eden’s Survivor to another Survivor region. Ideally, objects in the Eden region are basically dead, so there is very little data to copy, so this mark-copy algorithm works extremely well.
Another benefit of the Minor GC is that the entire heap is not garbage collected. One problem, however, is that old objects may refer to new ones. In other words, we need to scan objects in the old age when we mark them alive. If the object has a reference to a Cenozoic object, that reference is also treated as GC Roots.
Isn’t that another full heap scan?
Card table
HotSpot’s solution is a technology called Card Table. This technique divides the heap into 512-byte cards and maintains a card table that stores one identifying bit for each card. This identifier bit indicates whether the corresponding card is likely to contain references to the new generation object. If there is, then we consider the card to be dirty.
Instead of scanning the entire age during Minor GC, we can look for dirty cards in the card table and add objects from dirty cards to Minor GC Roots. After scanning for all dirty cards, the Java VIRTUAL machine clears all dirty cards.
Because the Minor GC is accompanied by a copy of the living object, the copy requires updating the reference to that object. Therefore, as we update the reference, we also set the identity bit of the card on which the reference resides. At this point, we can make sure that the dirty card contains references to the new generation object.
Prior to the Minor GC, we could not ensure that dirty cards contained references to new generation objects. The reason is related to how to set the identification bit of the card.
First, if you want to ensure that every card that might have a reference to a new generation object is marked as dirty, then the Java virtual machine needs to intercept writes to each referenced instance variable and make corresponding write identifier bits.
This operation is easier to implement in the interpretor. But in the machine code generated by the just-in-time compiler, additional logic needs to be inserted. This is also known as a write barrier (not to be confused with volatile fields).
Write barriers need to be kept as simple as possible. This is because we don’t want a long list of injected instructions to be followed by every write instruction to a reference instance variable.
Therefore, the write barrier does not determine whether the updated reference refers to an object in the new generation, but rather treats it as a reference that might refer to an object in the new generation.
In this way, the write barrier can be reduced to pseudo-code [1] below. Shifting nine bits to the right here is like dividing by 512, which is how the Java virtual machine maps from address to index in the card table. Eventually, the code is compiled into a shift instruction and a store instruction.
CARD_TABLE [this address >> 9] = DIRTY;
Copy the codeWhile the write barrier inevitably imposes some overhead, it can increase the throughput of Minor GC (application run time /(application run time + garbage collection time)). All in all, it was worth it. However, in high concurrency environments, write barriers introduce false sharing problems [2].
I mentioned virtual sharing in the introduction to object memory layout, where several volatile fields occur in the same cache row. The virtual sharing here is the virtual sharing problem between the identity bits of different cards in the card table.
In HotSpot, the card table is implemented through byte arrays. For a 64 byte cache line, if it was used to load part of the card table, it would correspond to 64 cards, or 32KB of memory.
If there are two Java threads doing reference updates in this 32KB memory, it will also cause a cache row in the same part of the memory card table to be written back, invalidated, or synchronized, thus indirectly affecting program performance.
To do this, HotSpot introduces a new parameter -xx :+UseCondCardMark to minimize writing to the card table. The pseudocode is as follows:
if (CARD_TABLE [this address >> 9] ! = DIRTY) CARD_TABLE [this address >> 9] = DIRTY;Copy the codeSummary and Practice
Today I covered some general knowledge of the concrete implementation of garbage collection in the Java Virtual Machine.
The Java virtual machine divides the heap into new generation and old generation, and adopts different garbage collection algorithms for different generations. Among them, the Cenozoic generation is divided into Eden zone and two Survivor zones of the same size, and one Survivor zone is empty.
In a minor-only GC, surviving objects in Eden and non-empty Survivor zones are copied into empty Survivor zones, and surviving objects in Survivor zones are promoted to the old age when they are replicated more than a certain number of times.
Because the Minor GC only collects garbage for the new generation, it needs to consider references from the old generation to the new generation when enumerating GC Roots. To avoid scanning the entire age, the Java VIRTUAL machine introduces a technique called card tables that roughly map out areas of memory where references from age to generation are likely to exist.