performance - 在我的速度测试中，Lua 表哈希索引比数组索引更快。为什么？

Question

我正在做一些测试，看看我可以在哪里提高我的 lua 代码的性能。

我正在阅读这份文件:https://www.lua.org/gems/sample.pdf
我认为使用整数作为表索引应该快得多，因为它使用表的数组部分并且不需要散列。

所以我写了这个测试程序:

    print('local x=0 local y=0 local z=0')
    local x=0 local y=0 local z=0
    t0 = os.clock()
    for i=1,1e7 do
        x = 1
        y = 2
        z = 3
    end
    print(os.clock()-t0 .. "\n")


    print("tab = {1,2,3}")
    tab = {1,2,3}
    t0 = os.clock()
    for i=1,1e7 do
        tab[1] = 1
        tab[2] = 2
        tab[3] = 3
    end
    print(os.clock()-t0 .. "\n")


    print("tab = {[1]=1,[2]=2,[3]=3}")
    tab = {[1]=1,[2]=2,[3]=3}
    t0 = os.clock()
    for i=1,1e7 do
        tab[1] = 1
        tab[2] = 2
        tab[3] = 3
    end
    print(os.clock()-t0 .. "\n")


    print("tab = {a=1,b=2,c=3}")
    tab = {a=1,b=2,c=3}
    t0 = os.clock()
    for i=1,1e7 do
        tab.a = 1
        tab.b = 2
        tab.c = 3
    end
    print(os.clock()-t0 .. "\n")


    print('tab = {["bli"]=1,["bla"]=2,["blu"]=3}')
    tab = {["bli"]=1,["bla"]=2,["blu"]=3}
    t0 = os.clock()
    for i=1,1e7 do
        tab["bli"] = 1
        tab["bla"] = 2
        tab["blu"] = 3
    end
    print(os.clock()-t0 .. "\n")


    print("tab = {verylongfieldname=1,anotherevenlongerfieldname=2,superincrediblylongfieldname=3}")
    tab = {verylongfieldname=1,anotherevenlongerfieldname=2,superincrediblylongfieldname=3}
    t0 = os.clock()
    for i=1,1e7 do
        tab.verylongfieldname = 1
        tab.anotherevenlongerfieldname = 2
        tab.superincrediblylongfieldname = 3
    end
    print(os.clock()-t0 .. "\n")


    print('local f = function(p1, p2, p3)')
    local f = function(p1, p2, p3)
        x = p1
        y = p2
        z = p3
        return x,y,z
    end

    local a=0
    local b=0
    local c=0
    t0 = os.clock()
    for i=1,1e7 do
        a,b,c = f(1,2,3)
    end
    print(os.clock()-t0 .. "\n")


    print('local g = function(params)')
    local g = function(params)
        x = params.p1
        y = params.p2
        z = params.p3
        return {x,y,z}
    end

    t0 = os.clock()
    for i=1,1e7 do
        t = g{p1=1, p2=2, p3=3}
    end
    print(os.clock()-t0 .. "\n")

我已经按照我预期会增加的时间消耗来订购块。 (我不确定函数调用，那只是一个测试。)但这里是令人惊讶的结果:

    local x=0 local y=0 local z=0
    0.093613

    tab = {1,2,3}
    0.678514

    tab = {[1]=1,[2]=2,[3]=3}
    0.83678

    tab = {a=1,b=2,c=3}
    0.62888

    tab = {["bli"]=1,["bla"]=2,["blu"]=3}
    0.733916

    tab = {verylongfieldname=1,anotherevenlongerfieldname=2,superincrediblylongfieldname=3}
    0.536726

    local f = function(p1, p2, p3)
    0.475592

    local g = function(params)
    3.576475

甚至应该导致最长散列过程的长字段名称也比使用整数访问数组更快。难道我做错了什么？

Answer 1

您的文档第6页(实际第20页)linked解释你所看到的。

If you write something like {[1] = true, [2] = true, [3] = true}, however, Lua is not smart enough to detect that the given expressions (literal numbers, in this case) describe array indices, so it creates a table with four slots in its hash part, wasting memory and CPU time.

您只有在 时才能获得阵列部分的主要好处。分配 不使用键的表。

table = {1,2,3}

如果您正在读取/写入已存在的表或数组，您将不会看到处理时间的大偏差。

文档中的例子包括for循环中表的创建

for i = 1, 1000000 do
    local a = {true, true, true}
    a[1] = 1; a[2] = 2; a[3] = 3
end

循环内所有局部变量的结果。编辑:如 siffiejoe 所指出的，将长字符串加长到 40 个字节

local x=0 local y=0 local z=0
0.18

tab = {1,2,3}
3.089

tab = {[1]=1,[2]=2,[3]=3}
4.59

tab = {a=1,b=2,c=3}
3.79

tab = {["bli"]=1,["bla"]=2,["blu"]=3}
3.967

tab = {verylongfieldnameverylongfieldnameverylongfieldname=1,anotherevenlongerfieldnameanotherevenlongerfieldname=2,superincrediblylongfieldnamesuperincrediblylongfieldname=3}
4.013

local f = function(p1, p2, p3)
1.238

local g = function(params)
6.325

此外，lua 对不同的键类型以不同的方式执行散列。

源代码可以在这里查看 5.2.4 ltable.c ，这包含我将要讨论的代码。
mainposition函数处理关于要执行哪个散列的决策

/*
** returns the `main' position of an element in a table (that is, the index
** of its hash value)
*/
static Node *mainposition (const Table *t, const TValue *key) {
  switch (ttype(key)) {
    case LUA_TNUMBER:
      return hashnum(t, nvalue(key));
    case LUA_TLNGSTR: {
      TString *s = rawtsvalue(key);
      if (s->tsv.extra == 0) {  /* no hash? */
        s->tsv.hash = luaS_hash(getstr(s), s->tsv.len, s->tsv.hash);
        s->tsv.extra = 1;  /* now it has its hash */
      }
      return hashstr(t, rawtsvalue(key));
    }
    case LUA_TSHRSTR:
      return hashstr(t, rawtsvalue(key));
    case LUA_TBOOLEAN:
      return hashboolean(t, bvalue(key));
    case LUA_TLIGHTUSERDATA:
      return hashpointer(t, pvalue(key));
    case LUA_TLCF:
      return hashpointer(t, fvalue(key));
    default:
      return hashpointer(t, gcvalue(key));
  }
}

当键是 Lua_Number 时，我们调用 hashnum

/*
** hash for lua_Numbers
*/
static Node *hashnum (const Table *t, lua_Number n) {
  int i;
  luai_hashnum(i, n);
  if (i < 0) {
    if (cast(unsigned int, i) == 0u - i)  /* use unsigned to avoid overflows */
      i = 0;  /* handle INT_MIN */
    i = -i;  /* must be a positive value */
  }
  return hashmod(t, i);
}

以下是其他类型的其他哈希实现:

#define hashpow2(t,n)           (gnode(t, lmod((n), sizenode(t))))

#define hashstr(t,str)          hashpow2(t, (str)->tsv.hash)
#define hashboolean(t,p)        hashpow2(t, p)


/*
** for some types, it is better to avoid modulus by power of 2, as
** they tend to have many 2 factors.
*/
#define hashmod(t,n)    (gnode(t, ((n) % ((sizenode(t)-1)|1))))


#define hashpointer(t,p)        hashmod(t, IntPoint(p))

这些散列解析为 2 个路径 hashpow2 和 hashmod。 LUA_TNUMBER使用 hashnum > hashmod 和 LUA_TSHRSTR使用 hashstr > hashpow2