Lua 5.3 hashint函数缺陷导致遍历table性能非常差

标签：5.3 hash lua hashint Lua key 5.4

最近发现线上有个服务器某些逻辑耗时比较久，问了下同事，他告诉我是因为lua的pairs函数很慢导致的。

“啊！不至于吧，这数据量才多少”我一脸诧异，记忆中Lua不至于慢到这种程度，遍历个几十万的table速度还是很快的，而我们线上的这个table数据量才几万。

他把线上的数据导了出来，做了一个测试，发现仅仅遍历一个5万多table，Lua确实花了将近3秒多的时间。

整个程序非常简单，大概就是

local tbl = {}
-- 里面保存了5万多个key，什么都不做，仅遍历
for _ in pairs(tbl) do end

就这样，它也能花将近3秒的时间，实在让人大跌眼镜。

考虑到线上的程序是从Lua 5.1升级到Lua 5.3的，而我们生成的id都是64位整数，我的直觉是5.3加入的64位整数出了bug。然而我随机了6万个数字做key，发现遍历还是挺快的，大约3毫秒左右。这说明Lua本身是没有问题的，可能是我们线上程序的key触发了某个bug。

于是我又下载了Lua 5.1和Lua 5.4进行测试，发现这两个版本是没问题的，耗时都在毫秒级别。

下载Lua 5.3.6的源码，修改src目录里的Makefile，使用-O0 -g3进行编译。再用valgrind --tool=callgrind ./lua test.lua跑一下性能测试，发现在程序在luaH_next -->> findindex -->>luaV_equalobj这里耗时很久。

从5.1到5.4版本，Lua table的基础设定都没有变化。整个table分为两部分，一部分是数组，一部分是hash。运行-g3编译的lua，通过gdb断点查看，5.3和5.4版本在当前测试的程序中，都没有使用数组。应该是hash的问题。那就剩下两种可能，一种是findindex逻辑有问题，还有一种就是hash逻辑有问题。

通过对比两个版本的findindex函数，虽然有细小的差异，但基本逻辑就是判断是否在数组中，如果不在，则进行hash，根据hash值从hash结构里取对象。

// ltable.c

static Node *mainposition (const Table *t, int ktt, const Value *kvl) {
  switch (withvariant(ktt)) {
    case LUA_VNUMINT:
      return hashint(t, ivalueraw(*kvl));
    case LUA_VNUMFLT:
      return hashmod(t, l_hashfloat(fltvalueraw(*kvl)));
    case LUA_VSHRSTR:
      return hashstr(t, tsvalueraw(*kvl));
    case LUA_VLNGSTR:
      return hashpow2(t, luaS_hashlongstr(tsvalueraw(*kvl)));
    case LUA_VFALSE:
      return hashboolean(t, 0);
    case LUA_VTRUE:
      return hashboolean(t, 1);
    case LUA_VLIGHTUSERDATA:
      return hashpointer(t, pvalueraw(*kvl));
    case LUA_VLCF:
      return hashpointer(t, fvalueraw(*kvl));
    default:
      return hashpointer(t, gcvalueraw(*kvl));
  }
}

static const TValue *getgeneric (Table *t, const TValue *key, int deadok) {
  Node *n = mainpositionTV(t, key);
  for (;;) {  /* check whether 'key' is somewhere in the chain */
    if (equalkey(key, n, deadok))
      return gval(n);  /* that's it */
    else {
      int nx = gnext(n);
      if (nx == 0)
        return &absentkey;  /* not found */
      n += nx;
    }
  }
}

static unsigned int findindex (lua_State *L, Table *t, TValue *key,
                               unsigned int asize) {
  unsigned int i;
  if (ttisnil(key)) return 0;  /* first iteration */
  i = ttisinteger(key) ? arrayindex(ivalue(key)) : 0;
  if (i - 1u < asize)  /* is 'key' inside array part? */
    return i;  /* yes; that's the index */
  else {
    const TValue *n = getgeneric(t, key, 1);
    if (unlikely(isabstkey(n)))
      luaG_runerror(L, "invalid key to 'next'");  /* key not found */
    i = cast_int(nodefromval(n) - gnode(t, 0));  /* key index in hash table */
    /* hash elements are numbered after array ones */
    return (i + 1) + asize;
  }
}

那剩下一种可能就是hash有问题了。lua有几个hash函数：hashstr、hashboolean、hashint、hashpointer等等，分别对应不同的类型作key。由于测试中使用的都是int64的整数作为key，那对比了一下5.3和5.4版本的hashint函数，发现他们真的不一样。

// lua 5.3.6
#define lmod(s,size) \
	(check_exp((size&(size-1))==0, (cast_int((s) & ((size)-1)))))
#define hashpow2(t,n)		(gnode(t, lmod((n), sizenode(t))))

