Re: Speed of # operator (Was: ipairs in Lua 5.3.0-alpha)

[Enrico Colombini <erix@...>]

On 15/08/2014 12.23, Anton Titov wrote:
> Anyway, bottom line is in the long run, realloc running time is
> proportional to min(oldsize, newsize), hence log(n)
> reallocations is O(n*log(n)).

Interesting considerations, thanks (sometimes one tends not to think too 
much about the time spent in low-level system libraries).

A note: if needed, realloc time could be made O(1) by using a constant 
time allocator such as TLSF (http://tlsf.baisoku.org/). It was suggested 
to me on this list and I used it with Lua with good results.
Of course that O(1) could still be longer than O(n*log(n)) with the 
system libraries, but for a large enough 'n' it could make a difference.
(the main usage of TLSF is in real-time systems where an upper bound is 
desirable for allocation calls time)

--
  Enrico