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

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

On Thu, 14 Aug 2014 09:59:14 +0200
Enrico Colombini <erix@erix.it> wrote:

> 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
> 
> -- 
>    Enrico


Just to clarify:

1. I didn't want to complain about the speed of the # operator. I
   think O(log(n)) is just fine to determine the size of a table.

2. 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.

3. Removing the __ipairs metamethod mechanism is not just about
   the overhead (and speed) of the # operator:

   a) Beside the repetitive call of luaB_ipairs, it is not
      possible to return a precalculated value as second item of
      the iterator triplet that may speed things up.

      EXAMPLE:
      // my own __ipairs metamethod:
      static int my_ipairs(lua_State *L) {
        luaL_checktype(L, 1, LUA_TTABLE);
        lua_pushcfunction(L, iterfunc);
        // we only need to do this once here and not
        // in iterfunc for every iteration step:
        lua_rawgetp(L, 1, &key_for_shadow_table);
        lua_pushinteger(L, 0);
        return 3;
      }

   b) As Roberto said, the O(1) of other __len metamethods may
      take longer than Lua's # operator. So this issue is really
      _not_ about the speed of the # operator in Lua. Still, the
      repetitive call of luaB_ipairs is overhead (whether it's
      O(1) or O(log(n)) overhead, it gets executed for every
      iteration, summing up to O(n) or O(n*log(n)) ). The O(n)
      may - in practice - be even slower than some other
      O(n*log(n)).

   In total, these two implications a) and b) slowed down the
   for-ipairs-loop by a factor of 5 in my benchmark. (Feel free
   to show a counter-example or other examples to back up my
   results.)

   I generally don't want to complain about a speed factor of 5.
   In most cases, the cost of the iteration will be small compared
   to what happens in the body of the interation. But there may be
   other cases:

   local yes = 0
   local no = 0
   local t = setmetatable({}, {
     __index = some_other_table,
     __len   = some_function
   })
   for i, v in ipairs(t) do  -- 5 times slower
     -- not much effort here:
     if v then yes = yes + 1 else no = no + 1 end
   end

   Wouldn't it be sad if ipairs slows down by a factor of 5 in
   this case?

4. Beside all speed issues, the __ipairs metamethod allows
   programmers still more flexibility than making ipairs(...) use
   __index and __len.

   I would propose to keep __ipairs, but nevertheless make ipairs
   by default also respect __index (but not __len).


Regards
Jan