Lua Performance Tips - About tables - 关于表

About tables
关于表


Usually, you do not need to know anything about how Lua implement tables to use them. Actually, Lua goes to great lengths to make sure that implementation details do not surface to the user. However, these details show themselves through the performance of table operations. So, to optimize programs that use tables (that is, practically any Lua program), it is good to know a little about how Lua implements tables.
通常，你不需要为使用表而了解有关Lua如何实现它们的任何事。实际上，Lua诉诸于极大的长度来确保不会向用户显露实现细节。然而，这些细节透过表操作的性能暴露出来。所以，要优化用到表的程序（即几乎任何Lua程序），对Lua如何实现表有一点了解会比较好。

    The implementation of tables in Lua involves some clever algorithms. Every table in Lua has two parts: the array part and the hash part. The array part stores entries with integer keys in the range 1 to n, for some particular n. (We will discuss how this n is computed in a moment.) All other entries (including integer keys outside that range) go to the hash part.
    Lua中表的实现涉及一些聪明的算法。在Lua中每个表有两部分：数组部分和散列部分。对于某些特殊的n，数组部分存储的条目带范围从1到n的整数键。（稍后我们会讨论这个n是如何计算的。）所有其他的条目（包括那个范围之外的整数键）转到散列部分。

    As the name implies, the hash part uses a hash algorithm to store and find its keys. It uses what is called an open address table, which means that all entries are stored in the hash array itself. A hash function gives the primary index of a key; if there is a collision (that is, if two keys are hashed to the same position), the keys are linked in a list, with each element occupying one array entry.
    顾名思义，散列部分用散列算法存储及查找它的键。它用的是开放地址表——所有条目存储在自身的散列数组中。散列函数给出键的主索引；如果有冲突（即两个键被散列到相同的位置），那些键被连接为一个列表，每个元素占用一个数组条目。

    When Lua needs to insert a new key into a table and the hash array is full, Lua does a rehash. The first step in the rehash is to decide the sizes of the new array part and the new hash part. So, Lua traverses all entries, counting and classifying them, and then chooses as the size of the array part the largest power of 2 such that more than half the elements of the array part are filled. The hash size is then the smallest power of 2 that can accommodate all the remaining entries (that is, those that did not fit into the array part).
    当需要向表中插入新键且散列数组是满的时候，Lua进行一次再散列。再散列的第一步是确定新数组部分和新散列部分的尺寸。所以，Lua遍历所有条目，计数并分类它们，然后选择2的最大的乘幂作为数组部分的尺寸，它使得数组部分超过半数的元素被填充。然后散列尺寸是能容纳所有剩余条目（即那些不适合数组部分的）的2的最小乘幂。

    When Lua creates an empty table, both parts have size 0 and, therefore, there are no arrays allocated for them. Let us see what happens when we run the following code:
    当Lua创建空表时，两各部分都具有0尺寸，所以，没有为它们分配数组。我们来看下当运行下面的代码时发生了什么：

local a = {}
for i = 1, 3 do
   a[i] = true
end

It starts by creating an empty table a. In the first loop iteration, the assignment a[1]=true triggers a rehash; Lua then sets the size of the array part of the table to 1 and keeps the hash part empty. In the second loop iteration, the assignment a[2]=true triggers another rehash, so that now the array part of the table has size 2. Finally, the third iteration triggers yet another rehash, growing the size of the array part to 4.
它开始于创建空表a。在第一次循环迭代中，赋值a[1]=true引发了一次再散列；Lua于是设置表的数组部分的尺寸为1并保持散列部分为空。在第二次循环迭代中，赋值a[2]=true引发了另一次再散列，所以现在表的数组部分尺寸为2.最后，第三次迭代再次引发再散列，增长数组部分的尺寸到4。


----------------------- Page 6-----------------------20


A code like
像

a = {}
a.x = 1; a.y = 2; a.z = 3

