lua gc分析

说明

分析lua使用的gc算法,如何做到分步gc,以及测试结论

gc算法分析

lua gc采用的是标记-清除算法,即一次gc分两步:

  1. 从根节点开始遍历gc对象,如果可达,则标记
  2. 遍历所有的gc对象,清除没有被标记的对象

二色标记法

image
lua 5.1之前采用的算法,二色回收法是最简单的标记-清除算法,缺点是gc的时候不能被打断,所以会严重卡住主线程

三色标记法

image

  1. lua5.1开始采用了一种三色回收的算法 * 白色:在gc开始阶段,所有对象颜色都为白色,如果遍历了一遍之后,对象还是白色的将被清除 * 灰色:灰色用在分步遍历阶段,如果一直有对象为灰色,则遍历将不会停止 * 黑色:确实被引用的对象,将不会被清除,gc完成之后会重置为白色
  2. luajit使用状态机来执行gc算法,共有6中状态: * GCSpause:gc开始阶段,初始化一些属性,将一些跟节点(主线程对象,主线程环境对象,全局对象等)push到灰色链表中 * GCSpropagate:分步进行扫描,每次从灰色链表pop一个对象,遍历该对象的子对象,例如如果该对象为table,并且value没有设置为week,则会遍历table所有table可达的value,如果value为gc对象且为白色,则会被push到灰色链表中,这一步将一直持续到灰色链表为空的时候。 * GCSatomic:原子操作,因为GCSpropagate是分步的,所以分步过程中可能会有新的对象创建,这时候将再进行一次补充遍历,这遍历是不能被打断的,但因为绝大部分工作被GCSpropagate做了,所以过程会很快。新创建的没有被引用的userdata,如果该userdata自定义了gc元方法,则会加入到全局的userdata链表中,该链表会在最后一步GCSfinalize处理。 * GCSsweepstring:遍历全局字符串hash表,每次遍历一个hash节点,如果hash冲突严重,会在这里影响gc。如果字符串为白色并且没有被设置为固定不释放,则进行释放 * GCSsweep:遍历所有全局gc对象,每次遍历40个,如果gc对象为白色,将被释放 * GCSfinalize:遍历GCSatomic生成的userdata链表,如果该userdata还存在gc元方法,调用该元方法,每次处理一个

什么时候会导致gc?

  1. luajit中有两个判断是否需要gc的宏,如果需要gc,则会直接进行一次gc的step操作

    1
    2
    3
    4
    5
    6
    7

  { if (LJ_UNLIKELY(G(L)->gc.total >= G(L)->gc.threshold))   
      lj_gc_step(L); }  
#define lj_gc_check_fixtop(L)   
  { if (LJ_UNLIKELY(G(L)->gc.total >= G(L)->gc.threshold))   
      lj_gc_step_fixtop(L); }  

—|—
* gc.total: 代表当前已经申请的内存 * gc.threshold:代表当前设置gc的阈值

  1. 这两个宏会在各个申请内存的地方进行调用,所以当前申请的内存如果已经达到设置的阈值,则会申请的所有对象都会有gc消耗。

lua gc api

lua可以通过

1  
collectgarbage([opt [, arg]])  

—|—

来进行一些gc操作,其中opt参数可以为:

  • “collect”:执行一个完整的垃圾回收周期,这是一个默认的选项
  • “stop”:停止垃圾收集器(如果它在运行),实现方式其实就是将gc.threshold设置为一个巨大的值,不再触发gc step操作
  • “restart”:将重新启动垃圾收集器(如果它已经停止)。
  • “count”:返回当前使用的的程序内存量(单位是Kbytes),返回gc->total/1024
  • “step”:执行垃圾回收的步骤,这个步骤的大小由参数arg(较大的数值意味着较多的步骤),如果这一步完成了一个回收周期则函数返回true。
  • “setpause”:设置回收器的暂停参数,并返回原来的暂停数值。该值是一个百分比,影响gc.threshold的大小,即影响触发下一次gc的时间,设置代码如下:

    1  
    
    g->gc.threshold = (g->gc.estimate/100) * g->gc.pause;  

—|—

