HotSpot 使用的 Mark-Compact 算法是什么? [英] What's the Mark-Compact algorithm used by HotSpot?
问题描述
阅读关于 垃圾收集的 Mark-Compact 章节时手册，提出了一系列替代方案，但其中大多数看起来陈旧/理论(例如，2-finger compaction 和 Lisp2 3-pass 方法需要每个对象额外的标题字).
When reading the Mark-Compact chapter on The Garbage Collection Handbook, a sequence of alternatives were presented, but most of them looked old / theoretical (for instance, the 2-finger compaction and the Lisp2 3-pass approach requiring an extra header word per object).
有谁知道 HotSpot 在运行 Mark-Compact 时使用什么算法(我假设是在它的老一代中)?
Is anyone aware of what algorithm does HotSpot uses when running Mark-Compact (in its old-generation, I assume)?
谢谢
推荐答案
免责声明:我不是 GC 专家/作家；下面写的所有内容都会发生变化，其中一些可能过于简单化.请谨慎对待.
Big disclaimer: I am not a GC expert/writer; all the things that are written bellow are subject to changes and some of them might be way too simplistic. Please take this with a grain of salt.
我只会谈论 Shenandoah，因为我认为我理解它；这不是分代 GC.
I will only speak about Shenandoah, as I think I understand it; which is not a generational GC.
这里实际上有两个阶段:Mark和Compact.我要在这里强烈强调两者都是并发，并且确实在您的应用程序运行时发生(带有一些非常短的 STW 事件).
There are two phases here actually: Mark and Compact. I would strongly emphases here that both are concurrent and do happen while your application is running (with some very short STW events).
现在是细节.我在这里解释了一些事情，但是因为这个答案与某种不同的问题有关；我会在这里解释更多.我假设遍历活动对象图对您来说不是什么新闻，毕竟您正在阅读一本关于 GC 的书.正如该答案所解释的，当应用程序完全停止(也称为安全点)时，识别活动对象很容易.没有人改变你脚下的任何东西，地板是僵硬的，你控制着一切.并行收集器执行此操作.
And now to the details. I have explained a bit of things here, but because that answer is related to somehow a different question; I'll explain more here. I assume that traversing the graph of live objects is no news for you, after all you are reading a book about GC. As that answer explains, when the application is fully stopped (also called brought to safe-points), identifying live objects is easy. No one is changing anything under you feet, the floor is rigid and you control everything. Parallel collectors do this.
真正痛苦的方法是同时做事.Shenandoah 采用了一种称为 Snapshot at the beginning 的算法(那本书解释它 AFAIK)，简称为 SATB.基本上这个算法是这样实现的:我将开始同时扫描对象图(从 GC 根)，如果有任何变化在我扫描时，我不会更改堆，但会记录这些更改并在以后处理它们".
The really painful way is to do things concurrent. Shenandoah employs an algorithm called Snapshot at the beginning (that book explains it AFAIK), will call it SATB for short. Basically this algorithm is implemented like this: "I will start to scan concurrently the graph of objects (from GC roots), if anything changes while I scan, I will not alter the heap, but will record these changes and deal with them later".
您需要提问的第一部分是:当我扫描时.这是如何实现的?嗯，在做并发标记之前，有一个STW事件叫做Initial Mark.在该阶段完成的一件事是设置一个标志，表明并发标记已经开始.稍后，在执行代码时，会检查该标志(Shenandoah 因此在解释器中使用了更改).在伪代码中:
The very first part that you need to question is : while I scan. How is that achieved? Well, before doing the concurrent mark, there is a STW event called Initial Mark. One of the things that gets done in that phase is to set a flag that concurrent marking has started. Later, while executing code, that flag is checked (Shenandoah thus employs changes in the interpreter). In pseudo-code:
if(!concurrentMarkingActive) {
// do whatever you were doing and alter the heap
} else {
// shenandoah magic
}
在机器代码中可能如下所示:
In machine code that might look like this:
test %r11, %r11 (test concurrentMarkingActive flag)
jne // concurrent marking is currently active
现在 GC 知道何时发生并发标记.
Now GC knows when concurrent marking is happening.
但是并发标记是如何实现的.当堆本身发生突变(不稳定)时，如何扫描堆?你脚下的地板增加了更多的洞，也将它们移除.
But how is concurrent marking even implemented. How can you scan the heap while the heap itself is mutated (not stable)? The floor under your feet adds more holes and removes them also.
这就是雪兰多魔法".对堆的更改会被拦截".而不是直接坚持.因此，如果 GC 在此时执行并发标记，并且应用程序代码尝试更改堆，则这些更改将记录在每个线程 SATB queues 中(开头的快照).当并发标记结束时，这些队列被排空(通过称为 Final Mark 的 STW 事件)并再次分析那些被排空的更改(请记住在 STW事件现在).
That is the "shenandoah magic". Changes to the heap are "intercepted" and not persisted directly. So if GC performs a concurrent mark at this point in time, and application code tries to mutate the heap, those changes are recorded in each threads SATB queues (snapshot at the beginning). When concurrent mark is over, those queues are drained (via a STW event called Final Mark) and those changes that were drained are analyzed again (remember under a STW event now).
当这个阶段Final Mark结束时，GC 知道什么是活着的，因此什么是隐含的垃圾.
When this phase Final Mark is over GC knows what is alive and thus what is implicitly garbage.
接下来是压缩阶段.Shenandoah 现在应该将活动对象移动到不同的区域(以紧凑的方式)并将当前区域标记为我们可以再次分配的区域.当然，在一个简单的STW 阶段 中，这很容易:移动对象，更新指向它的引用.完毕.当你必须同时进行...
Compact phase is next. Shenandoah is now supposed to move live objects to different regions (in a compact fashion) and mark the current region as one where we can allocate again. Of course, in a simple STW phase, this would be easy : move the object, update references pointing to it. Done. When you have to do it concurrently...
您不能将对象简单地移动到不同的区域并然后一一更新您的引用.想想看，假设这是我们拥有的第一个状态:
You can't take the object and simply move it to a different region and then update your references one by one. Think about it, let's suppose this is the first state we have:
refA, refB
|
---------
| i = 0 |
| j = 0 |
---------
此实例有两个引用:refA 和 refB.我们创建这个对象的副本:
There are two references to this instance: refA and refB. We create a copy of this object:
refA, refB
|
--------- ---------
| i = 0 | | i = 0 |
| j = 0 | | j = 0 |
--------- ---------
我们创建了一个副本，但尚未更新任何参考.我们现在移动一个引用以指向副本:
We created a copy, but have not updated any references yet. We now move a single reference to point to the copy:
refA refB
| |
--------- ---------
| i = 0 | | i = 0 |
| j = 0 | | j = 0 |
--------- ---------
现在有趣的部分是:ThreadA 执行 refA.i = 5，而 ThreadB 执行 refB.j = 6 所以你的状态变成:
And now the interesting part: ThreadA does refA.i = 5, while ThreadB does refB.j = 6 so your state becomes:
refA refB
| |
--------- ---------
| i = 5 | | i = 0 |
| j = 0 | | j = 6 |
--------- ---------
你现在如何合并这些对象?老实说 - 我不知道这是否可能，这也不是 Shenandoah 采取的路线.
How do you merge these objects now? I'll be honest - I have no idea if that would even be possible and neither is this a route that Shenandoah took.
相反，Shenandoah 的解决方案做了一件非常有趣的事情，恕我直言.为每个实例添加一个额外指针，也称为转发指针:
Instead, the solution from Shenandoah does a very interesting thing IMHO. An extra pointer added to each instance, also called forwarding pointer:
refA, refB
|
fwdPointer1
|
---------
| i = 0 |
| j = 0 |
---------
refA 和 refB 指向 fwdPointer1，而 fwdPointer1 指向真正的 Object.现在让我们创建副本:
refA and refB points to fwdPointer1, while fwdPointer1 to the real Object. Let's create the copy now:
refA, refB
|
fwdPointer1 fwdPointer2
| |
--------- ---------
| i = 0 | | i = 0 |
| j = 0 | | j = 0 |
--------- ---------
现在，我们要切换所有引用(refA 和 refB)指向副本.如果您仔细观察，这只需要更改一个指针 - fwdPointer1.让 fwdPointer1 指向 fwdPointer2 就完成了.这意味着与refA 和refB 的两个(在此设置中)相比，只有一个更改.这里更大的胜利是您无需扫描堆并找出指向您的实例的引用.
And now, we want to switch all references (refA and refB) to point to the copy. If you look closely, this requires only a single pointer change - fwdPointer1. Make fwdPointer1 point to fwdPointer2 and you are done. This means one single change as opposed to two (in this set-up) of refA and refB. The bigger win here is that you don't need to scan the heap and find out references that point to your instance.
有没有办法自动更新引用?当然:AtomicReference(至少在java中).这里的思路几乎一样，我们通过CAS(比较和交换)原子地改变fwdPointer1，如下:
Is there a way to atomically update a reference? Of course : AtomicReference (at least in java). The idea here is almost the same, we atomically change the fwdPointer1 via a CAS (compare and swap), as such:
refA, refB
|
fwdPointer1 ---- fwdPointer2
|
--------- ---------
| i = 0 | | i = 0 |
| j = 0 | | j = 0 |
--------- ---------
所以，refA 和 refB 指向 fwdPointer1，它现在指向我们创建的副本.通过单个 CAS 操作，我们同时将所有引用切换到新创建的副本.
So, refA and refB point to fwdPointer1, which now points to the copy we have created. Via a single CAS operation, we have switched concurrently all references to the newly created copy.
然后，GC 可以简单地(同时)更新所有引用 refA 和 refB 以指向 fwdPointer2.最后有这个:
Then, GC can simply (concurrently) update all references refA and refB to point to the fwdPointer2. In the end having this:
refA, refB
|
fwdPointer1 ---- fwdPointer2
|
--------- ---------
| i = 0 | | i = 0 |
| j = 0 | | j = 0 |
--------- ---------
所以，左边的对象现在是垃圾:没有指向它的引用.
So, the Object on the left is now garbage: there are no references pointing to it.
但是，我们需要了解其中的弊端，没有免费的午餐.
But, we need to understand the drawbacks, there is no free lunch.
首先，很明显:
Shenandoah添加了一个机器头，堆中的每个实例(进一步阅读，因为这是错误的；但更容易理解).
First, is obvious :
Shenandoahadds a machine header that each instance in the heap (read further, as this is false; but makes understanding easier).
这些副本中的每一个都会在新区域中生成一个额外的对象，因此在某些时候将至少有两个相同对象的副本(Shenandoah 需要额外的空间才能运行，因此).
Each of these copies will generate an extra object in the new region, thus at some point there will be at least two copies of the same object (extra space required for Shenandoah to function, as such).
当 ThreadA 执行 refA.i = 5(来自上一个示例)时，它如何知道是否应该尝试创建副本，写入那个副本和 CAS 那个 forwarding pointer vs 只是对对象进行写入?请记住，这是同时发生的.与 concurrentMarkingActive 标志相同的解决方案.有一个标志 isEvacuationToADifferentRegionActive(不是实际名称).如果那个标志是 true =>Shenandoah Magic，否则就直接写吧.
When ThreadA does refA.i = 5 (from the previous example), how does it know if it should try to create a copy, write to that copy and CAS that forwarding pointer vs simply do a write to the object? Remember that this happens concurrently. Same solution as with concurrentMarkingActive flag. There is a flag isEvacuationToADifferentRegionActive (not the actual name). If that flag is true => Shenandoah Magic, else simply do the write as it.
如果你真的理解了最后一点，你的自然问题应该是:
If you really understood this last point, your natural question should be :
等一下！这是否意味着Shenandoah 对isEvacuationToADifferentRegionActive 执行if/else 对实例的EACH AND SINGLE 写入- 是原语还是参考?这是否也意味着每次读取都必须通过 forwarding pointer 访问?"
"WAIT A SECOND! Does this mean that Shenandoah does an
if/elseagainstisEvacuationToADifferentRegionActivefor EACH AND SINGLE write to an instance - be that primitive or reference? Also does that mean that EACH read must be accessed via theforwarding pointer?"
答案曾经是 是；但事情发生了变化:通过这个问题(虽然我听起来很多比实际情况更糟).现在他们对整个 Object 使用 Load 屏障，更多细节 这里.他们没有在每次写入时设置障碍(即 if/else 对标志)并通过 forwarding pointer 为每次读取取消引用，而是转移到 load障碍.基本上只有在加载对象时才这样做 if/else .由于写入它意味着首先读取，因此它们保持到空间不变".显然这更简单，更好，更容易优化.万岁！
The answer used to be YES; but things have changed: via this issue (though I make it sound a lot worse than it really is). Now they use Load barriers for the entire Object, more details here. Instead of having a barrier on each write (that if/else against the flag) and a dereference via the forwarding pointer for each read, they moved to a load barrier. Basically do that if/else only when you load the object. Since writing to it implies reading first, they thus preserve "to-space invariant". Apparently this is simpler, better and easier to optimize. Hooray!
还记得转发指针吗?好吧，它已经不存在了.我不了解它的全部荣耀的细节(还)，但它必须做一些可能使用 mark word 和 from space 的事情，因为添加负载屏障，不再使用.很多 更多细节在这里.一旦我了解了它在内部的真正运作方式，就会更新帖子.
Remember that forwarding pointer? Well, it does not exist anymore. I don't understand the details in its entire glory (yet), but it has to do something with the possibility to use the mark word and the from space that, since the addition of load barriers, is not used anymore. A lot more details here. Once I understand how that really works internally, will update the post.
G1 与 Shenandoah 并没有太大的不同，但魔鬼在细节中.例如，G1 中的 Compact 阶段始终是 STW 事件.G1 是 always 世代相传的——不管你是否愿意(Shenandoah 可以有点像那样——那里是控制这个的设置)等.
G1 is not VERY much different than what Shenandoah is, but the devil is in the details. For example Compact phase in G1 is a STW event, always. G1 is always generational - even if you want that or not (Shenandoah can be sort of like that - there is a setting to control this), etc.
这篇关于HotSpot 使用的 Mark-Compact 算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
