标记-清除垃圾收集器有什么问题？

Question

我正在阅读Steve Yegge的“动态语言反击”演讲，在其中他有点批评标记-清除垃圾收集（在该链接的5-10％处，“猪尝试飞行”幻灯片）。它们有什么问题？

- RCIX

---

哦，好的。"Steve Yegge Strikes Back." - user166390

Answer 1

值得注意的是，Steve Yegge的演讲是很久以前的了，他对动态语言及其实现所做的一些概括已经过时。反过来说，暗示分代垃圾回收是解决GC暂停的方法有些“理想化”。特别是考虑到游戏玩家所需的实时特性。

以下是引用语中提到的各种技术的高层次比较（加上“标记和压缩”...这是一种变种的标记和扫除）：

引用计数集合的属性：
PRO-垃圾立即被回收（除了循环）
PRO-垃圾收集暂停更短，如果可以推迟更新“free space”数据结构，则最小
CON-大多数指针写操作都需要调整引用计数
CON-空闲空间永远不会被压缩
CON-因为未压缩空闲空间，必须维护“free space”数据结构，从而增加分配和释放成本。
CON-循环垃圾不会被收集，除非应用程序手动断开循环。
CON-在多线程应用程序中更新引用计数是额外昂贵的。

对于经典的标记和扫描：
PRO-无指针写入开销
PRO-循环数据被收集
PRO-可以避免存储管理并发瓶颈（除了GC）
CON-停止世界的垃圾回收
CON-空闲空间永远不会被压缩
CON-因为未压缩空闲空间，必须维护“free space”数据结构，从而增加分配和释放成本。

经典的标记和扫描有时会被修改，以便扫描阶段通过“滑动”非垃圾对象来压缩空闲空间。这称为“标记-扫描-压缩”。这相当复杂，但有以下优点：
PRO-无指针写入开销
PRO-循环数据被收集

优点 - 存储管理并发瓶颈可以轻松避免（除了 GC）

缺点 - 停止世界的垃圾收集

优点 - 空闲空间被压缩，所以分配便宜

缺点 - 压缩阶段相对昂贵

现代收集器（包括典型的分代收集器）是基于标记和复制的。其思想是，收集器跟踪“源区域”中的对象，将其复制到“目标空间”。完成后，“目标空间”的末尾会有一个连续的自由空间块，可用于分配新对象。“源区域”保留在一侧，以备下次垃圾收集器运行时使用。复制收集的好处在于，与垃圾对象相关联的垃圾收集成本接近于零。

• 缺点 - 指针写入开销（为记录何时将“新生成”的指针写入“旧生成”的对象）
• 优点 - 循环数据收集
• 优点 - 存储管理并发瓶颈可以轻松避免（除了 GC）
• 缺点 - 停止世界的垃圾收集，但这可以通过一些运行时开销来减轻
• 优点 - 使用分代收集器时，通常只对含有大量垃圾的堆部分进行 GC，因此平均 GC 开销较小
• 优点 - 较小的 GC 暂停时间（大多数情况下）
• 优点 - 空闲空间被压缩，所以分配便宜
• 优点 - 相比滑动紧缩程序，压缩更加便宜
• 缺点 - 需要为收集器预留额外的对象空间。

分代收集器是一种具有多个空间（代）的收集器，这些空间以不同的速率进行收集。其基于“弱分代假设”，即大多数对象很快变得不可访问；即它们死得很快。因此，通过垃圾收集包含年轻对象的空间，您可以以相对较低的成本回收相对较大的空间。仍然需要收集较旧的代，但可能不需要那么频繁。

标记-清除垃圾收集器可以是分代的，但相比于复制式垃圾收集器，其效益并不那么显著。

- Stephen C

---

只是出于好奇，您能详细说明一下“标记-复制”是什么吗？ - Preco Plusb

现代收集器（包括典型的代际收集器）基于标记-复制。其思想是，收集器跟踪“from space”中的对象，并将它们复制到“to space”中。完成后，“to space”末尾有一块连续的空闲空间，可用于分配新对象。旧的“from space”被放在一边，以备下次垃圾回收运行时使用。复制收集的好处是与垃圾对象相关的垃圾回收成本接近于零。 - Stephen C

非常抱歉没有理解上下文。我刚看到维基百科页面，有些困惑，因为这里使用的术语与之有所不同。当我第一次看到句子“现代收集器（包括典型的代际收集器）基于标记和复制。”时，我认为mark-and-copy是另一种与mark-sweep-compact不同的策略。 - Preco Plusb

“标记-清除-整理（滑动方法）”和“标记-复制”之间有什么显著的区别？ - Preco Plusb

标记-复制算法和标记-清除-整理算法的最大区别在于前者将对象复制到一个单独的空间，而后者则将其移动到同一空间的不同部分。这对实现有着显著的影响，例如使用旧空间来保存转发指针。在分代情况下，这些空间还可以用于表示不同的代。 - Stephen C

Answer 2

以下是引语的背景：

我认为分代垃圾收集器是最好的答案，因为它可以减少暂停时间，而且说实话，所有新型动态语言的垃圾收集器都很糟糕。它们采用标记-清除或引用计数的方式。

从引语中可以看出，他在谈论相当原始的垃圾收集器，这些垃圾收集器不是分代的。分代垃圾收集器仍然可以采用标记和清除的方式，但大部分时间需要标记的对象较少，这使得它们比“每次都要标记整个世界”的标记和清除算法更快。

如果他的意思是这样的，我同意——但他本可以表达得更加清晰。请注意，这是一次演讲而不是博士论文——当场想出最清晰的表达方式有点棘手 :)

- Jon Skeet

Answer 3

他将其与mark-compact进行对比：

对于这个问题，分代垃圾收集器是我得到的最好答案，因为它减少了暂停时间。坦白地说，所有新的动态语言的垃圾收集器都很糟糕。它们要么是标记-清除，要么是引用计数。

普通的标记和清除垃圾收集器并不好，因为它们存在堆碎片问题。在启用GC的语言中，高分配级别很常见，这通常比在C++中更快成为问题，因为许多对象只是存储在堆栈上。

话虽如此，紧凑型标记和清除垃圾收集器实际上就是将压缩处理加入其中的标记和清除垃圾收集器，因此术语可能需要更改。非压缩式收集器通常称为“保守式”以区分它们。

- Pavel Minaev

---

实际上，我认为“标记和清除”、“标记和压缩”以及“复制和压缩”是三种不同的方法，尽管术语“标记和清除”用于描述.net的GC，尽管在大对象堆之外，我认为它实际上是“复制和压缩”。我会将“复制和压缩”的操作描述为相当于将建筑物中有用的所有东西取出来，然后炸毁它并建造一个新的。在一个通过句柄访问对象的系统中（因此移动对象只需要更新一个指针）... - supercat

将每个堆对象添加其句柄的副本，可以使标记-压缩实现在原地压缩堆。这种方法不适用于“复制和压缩”，但后一种方法的优点是无需花费时间遍历死对象列表；只需丢弃未复制的所有内容即可。 - supercat