实时游戏中的垃圾回收

wiki

版本通知：Lua 5.1 已经实现了增量 GC，因此其中许多观点可能仅具有历史意义。

• 对于像动作游戏这样的应用，Lua 可以极大地受益于增量 GC，因为这些应用本质上是软实时系统。

• 主机游戏通常需要达到 60Hz 的帧率，因为在 30Hz 时，PS2 会显示恼人的隔行扫描。60Hz 意味着每帧最多有 16.7ms 的处理时间。主 CPU 的大部分时间都用于游戏玩法和图形任务，这些任务通常非常耗时。因此，一个可行的脚本语言绝对不能允许进行 GC 的延迟超过 1 到 2ms。通过在引擎创建过程中稍微注意，Lua GC 的偶尔长达约 120ms 的暂停不会被仔细训练的人注意到。另一方面，一个始终运行在 60Hz 并且动画数据是逐帧编码的格斗游戏，完全无法容忍任何帧延迟。所以这取决于具体情况。

• 另一方面，GC 的总摊销开销不是那么关键。只要 GC 的延迟不超过 1 到 2ms，那么它可以在每一帧中花费这么多时间。显然，摊销成本越低越好，但最坏情况下的成本对游戏来说远比这更重要。

• Lua 当前的垃圾收集器使用传统的简单非增量标记-清除算法。当收集周期开始时，它在标记阶段遍历所有可访问的堆对象，然后在清除阶段遍历整个堆。因此，时间成本与堆上的对象数量加上可访问对象的数量成正比。

• 其他收集器类型：复制收集器可能是可行的，但对于我们的目的来说，它可能需要比标记-清除更多的开销。分代 GC 大大改善了平均情况，但并没有阻止最坏情况下的抖动。此外，分代 GC 更复杂。在普通的增量 GC 之后，增量分代 GC 将是一个很好的下一步。

• 增量收集器：使标准的标记-清除算法增量化的难题已经得到了很好的研究。Johnstone 的论文很好地总结了这些方法。Lua 的主要额外成本是 Lua VM 在每次更改指针的值时必须使用“写屏障”。写屏障会查看收集器的内部状态，并在某些条件下标记新的指针或旧的指针。

为了保持低延迟操作，必须允许垃圾收集器定期执行少量工作。对于游戏来说，这意味着游戏循环应该每帧调用一次垃圾收集器。这比文献中通常讨论的粒度要粗糙得多，文献中的讨论通常侧重于多处理器算法。不过，Johnstone 的论文明确解决了单处理器的情况。

写屏障非常简单；根据具体的算法，有几种变化，但最终它只需要大约 5 到 10 行 C 代码和 10 到 20 条指令。

实现注意事项：最好是 Lua 实现 wherever 它向内部（表）指针写入时使用宏（也许它已经这样做了）。然后，一个附加的增量收集器可以将此宏定义为对写屏障的函数调用（或写屏障本身的内联代码）。

• 我之前为一个 Scheme 解释器编写过这样的收集器。那个项目最困难的部分是确保在每次更改指针的每个情况下都有写屏障。这绝对是可行的，而且 Lua API 阻止宿主程序访问 Lua 的内部指针，所以应该不会太难。

• 如果增量收集器在用作常规收集器时表现相似，那将是很好的。也就是说，如果从不调用“执行一些工作”的调用，收集仍然应该自动发生（尽管会以偶尔的长延迟为代价，就像现在一样）。如果增量收集器不会对代码大小、收集时间和内存使用量带来额外的开销，那将尤其好，因为这样就可以在不产生任何代价的情况下，用增量收集器完全替换常规收集器。我猜测可以使用编译时开关来确保没有额外的开销。另外，我怀疑通过一些谨慎的设计，增量收集器可以被编码为避免任何额外的内存使用。代码大小和时间开销将如何还有待观察。我怀疑这两种开销都会很小，但大于零。

• 引用计数收集器，可能与现有的标记-清除结合使用，可以达到最佳效果。引用计数是直接的，在 C++ 游戏引擎中常用（所以游戏开发者倾向于理解它），并且是确定性的。根据 C++ 游戏引擎的经验，它似乎具有足够的增量性。引用计数的主要缺点是它无法收集循环垃圾。为了解决这个问题，可以在方便的时候调用标记-清除。或者，程序员可以注意不要无意中创建循环。弱表可以在这里提供帮助；在 C++ 游戏引擎中，弱指针是解决此问题的常见方法。
  • 引用计数在空间和时间上都有相当大的开销。延迟也是一个缺点——收集单个对象可能会触发大量其他对象的收集。增量垃圾收集器没有这些问题。
  • 引用计数中的这些问题可以通过维护一个需要减少计数的对象工作列表，并增量地处理该列表来解决。您可以经常使用正在释放的对象中的存储来容纳列表。