does something similar, except that it grows the hash part of the table.
这样的代码做类似的事情，除了它增长表的散列部分。

    For large tables, this initial overhead is amortized over the entire creation: While a table with three elements needs three rehashings, a table with one million elements needs only twenty. But when you create thousands of small tables, the combined overhead can be significant.
    对于大型的表，该初始化开销被整个创建（过程）分摊：虽然带有三个元素的表需要三次再散列，带一百万个元素的表只需要二十次。但是当你创建数千个小表时，总的开销就非常大了。

    Older versions of Lua created empty tables with some pre-allocated slots (four, if I remember correctly), to avoid this overhead when initializing small tables. However, this approach wastes memory. For instance, if you create millions of points (represented as tables with only two entries) and each one uses twice the memory it really needs, you may pay a high price. That is why currently Lua creates empty tables with no pre-allocated slots.
    旧版Lua创建的空表带一些预分配的存储槽（4个，如果我记得正确的话），以避免这种初始化小表的开销。但是，这种方式浪费内存。例如，如果你创建数百万个点（用只带两个条目的表描述），每一个占用实际需要内存的二倍，你会付出很高的代价。这就是为什么现在Lua创建不带预分配的存储槽的空表。

    If you are programming in C, you can avoid those rehashings with the Lua API function lua_createtable. It receives two arguments after the omnipresent lua_State: the initial size of the array part and the initial size of the hash part of the new table.3 By giving appropriate sizes to the new table, it is easy to avoid those initial rehashes. Beware, however, that Lua can only shrink a table when rehashing it. So, if your initial sizes are larger than needed, Lua may never correct your waste of space.
    如果你用C编程，可用Lua API函数lua_createtable避免那些再散列。它在随处可见的lua_State后面接收两个参数：新表的数组部分的初始尺寸和散列部分初始尺寸。3通过向新表提供合适的尺寸，很容易避免那些初始再散列。注意，无论如何，Lua只能在再散列时收缩表。所以，如果你的初始尺寸比需要的大，Lua也许永不修正你浪费的空间。

    When programming in Lua, you may use constructors to avoid those initial rehashings. When you write {true, true, true}, Lua knows beforehand that the table will need three slots in its array part, so Lua creates the table with that size. Similarly, if you write {x = 1, y = 2, z = 3}, Lua will create a table with four slots in its hash part. As an example, the next loop runs in 2.0 seconds:
    当你用Lua编程时，你可用构造器来避免那些初始再散列。当你编写{true, true, true}时，Lua预先知道表的数组部分需要三个存储槽，所以Lua创建具有那个尺寸的表。类似地，如果你编写{x = 1, y = 2, z = 3}，Lua会创建散列部分具有四个存储槽的表。作为例子，下一段循环运行了2.0秒：

for i = 1, 1000000 do
   local a = {}
   a[1] = 1; a[2] = 2; a[3] = 3
end

If we create the tables with the right size, we reduce the run time to 0.7 seconds:
如果我们创建具有正确尺寸的表，会减少运行时间为0.7秒：

for i = 1, 1000000 do
   local a = {true, true, true}
   a[1] = 1; a[2] = 2; a[3] = 3
end

    If you write something like {[1] = true, [2] = true, [3] = true}, however, Lua is not smart enough to detect that the given expressions (literal numbers, in this case) describe array indices, so it creates a table with four slots in its hash part, wasting memory and CPU time.
    然而，如果你编写类似{[1] = true, [2] = true, [3] = true}的东西，Lua并非足够聪明得检测出所给的表达式（本例是字符数字）描述了数组索引，所以它创建一个散列部分具有四个存储槽的表，浪费了内存和CPU时间。（译者注——现在的版本似乎有这么智能了。？）

-----------------------
   3 Although the rehash algorithm always sets the array size to a power of two, the array size can be any value. The hash size, however, must be a power of two, so the second argument is always rounded to the smaller power of two not smaller than the original value.
     虽然再散列算法总是设置数组尺寸为2的乘幂，数组尺寸可谓任何值。然而，散列尺寸必须是2的乘幂，所以第二个参数总是被圆整为不比原始值小的更小的2的乘幂。

