本文只是半成品，还未最终完稿，请谨慎阅读。

这是我研究 lua gc 算法的一篇笔记，虽然网上可以找到很多分析文章，但写下自己的理解是很有必要的。本文涉及的 lua 版本从 5.0 到 5.4，主要内容包括：设计与实现、使用上的注意事项、一些问题的解决办法。

很多时候，想查证 lua 的一些细节，最快的方式不是在网上搜索别人的文章，而是自己去看它的源码，它的源码足够的简短小巧，阅读起来不费劲。当然，一开始总是有点难的，但积累一些经验之后就很通畅了。

lua 所有版本的源码都可以在这里下载：https://lua.org/ftp/ 。

1. 设计与实现

lua gc 一直使用标记清除算法（mark&sweep），随着版本的迭代，对这一算法逐步进行优化。各版本的情况大致如下：

版本	算法	备注
5.0	基本 mark&sweep	双色标记
5.1	增量式 mark&sweep	三色标记
5.2	增量式 mark&sweep + 分代式	引入分代式，实验性质的
5.3	增量式 mark&sweep	去掉分代式
5.4	增量式 mark&sweep + 分代式	再次引入分代式，比较成熟了

lua 5.4 的分代式 gc 表现不错，在 lua 可执行程序里，已经被设置为默认 gc 算法，而在 liblua.a 里默认 gc 算法还是增量式的。也就是说在命令行中直接运行的 lua 程序，用的是分代式 gc，把 lua 作为库链接到你的程序中，用的是增量式 gc。

以下将讨论的，就是标记清除算法的发展，从原始的 gc，到增量式 gc，再到分代式 gc。可以看到，实际上都是在对标记清除算法进行某种程度的优化，而这些优化并不是非黑即白的，都是某些妥协的结果。

为了避免原始 gc 的 stop the world 缺点，发展出增量式 gc，而增量式 gc 肯定比 stop the world 要复杂，回收效率也更低。

为了避免反复扫描所有的对象，发展出分代式 gc，但也有缺点，它分为部分执行还是全部执行两种模式，虽然比较少进入全部执行，但无论哪种模式，都会 stop the world。

所以，得根据具体项目的特点来选择 gc 算法。

1.1 原始的 gc

原始的 gc 只能在 lua 5.0 的代码中找到了。也是标记清除式的，但整个 gc 过程是原子的，中间不可被打断。

算法很简单，就是从根集开始扫描，找出所有被根集直接或间接引用到的对象，被引用的对象标为黑色，没被引用的对象标为白色，标记完成后，清除所有白色对象。由于只有黑白两种颜色，所以也称为双色标记。

所谓根集，就是 lua 虚拟机使用的一些基础对象，这些对象从虚拟机诞生到销毁都始终存活着，虚拟机运行过程中产生的其他对象都直接或间接被这些基础对象引用到。根集包含这些对象：registry(global table, main thread, package.loaded), shared metatables。

实现上，lua 用一个链表来保存所有这些 “可回收对象”。扫描结束的时候，只需要遍历这个链表，回收所有标为白色的对象。

这个算法的优点是：实现简单；缺点是：中间不可打断，会 stop the world，如果 gc 过久，会导致业务逻辑出现比较长的卡顿。

1.2 代码入口

接入来分别讲增量式 gc 和分代式 gc，以 lua 5.4.6 的源码为基础进行分析。

先大致讲一下代码的入口，gc 是条件触发式的，在源码的多个内存使用的地方调用一个叫 luaC_checkGC 的函数，此函数根据当前的一运行状态，决定是否进入 gc。

#define luaC_checkGC(L)		luaC_condGC(L,(void)0,(void)0)

整体调用链路：

luaC_checkGC 
-> luaC_condGC
-> luaC_step
-> genstep 或者 incstep

进入增量式 gc：

incstep
-> singlestep

进入分代式 gc：

genstep
-> fullgen（全量执行） 或者 youngcollection （部分执行）

1.2 增量式 gc

增量式 gc 也是标记清除式的。

下文以 lua 5.4.6 的源码为例进行分析。

为了解决 stop the world 问题，从 lua 5.1 开始就引入了增量 gc。它的核心目标就是避免一轮 gc 的时候 stop the world，核心做法就是把一轮 gc 拆成多个步骤。运行的时候是这样交替执行的：

