Lua笔记 效率&性能

本文使用对比测评的方式比较了几种Lua中代码和方式,并做了简要的总结和分析。结合其中结论,可指导写出质量更高、性能更优的脚本。本文基于Lua5.1,大部分内容也同样适用于Lua5.2和5.3。本文中引用到的Lua源代码都取自Lua 5.1.5版本。

评测方法

主要有运行时间和产生GC两个指标,以下是获取运行时间和内存用量/GC的方法:

获取运行时间

为了更好地做比较,使用下边的方法来记录代码的运行时间:

1
2
3
4
5
6
7
local a, b
a = os.clock()

-- do something

b = os.clock()
print(b-a)

获取内存用量

1
2
3
4
5
collectgarbage("stop")

collectgarbage("collect")

print(collectgarbage("count"))

上边三行代码都是调用函数collectgarbage(),配合传入的不同的参数达到不同的目的:

  • stop 停止自动GC

  • collect 执行一次完整的GC循环

  • count 返回当前内存用量,以k为单位

使用local保存全局变量的引用

使用local保存全局变量的引用可以提高变量访问效率。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
local sin = math.sin

local a,b
a = os.clock()
local res = 0
for i = 1, 10000000 do
res = res + math.sin(i) -- case 1
--res = res + sin(i) -- case 2
end

b = os.clock();
print("cost time = " .. b-a)

运行以上代码得到case1和case2的输出分别为:

1
2
3
4
5
//case 1
cost time = 2.10697

//case 2 [better]
cost time = 1.260123

分析

Lua使用的是基于寄存器的虚拟机(使用一个栈来提供寄存器),所有的local变量都会保存在寄存器里,因此访问local变量的速度会快于全局变量。在Lua的源码中可以看到对局部变量的最大数量有200的限制:

1
2
3
4
5
/*
@@ LUAI_MAXVARS is the maximum number of local variables per function
@* (must be smaller than 250).
*/
#define LUAI_MAXVARS 200

尾递归调用

对于一些情况下的函数递归调用,转为尾递归写法,可以减少调用栈的分配,提高函数运行效率同时也避免了栈溢出的风险。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
local n = 0

local add = function()
n = n + 1
end

local function fr(times)
if times <= 0 then
print("now n = " .. n)
return
end
add()
return fr(times - 1) -- case 1
-- fr(times - 1) -- case 2
end

local a, b
a = os.clock()

fr(100000)

b = os.clock()
print(b-a)

运行以上代码得到case1和case2的输出分别为:

1
2
3
4
5
6
7
//case 1  [better]
now n = 100000
0.020423

//case 2
now n = 100000
0.050295

分析

fr调用add后不会再做任何事情,这种情况下当被调用函数add结束时程序不需要返回到调用者fr;尾调用不需要使用额外的栈空间,因此尾调用递归的层次可以无限制的。

在Lua的源代码lvm.c中可以看到以下内容:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
case OP_CALL: {
int b = GETARG_B(i);
int nresults = GETARG_C(i) - 1;
if (b != 0) L->top = ra+b; /* else previous instruction set top */
L->savedpc = pc;
switch (luaD_precall(L, ra, nresults)) {
case PCRLUA: {
nexeccalls++;
goto reentry; /* restart luaV_execute over new Lua function */
}
case PCRC: {
/* it was a C function (`precall' called it); adjust results */
if (nresults >= 0) L->top = L->ci->top;
base = L->base;
continue;
}
default: {
return; /* yield */
}
}
}
case OP_TAILCALL: {
int b = GETARG_B(i);
if (b != 0) L->top = ra+b; /* else previous instruction set top */
L->savedpc = pc;
lua_assert(GETARG_C(i) - 1 == LUA_MULTRET);
switch (luaD_precall(L, ra, LUA_MULTRET)) {
case PCRLUA: {
/* tail call: put new frame in place of previous one */
CallInfo *ci = L->ci - 1; /* previous frame */
int aux;
StkId func = ci->func;
StkId pfunc = (ci+1)->func; /* previous function index */
if (L->openupval) luaF_close(L, ci->base);
L->base = ci->base = ci->func + ((ci+1)->base - pfunc);
for (aux = 0; pfunc+aux < L->top; aux++) /* move frame down */
setobjs2s(L, func+aux, pfunc+aux);
ci->top = L->top = func+aux; /* correct top */
lua_assert(L->top == L->base + clvalue(func)->l.p->maxstacksize);
ci->savedpc = L->savedpc;
ci->tailcalls++; /* one more call lost */
L->ci--; /* remove new frame */
goto reentry;
}
case PCRC: { /* it was a C function (`precall' called it) */
base = L->base;
continue;
}
default: {
return; /* yield */
}
}
}

