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

[Dirk Laurie <dpl@...>]

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