Lua中table类型变量的容量扩增代价很高

Lua的table是由数组部分(array part)哈希部分(hash part)组成。数组部分索引的key是1~n的整数,哈希部分是一个哈希表(open address table)。

向table中插入数据时,如果已经满了,Lua会重新设置数据部分或哈希表的大小,容量是成倍增加的,哈希部分还要对哈希表中的数据进行整理。

需要特别注意的没有赋初始值的table,数组和部分哈希部分默认容量为0。

local a = {}     --容量为0
a[1] = true      --重设数组部分的size为1
a[2] = true      --重设数组部分的size为2
a[3] = true      --重设数组部分的size为4

local b = {}     --容量为0
b.x = true       --重设哈希部分的size为1
b.y = true       --重设哈希部分的size为2
b.z = true       --重设哈希部分的size为4

因为容量是成倍增加的,因此越是容量小的table越容易受到影响,每次增加的容量太少,很快又满。

对于存放少量数据的table,要在创建table变量时,就设置它的大小,例如:

table_size_predefined.lua:

for i = 1, 1000000 do
  local a = {true, true, true}   -- table变量a的size在创建是确定
  a[1] = 1; a[2] = 2; a[3] = 3   -- 不会触发容量重设
end

如果创建空的table变量,插入数据时,会触发容量重设,例如:

table_size_undefined.lua:

for i = 1, 1000000 do
  local a = {}                   -- table变量a的size为0
  a[1] = 1; a[2] = 2; a[3] = 3   -- 触发3次容量重设
end

后者耗时几乎是前者的两倍:

➜  03-performance git:(master) ✗ time lua-5.1 table_size_predefined.lua
lua-5.1 table_size_predefined.lua  4.17s user 0.01s system 99% cpu 4.190 total

➜  03-performance git:(master) ✗ time lua-5.1 table_size_undefined.lua
lua-5.1 table_size_undefined.lua  7.63s user 0.01s system 99% cpu 7.650 total

对于哈希部分也是如此,用下面的方式初始化:

local b = {x = 1, y = 2, z = 3}