由于没有系统研读过Lua的源码,仅结合注释及上下文做出一些判断。Lua中高端函数调用与函数尾调用使用的是两个指令(OP_CALLOP_TAILCALL),二者很相似,都是通过luaD_precall执行函数调用,并根据调用了Lua函数还是C函数进行处理。在OP_TAILCALL中,调用Lua函数之后,可以看到有这样的操作:取到“previous frame”即之前的调用信息CallInfo *ci,使用新增的CallInfo中的信息取替换ci中的内容,并移除新增的CallInfo。直接复用CallInfo从而调用函数不增加栈的深度。

减少rehash

初始化一个表时,可以直接在构造表的时候为表内的key赋值,这样做会好于创建空表再为其填入键和值。因为后者可能触发大量rehash。

测试代码

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
40
41
42
43
44
45

local function gettable_1()
local t = {
a=1,
b=2,
c=3,
d=4,
e=5,
f=6,
g=7,
h=8,
i=9,
j=10
}
return t
end

local function gettable_2()
local t = {}
t.a=1
t.b=2
t.c=3
t.d=4
t.e=5
t.f=6
t.g=7
t.h=8
t.i=9
t.j=10
return t
end

local a,b
a = os.clock()

local t={}
for i = 1,100000 do

--t = gettable_1() -- case 1
t = gettable_2() -- case 2

end

b=os.clock()
print("cost time " .. b - a)

运行以上代码得到case1和case2的输出分别为:

1
2
3
4
5
//case 1 [better]
cost time 0.126207

//case 2
cost time 0.332967

分析

Lua中表的实现涉及到一些巧妙的算法。每个表都包含两个部分:array部分和hash部分。array部分保存以整数1到n为键的值,其中n是一些特定的值(稍后会说n是怎么算出来的)。所有的其它键值对(包括整数键但是整数超出1到n的范围)保存在hash部分。

如其名所示,hash部分使用hash算法来存储和查找键。它使用的是开放地址法(open address table),所有的键值对都存储在一个hash数组中。使用hash函数来为键取得索引;如果出现hash冲突(即两个不同的键hash得出了相同的索引位置),对应的键会存在一个list列表中,列表中每个元素对应的是一个hash数组中的元素。

当Lua需要向表中插入新的值并且此时hash数组已满时,就会触发rehash。rehash的第一步就是计算新的array部分和hash部分的尺寸。为此,Lua会遍历所有的键值对,计数并分类,然后选择能够使array部分的元素填充率超过一半的最大的2的次方数作为array部分的新尺寸。而hash部分的尺寸是能够容纳所有剩余元素的2的次方数(与array部分的策略不同)。

当创建空表时,array部分和hash部分的尺寸都是0,因此插入新的值的时候就会频繁地触发rehash。

字符串效率

这里基于Lua5.1(5.2开始有长短字符串之分,部分逻辑可能与这里不一样,但结论相似)。对于短小的字符串拼接(或字符串与数字拼接),直接使用..。对于较大量的字符串的拼接,存入table使用table.concat来拼接性能更佳。

测试代码

比较string.format 和 拼接..

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
local tostring = tostring
local format = string.format

local function stringformat_1(str,num)
return str.." " .. num
end

local function stringformat_2(str,num)
return format("%s %d",str,num)
end

local n = 1
local function getargs()
return tostring(n),n
end

collectgarbage("collect")
collectgarbage("stop")

local a,b
a = os.clock()

