Lua Performance Tips pdf

Cours Lua Performance Tips pdf, tutoriel & guide de travaux pratiques en pdf.

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.
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.
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).
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:
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.

Lua Performance Tips

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.
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.
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:
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:
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}, how-ever, Lua is not smart enough to detect that the given expressions (literal num-bers, in this case) describe array indices, so it creates a table with four slots in its hash part, wasting memory and CPU time.
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.
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.
A dirty trick to force a rehash is to insert enough nil elements into the table.
See the next example:
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
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:
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. 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
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.

About strings

As with tables, it is good to know how Lua implements strings to use them more efficiently.
The way Lua implements strings differs in two important ways from what is done in most other scripting languages. First, all strings in Lua are internalized; this means that Lua keeps a single copy of any string. Whenever a new string appears, Lua checks whether it already has a copy of that string and, if so, reuses that copy. Internalization makes operations like string comparison and table indexing very fast, but it slows down string creation.
Second, variables in Lua never hold strings, but only references to them. This implementation speeds up several string manipulations. For instance, in Perl, when you write something like $x = $y, where $y contains a string, the assignment copies the string contents from the $y buffer into the $x buffer. If the string is long, this becomes an expensive operation. In Lua, this assignment involves only copying a pointer to the actual string.