----------------------- Page 7-----------------------21


    The size of both parts of a table are recomputed only when the table rehashes, which happens only when the table is completely full and Lua needs to insert a new element. As a consequence, if you traverse a table erasing all its fields (that is, setting them all to nil), the table does not shrink. However, if you insert some new elements, then eventually the table will have to resize. Usually this is not a problem: if you keep erasing elements and inserting new ones (as is typical in many programs), the table size remains stable. However, you should not expect to recover memory by erasing the fields of a large table: It is better to free the table itself.
    仅当表再散列时，其两部分的尺寸才会被重新计算，这只在表完全满了并且Lua需要插入新元素时发生。因而，如果你遍历表，擦除其所有字段（即把它们都设为nil），表不会收缩。不过，如果你插入某个新元素，则最终表将不得不调整大小。通常这不成问题：如果你一直擦除元素和插入新的（在很多问题中具有代表性），表尺寸保持不变。不过，你不应期待通过擦除很大的表的字段来恢复内存：释放表自身会更好。

    A dirty trick to force a rehash is to insert enough nil elements into the table. See the next example:
    一个不算优雅的强制再散列的窍门是向表中插入足够过的nil元素。见下一个例子：

a = {}
lim = 10000000
for i = 1, lim do a[i] = i end                         --   create a huge table 创建一个巨大的表
print(collectgarbage("count"))                         --> 196626
for i = 1, lim do a[i] = nil end                       --   erase all its elements 擦除其所有元素
print(collectgarbage("count"))                         --> 196626
for i = lim + 1, 2*lim do a[i] = nil end               -- create many nil elements 创建很多nil元素
print(collectgarbage("count"))                         --> 17

I do not recommend this trick except in exceptional circumstances: It is slow and there is no easy way to know how many elements are "enough".
除特殊情况之外，我不推荐这个技巧：它很慢，并且没有简易的方法知道多少个元素是“足够的”。

    You may wonder why Lua does not shrink tables when we insert nils. First, to avoid testing what we are inserting into a table; a check for nil assignments would slow down all assignments. Second, and more important, to allow nil assignments when traversing a table. Consider the next loop:
    你或许疑惑为什么Lua不在插入nil时收缩表。首先，要避免测试插入表中的是什么；对nil赋值的检查会减缓所有的赋值。第二，而且是更重要的，当遍历表时要允许nil赋值。考虑下一个循环：

for k, v in pairs(t) do
   if some_property(v) then
     t[k] = nil        -- erase that element 擦除那个元素
   end
end

If Lua rehashed the table after a nil assignment, it would havoc the traversal.
如果Lua在nil赋值以后把表再散列，会破坏遍历。

    If you want to erase all elements from a table, a simple traversal is the correct way to do it:
    如果你要从表中擦除所有元素，简单的遍历是实现它的正确方法：

for k in pairs(t) do
   t[k] = nil
end

A "smart" alternative would be this loop:
一个“聪明的”选择会是这个循环：

while true do
   local k = next(t)
   if not k then break end
   t[k] = nil
end


----------------------- Page 8-----------------------22


However, this loop is very slow for large tables. Function next, when called without a previous key, returns the "first" element of a table (in some random order). To do that, next traverses the table arrays from the beginning, looking for a non-nil element. As the loop sets the first elements to nil, next takes longer and longer to find the first non-nil element. As a result, the "smart" loop takes 20 seconds to erase a table with 100,000 elements; the traversal loop using pairs takes 0.04 seconds.
不过，对于大型的表来说这个循环非常慢。当不带前一个键调用函数next时返回表的“第一个”元素（以某种随机顺序）。要做到那样，next从开头遍历表数组，查找一个非nil元素。由于该循环设置第一个元素为nil，next花费更长时间来寻找第一个非nil元素。结果“智能”循环擦除带100,000个元素的表花费20秒；使用pairs的遍历循环花费0.04秒。