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? 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). 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

I just created another (simple) benchmark that isn't based on my JSON
library, but uses two simple Lua programs without further dependencies.
The programs also contain some payload in the body of the loop
(counting true's).

========================================
constant-length.lua:

datatable = {}

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

proxytable = setmetatable({}, {
  __index = datatable,
  __len = function() return 10000 end,
  __ipairs = function(t)
    return ipairs(datatable)
  end
})

local yes = 0
local no = 0

for i = 1, 10000 do
  for j, v in ipairs(proxytable) do
    if v then yes = yes + 1 else no = no + 1 end
  end
end
========================================

and

========================================
dynamic-length.lua:

datatable = {}

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

proxytable = setmetatable({}, {
  __index = datatable,
  __len = function() return #datatable end,
  __ipairs = function(t)
    return ipairs(datatable)
  end
})

local yes = 0
local no = 0

for i = 1, 10000 do
  for j, v in ipairs(proxytable) do
    if v then yes = yes + 1 else no = no + 1 end
  end
end
========================================

I let these programs be executed by

* Lua 5.3.0-alpha without LUA_COMPAT_5_2
  ("lua53" below)
* Lua 5.3.0-alpha without LUA_COMPAT_5_2 but with LUA_COMPAT_IPAIRS
  ("lua53compat" below)

These are my test results:

~/lua_ipairs_test/lua53 % time bin/lua ../constant-length.lua
78.034u 0.000s 1:19.64 97.9%    259+172k 0+0io 0pf+0w

~/lua_ipairs_test/lua53compat % time bin/lua ../constant-length.lua
38.664u 0.000s 0:39.35 98.2%    259+172k 0+0io 0pf+0w

~/lua_ipairs_test/lua53 % time bin/lua ../dynamic-length.lua 
114.452u 0.007s 1:55.69 98.9%   259+172k 0+0io 0pf+0w

~/lua_ipairs_test/lua53compat % time bin/lua ../dynamic-length.lua
38.697u 0.000s 0:39.38 98.2%    259+172k 0+0io 0pf+0w


Therefore I conclude:

* Even if __len is a simple function that just returns a hard-coded
  constant, removing the __ipairs mechanism may still result in a
  slowdown of a factor of two (78.034 seconds vs. 38.664 seconds)

* If __len utilizes the fast built-in # operator, we get a slowdown of
  a factor of three (114.452 seconds vs. 38.697 seconds).


Regards
Jan Behrens