for i = 1,1000000 do

-- local str = stringformat_1(getargs()) -- case 1
local str = stringformat_2(getargs()) -- case 2

end

b=os.clock()
print("cost time " .. b - a)

local c,d
c= collectgarbage("count")
collectgarbage("collect")
d = collectgarbage("count")

print("gc " .. c - d)

运行以上代码得到case1和case2的输出分别为:

1
2
3
4
5
6
7
//case 1 [better]
cost time 1.222692
gc 0.2373046875

//case 2
cost time 1.533907
gc 0.9404296875

接下来是拼接..table.concat

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
40
41
local unpack = unpack or table.unpack

local function stringconcat_1(...)
local args = {...}
local ret = ""
for i,v in ipairs(args) do
ret = ret .. v
end
return ret
end

local function stringconcat_2(...)
local args = {...}
local ret = table.concat(args)
return ret
end

local t={}
for i = 1,10000 do
t[i] = tostring(i)
-- t[i] = ""
end

collectgarbage("collect")
collectgarbage("stop")

local a,b
a = os.clock()

local str = stringconcat_1(unpack(t)) -- case 3
-- local str = stringconcat_2(unpack(t)) -- case 4

b=os.clock()
print("cost time " .. b - a)

local c,d
c= collectgarbage("count")
collectgarbage("collect")
d = collectgarbage("count")

print("gc " .. c - d)

运行以上代码得到case3和case4的输出分别为:

1
2
3
4
5
6
7
//case 3
cost time 0.187638
gc 185725.85449219

//case 4 [better]
cost time 0.001454
gc 595.0361328125

分析

..拼接函数在lvm.c中定义:

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
void luaV_concat (lua_State *L, int total, int last) {
do {
StkId top = L->base + last + 1;
int n = 2; /* number of elements handled in this pass (at least 2) */
if (!(ttisstring(top-2) || ttisnumber(top-2)) || !tostring(L, top-1)) {
if (!call_binTM(L, top-2, top-1, top-2, TM_CONCAT))
luaG_concaterror(L, top-2, top-1);
} else if (tsvalue(top-1)->len == 0) /* second op is empty? */
(void)tostring(L, top - 2); /* result is first op (as string) */
else {
/* at least two string values; get as many as possible */
size_t tl = tsvalue(top-1)->len;
char *buffer;
int i;
/* collect total length */
for (n = 1; n < total && tostring(L, top-n-1); n++) {
size_t l = tsvalue(top-n-1)->len;
if (l >= MAX_SIZET - tl) luaG_runerror(L, "string length overflow");
tl += l;
}
buffer = luaZ_openspace(L, &G(L)->buff, tl);
tl = 0;
for (i=n; i>0; i--) { /* concat all strings */
size_t l = tsvalue(top-i)->len;
memcpy(buffer+tl, svalue(top-i), l);
tl += l;
}
setsvalue2s(L, top-n, luaS_newlstr(L, buffer, tl));
}
total -= n-1; /* got `n' strings to create 1 new */
last -= n-1;
} while (total > 1); /* repeat until only 1 result left */
}

else里边是最核心的逻辑。luaZ_openspace背后会调用C函数realloc&G(L)->buff是虚拟机上分配的一段用于拼接字符串(string concatentation)的临时空间。这里所做的就是内存分配与拷贝,最后再将buffer转为string放到栈里。

table.concat()是table库的函数,定义在ltablib.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static int tconcat (lua_State *L) {
luaL_Buffer b;
size_t lsep;
int i, last;
const char *sep = luaL_optlstring(L, 2, "", &lsep);
luaL_checktype(L, 1, LUA_TTABLE);
i = luaL_optint(L, 3, 1);
last = luaL_opt(L, luaL_checkint, 4, luaL_getn(L, 1));
luaL_buffinit(L, &b);
for (; i < last; i++) {
addfield(L, &b, i);
luaL_addlstring(&b, sep, lsep);
}
if (i == last) /* add last value (if interval was not empty) */
addfield(L, &b, i);
luaL_pushresult(&b);
return 1;
}

使用了这样一个东西luaL_Buffer

