« 动作游戏中的击打判定 | 返回首页 | Lua 的多线程支持 »

Lua GC 的工作原理

上次在 blog 上写 Lua GC 是 2011 年,lua 5.2 尚未发布时候的事情了。我认为仔细研读优秀开源代码是非常值得做的事情,但把研读过程写出来却意义不大。代人咀嚼这事吃力不讨好,每个人的技术背景不同,写得过细浪费阅读时间,写的粗糙又会使读者不得要领。一行行读代码本就只是件辛苦活,任何人沉下心来都能做到,想通过别人代读而节省时间,多半是做不到的。所以我那本 Lua 源码欣赏 也就一直搁置了。

沉在代码的逐行细节中往往一叶障目,反不如高屋建瓴的理解一下作者的思想。今年的 lua workshop ,Lua 的主要维护者 Roberto Ierusalimschy 做了题为 Garbage collection in Lua 的演讲,很好的讲述了 Lua 历史各个版本的 gc 算法实现。我没有听这个演讲,但阅读 Slide 结合源代码基本可以搞明白。这篇 Blog 分享一下我的理解。注意:我添加了许多自己的理解,很可能和演讲原意有极大的偏差。所以本篇仅代表我的个人立场。

几乎所有现代编程语言都有自动化内存管理设施,在内存不再使用的时候,能够自动释放它们。有两种方法可以做到这点,一是引用计数,二是垃圾收集。引用计数有循环引用无法将不再使用的对象引用减到零的问题,但这并不是 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 使用的是一个非常简单的标记扫描算法。它从根集开始遍历对象,把能遍历到的对象标记为活对象;然后再遍历通过分配器分配出来的对象全集链表,把没有标记为活对象的其它对象都删除。

但是,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 的性能表现对整个系统的性能表现影响重大。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) 。

我们有两种方式维持不变条件:一种是把白色对象变为灰色的(forward),另一种是把黑色对象变回 (backward) 灰色。如果参考 Lua 5.1 以后的代码,在 lgc.h 中能找到两个 api 对象这两种操作,luaC_barrierluaC_barrierback

什么时候采用什么方法更好是实现的时候凭经验(感觉?)决定的。比方说,给 table 赋值的时候,就直接把被赋值的黑色 table 变回灰色。我猜是因为大部分时候被修改的 table 都不会是黑色,同时不需要检查赋值的量的类型和颜色。如果一个黑色的 table 变回了灰色,就证明在扫描中途被打断(处于某种不常见的临界状态),就把它单独放在一个独立的链表 (grayagain)里,留待后面原子处理,避免它在黑和灰之间反复折腾。对于堆栈,则干脆不让它变黑,这样对栈的操作就不需要 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 ,程序使用的内存暴涨,无法及时回收。其实,正确的方法很简单,在分配新的 userdata 时,利用 lua_gc 传入 LUA_GCSTEP 让它步进相应真实占据的内存数量就可以了,而没有必要让虚拟机记住这个 userdata 真的使用了多少内存。

从上面的算法分析可见,步进式 GC 能够减少每次 GC 工作时的停顿时间,但是无法减少 GC 带来的额外开销,相反,GC 的时间成本(额外的 Barrier )和空间成本(未能及时回收不再使用的内存)反而较之全量 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 策略,更很难保持条件成立(对象很难知道谁引用了自己,就无法准确的把老对象变回新的)。

所以,需要引入第三态:触碰过的对象(The Touched Objects)。

当 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 按需工作。

Comments

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

这种想法很危险。首先,朴素的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。可以搜搜,这段故事挺让人痛心的。

@lichking 动态语言循环引用问题的确不可避免。但静态语言这种情况应该是可以避免吧?如果有非用不可的情况,也是很少,我猜想可以用弱引用的情况替代。

那么Lua5.1与LuaJIT的GC是一样的么?

有些引用循环又不是发生在程序员能看见的地方,程序员的理论知识欠缺,不要想当然