gc-开始 | gc-step | 正常逻辑 | ... | gc-step | 正常逻辑 |...| gc-结束 |  

1.2.1 增量式 gc 的触发条件

lua 的 gc 不是靠时间驱动的，是靠事件驱动的，当内存分配量达到设定的阈值时，就触发 gc。

lua 使用债务来描述内存占用，申请内存是增加债务，释放内存是减少债务，当债务达到某个值时，就会触发 gc。道理是很简单的，但 lua 实现这套债务机制的代码有点不好理解，准确的说是变量的命名很糟糕，容易造成误解，我是费了一些劲才理解了其中的机制。

跟触发条件相关的三个变量分别是 global_State 结构里面的：totalbytes, GCdebt, GCestimate 。

检查是否需要 gc 的函数是：luaC_checkGC，实际上它是个宏，真正调用的函数是 luaC_condGC，这个函数判断到 GCdebt 的值大于 0，就会触发 gc。lua 在多个内存申请的地方会调用 luaC_checkGC 来判断是否需要 gc 。

现在的关键就是搞清楚 GCdebt 这个变量是怎么工作的。

首先不要把 GCdebt 误解成一轮 gc 后的内存申请增量，也不要把 totalbytes 误解成当前内存申请总量，这就是我说它们命名糟糕的原因，太容易让人误解了。

应该把 GCdebt 和 totalbytes 当成与内存使用相关的指标值。有时候为了立即触发 GC，会直接修改 GCdebt 的值，比如调用 collectgarbage("step") 时。

而 GCestimate 是一个评估值，代表非垃圾内存总量 ( an estimate of the non-garbage memory in use )。

实际上，当前使用内存 = totalbytes + GCdebt ，任何时候都要维持这一条式子成立。也就是说如果当前使用内存不变，而 GCdebt 的值改变了，那 totalbytes 的值也要相应改变，来保持等式的成立。

三个变量的变化时机：

虚拟机初始时： totalbytes = 当前使用内存，GCdebt = 0，GCestimate = 0。
申请内存时：GCdebt = GCdebt + 内存申请量
释放内存时：GCdebt = GCdebt - 内存释放量
当 GCdebt > 0 时：触发 gc，调用一次或多次 singlestep，每次 singlestep 都会做一定的工作量（work），工作量会改变 GCdebt 的值：GCdebt = GCdebt - work ，直到把 GCdebt 的值降低到 -stepsize，或者完成了一轮 gc。
标记完成时：GCestimate = 当前使用内存
清除完成时：GCestimate = GCestimate - 清除掉的垃圾量
一轮 gc 完成时：
GCestimate = 当前非垃圾内存（约等于当前使用内存）
GCdebt = 当前使用内存 - GCestimate * pause / 100
totalbytes = 当前使用内存 - GCdebt

stepsize 表示一次增量 gc 需要做的工作量，在 lua 5.3 是一个固定值，在 lua 5.4 是一个允许用户改变的值。

pause 参数是一个以百分比为单位的变量，用于控制两轮 gc 的间隔，默认值是 200。

总结一下：

完成一轮 gc cycle 后，GCdebt 被设置为 (GCestimate - GCestimate * pause 参数 / 100) 。假设 pause 参数仍为默认值 200，则当内存申请总量变为 gc 结束时的两倍时，才会触发下一轮 gc。
一轮 gc 的触发，是一轮结束后，把 GCDebt 设为一个比较大的负值，待它累加到正值之后触发的。
进入一轮 gc 后，每一步 gc 的触发，是每个 step 推进 gc 工作，把 GCDebt 降回一个小的负值（ -stepsize ），待内存使用又导致 GCDebt 大于 0 时，触发下一步 gc step，如此往复，直到完成整一轮 gc。

1.2.2 增量式 gc 的 invariant（始终成立的条件）

invariant 也有人翻译成 “一致性原则”、“不变性原则”，都是同一回事。

在整个 gc 标记阶段，增量式 gc 必须需要保证一个始终成立的条件：黑色对象不能引用白色对象。

否则，由于标记阶段黑色对象不会被再次遍历，它引用的白色对象就可能不会被扫描到，导致被错误清除。

