跳到主要内容

Lua GC 的工作原理！

几乎所有现代编程语言都有自动化内存管理设施，在内存不再使用的时候，能够自动释放它们。有两种方法可以做到这点：

  1. 一是引用计数
  2. 二是垃圾收集

引用计数有循环引用无法将不再使用的对象引用减到零的问题，但这并不是 Lua 选择垃圾收集方法的主要原因。

主要原因是对于动态语言来说，引用计数带来的额外开销太大，尤其是即使一段程序完全不分配内存，你也需要承担这额外开销。

可以类比的动态语言是 Python ，它就是主要基于引用计数来实现自动内存管理的，Python 解释器的运行效率较低，我认为很大程度源于此。

以 Lua 为例，运行时的对象，要么存在于注册表间接引用的 table 中，要么存在于执行栈上（严格说来，注册表引用了主线程，执行栈在线程结构内）。

当一个对象被一个 table 引用时，对于步进式垃圾收集，它需要一个 Barrier 来维持对象的可见性状态，这和递增引用计数的成本一致；不过对象从 table 中移除则不需要额外做递减引用计数的操作；我们可以认为在这个问题上，引用计数带来的成本仅仅是垃圾收集的两倍。

但性能问题出在对象在执行栈上的操作。

不光是函数调用和返回会在栈帧间传递对象的引用，任何一段代码都会在栈上反复移动对象。

对于大部分静态语言，可以通过代码的静态分析，把加减引用的操作添加在必要的位置，然后再通过编译器优化，去掉不必要的操作。

例如 C++ 的 RAII 机制，Objective-C 的 ARC 都是这么干的。但对于 Lua 来说，这就增加了太多的解释器的复杂度；即便生成了类似的代码，开销也无法忽略。

对比 C++ ，它是通过大量 inline 函数才得以消除大部分 RAII 的冗余操作的，这在 Lua 这类动态语言中行不通。

Lua 因为引用计数的额外开销问题选择了垃圾收集器。

垃圾收集器并不负责内存分配释放，内存的底层管理是通过在创建 Lua 虚拟机时从外部注入的分配器完成的。

虚拟机工作时所有产生的对象都被串在一个链表上组成一个集合，而被虚拟机根集间接引用的对象都会被保留，剩下的对象引用无法被根集引用，则会在恰当的时机回收。

虚拟机的根集包括了注册表，以及原生类型的 metatable 。全局表、主线程、标准库的代码等等，都被注册表所引用。

Lua 5.0 以前使用标记扫描算法​

在 Lua 5.0 以前，Lua 使用的是一个非常简单的标记扫描算法。 它从根集开始遍历对象，把能遍历到的对象标记为活对象；然后再遍历通过分配器分配出来的对象全集链表，把没有标记为活对象的其它对象都删除。

Lua 5.0支持 __gc 方法​

但是，Lua 5.0 支持 userdata ，它可以有 __gc 方法，当 userdata 被回收时，会调用这个方法。

所以，一遍标记是不够的，不能简单的把死掉的 userdata 简单剔除，那样就无法正确的调用 __gc 了。

所以标记流程需要分两个阶段做，

第一阶段把包括 userdata 在内的死对象剔除出去，然后在死对象中找回有 __gc 方法的， 对它们再做一次标记复活相关的对象，这样才能保证 userdata 的 __gc 可以正确运行。

执行完 __gc 的 userdata 最终会在下一轮 GC 中释放（如果没有在 __gc 中复活）。

userdata 有一个单向标记， 标记 __gc 方法是否有运行过，这可以保证 userdata 的 __gc只会执行一次， 即使在 __gc 中复活（重新被根集引用），也不会再次分离出来反复运行 finalizer 。

也就是说，运行过 finalizer 的 userdata 就永久变成了一个没有 finalizer 的 userdata 了。

GC性能表现​

GC 的性能表现对整个系统的性能表现影响重大。

Go 语言早期就是因为 GC 问题而饱受诟病。

如果我们把 GC 关闭，那么 CPU 就完全没有额外开销，但是会有极大的内存开销；

如果我们每次分配新对象都运行一遍 GC ，那么就不会有任何额外的内存开销，但是 CPU 开销会完全不可接受

（现在 Lua 保留着一个宏开关，可以不停的运行完整的 GC ，用来测试 GC 实现的正确性）。

Lua 5.0 采用的是一个折中的方案：每当内存分配总量超过上次 GC 后的两倍，就跑一遍新的 GC 流程。

