Re: ... efficiency (was Re: class implementation)

[Mike Pall <mikelu-0604@...>]

Hi,

Mark Hamburg wrote:
> Mike is correct that introducing the iterator function -- even as useful as
> it is -- brings in memory allocation costs and hence is a lose for small
> numbers of arguments.

So, let's benchmark it. Here are the two ways to iterate over
arguments (without doing anything with them):

local function iterate_with_select(...)
  local select = select
  for j=1,1e6 do

    for i=1,select('#', ...) do
      local a = select(i, ...)
    end

  end
end

local function iterate_with_apairs(...)
  local apairs = apairs
  for j=1,1e6 do

    for i,a in apairs(...) do end

  end
end

I've run these with different number of arguments and timed it
(lower numbers are better):

  #   select  apairs
--------------------
  0     0.46    1.01
  1     0.81    1.33
  2     1.16    1.73
  3     1.58    2.03
  4     2.00    2.39
  5     2.54    2.92
  6     3.09    3.29
  7     3.46 \/ 3.72
  8     4.13 /\ 3.86
  9     4.43    4.24
 10     5.10    4.50
 15     8.46    6.21
 20    12.58    7.77
 25    16.84    9.44
 50    49.60   18.13
100   154.03   34.40
200   555.21   66.00

The cross-over point when apairs() becomes more efficient is
between 7 and 8 arguments. So it pays off if you have more than
this on average. But it's not dramatically slower for lower
numbers, too.

IMHO apairs always pays off because it's much more readable. :-)

> My concern is that the standard idioms for iterating over varargs have
> essentially quadratic time complexity and that's basically a problem waiting
> to happen.

The point where this becomes painfully obvious (2:1 ratio) is at
about 30 arguments (on average). This is above the point where
passing a table would be a preferrable choice.

But I agree that somebody using the select() iteration idiom
naively is bound to discover this by accident.

Bye,
     Mike