Lua pairs与ipairs效率分析

介于大家目前有些人比较关心 lua table中pairs 和 ipairs的效率问题, 特此研究了一下... 如有不正还需指出..

首先来看下 lua中table的结构定义:

table中分为2个存储空间, 一个是线性数组空间(TValue *array), 和一个hash空间(Node *node)

当我们使用 pairs 和 ipairs 会产生两种不同的迭代器, 一个仅仅遍历数组, 一个遍历所有的值

所以, 当调用ipairs的时候, 在线性数组中遇到第一个nil时便停止遍历, 不管后面还是否有值, 这点在遍历的时候要格外注意

而pairs的迭代器会调用lua_next, lua_next的实现:

这个函数会根据top信息调用luaH_next获取当前table中的下一组键值, 那么关键就在luaH_next中, 来看看这个函数的实现:

我们粗略的可以看到, 这个函数会先计算索引位置, 并根据该位置优先从线性数组中查找, 如果没有找到, 再从hash表中查找, 所以如果用pairs遍历array, 实则和ipairs等效, 并无差异.

所以, 由上面的分析, 如果我们明确table中的数据全部存放在线性数组中, 调用ipairs或者pairs均可, 并无太大差异(注意ipairs时中间不要出现nil值, 否则会导致遍历中断), 如果我们明确遍历hash表中的值, 则使用pairs, 其效率会较遍历array中的差

简单测试遍历500 000 000个array or hash value的效率:

local array = {}
for i = 1, 500000000 dotable.insert(array, i)
endlocal startTime = os.time()
for i, v in pairs(array) doend
print(string.format("pairs time : %d", os.time() - startTime))startTime = os.time()
for i, v in ipairs(array) doend
print(string.format("ipairs time : %d", os.time() - startTime))