Re: [ANN] Lua 5.2.0 (alpha) now available

[Dirk Laurie <dpl@...>]

On Sun, Dec 12, 2010 at 09:33:02PM +0200, Peter Cawley wrote:
> On Sun, Dec 12, 2010 at 7:30 PM, Enrico Colombini <erix@erix.it> wrote:
> > On 12/12/2010 19.57, Geoff Leyland wrote:
> >>
> >> t[1] is quicker than #t>  0, especially if t is a long array.
> >
> >> (Not my idea, Javier Guerra pointed this out in
> >> http://lua-users.org/lists/lua-l/2008-03/msg00540.html)
> >
> > Interesting... I always thought #t required constant time.
> 
> #t can require linear time in the worst case, and (probably)
> logarithmic time in the average case.

Constant time sometimes, logarithmic otherwise, except when the 
"table was built with bad purposes".

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.

The exception occurs when doubling would overflow without
an upper bound.  For that to happen, the table must have
non-nil entries precisely at the indices generated by doubling.
This is unlikely except if the table was specially constructed 
to disprove the claim that the time is always logarithmic. 

Dirk