Lua笔记 效率&性能

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

评测方法

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

获取运行时间

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

local a, b
a = os.clock()

-- do something

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

获取内存用量

collectgarbage("stop")

collectgarbage("collect")

print(collectgarbage("count"))

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

stop 停止自动GC
collect 执行一次完整的GC循环
count 返回当前内存用量，以k为单位

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

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

测试代码

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的输出分别为：

//case 1
cost time = 2.10697

//case 2 [better]
cost time = 1.260123

分析

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

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

尾递归调用

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

测试代码

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的输出分别为：

//case 1  [better]
now n = 100000
0.020423

//case 2
now n = 100000
0.050295

分析

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

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

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_CALL和OP_TAILCALL），二者很相似，都是通过luaD_precall执行函数调用，并根据调用了Lua函数还是C函数进行处理。在OP_TAILCALL中，调用Lua函数之后，可以看到有这样的操作：取到“previous frame”即之前的调用信息CallInfo *ci，使用新增的CallInfo中的信息取替换ci中的内容，并移除新增的CallInfo。直接复用CallInfo从而调用函数不增加栈的深度。

减少rehash

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

测试代码


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的输出分别为：

//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 和拼接..：

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的输出分别为：

//case 1 [better]
cost time  1.222692
gc  0.2373046875

//case 2
cost time  1.533907
gc  0.9404296875

接下来是拼接.. 和 table.concat：

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的输出分别为：

//case 3
cost time  0.187638
gc  185725.85449219

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

分析

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

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

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：

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：

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数组form和buff，使用sprintf来格式化字符串。逐个解析参数并将buff写入luaL_Buffer。最后将得到的字符串写到栈中。

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

对于简单的字符串拼接或字符串与数字的拼接，直接使用..就好，使用string.format的方式会增加更多格式解析、内存分配开销，然而其最终使用的还是..。string.format更适合去处理较为复杂的带格式的字符串处理。
对于字符串的反复拼接，使用table.concat会更高效。每次调用..都会产生内存的分配或者拷贝，且中间会产生很多临时的字符串（额外的GC），而使用table.concat则是将拼接动作放到最后一次性完成，借助luaL_Buffer减少了调用lua_concat的次数，并且避免了合并期间产生的额外的字符串（额外的GC）。

创建字符串时：

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。结果证明，对于连续的插入数据，最后一种方法最佳。

测试代码

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的输出分别为：

// 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的实现：

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的实现：

/*
** 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

Aillieo Collection

Lua笔记效率&性能

评测方法

获取运行时间

获取内存用量

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

测试代码

分析

尾递归调用

测试代码

分析

减少rehash

测试代码

分析

字符串效率

测试代码

分析

插入数据

测试代码

分析

REFERENCE