最近發現線上有個服務器某些邏輯耗時比較久，問了下同事，他告訴我是因為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版本是老版本了，我也不想再去研究這個。
浙公網安備 33010602011771號