实时游戏中的垃圾回收

wiki

版本说明：Lua 5.1 已经有了增量式 GC，所以这些要点中很多可能只有历史意义。

• 对于像动作游戏这样的应用程序，Lua 可以从增量式 GC 中获益良多，这些应用程序基本上是软实时系统。

• 主机游戏通常需要达到 60Hz，因为在 30Hz 时，PS2 会显示令人讨厌的隔行扫描。60Hz 相当于每帧 16.7 毫秒的最大处理时间。主 CPU 的大部分时间都消耗在游戏玩法和图形任务上，这些任务通常非常苛刻。因此，一个可行的脚本语言实际上不能被允许在进行 GC 时 *永远* 出现超过 1 或 2 毫秒的延迟。只要在创建引擎时稍加注意，偶尔的 Lua GC 暂停时间最多可达 120 毫秒，除了经过精心训练的人以外，其他人是不会注意到的。另一方面，一个始终以 60Hz 运行并且在每帧基础上编码动画数据的格斗游戏，根本无法容忍任何长时间的帧。所以这取决于具体情况。

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

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

• 其他收集器类型：复制收集器可能是可行的，但对于我们的目的来说，它可能比标记-清除需要更多的开销。分代 GC 极大地提高了平均情况，但不能防止最坏情况下的卡顿。此外，分代 GC 更复杂。增量式分代 GC 将是普通增量式 GC 之后的一个很好的下一步。

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

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

写屏障非常简单；根据具体算法的不同，存在一些变体，但最终它可能只有 5 到 10 行 C 代码，以及 10 到 20 条指令。

实现说明：如果 Lua 实现能够在写入内部（表）指针时使用宏（也许它已经这样做了），那就太好了。然后，一个增量收集器插件可以将这个宏定义为对写屏障的函数调用（或写屏障本身的内联代码）。

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

• 如果增量收集器在用作常规收集器时表现得像常规收集器一样，那就太好了。也就是说，如果从未调用过“执行一些工作”的调用，收集仍然应该自动发生（尽管会以偶尔出现较长延迟为代价，就像现在一样）。如果增量收集器与常规收集器相比，在代码大小、收集时间和内存使用方面没有额外的开销，那就更好了，因为这样就可以用它完全替换掉库存 Lua 中的常规收集器，而不会有任何损失。我猜想可以使用一个编译时开关来确保没有额外的开销。此外，我怀疑通过一些小心处理，增量收集器可以被编码为避免任何额外的内存使用。代码大小和时间开销将是多少还有待观察。我怀疑这两种开销都将很小，但肯定大于零。

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