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

[Jan Behrens <jbe-lua-l@...>]

On Thu, 14 Aug 2014 22:36:05 +0200
Dirk Laurie <dirk.laurie@gmail.com> wrote:

> 2014-08-14 13:09 GMT+02:00 Jan Behrens <jbe-lua-l@public-software-group.org>:
> 
> > I'm aware of the fact that t[#t + 1] = v is a common idiom
> >    and that the usage of the # operator has a complexity of
> >    O(n*log(n)) when used in a loop to fill a table. In many
> >    programs that doesn't matter (it's still fast enough and
> >    filling a table is O(n*log(n) anyway), so I usually don't
> >    care to optimize here.
> 
> Actually, filling a table is O(n). It is true that there may be
> O(log n) reallocations, but these are all doublings, so the
> total time is like 1+2+4+8+...+2^k = 2n where n=2^k.
> 

Oh, I didn't know :-) Thanks for that information. I always thought
filling tables is O(n*log(n)).

But I'm still unsure about the # operator in that case (see below).


On Thu, 14 Aug 2014 20:36:47 +0200
Dirk Laurie <dirk.laurie@gmail.com> wrote:

> 2014-08-14 9:59 GMT+02:00 Enrico Colombini <erix@erix.it>:
> > On 14/08/2014 8.16, Dirk Laurie wrote:
> >>
> >> In actual applications, finding #tbl is quite often followed shortly
> >> by traversing tbl from 1 to #tbl soon afterwards. E.g.
> >>     for i=1.#tbl do ...
> >>
> >> I.e. the O(log n) length operator becomes insignificant in comparison
> >> to the O(n) table traversal.
> >
> >
> > A common case where this does not happen is when appending data:
> >   t[#t + 1] = v
> 
> But in that case the built-in length operator is O(1). The very first
> index it tries will work.
> 

Can you explain this to me? Why is the built-in length operator O(1)?
Doesn't it do a binary search?

/*
** Try to find a boundary in table `t'. A `boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
int luaH_getn (Table *t) {
  unsigned int j = t->sizearray;
  if (j > 0 && ttisnil(&t->array[j - 1])) {
    /* there is a boundary in the array part: (binary) search for it */
    unsigned int i = 0;
    while (j - i > 1) {
      unsigned int m = (i+j)/2;
      if (ttisnil(&t->array[m - 1])) j = m;
      else i = m;
    }
    return i;
  }
  /* else must find a boundary in hash part */
  else if (isdummy(t->node))  /* hash part is empty? */
    return j;  /* that is easy... */
  else return unbound_search(t, j);
}

Here, t->sizearray is not equal to #t, is it?


Regards
Jan