Generally, you don't need to know the details of the Lua implementation table to use it. In fact, Lua has spent a lot of effort to hide the internal implementation details. However, implementation details reveal the performance overhead of table operations. Therefore, to optimize the program that uses tables (specifically refer to Lua programs here), it is very beneficial to understand the implementation details of some tables.
Lua's table implementation uses some very clever algorithms. The interior of each Lua table contains two parts: the array part and the hash part. The array part saves the element with integers from 1 to a specific n as keys (we will discuss how this n is calculated later). All other elements (including integer keys outside the above range) are stored in the hash section.
As its name suggests, the hashing part uses a hash algorithm to save and find keys. It uses an implementation called an open address table, meaning that all elements are stored in a hash array. Use a hash function to get the index corresponding to a key; if there is a conflict (i.e., if two keys produce the same hash value), these keys will be placed in a linked list where each element corresponds to an array item. When Lua needs to add a new key to the table, but the hash array is full, Lua will rehash. The first step to rehashing is to decide the size of the new array part and hash part. Therefore, Lua traverses all elements, counts and classifies them, and then selects a size for the array part, which is equivalent to the largest power of 2 that can make more than half of the space of the array part be filled with; then selects a size for the hash part, which is equivalent to the smallest power of 2 that can just accommodate all elements of the hash part.
When Lua creates an empty table, the size of both parts is 0. Therefore, no array is assigned to it. Let's take a look at what happens when the following code is executed:
local a = {}
for i = 1, 3 do
a[i] = true
end
This code begins with creating an empty table. In the first iteration of the loop, the assignment statement
a[1] = true
Triggered a rehash; Lua sets the size of the array part to 1, and the hash part is still empty; during the second iteration
a[2] = true
Another rehash is triggered, expanding the array part to 2. Finally, the third iteration triggers another rehash, expanding the size of the array part to 4.
Similar to the following code
a = {}
= 1; = 2; = 3
What is done is similar, except that the size of the hash part is increased.
For large tables, the overhead of the initial rehash is distributed to the entire table creation process. A table with three elements requires three rehashing, and a table with one million elements only requires twenty times. But when thousands of small tables are created, the performance impact of rehashing will be very significant.
Older versions of Lua preselect the allocated size when creating empty tables (4, if I remember correctly) to prevent these overheads when initializing small tables. But such an implementation will waste memory. For example, if you want to create millions of points (represented as tables with two elements), each using twice the memory it actually needs, it will be a high price. This is why Lua no longer preallocates arrays for new tables.
If you are programming in C, you can avoid rehashing through Lua's API function lua_createtable; in addition to lua_State, it also accepts two parameters: the initial size of the array part and the initial size of the hash part [1]. Rehashing at initialization can be avoided by specifying the appropriate value. Be wary of this, Lua will only shrink the size of the table when rehashed, so if you specify an excessively large value at initialization, Lua may never correct the memory space you wasted.
When programming with Lua, you may be able to use constructors to avoid rehashing during initialization. When you write it
{true, true, true}
When Lua knows that the array part of this table will have three elements, so an array of corresponding size will be created. Similar, if you write it
{x = 1, y = 2, z = 3}
Lua will also create an array of size 4 for the hash part. For example, it takes 2.0 seconds to execute the following code:
for i = 1, 1000000 do
local a = {}
a[1] = 1; a[2] = 2; a[3] = 3
end
If the correct size is given when creating the table, the execution time can be reduced to 0.7 seconds:
for i = 1, 1000000 do
local a = {true, true, true}
a[1] = 1; a[2] = 2; a[3] = 3
end
But, if you write something like
{[1] = true, [2] = true, [3] = true}
The code of Lua is not smart enough to recognize the array index specified by the expression (in this case a numeric literal), so it creates an array of size 4 for the hash part, wasting memory and CPU time.
The size of the two parts will only be recalculated when Lua rehash, and rehash will only happen when Lua needs to insert new elements after the table is completely filled. So if you iterate over a table and clear all its entries (that is, all set to nil), the table size will not shrink. But at this time, if you need to insert a new element, the table size will be resized. This will not become a problem in most cases, but don't expect to recycle memory by clearing table entries: it's best to clear the table itself directly.
A rude way to force rehash is to insert enough nils into the table. For example:
a = {}
lim = 10000000
for i = 1, lim do a[i] = i end �
print(collectgarbage("count")) --> 196626
for i = 1, lim do a[i] = nil end
print(collectgarbage("count")) --> 196626
for i = lim + 1, 2 * lim do a[i] = nil end -- Create a bunch of nil elements
print(collectgarbage("count")) --> 17
Unless it is in special cases, I do not recommend this trick: it is slow and there is no easy way to know how many nils to insert to be enough.
You may be wondering why Lua doesn't shrink the table when clearing the table entry. The first is to avoid testing what is written to the table. If you check whether the value is nil during assignment, all assignment operations will be slowed down. Second, and most importantly, it allows the table entry to be assigned to nil when traversing the table. For example, the following loop:
for k, v in pairs(t) do
if some_property(v) then
t[k] = nil – Clear element
end
end
If Lua rehashs the table after each nil assignment, the loop will be broken.
If you want to clear all elements in a table, just simply iterate over it:
for k in pairs(t) do
t[k] = nil
end
A "smart" alternative solution:
while true do
local k = next(t)
if not k then break end
t[k] = nil
end
However, for large tables, this cycle will be very slow. When calling the function next, if the previous key is not given, the first element of the table will be returned (in some random order). In this example, next will traverse the table and look for a non-nil element from the beginning. Since the loop always sets the first element found to nil, the next function will take longer and longer to find the first non-nil element. The result is that this "smart" loop takes 20 seconds to clear a table with 100,000 elements, while a loop implemented with pairs takes only 0.04 seconds.
[1] Although the rehash algorithm always sets the size of the array to a power of 2, the size of the array can still be any natural value. The size of the hash must be a power of 2, so the second parameter will always be rounded into a minimum power of 2 not less than the original value.