Re: Speed of #t (was: Re: [ANN] Lua 5.2.0 (alpha) now available

[starwing <weasley.wx@...>]

2010/12/13 Dirk Laurie <dpl@sun.ac.za>

On Mon, Dec 13, 2010 at 10:39:09AM +0200, Enrico Colombini wrote:
> On 13/12/2010 9.29, Dirk Laurie wrote:
> > The algorithm for #t in ltable.c is (if I read it right):
> >
> > Consider k, the size of the array part of t.  If t has no hash
> > part and t[k] is not nil, we immediately have #t=k (constant time).
> >
> > Otherwise either k-1 is an upper bound, or k is a lower bound for #t,
> > depending whether t[k] is nil.  In the latter case, an upper bound
> > can be found by doubling (logarithmic time). Having an upper and a
> > lower bound, binary search (logarithmic time) is used to find #t.
>
> So, accessing #t for a mixed table (array + hash) is slower than
> accessing it for a pure array with the same data?
>
Not always.  Here is a counterexample.  To demonstrate it, copy your
Lua source to a temporary directory, put the line
   printf("[%i,%i]\n",i,j);
inside the binary searches in ltable.c, and recompile Lua.

Lua 5.2.0 (alpha)  Copyright (C) 1994-2010 Lua.org, PUC-Rio
> a={1,2,nil,4,5,6,nil,8,nil,nil,nil,12,nil,nil,nil}; return #a
[0,7]
[0,3]
[1,3]
[2,3]
2
> a={1,2,nil,4,5,6,nil,8}; a[12]=12; return #a
8

No binary search at all in the array+hash case!

Dirk

yes, it may slow when lua found you used all array-part. in this scene it turns to unbound_search, and in the worst situation, it will do linear search on a big hash-table.

why we can't use primitive define of the mean of "length"? that, the real element in table. that will be easy if we maintain a total size field, if we set a nil-value in table to non-nil, it plus one, and if we set a non-nil value to nil, it minus one, wherever it happened in normal code or meta-method.

if we want the maximum bound of the array, we can product a function that return the maximum bound, and they can slow--because anybody use this function will notice that they may cache the value of that function.

in another way, this bound value can be maintain by lua self. just check the new added value's index and the current bound value. and change it when necessary.

all these tech can avoid linear search, so why remain it in the source?