Lua table 如何實現最快的 insert?
- 2020 年 3 月 18 日
- 筆記
前兩天群里有個朋友貼出一段代碼：
function _M.table_keys(self, tb) if type(tb) ~= "table" then ngx.log(ngx.WARN, type(tb) .. "was given to table_keys") return tb end local t = {} for key,_ in pairs(tb) do table.insert(t, key) end return tend
用來拷貝 HTTP Header，是這樣來調用的：
request.REQUEST_HEADERS_NAMES = twaf_func:table_keys(request_headers)
但是他發現，這個操作很耗性能。加了這句，就少了 "5000" 並發。
且不管他這 "5000" 並發是怎麼計算出來的。今天，我們就來探討下 table insert 最快的方法。
CASE 1
題外話：根據 Lua Wiki 上的優化建議，local 化的變量會更快。但是這在 LuaJIT 上幾乎已經沒有了優勢。
local t = {}local table_insert = table.insert for i=1,1e7 do table_insert(t, i)end
最經典的寫法，LuaJIT 2.1 耗時：1838ms
CASE 2
根據 Lua Wiki 上的優化建議 Lua 5.1 Optimization Notes:
Short inline expressions can be faster than function calls.
t[#t+1] = 0is faster thantable.insert(t, 0).
local t = {} for i=1,1e7 do t[#t+1] = iend
優化後，LuaJIT 2.1 耗時：1836ms
似乎和 CASE-1 並沒有明顯差距，lua-resty-waf 的作者指出了其中的問題：
通過對比二者的 trace log，可以發現它們幾乎沒有明顯區別，但是都調用了 lj_tab_len 來獲取 t 的長度，這個操作的時間複雜度為 O(log n)，那麼完成整個 insert 動作的時間複雜度就是 O(n log n)，是影響二者耗時的主要原因。
CASE 3
我們嘗試將 lj_tab_len 幹掉，自己來計算 t 的長度。那麼理論上完成整個 insert 動作的時間複雜度就簡化為了 O(n)。
local t = {}local c = 1 for i=1,1e7 do t[c] = i c = c + 1end
結果 LuaJIT 2.1 耗時：57ms
一個簡單的優化，性能就提升了驚人的 32 倍！
CASE 4
CASE-3 的性能已經非常好了，但還是漏了一個優化的點：table 的擴容。
table 的擴容用的是
hashpow2，它是不小於 table hash or array 區域數量的 2^n^ 形式的整數
local table_new = require "table.new" local t = table_new(1e7, 0)local c = 1 for i=1,1e7 do t[c] = i c = c + 1end
結果 LuaJIT 2.1 耗時：30ms
性能進一步提升到 64 倍！！！還可以更快嗎？
參考文獻
•Optimisation Coding Tips•Fast(er)(est) Table Inserts in LuaJIT•Performance of array creation in Lua