但 Lua 5.0 这种会把整个虚拟机都停下来的 （Stop the World）的简单粗暴的 GC 实现，在实践中的问题非常明显，这导致 Lua 5.0 成为一个分水岭。

5.0 之前的 Lua 多用于内嵌脚本，只充当系统中的底层模块间的粘合剂，而之后解决了大部分的 GC 停顿问题后， 人们才逐渐让 Lua 承担更多工作。

从 Lua 5.1 开始，Lua 实现了一个步进式垃圾收集器。

这个新的垃圾收集器会在虚拟机的正常指令逻辑间交错分布运行，尽量把每步的执行时间减到合理的范围。

一旦 GC 不能一次完成，它就无法把整个虚拟机看成一块静态数据加以分析。

那么怎么办呢？我们就要借助 Mutator 模式 。

只要我们把所有对象的修改都监控起来，从垃圾收集器的角度来看，程序就只是一段段在修改它需要去回收的数据的东西，它不用管程序到底执行了什么，只要知道什么时候修改了什么。

三色标记​

Lua 5.1 采用了一种三色标记的算法。每个对象都有三个状态：

无法被访问到的对象是白色，可访问到，但没有递归扫描完全的对象是灰色，完全扫描过的对象是黑色。

我们可以假定在任何时间点，下列条件始终成立（ Invariants）：

所有被根集引用的对象要么是黑色，要么是灰色的。黑色的对象不可能指向白色的。

那么，白色对象集就是日后会被回收的部分；黑色对象集就是需要保留的部分；灰色对象集是黑色集和白色集的边界。

随着收集器的运作，通过充分遍历灰色对象，就可以把它们转变为黑色对象，从而扩大黑色集。一旦所有灰色对象消失，收集过程也就完成了。

但 mutator 本身会打破上面的规则，比如原有一个黑色对象 t ，和一个白色对象 {}，

当我们运行 t.x = {} （触发了一个 mutator ) 时，就会让这个黑色对象指向一个白色对象。

这时，我们需要在所有这种赋值的地方插入一个 write barrier 检查这种情况，恢复不变条件（invariant) 。

我们有两种方式维持不变条件：

如果参考 Lua 5.1 以后的代码，在 lgc.h 中能找到两个 api 对象这两种操作，luaC_barrier 和 luaC_barrierback 。

什么时候采用什么方法更好是实现的时候凭经验（感觉？）决定的。

比方说，给 table 赋值的时候，就直接把被赋值的黑色 table 变回灰色。

我猜是因为大部分时候被修改的 table 都不会是黑色，同时不需要检查赋值的量的类型和颜色。

