A common pattern is to use Lua tables as arrays: there is no other data structure so the choice is imposed. This does not usually pose any problem apart the fact you cannot store nil values in tables blindly.

However, when populating with millions of items, using Lua tables becomes a performance issue because the length operator has O(n) complexity. table.insert, the obvious candidate for such operation, has the worse performance. Directly using v[#v+1] avoids a call but still suffers from the O(n) problem. The proper solution is to avoid relying on the lengh operator by keeping a separate pointer or directly use the iterator variable of the cycle.

$ time lua -e 'a = {} for n = 1, 10000000 do table.insert(a, n) end'

real    0m3.218s
user    0m3.173s
sys 0m0.040s
$ time lua -e 'a = {} for n = 1, 10000000 do a[#a+1] = n end'

real    0m2.656s
user    0m2.623s
sys 0m0.027s
$ time lua -e 'a = {} for n = 1, 10000000 do a[n] = n end'

real    0m0.435s
user    0m0.403s
sys 0m0.027s

Post your comment


No one has commented on this page yet.

RSS feed for comments on this page RSS feed for all comments