g->gc.estimate为当前实际使用的内存的大小,如果gc.pause为200,则该段代码表示,设置gc的阈值为当前实际使用内存的2倍

  • “setstepmul”:设置回收器的步进乘数,并返回原值。该值代表每次自动step的步长倍率,影响每次gc step的速率,具体这么影响可以查看后面小节

luajit gc速率控制

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
int LJ_FASTCALL (lua_State *L)  
{  
  global_State *g = G(L);  
  GCSize lim;  
  int32_t ostate = g->vmstate;  
  setvmstate(g, GC);  
  // 设置此次遍历的限制值,每次调用gc_onestep都会返回此次step的消耗,限制值消耗完毕之后此次step结束;  
  lim = (GCSTEPSIZE/100) * g->gc.stepmul;  
  if (lim == 0)  
    lim = LJ_MAX_MEM;  
  if (g->gc.total > g->gc.threshold)  
    g->gc.debt += g->gc.total - g->gc.threshold;  
  do {  
    lim -= (GCSize)gc_onestep(L);  
    if (g->gc.state == GCSpause) {  
      g->gc.threshold = (g->gc.estimate/100) * g->gc.pause;  
      g->vmstate = ostate;  
      return 1;  /* Finished a GC cycle. */  
    }  
  } while (sizeof(lim) == 8 ? ((int64_t)lim > 0) : ((int32_t)lim > 0));  
  if (g->gc.debt < GCSTEPSIZE) {  
    g->gc.threshold = g->gc.total + GCSTEPSIZE;  
    g->vmstate = ostate;  
    return -1;  
  } else {  
    // 加快内存上涨速度;  
    g->gc.debt -= GCSTEPSIZE;  
    g->gc.threshold = g->gc.total;  
    g->vmstate = ostate;  
    return 0;  
  }  
}  

—|—

  • 可以看到最重要的变量为lim,该变量控制着一个lj_gc_step里的循环次数。每次调用gc_onestep都会返回此次的step消耗,例如如果处于GCSpropagate阶段,则返回值为该step遍历的内存大小,所以如果遍历了一个较大的table就会消耗更多的lim值
  • lim大小主要由gc.stepmul控制,所以设置该值的大小会影响每次step的调用时间

测试大table对gc的影响

从luajit gc原理上看,以为每次gc的遍历都会遍历所有的gc对象,所以大的table是会影响gc性能

测试环境

操作系统:Debian GNU/Linux 8
CPU:Intel(R) Xeon(R) CPU E5-2640 v2 @ 2.00GHz
内存:64G
lua环境:LuaJIT-2.1.0-beta3 (测试的时候关闭jit)

测试代码

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
-- 关闭jit  
if jit then  
    jit.off()  
end  
  
local data = {} -- 一个大的table,用来模拟常驻内存的table,测试的时候使用的是drop_data.lua里面的数据,该data有8655个table元素(在gc的时候产生消耗),60810个元素(包括table元素,会在遍历的时候产生消耗)  
  
function deepCopyTable(t)  
    local ret = {}  
    for k, v in pairs(t) do  
        if type(v) == "table" then  
            ret[k] = deepCopyTable(v)  
        else  
            ret[k] = v  
        end  
    end  
    return ret  
end  
  
datas = {}  
  