1
2
3
4
5
6
typedef struct luaL_Buffer {
char *p; /* current position in buffer */
int lvl; /* number of strings in the stack (level) */
lua_State *L;
char buffer[LUAL_BUFFERSIZE];
} luaL_Buffer;

内部维护了一个buffer和一个lvl,当buffer被写满时会把string存入栈,然后清空buffer。最后concat完成时,会把buffer中的内容和已存入栈中的string(可能会有多个)使用lua_concat拼接在一起。lua_concat会调用到前边的luaV_concat

string.format()是string库的函数,定义在lstrlib.c

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
static int str_format (lua_State *L) {
int top = lua_gettop(L);
int arg = 1;
size_t sfl;
const char *strfrmt = luaL_checklstring(L, arg, &sfl);
const char *strfrmt_end = strfrmt+sfl;
luaL_Buffer b;
luaL_buffinit(L, &b);
while (strfrmt < strfrmt_end) {
if (*strfrmt != L_ESC)
luaL_addchar(&b, *strfrmt++);
else if (*++strfrmt == L_ESC)
luaL_addchar(&b, *strfrmt++); /* %% */
else { /* format item */
char form[MAX_FORMAT]; /* to store the format (`%...') */
char buff[MAX_ITEM]; /* to store the formatted item */
if (++arg > top)
luaL_argerror(L, arg, "no value");
strfrmt = scanformat(L, strfrmt, form);
switch (*strfrmt++) {
case 'c': {
sprintf(buff, form, (int)luaL_checknumber(L, arg));
break;
}
case 'd': case 'i': {
addintlen(form);
sprintf(buff, form, (LUA_INTFRM_T)luaL_checknumber(L, arg));
break;
}
case 'o': case 'u': case 'x': case 'X': {
addintlen(form);
sprintf(buff, form, (unsigned LUA_INTFRM_T)luaL_checknumber(L, arg));
break;
}
case 'e': case 'E': case 'f':
case 'g': case 'G': {
sprintf(buff, form, (double)luaL_checknumber(L, arg));
break;
}
case 'q': {
addquoted(L, &b, arg);
continue; /* skip the 'addsize' at the end */
}
case 's': {
size_t l;
const char *s = luaL_checklstring(L, arg, &l);
if (!strchr(form, '.') && l >= 100) {
/* no precision and string is too long to be formatted;
keep original string */
lua_pushvalue(L, arg);
luaL_addvalue(&b);
continue; /* skip the `addsize' at the end */
}
else {
sprintf(buff, form, s);
break;
}
}
default: { /* also treat cases `pnLlh' */
return luaL_error(L, "invalid option " LUA_QL("%%%c") " to "
LUA_QL("format"), *(strfrmt - 1));
}
}
luaL_addlstring(&b, buff, strlen(buff));
}
}
luaL_pushresult(&b);
return 1;
}

也借助了luaL_Buffer,同时内部又分配了两个Char数组formbuff,使用sprintf来格式化字符串。逐个解析参数并将buff写入luaL_Buffer。最后将得到的字符串写到栈中。

通过对比上边三种拼接字符串的方式可知:

  • 对于简单的字符串拼接或字符串与数字的拼接,直接使用..就好,使用string.format的方式会增加更多格式解析、内存分配开销,然而其最终使用的还是..string.format更适合去处理较为复杂的带格式的字符串处理。

  • 对于字符串的反复拼接,使用table.concat会更高效。每次调用..都会产生内存的分配或者拷贝,且中间会产生很多临时的字符串(额外的GC),而使用table.concat则是将拼接动作放到最后一次性完成,借助luaL_Buffer减少了调用lua_concat的次数,并且避免了合并期间产生的额外的字符串(额外的GC)。

创建字符串时:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
GCObject *o;
unsigned int h = cast(unsigned int, l); /* seed */
size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */
size_t l1;
for (l1=l; l1>=step; l1-=step) /* compute hash */
h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
o != NULL;
o = o->gch.next) {
TString *ts = rawgco2ts(o);
if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
/* string may be dead */
if (isdead(G(L), o)) changewhite(o);
return ts;
}
}
return newlstr(L, str, l, h); /* not found */
}