lua 使用写屏障 (write barrier) 来保证这个 invariant，下面具体描述一下。

标记阶段的 GCSpropagate 步骤是分步的，会与正常逻辑交替执行，那么会出现这样的情况：

被标为灰色或黑色的对象不再被引用了；
被标为黑色的对象引用了白色对象；

第 1 种情况可以不处理，顶多导致本轮漏回收一些内存，我们可以在下一轮再回收。第 2 种情况必须处理，否则新的对象会由于没有标记到而被错误的回收。

lua 使用写屏障 (write barrier) 来解决第 2 种情况。写屏障有两种做法，一种被称为 barrier forward，另一种是 barrier backward。两者的区别是，forward 是把新的白色对象 mark 为灰色并加入 gray 链表；而 backward 是把黑色对象改回灰色并加入 grayagain 列表，grayagain 链表会在标记阶段的末尾被一次性扫描。

lua 同时使用了这两种做法，如果黑色对象是 table 或 userdata，则使用 barrier backward，否则使用 barrier forward。

barrier backward 的做法，可以避免频繁的新增引用导致出现大量的灰色对象，以至于超过了每步可以处理的灰色对象个数，导致 propagate 阶段永远处理不完。

1.2.3 工作过程

各个 gc 步骤

gc 总体上可以分成4个阶段，分别是：开始、标记、清除、结束，每个阶段会有1个或多个步骤(step)。

几乎每个版本都对增量式 gc 算法有所改进，每次改进可能会细化 gc 步骤，lua 5.4.6 的 gc 步骤定义如下（取自 lgc.h ）：

#define GCSpropagate	0
#define GCSenteratomic	1
#define GCSatomic	2
#define GCSswpallgc	3
#define GCSswpfinobj	4
#define GCSswptobefnz	5
#define GCSswpend	6
#define GCScallfin	7
#define GCSpause	8

下面表格列的是 lua 5.4 的各个 gc step 做的事情，其中 GCSenteratomic 是一个过渡性的 step，此处不必列出。

阶段	步骤	是否分步	作用
开始	GCSpause	分步	标记根集
标记	GCSpropagate	分步	每次从 g->gray 链表取一个对象，置为黑色，然后 mark 它引用的对象
标记	GCSatomic	不分步	1、再次标记根集；2、标记完 gray 链表；3、标记完 grayagain 链表；4、处理弱表；5、分离出需要析构 (finalize) 的对象到 tobefnz 链表，并做标记；6、翻转current white
清除	GCSswpallgc	分步	每次从 g->allgc 链表取若干个对象，如果是 other-white 则清除掉，否则，重新标记为 current white
清除	GCSswpfinobj	分步	每次从 g->finobj 链表取若干个对象，标记为 current white
清除	GCSswptobefnz	分步	每次从 g->tobefnz 链表取若干个对象，标记为 current white
清除	GCSswpend	不分步	尝试收缩短字符串 hash 表的 size，确保利用率高于 1/4
结束	GCScallfin	分步	每次从 g->tobefnz 链表中取若干对象，调用其析构函数（finalize），析构过的对象会移动到 g->allgc 链表

GCSatomic 阶段

为何需要重新对根集进行扫描？

根集的这几个对象，是被 global_State 引用的，而 global_State 不参与 gc，所以根集不受写屏障保护。在增量的过程中，它们也可能被替换或修改，所以需要重新对它们扫描一次。

GCSswpfinobj 和 GCSswptobefnz 阶段

参考：

这两个阶段虽然都属于 sweep，但实际上并不会清除对象，只会把对象都重新标记为 current white，因为这两个链表上的对象都有 FINALIZEDBIT 标记，sweeplist 用 isdeadm 测试这些 obj 时返回的都肯定是 false，即不是 dead mark，所以只会执行标记 current white 的逻辑。

即下面 sweeplist 代码中的 else 部分的逻辑:

static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
  global_State *g = G(L);
  int ow = otherwhite(g);
  int white = luaC_white(g);  /* current white */
  while (*p != NULL && count-- > 0) {
    GCObject *curr = *p;
    int marked = curr->marked;
    if (isdeadm(ow, marked)) {  /* is 'curr' dead? */
      *p = curr->next;  /* remove 'curr' from list */
      freeobj(L, curr);  /* erase 'curr' */
    }
    else {  /* change mark to 'white' */
      curr->marked = cast_byte((marked & maskcolors) | white);
      p = &curr->next;  /* go to next element */
    }
  }
  return (*p == NULL) ? NULL : p;
}

