内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

Lua GC的工作原理

2018-10-11 12:11 出处:清屏网 人气: 评论(0

上次在 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 按需工作。


分享给小伙伴们:
本文标签: LuaGC

相关文章

发表评论愿您的每句评论,都能给大家的生活添色彩,带来共鸣,带来思索,带来快乐。

CopyRight © 2015-2016 QingPingShan.com , All Rights Reserved.

清屏网 版权所有 豫ICP备15026204号