Re: ipairs in Lua 5.3.0-alpha

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

On Fri, 15 Aug 2014 10:50:04 -0700
Coda Highland <chighland@gmail.com> wrote:

> On Fri, Aug 15, 2014 at 10:47 AM,
> Doug Currie <doug.currie@gmail.com> wrote:
> >
> > On Fri, Aug 15, 2014 at 1:16 PM,
> > Jan Behrens <jbe-lua-l@public-software-group.org> wrote:
> > >
> > > On Fri, 15 Aug 2014 13:37:41 -0300
> > > Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:
> > >
> > > > If the goal is only to reduce calls to length, another option would be
> > > > to modify ipairs so that it stops in the first nil entry with an index
> > > > larger than #t. That would have some nice properties:
> > >
> > > It sounds like a "hack" to me.
> >
> > It is very clever. I like it.
> 
> I like it too!


Maybe I should explain what I meant with "hack":
it helps only if nil is an exception.

In all other cases it doesn't speed things up.


I couldn't resist to do a further benchmark for demonstration (even if
I think it's more important to clarify the semantics of ipairs first).

The benchmark implements a sparse array in Lua (Note: In C this
benchmark might produce different results).

============================================================
sparse-array.lua:

do
  local function sparse_ipairsaux(t, i)
    if i < t.len then
      i = i + 1
      local v = rawget(t, i)
      if v == nil then
        return i, t.default
      else
        return i, v
      end
    else
      return nil
    end
  end

  local sparse_metatable = {
    __index = function(t, k)
      if type(k) == "number" and k > 0 and k <= t.len then
        return t.default
      else
        return rawget(t, k)
      end
    end,
    __len = function(t) return t.len end,
    __ipairs = function(t)
      return sparse_ipairsaux, t, 0
    end
  }

  function sparse_array(entries, len, default)
    return setmetatable({
      entries = entries,
      len     = len,
      default = default
    }, sparse_metatable)
  end
end

do
  local field = sparse_array({}, 10000, nil)
  field[3]    = "a"
  field[2520] = "b"
  field[6667] = "c"

  local string_count = 0

  for i = 1, 1000 do
    for j, v in ipairs(field) do
      if type(v) == "string" then string_count = string_count + 1 end
    end
  end

  print(string_count .. " strings found")
end
============================================================


Running this program with different approaches, I get the following run-time:


Lua 5.3.0-alpha without LUA_COMPAT_5_2:
27.481 seconds

Lua 5.3.0-alpha with LUA_COMPAT_IPAIRS:
22.867 seconds

Lua 5.3.0-alpha with a cached length (see patch below):
24.720 seconds

Lua 5.3.0-alpha with Roberto's approach (see patch below) to only
determine the length when a nil is encountered:
28.181 seconds


Here, Roberto's approach would be slowest.

Note that the inner loop contains a function call type(v), so it's not
that surprising that the numbers are similar to each other.


Patch to simulate cached length:

--- lua-5.3.0-alpha/src/lbaselib.c      2014-07-24 21:33:29.000000000 +0200
+++ lua-5.3.0-alpha-staticlen/src/lbaselib.c    2014-08-15 17:17:32.078783582 +0200
@@ -260,7 +260,11 @@
 */
 static int ipairsaux (lua_State *L) {
   int i = luaL_checkint(L, 2) + 1;
-  if (i > luaL_len(L, 1)) {  /* larger than length? */
+  int maxi;
+  lua_settop(L, 2);
+  lua_pushinteger(L, 10000);  
+  maxi = luaL_checkint(L, 3);
+  if (i > maxi) {  /* larger than length? */
     lua_pushnil(L);  /* end traversal */
     return 1;
   }


Patch to only check length when nil is encountered (Roberto's idea):

--- lua-5.3.0-alpha/src/lbaselib.c      2014-07-24 21:33:29.000000000 +0200
+++ lua-5.3.0-alpha-lenhack/src/lbaselib.c      2014-08-16 11:36:59.485253075 +0200
@@ -260,14 +260,12 @@
 */
 static int ipairsaux (lua_State *L) {
   int i = luaL_checkint(L, 2) + 1;
-  if (i > luaL_len(L, 1)) {  /* larger than length? */
-    lua_pushnil(L);  /* end traversal */
-    return 1;
-  }
-  else {
-    lua_pushinteger(L, i);
-    lua_pushinteger(L, i);  /* key for indexing table */
-    lua_gettable(L, 1);
+  lua_pushinteger(L, i);
+  lua_pushinteger(L, i);  /* key for indexing table */
+  lua_gettable(L, 1);
+  if (lua_isnil(L, -1) && i > luaL_len(L, 1)) {  /* check len only if nil */
+    return 1;  /* end traversal */
+  } else {
     return 2;
   }
 }


Output of my benchmark:

without LUA_COMPAT_5_2:
~/lua_ipairs_test/lua53 % time bin/lua ../sparse-array.lua
3000 strings found
27.481u 0.000s 0:28.26 97.2%    258+172k 0+0io 0pf+0w

with LUA_COMPAT_IPAIRS:
~/lua_ipairs_test/lua53compat % time bin/lua ../sparse-array.lua
3000 strings found
22.867u 0.000s 0:23.44 97.5%    258+172k 0+0io 0pf+0w

lua-5.3.0-alpha-staticlen:
~/lua_ipairs_test/lua53patched % time bin/lua ../sparse-array.lua
3000 strings found
24.720u 0.000s 0:25.17 98.2%    258+172k 0+0io 0pf+0w

lua-5.3.0-alpha-lenhack:
~/lua_ipairs_test/lua53lenhack % time bin/lua ../sparse-array.lua
3000 strings found
28.181u 0.000s 0:29.07 96.9%    258+172k 0+0io 0pf+0w


But as I previously said: more important than these benchmarks would be
(for me) to understand the semantics of ipairs first. In particular:

Should

* for i, v in ipairs(t) do ... end

always do the same as:

* for i = 1, #t do local v = t[i]; ... end

Or should __ipairs allow specific optimizations and/or iterations over
objects that might not even have a length (or where the length can't be
determined easily).


Regards
Jan