根集

在 lua 5.4.6 中，处理根集的逻辑是：

static void restartcollection (global_State *g) {
  cleargraylists(g);
  markobject(g, g->mainthread);
  markvalue(g, &g->l_registry);
  markmt(g);
  markbeingfnz(g);  /* mark any finalizing object left from previous cycle */
}

所以根集包括：mainthread（主线程）、l_registry（注册表）、mt（基本类型的 metatable）、tobefnz（待析构对象链表）。

l_registry 是一个 Table，里面维持了一些对象的索引，在初始的时候包括：mainthread（LUA_RIDX_MAINTHREAD），global table（LUA_RIDX_GLOBALS）。global table 即对应 _G。

标记算法

标记即染色，使用 3 种颜色来标记对象，分别是白、灰、黑，所以增量式标记清除也常被称为三色标记清除。

如果对象会引用其他对象，则置为灰色，并加入 gray 链表；否则置为黑色。

但实际上，白里面还分了 current-white 和 other-white，current-white 表示本轮 gc 标记完成之后新建的对象，other-white 表示之前的，在清除阶段，只会清除掉 other-white 对象。

1.3 分代式 gc

分代 gc 可以认为是标记清除算法的一种优化策略。它的核心目标就是减少每轮 gc 需要扫描的对象个数，有些对象是长期存在的，没必要频繁去扫描。基本思路就是根据存活时间对这些对象分类，对于 “年老” 的对象，减少扫描次数，对于 “年轻” 的对象，多扫描。

lua 5.2 开始，就引入了分代式 gc，当时只是试验性质的，默认还是增量式。但是由于实现上不太成熟，实际运行效果不佳，在 lua 5.3 被删掉了。到了 lua 5.4，它又被重新实现出来。

1.3.1 分代式 gc 的触发条件

TODO

1.3.2 分代式 gc 的 invariant (始终成立的条件)

跟增量式 gc 类似，分代式 gc 也必须保证一个始终成立的条件：老对象不会指向新对象。

Lua GC 的工作原理:

对于分代 GC ，我们也有一个始终成立的条件（Invariant）：老对象不会指向新对象。但是，分步却变得更困难了。当变化发生时，无论是 forward 还是 backward 都有问题：对于 forward ，也就是把新对象变成老的，无疑会制造大量老对象，还需要递归变量，否则就会打破规则。如果是采用 backward 策略，更很难保持条件成立（对象很难知道谁引用了自己，就无法准确的把老对象变回新的）。

1.3.3 工作过程

理论上分代式 gc 可以根据对象的存活时间分成很多代，不过 lua 这里只简单的分了两代：年轻一代和老一代。

数据结构上，可 gc 的 object 会存在于 4 个链表中：

allgc 链表，存储了所有无析构器的对象，即没有 __gc 元方法的 GCObject；
finobj 链表，存储了所有带析构器的对象，即拥有 __gc 元方法的 GCObject；
tobefnz 链表，在本轮 GC 中将要被清除的带 __gc 元方法的对象，这些对象是从 finobj 链表转移过来的；
fixedgc 链表，标记为不需要 gc 的对象会从 allgc 链表中移出，并移入 fixedgc 链表，比如一些元方法名 __add 之类的字符串，具体可搜索调用到 luaC_fix 的地方；

部分执行

为什么是从 old1 开始？那 old0 呢？

old 现在指向的都是些什么对象？都只指向一些 old 对象吗？

全部执行

1.3.4 参考阅读

这几篇文章比较详细地介绍了 lua 5.4 的分代 gc 算法，写得挺不错的，可以参考一下：

2. 增量式与分代式对比

增量式有哪些不足之处？可以归结为三点：

每个完整周期的总任务量都很大，对所有对象做了全量扫描；
及时性不足，对于新旧对象都一视同仁的处理；
性能消耗不会随着程序运行稳定而下降，即使长期存活的对象也是一再的被扫描，gc 可以说没有消停的时候；