如果一个黑色的 table 变回了灰色，就证明在扫描中途被打断（处于某种不常见的临界状态）， 就把它单独放在一个独立的链表 (gray again ）里，留待后面原子处理，避免它在黑和灰之间反复折腾。

对于堆栈，则干脆不让它变黑，这样对栈的操作就不需要 barrier ，提高栈写入的性能。

如果是给对象设置一个 metatable ，例如 setmetatable(obj, mt)这样的，我们可以采用 forward 策略，当 obj 为黑，而 mt 为白色的，将 mt 置灰。

扫描过程一步步的将灰色对象标记为黑色，最后会留下一些反复的灰色对象（曾被标记为黑色，又因为mutator 的 barrier 检查变回了灰色），这些一次性原子的递归遍历，最后再遍历所有的堆栈。

原子步骤中还包括清理需要清理的弱表（弱表中有至少一个白色对象的引用）、分离出需要调用 __gc 的对象。

这些原子步骤是 GC 最可能长时间停顿的时机，但原子步骤是 GC 算法正确性的前提。

所以我们应该注意，尽量减少不必要的 __gc 对象，减少不必要的弱表使用，才能尽可能的减少 GC 停顿。

和 Lua 5.0 的单次全量 GC 一样，__gc 对象对 GC 过程的影响很大。 因为我们需要单独把带 __gc 方法的对象重新扫描一次复活所有相关对象，保证在 __gc 调用时相关对象都还在，和普通地扫描流程不同，这一步必须原子的单步完成，不可拆解。

步进式 GC 如何步进工作的呢？​

和很多不了解算法实现的人的直觉不同，GC 的步进并不和真实的时间相关 （通常多线程 GC 和时间相关，因为 GC 运行过程独立于主逻辑线程之外），它只和虚拟机分配新的内存有关。

也就是说，只要虚拟机不分配更多内存，GC 是不会自动运行的。

GC 依靠新增内存量来决定该做多少工作，它也依靠标记或清理的内存量来决定工作做了多少。 每次做多了，会导致程序更多额外的停顿，做少了，会导致内存回收速度赶不上新增速度。

步进式 GC 比全量 GC 复杂，不能再只用一个量来控制 GC 的工作时间。

对于全量 GC ，我们能调节的是 GC 的发生时机，对于 lua 5.0 ，就是 2 倍上次 GC 后的内存使用量；

在 5.1 以后的版本中，这个 2 倍可以由 LUA_GCSETPAUSE 调节。另外增加了 LUA_GCSETSTEPMUL 来控制 GC 推进的速度，默认是 2 ，也就是新增内存速度的两倍。

lua 用扫描内存的字节数和清理内存的字节数作为衡量工作进度的标准，有在使用的内存需要标记，没在使用的内存需要清理，GC 一个循环大约就需要处理所有已分配的内存数量的总量的工作。

这里 2 是个经验数字，通常可以保证内存清理流程可以跑的比新增要快。

我见过不少人曾在邮件列表中抱怨，自己实现的 userdata 可能能被 Lua 感知到的内存并没有多少（只有一个指针），但实际占了很大的内存（背后的 C/C++ 对象），lua 虚拟机无法正确的驱动 GC 工作。

如果大量分配这种 userdata ，程序使用的内存暴涨，无法及时回收。

其实，正确的方法很简单:

从上面的算法分析可见，步进式 GC 能够减少每次 GC 工作时的停顿时间，但是无法减少 GC 带来的额外开销，

相反，GC 的时间成本（额外的 Barrier ）和空间成本（未能及时回收不再使用的内存）反而较之全量 GC 增加了。

分代 GC​

我们经常可以看到峰值时 Lua 会使用大量超过我们预期的内存总量，是我们估算的程序需要的内存的两倍左右。

这是因为长期运行的程序理论上应该稳定在一定的内存总开销左右，但 Lua 的 GC 周期触发条件却是新的不断分配的对象的内存总量达到过去的两倍。

为了改善这点，Lua 引入了分代 GC。在 Lua 5.2 中，以一个试验特性提供，后来因为没有收到太多正面反馈，又在 Lua 5.3 中移除。

事实上 Lua 5.2 提供的分代 GC 过于简单，的确有设计问题，未能很好地解决问题，在还没有发布的 Lua 5.4 中，分代 GC 被重新设计实现。

分代 GC 之所以可以更及时的回收内存其实是基于这样的假设：

大部分对象被分配出来后很快就回收掉了（C/C++/Go 等静态语言中，特别把只存在于栈上的临时对象单列出来做内存管理正是如此）。 所以，垃圾收集器可以集中精力对付刚刚构造出来的年轻对象。

我们将对象分为青年的和年老的两代，新创建出来的对象一律归为青年代，一旦年轻的对象经历了两轮收集周期而依旧健在，他们就成长为老年对象。

在每个次级收集周期，收集器只对青年代的对象进行遍历清除工作。

这样就避免了每次都遍历大量并不活跃却长期存活的老年对象，又可以及时清理掉大量生命短暂的青年对象。

次级收集周期越密集，单个周期内的青年对象数量就越少，需要做的工作也越少，停顿时间也就缩小了。

可见增加收集周期并不会太多的增加整体工作量，却可以更及时的回收内存；

而相对于之前的算法，增加收集周期则意味了更多的工作（因为每个周期都需要遍历所有的对象）。

对于分代 GC ，我们也有一个始终成立的条件（Invariant）： 老对象不会指向新对象。

但是，分步却变得更困难了。

当变化发生时，无论是 forward 还是 backward 都有问题：

对于 forward ，也就是把新对象变成老的，无疑会制造大量老对象，还需要递归变量，否则就会打破规则。

如果是采用 backward 策略，更很难保持条件成立（对象很难知道谁引用了自己，就无法准确的把老对象变回新的）。

所以，需要引入第三态：

当 back barrier 需要解决老对象指向新对象的问题时，老对象被标记为触碰过，并放入一个特别地集合。

触碰过的对象在次级收集周期中也会参与遍历，但是不会被清理。被触碰的对象如果不再被触碰，那么在两个周期后，它会回到老年集。

为什么强调是两个次级收集周期而不是单个？​

这就要提到 Lua 5.2 所犯的错误。Lua 5.2 的分代 GC 算法中，就只针对单个次级收集周期处理。

任何对象活过当前的收集周期，就会变老。

这样处理固然简单，但有极大的问题。

如果一个对象刚刚被创建出来，次级收集过程就开启了，它很容易就活过这个周期（例如函数尚未返回，刚在堆栈上创建出来的对象就不能回收），这个对象就迅速变老了。

这种本该随即回收的对象未被回收的越多，并不老的老对象增多会进一步增加中间状态的对象数量，次级收集过程能收集的临时对象更少。

但是两个周期的实现算法势必要复杂的多。

只判断在当前周期存活的规则很简单，每次次级收集后，所有没被收集的对象都归为老年代即可，然后就可以把触碰集直接清空。

而两个周期的规则，则需要好几个链表之间倒腾：每个次级收集周期结束， 只有部分新对象变老，另一些还需要维持，触碰对象集的一部分需要继承到下一个周期。 这实现起来真的很复杂，并难以测试。

不过一个正确实现的分代 GC 可以极大地减少传统 GC 额外的内存开销。

有同学在他的基于 skynet 的项目中尝试过切换到 lua 5.4 ，进程在长期运行时，内存使用峰值要少且稳定的多。

分代模式​

分代模式的一个问题是当进入主收集周期，必须做一次完整的标记清除，这和 Lua 5.0 的全量 GC 是一样的，这会带来停顿问题。

只不过分代 GC 模式下，全量 GC 频率可以降得非常低，因为大量临时内存都通过次级收集周期清理掉了，内存并不会增长太快。

当遇到必须消除停顿的环境，我们可以手工精确调整：发现内存持续增长，不要主动触发完整的主收集周期，而是主动切换到步进模式， 然后周期性的调用 gc step （不等内存分配器来触发）在合理的时间内分布报完一个完整的 GC 周期，再切换回分代模式。

我认为 Lua 5.2/5.4 没有默认做这种自动模式切换，是因为默认 GC 无法通过时间驱动来分片工作，而必须依赖内存分配器新增内存驱动导致的。如果我们对 GC 工作原理有清晰地理解，便很容易在程序框架的周期循环内自己来驱动 GC 按需工作。

讨论:​

Cloud:

与 "引用计数"（reference counting）相对的是"追踪"（tracing），译为"扫描标记"也比较贴切。

深究的话，垃圾回收（garbage collection）包括:

  • 内存分配（allocation） :
    • free-list
    • bump pointer
  • 垃圾识别（identification）:
    • 引用计数（reference counting）
    • 追踪（tracing，也称为追踪式回收，即tracing collection）
      • tracing指的是"从根（局部变量和全局变量）出发寻找可达对象，不可达的就是垃圾"的算法
  • 内存回收（reclamation）:
    • sweep-to-free-list（适用于free-list）
    • compaction（适用于bump pointer）
    • evacuation（适用于bump pointer）

而各个GC算法就是上述几种分配、识别、回收算法的组合。

  • 朴素地引用计数（naive RC）是free-list+RC+sweep-to-free-list；
  • 标记清除（mark-sweep）是free-list+tracing+sweep-to-free-list；
  • 标记压缩（mark-compact）是bump-pointer+tracing+compaction；
  • 半空间（semi-space）是bump-pointer+tracing+evacuation。
  • 分代垃圾回收（generational collection）的年轻代可以用一个专用的空间存放然后evacuate，也可以不用单独的空间， 而是用一个标志位（sticky bit）来表示。

还有一些内存分配、释放的方法是基于区块（region）的，在区块内bump pointer，区块本身用free-list管理，兼有两者的优点。

新的一些算法，比如C4、G1、Immix、Shenandoah、ZGC还有Android Oreo的JVM里的GC，都是基于区块的算法。

lichking :RC计数应该能保证实时性和简洁，毕竟循环引用的问题本来就是程序员自己要避免的，何苦留给vm？

cybtron:

这种想法很危险。首先，朴素的RC（即非deferred(推迟)的RC）既不能保证实时性也不简洁。RC在"多数情况下"回收得比较及时，是真的。 但是极端情况下（如释放一个单向链表）就会一下子引入特别大的延迟。

而且RC并不像人们想象的那样容易实现。

RC计数只要错了一个，要么造成对象无法释放而内存泄漏，要么提前释放造成程序崩溃，除非有backup tracing帮你修复计数。

所以必须全面考虑到所有有可能加减引用计数的地方。如果只有VM部分使用自动进行的RC增减操作，还好，因为VM一般只能用专门地读写指令来修改对象和变量； 但是，如果在和外部的C扩展程序的接口上暴露了RC这一实现细节，那么，C程序不得不手动维护RC，极易出错。

更可怕的是，语言设计会是受实现策略影响的。

一个VM一旦在设计之初选用了某种实现策略（如RC），之后设计语言、API的时候很容易把这种策略当成想当然的，然后整个语言的设计就走歪了。

就拿环引用来说。objc和swift禁止环引用，是因为RC本身的弱点，因为他们设计swift语言的时候想沿用objc的runtime，不愿意断舍离，换一个好一点的runtime。

世界上比朴素RC更高效的垃圾回收方法是存在的，而且环引用在那些垃圾回收系统中并不是问题。

为了RC的弱点而把一个没有必要地限制强加给程序员，是没有必要的。

一旦这种对RC的依赖暴露给了用户，以后发现RC的效率是个瓶颈，想换成别的GC算法，就难了。

Pyston项目想要做个高效的Python VM，想改用mark-sweep，但到了0.5版又换回朴素RC了，因为他们想让extension module与CPython兼容，但CPython用了朴素的RC。

可以搜搜，这段故事挺让人痛心的。

Cloud:

python是因为兼容Cpython而使用RC的方式（摘自官网），同时也用了mark&sweep解决循环引用问题。 object C使用RC处理GC应该也是考虑到实时性问题，相比基于java的M&S，我想效果还是很明显的。

cybtron:

关于 RC ， 和 GC 相比，额外的回收代价是每个对象都需要在生命期结束时需要解除和其它对象的引用关系。

如果一大批对象一次全部销毁，那么这些对象间的引用关系解除其实是不必要的。

如果一次销毁一个由很多小对象组成的大对象，那么额外做的这些无用操作就可能造成停顿。

Cloud:

RC对计数器值的增减处理繁重，而且RC的计数器需要额外占用字节。因此有延迟引用计数法(Deferred Reference Counting)算法提出减少计数器的增减处理（没找到原论文出处，但应该可以搜到）。

但是相比mark&sweep必须stop the world的深度遍历，我想RC的实时性相对还是好些。

两种回收策略各有优缺，但没有完美的方式能同时解决所有的问题。

cybtron:

我前面强调的不是计数器值的增减操作，而是解除对象之间的引用关系这件事。我谈论的是总体开销的问题，不是 stop the world 的问题。

我的意思是，采用 RC 时，当一个对象销毁，它需要由引用它的对象来解除关系。实际操作可以是减一次引用。

这个操作无论是马上做，还是延迟做，都是要做的。在对象关系复杂时，这个操作本身是无用的。

比如，如果你的系统有一万个最小粒度的对象，如果在某个任务后，有一千个对象存活。那么理论上，有效工作是分别销毁 9000 个对象占用的资源。

对于 GC ，它做的操作是 mark 了 1000 个对象，然后销毁了 9000 个对象占用的资源；对于 RC，后者是不可省略的，前者是不必要的；但是它还需要对 9000 个退出生命期对象之间的关系进行解除。这些操作未必比 mark 1000 个对象开销更小。

当然，如果这 9000 个对象如果是一个整体，一起销毁的话。RC 的处理是一次把所有的事情做完，所以一样可能造成停顿。（就是前面 @wks 的例子"释放一个单向链表"）

凌:

分代 GC 解决的就是重复 mark 老对象的工作浪费问题。

但我认为 RC 和 GC 的核心区别是：GC 是对对象的正常运行和回收对象不再使用的资源这两件事情的解耦；而 RC 是强耦合的。

在软件复杂程度到达一定后，解耦就是必然的选择。

Colud

分代模式的一个问题是当进入主收集周期，必须做一次完整的标记清除，这和 Lua 5.0 的全量 GC 是一样的，这会带来停顿问题。

只不过分代 GC 模式下，全量 GC 频率可以降得非常低，因为大量临时内存都通过次级收集周期清理掉了，内存并不会增长太快。

当遇到必须消除停顿的环境，我们可以手工精确调整：发现内存持续增长，不要主动触发完整的主收集周期，而是主动切换到步进模式，然后周期性的调用 gc step （不等内存分配器来触发）在合理的时间内分布报完一个完整的 GC 周期，再切换回分代模式。

@Cloud 在合理的时间内分布报完一个完整的 GC 周期，再切换回分代模式。 此处有个问题，lua版本5.4.2，gc step做完完整的收集后，如果此时内存比较大比如还剩3,4个g，此时切换回分代会触发分代的fullgc，这个时候也会造成阻断吧？