全量GC:Lua5.0及以前
Lua5.0及以前的版本使用的是双色标记清除算法(Two-Color Mark and Sweep)。
该算法的原理是:系统中的每个对象非黑(black)即白(white),也就是要么被引用,要么没有被引用。
具体的伪代码如下:
每个新创建的对象颜色为白色(white) // 初始化阶段 遍历在root链表中的对象,加入到对象链表 // 标记阶段 当对象链表中还有未扫描的元素: 从中取出一个对象,标记为黑色(black) 遍历这个对象关联的其他所有对象: 标记为黑色(black) // 回收阶段 遍历所有对象: 如果为白色(white): 这些对象都是没有被引用的对象,逐个回收 否则: 这些对象时被引用的对象,重新加入对象链表中等待下一轮的GC检查
颜色状态转换图如下:
该算法的问题是:整个GC过程不能被打断,必须暂停程序(Stop the World),一次性扫描并清除完所有对象。
步进式GC(增量模式):Lua5.1
Lua5.1在双色标记清除算法上改进实现了三色增量标记清除算法(Tri-Color Incremental Mark and Sweep)。
该GC算法不再要求一次性扫描完所有对象,可以被中断去执行业务逻辑,然后再恢复回来继续执行,是一种增量式垃圾收集器(Incremental Collector)。
增加一种颜色状态(灰色),说明如下:
白色(White):表示当前对象为待访问状态,用于表示对象还没有被GC的标记过,这也是任何一个Lua对象在创建之后的初始状态。
换言之,如果一个对象,在一个GC扫描完毕之后,仍然是白色的,那么说明该对象没有被系统中任何一个对象所引用,可以回收其空间了。
灰色(Gray):表示当前对象为带扫描状态,用于表示对象已经被GC访问过,但是被该对象直接引用的其他对象还没有被访问到。
黑色(Black):表示当前对象为已扫描状态,用于表示对象已经被GC访问过,并且被该对象直接引用的其他对象也已经被访问过了。
注1:完成整个标记阶段,只会存在两种颜色(白色和黑色)
注2:完整地执行一次GC之后,黑色的对象会被重置为白色
具体的伪代码如下:
每个新创建的对象颜色为白色(white) // 初始化阶段 遍历在root节点中引用的对象从白色(white)置为灰色(gray),并且放入到灰色节点列表中. // 标记阶段 当灰色链表中还有未扫描的元素: 从中取出一个对象,标记为黑色(black) 遍历这个对象关联的其他所有对象: 如果是白色(white): 标记为灰色(gray),加入灰色链表 // 回收阶段 遍历所有对象: 如果为白色(white): 这些对象都是没有被引用的对象,逐个回收 否则: 重新加入对象链表中等待下一轮的GC检查
颜色状态转换图如下:
可以看到,引入了新的灰色节点的概念之后,算法不再要求一次性完整地执行完毕,而是可以把已经扫描但是其引用的对象还未被扫描的对象置为灰色
在标记阶段中,只要灰色节点集合中还有元素在,那么这个标记过程就会继续下去,即使在中间该阶段被打断转而执行其它的操作了也没有关系
对象引用关系图如下:
双白色
从上面的算法可以看出,没有被引用的对象其颜色在一个扫描过程中始终保持不变为白色。
那么假如一个对象在一个GC过程的标记阶段之后被创建,根据前面对颜色的描述,它应该是白色的,这样在紧跟着的回收阶段,这个对象就会在没有被扫描标记的情况下被认为是没有被引用的对象而删除。
因此,Lua除了前面的三色概念之外,又细分出来一个"双白色"的概念。简单的说,Lua中的白色分为"当前白色(currentwhite)"和"非当前白色(otherwhite)"。
这两种白色的状态交替使用,第N次GC使用的是第一种白色,那么下一次就是另外一种,以此类推...
代码在回收时候会做判断,如果某个对象的白色不是此次GC回收使用的白色状态将不会被认为是没有被引用的对象而回收。
这样的白色对象将留在下一次GC中进行扫描,因为在下一次GC中上一次幸免的白色将成为这次的回收颜色。
分代GC:Lua5.4
lua5.2引入了分代gc(Generational Collector),属于实验性质,实际效果不好,在5.3的时候又移除了,lua5.4重新实现了分代gc并正式发布。
lua 5.4支持两种 gc 方式:增量式 gc 和分代 gc ,默认是增量式,可以在运行时随时动态切换。
切换为增量gc
在c语言中:lua_gc(L, LUA_GCINC, 0, 0, 0);
在lua语言中:collectgarbage("incremental");
切换为分代gc
在c语言中:lua_gc(L, LUA_GCGEN, 0, 0);
在lua语言中:collectgarbage("generational");
分代原理
经验表明,大部分对象在被分配之后很快就被回收掉了,长时间存活的对象很大可能会一直存活下去。所以,垃圾回收可以集中精力去回收刚刚造出来的对象。
将所有gc对象分成两种,young和old;过程也分为minor(浅扫描,或次级收集周期)和major(深扫描,或主收集周期)。
对象创建时标记为 young,minor过程扫描 young 对象,当young节点活过了两次gc过程,就会标记成 old对象 。
old 对象在minor将不再被清除和遍历。当总的内存增长超过阈值时,执行major扫描全部young 对象和old对象,清理垃圾对象后,把所有存活对象都变为 old 对象。
注:活过两次gc过程也是与lua5.2 gc过程的最大不同点。lua5.2 gc只需要活过一次,就算做old。
自动触发gc step
/* ** Does one step of collection when debt becomes positive. ** 'condchangemem' is used only for heavy tests */ #define luaC_condGC(L,pre,pos) \ { if (G(L)->GCdebt > 0) { pre; luaC_step(L); pos;}; \ condchangemem(L,pre,pos); } #define luaC_checkGC(L) luaC_condGC(L,(void)0,(void)0)
在以下代码中,使用 luaC_checkGC 检查 gc 阈值 GCdebt ,当 GCdebt 大于0 时,执行 gc step
1、创建新数据时 string, thread, userdata, table, closure
3、语法解析时
4、错误发生时
5、字符串拼接时 concat
6、栈增长时
注:这里提下GCdebt,字面意思就是 gc 债务,用以调节 gc 是否触发。当 GCdebt 大于0时,触发 gc, 而且,gc 单次的工作量也受这个参数影响。
手动触发gc step
在c语言中:lua_gc(L, LUA_GCSTEP, 0);
在lua语言中:collectgarbage("step");
手动触发全量gc
在c语言中:lua_gc(L, LUA_GCCOLLECT, 0);
在lua语言中:collectgarbage("collect");
GC API用法
标签 | 类型 | 说明 | c语言示例 | lua语言示例 |
#define LUA_GCSTOP 0 | 控制GC行为 | 停止垃圾收集器(如果在执行的话)注:会将gc.threshold设置为一个巨大的值,不再触发gc step操作 | lua_gc(L, LUA_GCSTOP, 0); | collectgarbage("stop"); |
#define LUA_GCRESTART 1 | 控制GC行为 | 重启垃圾收集器(如果已经停止的话) | lua_gc(L, LUA_GCRESTART, 0); | collectgarbage("restart"); |
#define LUA_GCCOLLECT 2 | 控制GC行为 | 发起一次完整的垃圾收集循环 | lua_gc(L, LUA_GCCOLLECT, 0); |
collectgarbage(""); // 等同collectgarbage("collect") collectgarbage("collect"); |
#define LUA_GCCOUNT 3 | 获取GC数据 | 返回 Lua 使用的内存总量(以 K 字节为单位) | lua_gc(L, LUA_GCCOUNT, 0); |
print(collectgarbage("count")); // 输出22174.333984375 local integer, decimal = math.modf(collectgarbage("count")); // integer即为该项的值 |
#define LUA_GCCOUNTB 4 | 获取GC状态 | 返回当前内存使用量除以 1024 的余数 | lua_gc(L, LUA_GCCOUNTB, 0); |
print(collectgarbage("count")); // 输出22174.333984375 local integer, decimal = math.modf(collectgarbage("count")); // decimal*1024,然后取整即为该项的值 |
#define LUA_GCSTEP 5 |
控制GC行为 |
发起单步增量垃圾收集。步长“大小”由 arg 控制。 传入 0 或空时,收集器步进(不可分割的)一步。 传入非 0 值, 收集器收集相当于 Lua 分配这些多(K 字节)内存的工作。 如果完成了一个GC周期将返回 true 。 |
lua_gc(L, LUA_GCSTEP, 0);
lua_gc(L, LUA_GCSTEP, 1); |
collectgarbage("step"); collectgarbage("step", 0); // 等同collectgarbage("step") collectgarbage("step", nil); // 等同collectgarbage("step") collectgarbage("step", 1); |
#define LUA_GCSETPAUSE 6 |
用于增量GC |
把 data 设为 垃圾收集器间歇率 (使用百分数为单位,100表示 1),并返回之前设置的值。 垃圾收集器间歇率控制着收集器需要在开启新的循环前要等待多久。 增大这个值会减少收集器的积极性。 当这个值小于或等于100时,收集器执行完一个循环周期之后不会等待,直接进入下一个循环周期。 当这个值为200的时候,就代表当内存达到上一个循环周期结束时的两倍的时候,才进入下一个循环周期。 通过调整gc.threshold的大小,来影响触发下一次gc的时间 |
lua_gc(L, LUA_GCSETPAUSE, 120); | collectgarbage("setpause", 120); |
#define LUA_GCSETSTEPMUL 7 |
用于增量GC |
把 data 设为 垃圾收集器步进倍率(使用百分数为单位,100表示 1),并返回之前设置的值。 垃圾收集器步进倍率控制着收集器运作速度相对于内存分配速度的倍率。 默认值是 200 ,这表示收集器以内存分配的“两倍”速工作。 增大这个值不仅会让收集器更加积极,还会增加每个增量步骤的长度。 不要把这个值设得小于 100 , 那样的话收集器就工作的太慢了以至于永远都干不完一个循环。 如果把步进倍率设为一个非常大的数字 (比整个进程用到的字节数还大 10% ), 收集器的行为就像一个 stop-the-world 收集器。 通过调步进速率的大小,来影响每次gc step的速率 |
lua_gc(L, LUA_GCSETSTEPMUL, 200); | collectgarbage("setstepmul", 200); |
#define LUA_GCISRUNNING 9 | 获取GC状态 | 返回收集器是否在运行(即没有停止) | lua_gc(L, LUA_GCISRUNNING, 0); | collectgarbage("isrunning"); |
#define LUA_GCGEN 10 | 切换成分代GC |
lua5.4版本新增。设置为分代GC。 还支持2个参数,分别为 minormul, majormul,缺省值为 0, 不改变原设定。 minormul 控制 minor 回收的频率,默认值20,没有数值范围限制,建议最大值 200。 minormul 的值越大,gc 触发的频率越低。这个参数同时影响了浅扫描(minor)和 深扫描(major) majormul 控制深扫描(major)回收的频率,默认值100,没有数值范围限制,建议最大值 1000。 |
lua_gc(L, LUA_GCGEN, 0, 0); |
collectgarbage("generational"); |
#define LUA_GCINC 11 | 切换成增量GC |
lua5.4版本新增。设置为增量GC。 还支持3个参数,分别为 pause, stepmul, step(作用同上),缺省值为0, 不改变原设定。 |
lua_gc(L, LUA_GCINC, 0, 0, 0); lua_gc(L, LUA_GCINC, 120, 200, 0); |
collectgarbage("incremental"); collectgarbage("incremental",120, 200, 0); |
参考