而分代式可以说是把上面的 3 个缺点都克服了，是一种更理想的想法。

但分代式也有它的缺点，它分为部分执行和全部执行两种模式，这两种模式都不是增量式的，部分执行不需要处理所有对象，开销较小，全部执行需要处理所有对象，开销较大。虽然分代式不会过多的进入全部执行模式，但一旦进入，则相当于一次 stop the world 式的 gc，会出现比较大的卡顿。

3. 若干问题探究

3.1 一轮增量式 gc 还未完成时切换 gc 模式为分代式

TODO

3.2 增量式 gc 如何减少停顿

gc 过程中原子性（即不分步）的步骤最容易导致卡顿，从上面表格中可以看得出，标记阶段的 GCSatomic 步骤最容易卡顿，其中有些操作是无法避免的，而有些操作是我们能够努力减少其消耗的，比如减少不必要的弱表，减少不必要的带 __gc 的对象。

3.3 增量式 gc 的参数

lua 5.1~5.4 都是通过 collectgarbage 函数修改 gc 参数的，只不过 5.4 开始，用法有些变化。另外，5.4 增加了一个新的参数：stepsize。

参数	作用	版本	设置方法
pause	一轮gc结束后隔多久启动下轮gc	5.1~5.4	collectgarbage(“setpause”, Val)
stepmul	gc step 工作量的倍数	5.1~5.4	collectgarbage(“setstepmul”, Val)
stepsize	gc step	5.4	collectgarbage(“incremental”, 0, 0, Val)

lua 5.4 虽然仍支持使用 “setpause” / “setstepmul”，但文档中已经移除了，取而代之的是 “incremental”，用于统一的设置 pause / stepmul / stepsize 这几个参数：

pause 参数推荐这么设置： collectgarbage("incremental", Val, 0, 0)
stepmul 参数推荐这么设置：collectgarbage("incremental", 0, Val, 0)

需要注意的是，当这样调用时: collectgarbage("incremental", ...)，会把 gc 模式设置为增量式的。

