Re: ipairs in Lua 5.3.0-alpha

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

On Wed, 13 Aug 2014 19:02:25 -0300
Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:

> > The behavior defined by the Lua 5.3.0 documentation, where the
> > iteration runs from 1 to #t) looks acceptable to me, even though
> > its implementation seems - by principle (as explained above) -
> > inefficient to me.
> 
> Do you have any real data to back your worries?

It was an assumption until now. But I just made some benchmarks.
(see below)

> Among other things, if you are providing your own __len metamethod,
> it most probably returns the value of some count associated with the
> array, and therefore is O(1), not O(log n).

In my case, I want to return the length of a proxied shadow table,
using Lua's built-in length operator on that shadow table:

// returns the length of a JSON array (or zero for a table without numeric keys):
static int json_len(lua_State *L) {
  // stack shall contain one function argument:
  lua_settop(L, 1);
  // push shadow table or nil onto stack:
  json_getshadow(L, 1);
  // pop nil from stack if no shadow table has been found:
  if (lua_isnil(L, -1)) lua_pop(L, 1);
  // return length of argument or shadow table:
  lua_pushnumber(L, lua_rawlen(L, -1));
  return 1;
}

> So, by principle, this implementation should not seem inefficient.
> (Never mind that quite probably this O(1) is slower than Lua's
> built-in O(log n) length anyway :)
> 
> -- Roberto
> 

If Lua's built-in O(log n) length operator is really that fast, then
caching the length might not make sense in my case.


Here are the results of my benchmarks:


I used three different Lua versions, compiled on FreeBSD with the
clang compiler.

* Lua 5.2.3 without LUA_COMPAT_ALL
* Lua 5.3.0-alpha without LUA_COMPAT_5_2
* Lua 5.3.0-alpha without LUA_COMPAT_5_2 but with LUA_COMPAT_IPAIRS


The json library is json.c taken from http://www.public-software-group.org/mercurial/webmcp/file/035b58aa430a/libraries/json/json.c

It has been compiled as follows:

cc -c -O2 -fPIC -Wall -I ./lua52/include -o lua52/json.o json.c
ld -shared -L ./lua52/lib -o lua52/json.so lua52/json.o
cc -c -O2 -fPIC -Wall -I ./lua53/include -o lua53/json.o json.c
ld -shared -L ./lua53/lib -o lua53/json.so lua53/json.o
cc -c -O2 -fPIC -Wall -I ./lua53compat/include -o lua53compat/json.o json.c
ld -shared -L ./lua53compat/lib -o lua53compat/json.so lua53compat/json.o


I used this Lua program to benchmark ipairs
_with_ shadow- and metatable:

========================================
test-array.lua:

json = require "json"

a = json.array()

for i = 1, 10000 do
  a[i] = tostring(i)
end

local d

for i = 1, 10000 do
  for j, v in ipairs(a) do
    d = v
  end
end
========================================


And I used the following program to benchmark ipairs
_without_ shadow- and metatable:

========================================
test-table.lua:

json = require "json"

a = {}

for i = 1, 10000 do
  a[i] = tostring(i)
end

local d

for i = 1, 10000 do
  for j, v in ipairs(a) do
    d = v
  end
end
========================================


These are my test results:

~/lua_ipairs_test/lua52 % time bin/lua ../test-array.lua
31.559u 0.007s 0:32.33 97.5%    233+172k 0+0io 0pf+0w
~/lua_ipairs_test/lua53 % time bin/lua ../test-array.lua
149.107u 0.007s 2:33.27 97.2%   259+172k 0+0io 6pf+0w
~/lua_ipairs_test/lua53compat % time bin/lua ../test-array.lua
30.539u 0.007s 0:31.17 97.9%    259+172k 0+0io 6pf+0w

~/lua_ipairs_test/lua52 % time bin/lua ../test-table.lua
28.618u 0.000s 0:29.47 97.0%    233+172k 0+0io 3pf+0w
~/lua_ipairs_test/lua53 % time bin/lua ../test-table.lua
29.908u 0.000s 0:30.71 97.3%    258+172k 0+0io 0pf+0w
~/lua_ipairs_test/lua53compat % time bin/lua ../test-table.lua
29.900u 0.015s 0:30.54 97.9%    259+172k 0+0io 0pf+0w


Thus, iteration without LUA_COMPAT_IPAIRS is almost 5 times slower when
metamethods are used (149.107 seconds compared to 30.539 seconds).


I hope I didn't make a mistake, but I took care to use exactly the same
versions of Lua 5.3.0-alpha, just differing by the src/Makefile in the
following lines:

lua53:
CC= cc  # instead of gcc, since I'm on FreeBSD
CFLAGS= -O2 -Wall -Wextra $(SYSCFLAGS) $(MYCFLAGS)

lua53compat:
CC= cc  # instead of gcc, since I'm on FreeBSD
CFLAGS= -O2 -Wall -Wextra -DLUA_COMPAT_IPAIRS $(SYSCFLAGS) $(MYCFLAGS)


I don't want to claim that this is a problem for me in the real world.
Yet it seems to be 5x slower without LUA_COMPAT_IPAIRS in my test case
(with an almost empty body in the loop).


Without being really an expert on Lua's internals, I would still like to
bring up the following idea:

* Make ipairs(...) return a triplet such that "for i,v in ipairs(t)"
  iterates from (1,t[1]) to (n,t[n]) for the smallest non-negative
  integer n such that t[n+1] == nil, where t[x] respects the __index
  metamethod. That way, iteration speed will not depend on the
  complexity of the particular __len metamethod that is being used.

* Keep the __ipairs metamethod functionality in Lua 5.3 for those cases
  where the length is not determined by the first nil value. That way,
  programmers keep full flexibility on customizing the iteration
  behavior of the ipairs function. (In particular it is possible to
  implement sparse arrays, where holes are represented as nil's, even
  if ipairs - by default - stops at the first nil value.)


NOTE: This reads almost the same as in
http://www.lua.org/manual/5.2/manual.html#pdf-ipairs . Maybe it would
be good to clarify in the documentation of Lua 5.2 that it iterates
over the pairs (1,rawget(t,1)), (2,rawget(t,2)), ... instead of
(1,t[1]), (2,t[2]), ..., since the notation t[x] might be misunderstood
as potentially invoking __index here (which doesn't happen in Lua 5.2).


Kind Regards
Jan Behrens