前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Lua table 如何实现最快的 insert?

Lua table 如何实现最快的 insert?

作者头像
poslua
发布2020-03-18 08:34:09
2.5K4
发布2020-03-18 08:34:09
举报
文章被收录于专栏:poslua

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

代码语言:javascript
复制
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,是这样来调用的:

代码语言:javascript
复制
request.REQUEST_HEADERS_NAMES = twaf_func:table_keys(request_headers)

但是他发现,这个操作很耗性能。加了这句,就少了 "5000" 并发。

且不管他这 "5000" 并发是怎么计算出来的。今天,我们就来探讨下 table insert 最快的方法。

CASE 1

题外话:根据 Lua Wiki 上的优化建议,local 化的变量会更快。但是这在 LuaJIT 上几乎已经没有了优势。

代码语言:javascript
复制
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).

代码语言:javascript
复制
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)

代码语言:javascript
复制
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^ 形式的整数

代码语言:javascript
复制
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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 poslua 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • CASE 1
  • CASE 2
  • CASE 3
  • CASE 4
  • 参考文献
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档