如果在string的hash表中包含有与要创建的字符串相同的字符串(没有被GC回收掉),则直接复用,否则才会创建新的。

插入数据

三种插入数据的方式对比:

table.insert,或者t[#t+1] = xxx,再或者记录表的长度,每次插入新数据时使用t[n+1] = xxx。结果证明,对于连续的插入数据,最后一种方法最佳。

测试代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
local function insert_1(t,data)
for i,v in ipairs(data) do
table.insert(t,v)
end
return t
end


local function insert_2(t,data)
for i,v in ipairs(data) do
t[#t + 1] = v
end
return t
end


local function insert_3(t,data)
local n = #t
for i,v in ipairs(data) do
n = n + 1
t[n] = v
end
return t
end


local data = {}
for i = 1,1000000 do
data[i] = i
end



collectgarbage("collect")
collectgarbage("stop")

local a,b
a = os.clock()

local t = {}

-- insert_1(t,data) -- case 1

-- insert_2(t,data) -- case 2

insert_3(t,data) -- case 3


b=os.clock()
print("cost time " .. b - a)

local c,d
c= collectgarbage("count")
collectgarbage("collect")
d = collectgarbage("count")

print("gc " .. c - d)

运行以上代码得到case1、case2和case3的输出分别为:

1
2
3
4
5
6
7
8
9
10
11
// case 1
cost time 0.50343
gc 0.5576171875

// case 2
cost time 0.365689
gc 0.5595703125

// case 3 [best]
cost time 0.169078
gc 0.5595703125

分析

table.insert的实现:

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
static int tinsert (lua_State *L) {
int e = aux_getn(L, 1) + 1; /* first empty element */
int pos; /* where to insert new element */
switch (lua_gettop(L)) {
case 2: { /* called with only 2 arguments */
pos = e; /* insert new element at the end */
break;
}
case 3: {
int i;
pos = luaL_checkint(L, 2); /* 2nd argument is the position */
if (pos > e) e = pos; /* `grow' array if necessary */
for (i = e; i > pos; i--) { /* move up elements */
lua_rawgeti(L, 1, i-1);
lua_rawseti(L, 1, i); /* t[i] = t[i-1] */
}
break;
}
default: {
return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));
}
}
luaL_setn(L, 1, e); /* new size */
lua_rawseti(L, 1, pos); /* t[pos] = v */
return 0;
}

在向其中插入数据时(暂时只考虑两参数,即向末尾插入新的数据),每次插入数据都会调用aux_getn方法(会调用luaH_getn),用于获取table的长度。事实上#这个运算符(OP_LEN)也是调用的luaH_getn。也就是说其实table.insert的内部会有一次类似于t[#t+1] = xxx这样的操作。以下是luaH_getn的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** Try to find a boundary in table `t'. A `boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
int luaH_getn (Table *t) {
unsigned int j = t->sizearray;
if (j > 0 && ttisnil(&t->array[j - 1])) {
/* there is a boundary in the array part: (binary) search for it */
unsigned int i = 0;
while (j - i > 1) {
unsigned int m = (i+j)/2;
if (ttisnil(&t->array[m - 1])) j = m;
else i = m;
}
return i;
}
/* else must find a boundary in hash part */
else if (t->node == dummynode) /* hash part is empty? */
return j; /* that is easy... */
else return unbound_search(t, j);
}

首先是使用二分查找来获取array部分的边界(前边说到array部分长度总是2的倍数,没有数据的部分会被nil填充),否则如果没有hash部分(array部分为空或者array部分刚好填满),直接返回array长度,再否则就调用unbound_search(查找hash部分)。整体来看这个获取长度的开销还是不小的,因此缓存下来长度,并且在插入数据时直接以n+1为key,是一种很高效的做法。

REFERENCE

http://www.lua.org/gems/sample.pdf

https://www.lua.org/source/5.1/

LUA程序设计(第2版)

http://www.cppblog.com/airtrack/archive/2012/09/19/191233.html