#define hashint(t,i)		hashpow2(t, i)

// lua 5.4.4

#define sizenode(t)	(twoto((t)->lsizenode))

#define hashmod(t,n)	(gnode(t, ((n) % ((sizenode(t)-1)|1))))

static Node *hashint (const Table *t, lua_Integer i) {
  lua_Unsigned ui = l_castS2U(i);
  if (ui <= (unsigned int)INT_MAX)
    return hashmod(t, cast_int(ui));
  else
    return hashmod(t, ui);
}

sizenode(t)是取当前table的节点数量，当插入一个元素到table时，无论是插入到数组部分，还是到hash部分，如果是超过了预留的节点，那这个节点就会相应地增加，然后进行rehash，所有元素进行重排。因此遍历table的时候，这个节点数量是不变的。从gdb调试的堆栈查到，Lua 5.3运行这个测试程序时这个值为16。那它的这个hash逻辑就变成了

// 假如现在有一个key为100，当前sizenode(t)为16

hashint(t,i);
// 宏展开为
(gnode(t, lmod(100, 16)));
// 宏展开为
(gnode(t, 100 & 15));
// 宏展开为
t->node[100 & 15];

所以，Lua 5.3的hashint函数可以总结为： key & sizenode(t)。大多数语言的hash函数(java、c++之类)，基本就两个要点：一是效率高，因为插入、查找都要频繁调用hash，因此这个函数执行效率一定要高；二是冲突少，如果冲突太多，hash就会往数组那边退化导致效率下降。Lua 5.3的这个hash函数，效率是足够高了，可冲突就多得不行了。由于需要考虑内存占用的问题，sizenode(t)的值肯定不会太大(比如测试的例子中，值为16)。key与sizenode(t)做一个与操作基本就是取低N位。假如有几个数，他们的低位是一样的，但高位不一样，那不就冲突了吗？

为了验证这个问题，我特意重新设计了测试程序

local random_key = {}
for i = 1, 60000 do
        local k = math.random(1000000, 10000000)
        random_key[k] = true
end

local count = 0
local beg = os.clock()
for _ in pairs(random_key) do count = count + 1 end
print("random key", os.clock() - beg, count)


local tbl = {}
for i = 1, 60000 do
        local k = (i << 32) | 10086
        tbl[k] = true
end

local beg = os.clock()
for _ in pairs(tbl) do end
print("test done", os.clock() - beg, _VERSION)

结果跑下来，这些数字作key的话，就真的很慢。可以看到，随机数字的话，大约为3ms，这些特意生成的数字，Lua 5.3跑出了14s。

debian:~/local_code/lua-5.3.6/src$ lua test.lua 
random key      0.003292        59805
test done       3.368816        Lua 5.4
debian:~/local_code/lua-5.3.6/src$ ./lua test.lua 
random key      0.003773        59811
test done       14.956801       Lua 5.3

采用高低位合并成一个64位整数来生成id，是很多业务中常用的逻辑，然则这里就踩坑了。
后来，通过把Lua 5.4.4的hash函数移植到Lua 5.3，重新编译后再测试就正常了。不过我建议还是直接升级到Lua 5.4.4，不用改源码。

细心的读者可能会发现，上面的测试结果中，Lua 5.4虽然比Lua 5.3快，但也花了3s多，这明显是不正常的。是的，这确实是有问题。这是因为我这系统中的Lua是很久之前安装的，虽然是5.4的版本，但我不太清楚具体是哪个版本，我翻了下本地的一个源码包，可能是5.4.2，这个版本的hash函数还是和Lua 5.3是一样的。我重新下了一个5.4.4的版本编译后执行，结果才是正常的

debian:~/local_code/lua-5.4.4/src$ ./lua test.lua 
random key      0.003401        59794
test done       0.002218        Lua 5.4

这里又有一个问题，那就是Lua 5.4.2的hash函数即使和Lua 5.3一样，为什么它还是要比5.3要快很多。关注过Lua版本的大概是知道原因的。Lua 5.1是一个经典的版本，发布时间长，使用的人也多，优化得很好。到了5.3版本，加入了int64的支持，做了比较大的改动，性能下降比较多。到了5.4，又做了很多优化，连lua的虚拟机都重构了，所以即使同样的算法，执行效率也比5.3高一些。根据网上的一些测试结果，比5.1都要好。

这里我不明白的是为什么Lua 5.3会选择这样一个hash函数，因为从5.1和5.4.4的hash函数是一样的，唯独5.3采用这么一个性能比较差的算法。不过由于5.3版本是老版本了，我也不想再去研究这个。

标签：5.3,hash,lua,hashint,Lua,key,5.4
From： https://www.cnblogs.com/coding-my-life/p/16990992.html