-- 循环产生更多的常驻内存的table,可以看到总共会有865W+的table元素和总共6000W+的元素  
for i = 1, 1000 do  
	datas[#datas+1] = deepCopyTable(data)  
end  
  
print("begin")  
local time = os.clock()  
for i = 1, 2000000 do  
    -- 模拟产生临时变量  
	local temp = deepCopyTable(data)  
  
    -- 每10次计算一次时间和内存  
	if i % 10 == 0 then  
		local time_temp = os.clock()  
		print(collectgarbage("count"), time_temp-time)  
		time = time_temp  
	end  
end  

—|—

测试结果(第一个列为当前内存,第二列为当前内存阈值,第三列为当前gc状态,第四列为循环10次的时间)

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
-- gc没有介入阶段,平均时间大概在0.059s,这时候代表着内存的分配速度  
3345733.2617188	4136590.0390625	0	0.058304  
3366347.6367188	4136590.0390625	0	0.058013000000003  
3386962.0117188	4136590.0390625	0	0.058147999999996  
3407576.3867188	4136590.0390625	0	0.059978000000001  
3428190.7617188	4136590.0390625	0	0.059843999999998  
3448805.1367188	4136590.0390625	0	0.058331000000003  
3469419.5117188	4136590.0390625	0	0.058205000000001  
3490033.8867188	4136590.0390625	0	0.058352999999997  
3510648.2617188	4136590.0390625	0	0.058503000000002  
3531262.6367188	4136590.0390625	0	0.058151000000002  
3551877.0117188	4136590.0390625	0	0.058059999999998  
  
-- gc进入sweep阶段,删除内存,峰值时间在0.78s左右,后面时间变少应该是因为那一块都是常驻内存的gc对象,很少会去调用free函数  
5056726.3867188	5056726.3242188	1	0.076171000000002  
5077340.7617188	5077340.9492188	1	0.076453999999998  
4955367.8554688	4955368.0429688	4	0.140509  
3994134.0820313	3994134.0195313	4	0.679567  
3032849.7617188	3032850.1992188	4	0.786561  
2133608.0117188	2133608.7617188	4	0.788004  
2154222.3867188	2154222.3242188	4	0.255904  
2174836.7617188	2174837.1992188	4	0.254212  
full sweep time: 2.850359  
2195451.1367188	4137406.4453125	0	0.066203999999999  

—|—

  • 火焰图分析(gc处于sweep状态):
    image
    主要时间消耗在gc_sweep(51.34%):该步骤会遍历所有的gc对象,如果可回收,就进行free操作,所以gc_sweep里面最耗时的就是free函数(34%左右)

gc优化

从火焰图上看到,gc_sweep函数耗时严重,其主要工作是遍历所有gc对象,如果为白色,则free它,所以优化方案有两点:

  1. 内存分配算法优化
  2. 减少gc遍历的对象,即减少那些明确常驻内存的gc对象遍历

内存分配算法优化

luajit默认使用的是自己的内存分配算法,现在尝试分别使用glibc自带的内存分配和第三方高性能jemalloc(选择的版本是jemalloc- stable-4),tcmalloc(选择的是gperftools-2.7)的分配算法进行分析

测试结果

image
image
image

结果分析

  • 申请内存的速率跟常驻内存的table大小关系不大,luajit自带的分配算法最快,但是总体相差不大
  • 随着常驻内存的table大小变大,会影响gc释放速度,这将会卡主主线程
  • 释放内存速率jemalloc最好,并且随着常驻内存的table大小变大,效率体现的越明显

table缓存优化

思路

自己写一个table缓冲池,缓冲一定数量、一定大小的table在c++内存,避免每次反复申请内存及rehash,reszie table操作
TODO: 需要具体修改luajit源码进行测试

减少gc遍历的对象

思路

对于那些常驻内存的table,可以主动加一个标记,在gc时候遍历到这个table,将对其以及所有子gc对象从全局gc链表删除,并加入到一个全局const gc对象链表中。
源代码可以查看github

测试结果

image

对比结果

image

火焰图(jemalloc-4G内存)

image

  • gc_sweep在总的采样占比上已经变得很少,这点从打log上面就能看出
  • free占比gc_sweep的时间比重增加,说明减少了遍历的时间消耗

注意点

  • 从给table设置constant之后完整的一次gc之前,不能主动调用full gc否则会导致table子元素没有被标记,这样就会被误删除,导致访问的时候出现内存问题
  • table不能设置weak
  • table元素只能是table、string、number,不能有function,线程

结论

可以看到优化在常驻内存table大的时候很明显,主要提升了两个方面的速度:

  • 在GCSpropagate阶段减少不必要的遍历,加快遍历速度,同时减少了新临时变量的生成
  • 在GCSweep阶段,减少不必要的遍历,同时因为加快遍历速度,需要free的临时变量变少,所以减少了GCSweep的时间

糖果

糖果
LUA教程

Lapis框架的常用处理方法

Lapis框架的常用处理方法 Continue reading

MoonScript实现选择排序

Published on February 26, 2017

MoonScript与Redis客户端

Published on January 19, 2017