这些参数的意义，官方文档 ( https://lua.org/manual/5.4/manual.html#2.5.1 ) 解释得更清楚，如下：

The garbage-collector pause controls how long the collector waits before starting a new cycle. The collector starts a new cycle when the use of memory hits n% of the use after the previous collection. Larger values make the collector less aggressive. Values equal to or less than 100 mean the collector will not wait to start a new cycle. A value of 200 means that the collector waits for the total memory in use to double before starting a new cycle. The default value is 200; the maximum value is 1000.

The garbage-collector step multiplier controls the speed of the collector relative to memory allocation, that is, how many elements it marks or sweeps for each kilobyte of memory allocated. Larger values make the collector more aggressive but also increase the size of each incremental step. You should not use values less than 100, because they make the collector too slow and can result in the collector never finishing a cycle. The default value is 100; the maximum value is 1000.

The garbage-collector step size controls the size of each incremental step, specifically how many bytes the interpreter allocates before performing a step. This parameter is logarithmic: A value of n means the interpreter will allocate 2n bytes between steps and perform equivalent work during the step. A large value (e.g., 60) makes the collector a stop-the-world (non-incremental) collector. The default value is 13, which means steps of approximately 8 Kbytes.

3.4 分代式 gc 的参数

参数	作用	版本	设置方法
minor multiplier	控制短gc的频率	5.4	collectgarbage(“generational”, Val, 0)
major multiplier	控制长gc的频率	5.4	collectgarbage(“generational”, 0, Val)

这些参数的意义，官方文档 ( https://lua.org/manual/5.4/manual.html#2.5.2 ) 解释得更清楚，如下：

In generational mode, the collector does frequent minor collections, which traverses only objects recently created. If after a minor collection the use of memory is still above a limit, the collector does a stop-the-world major collection, which traverses all objects. The generational mode uses two parameters: the minor multiplier and the the major multiplier.

The minor multiplier controls the frequency of minor collections. For a minor multiplier x, a new minor collection will be done when memory grows x% larger than the memory in use after the previous major collection. For instance, for a multiplier of 20, the collector will do a minor collection when the use of memory gets 20% larger than the use after the previous major collection. The default value is 20; the maximum value is 200.

The major multiplier controls the frequency of major collections. For a major multiplier x, a new major collection will be done when memory grows x% larger than the memory in use after the previous major collection. For instance, for a multiplier of 100, the collector will do a major collection when the use of memory gets larger than twice the use after the previous collection. The default value is 100; the maximum value is 1000.

3.5 弱表

弱表是 lua 的一种特性，为了支持这种特性，gc 算法也需要有相应的处理。同时，这种特性也带来了 gc 算法上的一些麻烦。

弱表的问题在于无法像 “强表” 那样简单的对 key 或 value 进行标记。弱表分3种，弱键+弱值，弱键+强值、强键+弱值，用英文表示，分别为 kv_weaktable, key_weaktable, value_weaktable。

这三种弱表要如何处理标记，需要分情况讨论。

首先是 kv_weaktable，最简单，标记阶段不需要标记 key 或 value，等标记阶段结束后，遍历看看哪些 key 或 value 是没被标记的，将它们从表中移除。

其次是 value_weaktable，也较简单，标记阶段只标记所有 key，不标记任何 value，等标记阶段结束后，遍历看看哪些 value 是没被标记过的，把这些 value 及对应的 key 从表中移除。

最后是 key_weaktable，这个很复杂。

蜉蝣表 (ephemeron table，也有被译为瞬表) 的作用是解决弱表循环引用，拥有弱 key 和强 value 的表就是蜉蝣表。

3.6 弱表的使用场景

弱表有特定的作用，但其实作用不算特别大，而且由于它的 gc 标记很多工作量是放在原子阶段(atomic)做的，所以如果过度使用弱表，会导致原子阶段卡顿。

3.7 析构

“带有自动内存管理的编程一般都会在客户程序和垃圾回收器提供一个接口，这个接口一般都会允许客户程序与垃圾回收器进行交互，典型的代表是 finalizer (清理器)和 weak reference(弱引用)”。 [2]

可见，析构是垃圾回收器与客户程序进行交互的一种接口。

通过给一个对象设置一个包含 __gc 元方法的元表，可以把这个对象标为为需要进行析构处理的对象。

这里有一个需要注意的点，即设置元表 (setmetatable) 时，元表必须已经包含 __gc 方法，如果是设置元表之后，再给元表加上 __gc 方法，则是无效的，因为 lua vm 是在 setmetatable 时做 __gc 方法检测的。

以下展示的就是无效设置[1]，这种情况是不会有输出的：

o = {x = "hi"}
mt = {}
setmetatable(o, mt)
mt.__gc = function(o) print(o.x) end
o = nil
collectgarbage()  -- 不会有输出的

如果一开始无法确定 __gc 函数，可以先使用一个值占位，后续再设置 __gc 函数[1]，比如这样：

o = {x = "hi"}
mt = {__gc = true}
setmetatable(o, mt)
mt.__gc = function(o) print(o.x) end
o = nil
collectgarbage()  -- 会输出 hi

3.8 值对象与引用对象

lua 5.1 ~ 5.4，定义的类型有9种：

#define LUA_TNIL		0
#define LUA_TBOOLEAN		1
#define LUA_TLIGHTUSERDATA	2
#define LUA_TNUMBER		3
#define LUA_TSTRING		4
#define LUA_TTABLE		5
#define LUA_TFUNCTION		6
#define LUA_TUSERDATA		7
#define LUA_TTHREAD		8

其中 LUA_TSTRING 之前的（LUA_TNIL、LUA_TBOOLEAN、LUA_TLIGHTUSERDATA、LUA_TNUMBER）都属于值类型，LUA_TSTRING 以及之后的都属于引用类型。

值类型不需要被垃圾回收，作为参数传递的时候 “按值传递”，即函数中不会修改实参的值。引用类型则相反，需要垃圾回收，参数传递时是 “按引用传递”。

3.9 短字符的 gc

lua 5.1 的时候，所有的字符串不论大小都放在一个 hash table 里，即 global_State 的 strt 字段，创建字符串时，先从 hash table 查找，找不到再新建。

lua 5.2 开始，做了一点限制，只有长度（strlen）小于等于 40 的字符串才会放到 hash table 里。

在同个虚拟机里相同短字符串肯定是同一个对象，直接比较地址就行了，所以短字符的比较效率特别高。

3.10 基于寄存器的虚拟机

lua 的寄存器和栈是两个让人容易误解的称呼，与我们熟知的寄存器和栈有些差别。lua 虚拟机会维护一个数据栈，这个数据栈是一个 TValue 类型的数组，而寄存器实际上就是这个数组的索引。

lua 虚拟机里面还有另一个栈，是一个 CallInfo 类型的数组。这个跟我们熟知的栈就比较类似了，CallInfo 记录的是函数调用信息，这个栈就是按调用层次顺序存储调用信息的。

说回正题，我们知道目前 lua 是基于寄存器的虚拟机 (register-based vm)，与之相对的是基于栈的虚拟机(stack-based vm)。这两者有何区别？通常我们会看到这样的一个例子，对于这样一个运算 c = a + b，

如果是 stack-based vm，可能生成这样的指令：

pushstack a 
pushstack b
call add

如果是 register-based vm，可能生成这样的指令：

load a to r0
load b to r1
call add r0 r1 r2

区别在哪？stack-based vm 的 add 指令，并不需要关心操作数在哪里，设计上已经约定操作数就是 “栈顶” 和 “栈顶-1” 这两个位置。而 register-based vm 的 add 指令，需要指定操作数的位置，add r0 r1 r2 就表示要把 r0 位置跟 r1 位置的数相加并存到 r2 位置。

通常的说法是 register-based vm 的效率更高。是这样吗？从上面的例子看，实现加法都使用了三条指令，并且 stack-based 看起来还更简单。

寄存器的本意就是高速的缓存，这里也是类似意思。当某些操作数需要被频繁操作的时候，register-based 的优势就体现出来了。比如这样：

c = a + b
d = h + b
e = i + b

这种情况，我们可以只 load 一次 b 到某个寄存器里，重复的使用它，不像 stack-based 需要反复的把它 pushstack，所以 register-based 在指令分派次数，内存访问次数上都要优于 stack-based。

3.11 collectgarbage(“count”) 的性能消耗

collectgarbage("count") 的作用是返回 lua vm 的内存占用。几乎没有性能消耗，它只需要拿内部的几个字段就可以计算出内存消耗。对于 lua 5.4.6，计算的函数是 gettotalbytes，用到的字段是 global_State 结构体里的 totalbytes 和 GCdebt 字段。

#define gettotalbytes(g)	cast(lu_mem, (g)->totalbytes + (g)->GCdebt)

4. 调参优化

普通的应用，不需要对 gc 参数进行调优，使用默认的 gc 参数就够了。游戏服务器对于 cpu 突刺是很敏感的，很容易引起掉帧问题。所谓掉帧就是游戏服运行过程中每秒跑的逻辑帧数不及预期，比如本来设计是每秒 20 帧，结果由于 gc 消耗了过多的 cpu 时间，导致一秒跑不了 20 帧。

4.1 skynet 中的 lua gc 优化

现在很多游戏都用 skynet，skynet 框架中，基本游戏逻辑都是用 lua 写的，要很重视 gc 带来的卡顿问题。

云风分享过关于《三国志战略版》的一次 gc 优化的例子：三国志战略版服务器卡顿问题。它的主要问题是：

目前遇到的直接问题是，skynet 中有个巨大的服务，管理了整个游戏场景的数据，大约有 20G 。所有的地块、部队、建筑对象都在这个服务中。且注册了大量的 timer 用来更新这些对象。最终导致在游戏繁忙时，该服务会以大约每分钟 500M 的速度生成临时数据。

这给 gc 带来的极大的负担。gc 会造成该服务的卡顿。而其它业务逻辑反而不太占用 cpu 。

通过监控数据的分析，我认为，gc 的原子操作阶段时间过长是罪魁祸首。这个阶段是不可分割的，真正的 stop the world 。而导致这个步骤过长的原因是，该服务大量使用了弱表。当弱表项高达几十万时，清理重置被影响的弱表，就需要很长的时间。

而实现中几乎把所有的对象都关联在了弱表中，仅仅是为了追踪每个类型的对象在内存中的存活情况，方便排查内存泄漏。我认为这是对弱表的滥用。在真的有这类需求时，通过遍历 vm 一样方便查找，不必为了监控而加大 gc 的负担。

去掉这些无谓的弱表后，情况得到了改观。

所以，总结起来，有如下原则：

重视 atomic 阶段的 gc 消耗，非必要不使用弱表，非必要不使用带 __gc 的对象。
根据项目的实际状况调整 gc 策略：
- 调整 gc 间隔（pause参数），调整 gc step 的工作量（stepmul参数）。
- 每收到一个消息都调用一次 gc step，即执行 collectgarbage("step", <arg>), arg 为 0 时，表示收集器原子的步进一步，非 0 时，表示收集器收集相当于 arg k 字节的工作。

5. 解决内存泄漏

按理说有了 gc，不应该内存泄漏了，但实际上，还是会有的。

TODO

6. 扩展阅读

6.1 书

日本人的写的一本书：《垃圾回收的算法与实现》

6.2 评论

一些有意思的评论

以下取自这篇文章（ Lua GC 的工作原理）的评论区，我觉得讲的颇有道理，就摘抄下来了。这个叫 wks 的小哥对于 gc 算法颇有研究，他的 blog 是：https://wks.github.io/ 。

图1：wks 评论1

图2：wks 评论2

6.3 文章

codedump：《Lua设计与实现》
云风: Lua GC 的源码剖析
云风: Lua GC 的工作原理
Roberto Ierusalimschy: The Implementation of Lua 5
Roberto Ierusalimschy: Garbage Collection in Lua
feileo: GC 机制探究之 Python 篇
Dibyendu Majumdar: Lua 5.3 Bytecode Reference
Kein-Hong Man: A No-Frills Introduction to Lua 5.1 VM Instructions
lua 5.3 垃圾回收分析 – 没有开花的树
lua 5.4 分代垃圾回收 – 没有开花的树
消除弱表中的循环（Eliminating Cycles in Weak Tables）

7. 参考

[1] [巴西]Roberto lerusalimschy. Lua 程序设计 (第4版). 梅隆魁. 北京: 电子工业出版社, 2018-6(1): 264.

[2] 重归混沌. 消除弱表中的循环（Eliminating Cycles in Weak Tables）. Available at https://zhuanlan.zhihu.com/p/385596480, 2021-07-01.

TODO

弱表的作用原理： https://zhuanlan.zhihu.com/p/385596480
atomic step 具体做的事情
弱表的实现及 gc 对应的问题，蜉蝣表（瞬表）
弱表的使用场景
分代 gc 是怎么 work 的
触发条件补充分代式 gc 的情形
明确根集的范围
补充完整短字符的 gc
分代 gc 仍然存在 fullgc 的情况，要如何解决？ lua_gc
关于 gc 模式切换的性能问题，见 http://lua-users.org/lists/lua-l/2020-12/msg00175.html
object 与 value 的区别？
调整文章的结构布局
补充完备的参考

lua 笔记：gc 算法

1. 设计与实现

1.1 原始的 gc

1.2 代码入口

1.2 增量式 gc

1.2.1 增量式 gc 的触发条件

1.2.2 增量式 gc 的 invariant（始终成立的条件）

1.2.3 工作过程

各个 gc 步骤

GCSatomic 阶段

GCSswpfinobj 和 GCSswptobefnz 阶段

根集

标记算法

1.3 分代式 gc

1.3.1 分代式 gc 的触发条件

1.3.2 分代式 gc 的 invariant (始终成立的条件)

1.3.3 工作过程

部分执行

全部执行

1.3.4 参考阅读

2. 增量式与分代式对比

3. 若干问题探究

3.1 一轮增量式 gc 还未完成时切换 gc 模式为分代式

3.2 增量式 gc 如何减少停顿

3.3 增量式 gc 的参数

3.4 分代式 gc 的参数

3.5 弱表

3.6 弱表的使用场景

3.7 析构

3.8 值对象与引用对象

3.9 短字符的 gc

3.10 基于寄存器的虚拟机

3.11 collectgarbage(“count”) 的性能消耗

4. 调参优化

4.1 skynet 中的 lua gc 优化

5. 解决内存泄漏

6. 扩展阅读

6.1 书

6.2 评论

6.3 文章

7. 参考