Re: iterators

[spir <denis.spir@...>]

Le Fri, 13 Nov 2009 11:17:22 +0100,
Jerome Vuarand <jerome.vuarand@gmail.com> s'exprima ainsi:

> 2009/11/13 spir <denis.spir@free.fr>:
> > I find great that lua introduced proper iterators, including generators,
> > without addition of any new language feature such as continuations and
> > magic "yield" statements. Actually, the magic is rather done by lua under
> > the hood but does not directly affect the user --if I understand
> > correctly. Still, after a first lucky trial, I had rather hard and long
> > time guessing how to properly interpret the syntax (esp the "invisible"
> > variables) and consequentely how to implement iterators for various uses
> > -- esp. the highly different cases of collection and generator iterators,
> > respectively. I was surprised to endly discover that defining the
> > iterator func (the actual data yielding one) inside the iterator allows
> > getting rid of the said invisible vars alltogether. I may be wrong, sure,
> > maybe in some cases they are needed, still maybe we could simplify the
> > syntax in a way that would let using this great feature much more easily.
> > I wrote a doc about this, but put it on the wiki for it's rather long:
> > http://lua-users.org/wiki/SimplerForIterator
> >
> > (Took a risk if I'm totally wrong ;-) & hope it's not full of stupidity,
> > because there it will remain -- but anyway a wiki is intended to be
> > corrected.)
> 
> Removing these "invisible" variables would force all iterator
> functions to be specially instanciated closures with upvalues. This is
> a performance hit. The following wouldn't be possible any longer :
>     for k,v in next,t,nil do print(k, v) end
> 
> On the other hand the current syntax doesn't force you to use these
> hidden variables. Just ignore them.
> 

Someone said a thread on lua-list requires some benchmark. Some, I did test for this thread. I hope these tests are properly done, because I'm not used to that (please tell me in a PM if ever there are things to change in the testing method) ...

I was wondering whether performance penalty would mainly come from closure creation at loop initialisation time, or instead that calling a "closured" func with upvalue in a loop would be significantly slower. So, I wrote 2 versions of simple iteration on an array-table with a fake (empty) loop body: one with direct call to iteration func, one with closure. Then measured time (in seconds) for the following processes:

-1- Many (33,333,333) loops on empty table (meaning each loop initialisation requires closure creation for the closure version, but then in both cases loop process is a single func call + a single test):
	result: 10 / 33.
My interpretation: closure creation is clostly. But the test itself does not mirror any meaningful use case.

-2- Single loop on a table with many (33,333,333) items: 
	result: 17 / 19
My interpretation: this test is meaningful for the actual use case of walking through big arrays; but note there is no job done at all in the loop body, the test actually only measures the looping mechanics: with some job in the loop, the difference will reduce in proportion. The overhead for using a closure on an empty loop has an order of magnitude of 10%. (As far as I'm concerned, it's already neglectable even with empty loop.)

Then for further information: I wondered about the "weight" (in time) of actual iteration through items, compared to loop initialisation. So, I repeated the first case for arrays of 10 items:

-3- Many (3,333,333) loops on 10-items table. (Beware outside loop count is /10.)
	result: 10 / 16.
My interpretation: once multiplied per ten, we get 100 / 160. The first case is as expected, as loop init is nearly nothing, then we simply call the func 10 times more. For the case of a closure, we can evaluate each func call to ~ 13, and the loop init/closure creation to ~ 20 (for 33,333,333 times repeting the whole thing).

As a last test, I added some actual operation in the loop body (copy of the table):
-4- single loop on 11,111,111-items array + copy
	result: 14 / 15
My interpretation: the times here are rather unstable (the other test where highly stable instable with only +/- 1 variation), varying with ~ 30% incertitude on my computer. Sometimes the closure version is even faster.
Anyway, I would interpret this as meaning that, in the general case with non-empty arrays and some job in the loop body, the closure overhead is "very tiny".

Below the code with results (cases are not in the same order).

Denis
--------------------------------
* la vita e estrany *

http://spir.wikidot.com/



-- iterators
function next_item(array, index)
    if index < #array then
        index = index+1
        return index, array[index]
    end
end 
function items(array)
    local index = 0
    local function next_item()
        if index < #array then
            index = index+1
            return array[index]
        end
    end
    return next_item
end
require "os"

-- 33,333,333 iterations on empty array + no-op --> 10 / 33
function empty()    
    local array = {}

    local t0 = os.time()
    for i = 1,33333333 do
        for i,n in next_item, array, 0 do end
    end
    print ((os.time()-t0))     --> 11

    local t0 = os.time()
    for i = 1,33333333 do
        for n in items(array) do end
    end
    print ((os.time()-t0))     --> 35
end

-- 3,333,333 iterations on 10-item array + no-op --> 10 / 16
function ten()    
    local array = {0,1,2,3,4,5,6,7,8,9}

    local t0 = os.time()
    for i = 1,3333333 do
        for i,n in next_item, array, 0 do end
    end
    print ((os.time()-t0))     --> 11

    local t0 = os.time()
    for i = 1,3333333 do
        for n in items(array) do end
    end
    print ((os.time()-t0))     --> 16
end

-- 1 iteration on 33,333,333-items array + no-op --> 17 /19
function full()     
    local array = {}
    for i = 1,33333333 do table.insert(array, 0) end

    local t0 = os.time()
    for i,n in next_item, array, 0 do end
    print ((os.time()-t0))     --> 17

    local t0 = os.time()
    for n in items(array) do end
    print ((os.time()-t0))     --> 19
end

-- 1 iteration on 11,111,111-items array + copy --> 14 / 15
function copyfull()     
    local array = {}
    for i = 1,11111111 do table.insert(array, 0) end
    a = {}
    local t0 = os.time()
    for i,n in next_item, array, 0 do a[#a+1]=n end
    print ((os.time()-t0))     --> 14
    a = {}
    local t0 = os.time()
    for n in items(array) do a[#a+1]=n  end
    print ((os.time()-t0))     --> 15
end

function test()
--~     empty()
--~     ten()
--~     full()
    copyfull()
end
test()