堆压缩如何快速工作?

压缩意味着在ram中移动对象,以便移除一些对象(死掉的对象,gc应该回收),并且所有剩余的对象在ram中成为连续的。

大多数压缩GC通过在 单一的 ,从操作系统获取的相邻区域。然后,压缩就像移除死物体,然后将所有剩余的活物体“推到左边”,挤压出孔洞。如果gc通过压缩工作,那么分配只是向上移动“已分配区域结束”指针的问题。综合而言,在分配区域内,存在一个指针,使得空闲区域由该指针之后的字节组成。要为对象分配空间,指针只需按新的对象大小向上移动。有时,gc决定是时候运行了,检测死对象,挤压出漏洞,从而降低分配指针。

压缩GC的性能提高来自以下几个方面:

• 对于分配,不需要找到一个合适的“洞”:通过构造,自由空间在任何时候都是一个大面积的区域,只要向上移动一个指针就足够了。
• 没有碎片:压缩将所有活动对象移动到一起,但这可以看作是移动所有 洞 一起进入一个大的自由空间。
• 局部性得到改善。通过将活动对象移动到相邻区域,可以改善与缓存相关的行为。特别是,压缩算法倾向于将对象保持在它们各自的分配顺序中(对象是滑动的,但不是交换的),这在大多数应用中都是启发式的。

如果 操作系统拒绝给出一个分配区域,而是产生几个块,然后事情变得有点复杂,并可能开始看起来像装箱问题,因为压缩GC然后必须决定每个活动对象进入哪个块。然而,装箱的复杂性在于在一般情况下找到“完美”匹配;对于内存分配器来说,近似的解决方案已经足够好了。

压缩算法的算法难点在于更新所有指针,使它们指向新的对象位置。通过严格的输入,.net虚拟机可以毫不含糊地决定ram中的每个单词是否是指针,但是在不使用太多额外ram的情况下高效地更新所有指针可能会很棘手。h.b.m.jonkers在《快速垃圾压缩算法》(information processing letters,第9卷,第1期,1979年,第26-30页)中描述了一种非常智能的算法。我在浩瀚的互联网上找不到那篇论文的副本,但是算法在 "Garbage Collection" 琼斯和林斯的书(第5.6节)。我热情地向任何有兴趣了解垃圾收集员的人推荐这本书。jonkers的算法需要对活动对象进行两次线性传递,结果很容易实现(不再需要几十行代码;最困难的部分是理解其工作原理)。

额外的复杂性来自 世代收藏家 在大多数情况下,他们试图让大多数对象保持原样,只优先处理年轻对象。这里,这意味着只压缩堆的末端;很少应用完全压缩。这里的要点是,完全压实虽然是线性的,但仍然会引起明显的停顿。代际gc试图减少这种停顿。再说一遍,琼斯和林斯的书是必读的。