golang 也没有引入分代GC,可能是分代GC虽然能减少碎片,但增加了对内存需求和复杂度。我想在嵌入式环境,RC计数应该能保证实时性和简洁,毕竟循环引用的问题本来就是程序员自己要避免的,何苦留给vm?类似ObjectC的设计,虽然用起来难看些

引用计数 和 垃圾收集 对应是原 slide 的说法,本文主要是介绍这个 slide 所以就直接引用了。

@cybtron 有道理。与“引用计数”(reference counting)相对的是“追踪”(tracing),译为“扫描标记”也比较贴切。

深究的话,垃圾回收(garbage collection)包括内存分配(allocation)、垃圾识别(identification)、内存回收(reclamation)。其中垃圾识别的两种基本方法是引用计数(reference counting)和追踪(tracing,也称为追踪式回收,即tracing collection)。RC不用说了,tracing指的是“从根(局部变量和全局变量)出发寻找可达对象,不可达的就是垃圾”的算法。内存的分配大体可以分为free-list和bump pointer两类,而内存回收可以分为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)是bmup-pointer+tracing+evacuation。
分代垃圾回收(generational collection)的年轻代可以用一个专用的空间存放然后evacuate,也可以不用单独的空间,而是用一个标志位(sticky bit)来表示。还有一些内存分配、释放的方法是基于区块(region)的,在区块内bump pointer,区块本身用free-list管理,兼有两者的优点。新的一些算法,比如C4、G1、Immix、Shenandoah、ZGC还有Android Oreo的JVM里的GC,都是基于区块的算法。

有两种方法可以做到这点,一是引用计数,而是垃圾收集。
应该是
一是引用计数,二是扫描标记

5.3 增加的代码大多是注释。5.3 是首个可以在 32bit 平台用 float 的 lua 版本(small lua).

之前的版本都必须用 double 来表示整数。small lua 可以在 32bit 平台节省 1/3 的 runtime 内存,这对内存有限的环境意义更大。

看来5.2虽然做了点减法,但还是有更多的加法,从代码量上就能看出一版比一版大.
受限的嵌入式环境怎么可能重视64位...

不。

Lua 5.3 减掉了 Lua 5.2 中分代 GC ,错误定义的 __ipairs 和不完全的 bit32 库。只增加了 64bit 整型支持,这在现代普遍的 64 位架构下,是非常重要的改进。

lua 5.2 也可以, 考虑5.1只是因为更流行且同时可以考虑luajit而已.
不过5.3以后就基本都是加法了.

@dwing

lua 5.2+ 比起 lua 5.1 做的是减法。GC 部分的结构是简化了,更清晰。(其它特性也做了很多减法,比如去掉 fenv ,去掉全局表,去掉 module )

例如 lua 5.1 中需要在每个 object 标注一个标记位来标记永久不回收的对象;在后面的版本里,就去掉了这个标记位。

增加的代码是为了补完语言上不完备的特性,比如 ephemeron table ;比如复活后的对象不会再次调用 finalizer.

另外 lua 5.1 的 gc 是遗留有一些 bug 并未解决的,例如在 table resize 的过程中发生 oom 就会产生泄露。对于内存受限的嵌入式环境,这个 bug 更为敏感。

没办法,垃圾回收本来就不简单,高性能的垃圾回收更不简单了。想要性能的编程语言实现,早晚要把Richard Jones的《GC Handbook》的内容都学一遍。不过,Lua已经做得很好了,它的API和VM设计已经把有垃圾回收的执行环境和C程序隔离得很漂亮了,没有贪图简单而像Python那样走向naive RC的不归路。

从支持分代GC开始就感觉Lua正在走向越来越复杂的不归路.
不过也没办法, 看着身边的js(v8), ruby(2.1), php(5.3)的gc都在大幅进步.
受限的嵌入式环境保留在简单的5.1版本也挺好.

谢谢博主,你把lua GC的演进总结得真好。

我想推荐一下人民邮电出版社引进的《垃圾回收的算法与实现》,里面对常见GC算法有深入浅出的描述。

不错,通俗易懂。

发现一个 typo
有两种方法可以做到这点,一是引用计数,而是垃圾收集。

二是

Post a comment

非这个主题相关的留言请到:留言本