8

Lua table 如何实现最快的 insert?

 3 years ago
source link: https://ms2008.github.io/2020/03/10/luajit-table-insert/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

前两天群里有个朋友贴出一段代码：

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 t
end

用来拷贝 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] = 0 is faster than table.insert(t, 0).

local t = {}

for i=1,1e7 do
    t[#t+1] = i
end

优化后，LuaJIT 2.1 耗时：1836ms

似乎和 CASE-1 并没有明显差距，lua-resty-waf 的作者指出了其中的问题：

loop-comp.png

通过对比二者的 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 + 1
end

结果 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 + 1
end

结果 LuaJIT 2.1 耗时：30ms

性能进一步提升到 64 倍！！！还可以更快吗？


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK