algorithm - 堆压缩如何快速工作？

Question

他们说压缩垃圾收集器比传统的内存管理更快，因为它们只需要收集事件对象，并通过在内存中重新排列它们，使所有内容都在一个连续的 block 中，最终不会产生堆碎片。但如何才能快速完成呢？在我看来，这相当于装箱问题，即 NP-hard并且在我们当前的计算知识范围内，无法在合理的时间内在大型数据集上完成。我错过了什么？

Answer 1

压缩意味着移动 RAM 中的对象，以便删除一些对象(死对象，GC 应该回收)并且所有剩余的对象在 RAM 中变得连续。

大多数压缩 GC 通过在从操作系统获得的单个 连续区域中分配对象来工作。然后压缩就像移除死对象，然后将所有剩余的活对象“向左”推，挤出洞。如果 GC 通过压缩工作，那么分配只是将“已分配区域结束”指针向上移动的问题。综合而言，在分配区内，有一个指针，使得空闲区由该指针之后的字节组成。要为对象分配空间，只需将指针向上移动新的对象大小即可。偶尔，GC 会决定运行时间，检测死对象，将空洞挤出，从而降低分配指针。

压缩 GC 的性能提升来自几个方面:

• 对于分配，无需寻找合适的“洞”:通过构建，空闲空间始终是一个单一的大区域，只需将指针向上移动即可。
• 没有碎片:压缩将所有事件对象移动到一起，但这可以看作是将所有孔移动到一个大的自由空间中。
• 局部性得到改善。通过将事件对象移动到相邻区域，可以改进缓存内存的行为。特别是，压缩算法倾向于将对象保持在各自的分配顺序(对象滑动但不交换)，据报道这对于大多数应用程序来说在启发式上是好的。

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

压缩算法的算法难点在于更新所有指针，以便它们指向新的对象位置。通过严格类型化，.NET 虚拟机可以明确地决定 RAM 中的每个单词是否是一个指针，但是在不使用太多额外 RAM 的情况下有效地更新所有指针可能会很棘手。 H.B.M. Jonkers 在“A Fast Garbage Compaction Algorithm”(信息处理快报，第 9 卷，第 1 期，1979 年，第 26-30 页)中描述了一个非常聪明的算法。我无法在 Vast Internet 上找到该论文的副本，但该算法在 "Garbage Collection" 中有所描述。 Jones 和 Lins 的书(第 5.6 节)。我热烈地向任何有兴趣了解垃圾收集器的人推荐这本书。 Jonkers 的算法需要对事件对象进行两次线性传递，结果很容易实现(几十行代码，仅此而已；最困难的部分是理解其工作原理)。

额外的复杂性来自分代收集器，它们在大多数情况下试图让大部分对象保持不变，优先只处理年轻的对象。在这里，这意味着只压缩堆的末端；很少应用完全压实。这里的要点是，完全压缩虽然是线性的，但仍然会引起明显的停顿。分代 GC 试图让这种停顿变得更少。同样，琼斯和林斯的书是必读的。