Generators vs. Functions?

[Wolfgang Keller]

Hello,

in <dr86uc$8kt$1@w ake.carmen.se>, Magnus Lycka <lycka@carmen.s e> posts the
result of a short test that seems to indicate that resuming a generator takes
more time than calling a function.

If this is actually also true in the general case, and not due to eventual
non-representativen ess of the test mentioned above, is it simply due to a
less-than-optimum implementation of generators in the current Pyython
interpreter and thus likely to change in the future or is this a matter of
principle and will consequently remain like this forever?

TIA,

Sincerely,

Wolfgang Keller

[Joseph Garvin]

Re: Generators vs. Functions?

Wolfgang Keller wrote:
[color=blue]
>If this is actually also true in the general case, and not due to eventual
>non-representativen ess of the test mentioned above, is it simply due to a
>less-than-optimum implementation of generators in the current Pyython
>interpreter and thus likely to change in the future or is this a matter of
>principle and will consequently remain like this forever?
>
>[/color]

I am not a CPython or PyPy hacker, but I would guess that it will always
be slower as a matter of principal. When resuming a generator you have
to resetup the state the function was in when it was last called, which
I think should always be more costly than calling the function with a
clean state.

Someone want to correct me?

Whether or not the difference is that significant though I am unsure. It
may be small enough that for most applications no one cares.

[Max]

Re: Generators vs. Functions?

Joseph Garvin wrote:[color=blue]
>
> I am not a CPython or PyPy hacker, but I would guess that it will always
> be slower as a matter of principal. When resuming a generator you have
> to resetup the state the function was in when it was last called, which
> I think should always be more costly than calling the function with a
> clean state.
>
> Someone want to correct me?[/color]

In cases where there are thousands of (large) values to return, the list
(as returned by the function) may be large enough to require memory
paging, whereas the generator only returns one value at a time.
[color=blue]
>
> Whether or not the difference is that significant though I am unsure. It
> may be small enough that for most applications no one cares.[/color]

I just wrote an application which retrieves values from a 300mb
database, and got a significant speedup using iterators.

--Max

[Peter Hansen]

Re: Generators vs. Functions?

Joseph Garvin wrote:[color=blue]
> Wolfgang Keller wrote:[color=green]
>>If this is actually also true in the general case, and not due to eventual
>>non-representativen ess of the test mentioned above, is it simply due to a
>>less-than-optimum implementation of generators in the current Pyython
>>interpreter and thus likely to change in the future or is this a matter of
>>principle and will consequently remain like this forever?[/color]
>
> I am not a CPython or PyPy hacker, but I would guess that it will always
> be slower as a matter of principal. When resuming a generator you have
> to resetup the state the function was in when it was last called, which
> I think should always be more costly than calling the function with a
> clean state.
>
> Someone want to correct me?[/color]

Sure. "You have to resetup the state of the function"... depending on
what "resetup" means (not a usual English word, so we might all imagine
different meanings for it), either the first or the second part of the
last sentence is false.

More precisely, the state of the function is *saved* when a yield
occurs, so you certainly don't *recreate* it from scratch, but merely
restore the state, and this should definitely be faster than creating it
from scratch in the first place. I haven't looked at the source, but
this wouldn't have to involve much beyond a little memory copying, or
even a few pointer changes, whereas the original could involve a lot of
work, depending on how many arguments were passed, how many locals
exist, and so on.

-Peter

[Neil Schemenauer]

Re: Generators vs. Functions?

Peter Hansen <peter@engcorp. com> wrote:[color=blue]
> More precisely, the state of the function is *saved* when a yield
> occurs, so you certainly don't *recreate* it from scratch, but merely
> restore the state, and this should definitely be faster than creating it
> from scratch in the first place.[/color]

Right. Resuming a generator is faster than calling a function.

Neil

[Steven D'Aprano]

Re: Generators vs. Functions?

On Sun, 05 Feb 2006 03:31:24 +0000, Neil Schemenauer wrote:
[color=blue]
> Peter Hansen <peter@engcorp. com> wrote:[color=green]
>> More precisely, the state of the function is *saved* when a yield
>> occurs, so you certainly don't *recreate* it from scratch, but merely
>> restore the state, and this should definitely be faster than creating it
>> from scratch in the first place.[/color]
>
> Right. Resuming a generator is faster than calling a function.[/color]

Have you actually measured this, or are you just making a wild guess?

According to a short test performed by Magnus Lycka, resuming a generator
takes more time than calling a function. My own test agrees.

Here is my test, using Python 2.3. I've tried to make the test as fair as
possible, with the same number of name lookups in both pieces of test code.

# straight function, two name lookups
[color=blue][color=green][color=darkred]
>>> import timeit
>>>
>>> t1 = timeit.Timer(st mt="func.next() ", setup=[/color][/color][/color]
.... """class K:
.... pass
....
.... def next():
.... return 1
....
.... func = K()
.... func.next = next
.... """)[color=blue][color=green][color=darkred]
>>>
>>> t1.timeit()[/color][/color][/color]
0.6398038864135 7422


# generator, two name lookups
[color=blue][color=green][color=darkred]
>>> t2 = timeit.Timer(st mt="gen.next()" , setup=[/color][/color][/color]
.... """def g():
.... while 1: yield 1
....
.... gen = g()
.... """)[color=blue][color=green][color=darkred]
>>>
>>> t2.timeit()[/color][/color][/color]
0.8208179473876 9531


# straight function, one name lookup
[color=blue][color=green][color=darkred]
>>> t3 = timeit.Timer(st mt="f()", setup=[/color][/color][/color]
.... """def f():
.... return 1
.... """)[color=blue][color=green][color=darkred]
>>>
>>> t3.timeit()[/color][/color][/color]
0.4727349281311 0352


# generator, one name lookup
[color=blue][color=green][color=darkred]
>>> t4 = timeit.Timer(st mt="gnext()", setup=[/color][/color][/color]
.... """def g():
.... while 1: yield 1
....
.... gnext = g().next
.... """)[color=blue][color=green][color=darkred]
>>>
>>> t4.timeit()[/color][/color][/color]
0.5508549213409 4238


So on the basis of my tests, there is a small, but significant speed
advantage to _calling_ a function versus _resuming_ a generator.

Of course the other advantages of generators often far outweigh the tiny
setup cost each time you call one. In addition, for any complex function
with significant execution time, the call/resume time may be an
insignificant fraction of the total execution time. There is little or no
point in avoiding generators due to a misplaced and foolish attempt to
optimise your code.


--
Steven.

[Fredrik Lundh]

Re: Generators vs. Functions?

Steven D'Aprano wrote:
[color=blue]
> So on the basis of my tests, there is a small, but significant speed
> advantage to _calling_ a function versus _resuming_ a generator.[/color]

now add state handling to your micro-benchmark, and see if the function
example still runs faster.

(hint: functions and generators do different things, and are designed
for different use cases. they're not two different ways to do the same
thing, and benchmarks that ignore that simple fact are pretty much use-
less, except, perhaps, for a very small group of VM developers.)

</F>

[Duncan Booth]

Re: Generators vs. Functions?

Steven D'Aprano wrote:
[color=blue][color=green][color=darkred]
>>>> t1.timeit()[/color][/color]
> 0.6398038864135 7422[/color]
....[color=blue][color=green][color=darkred]
>>>> t2.timeit()[/color][/color]
> 0.8208179473876 9531
>
> So on the basis of my tests, there is a small, but significant speed
> advantage to _calling_ a function versus _resuming_ a generator.[/color]

I get the same, but the difference is much less on my system:
[color=blue][color=green][color=darkred]
>>> min(t1.timeit() for i in range(3))[/color][/color][/color]
0.4392957764185 8941[color=blue][color=green][color=darkred]
>>> min(t2.timeit() for i in range(3))[/color][/color][/color]
0.4647316907595 4956

You missed though what is perhaps a more representative case. Generators
have state, so for a fair comparison you need to restore some state. I
think a fairer comparison is:
[color=blue][color=green][color=darkred]
>>> t5 = timeit.Timer(st mt="func.next() ", setup=[/color][/color][/color]
"""class K:
pass

def next(self):
return 1

func = K()
""")[color=blue][color=green][color=darkred]
>>>
>>> min(t5.timeit() for i in range(3))[/color][/color][/color]
0.5850830203280 5659


The method call is slower than the generator resumption and that is without
even accessing any of the saved state. If you do access the saved state the
generator runs at about the same speed as the original (local variable
access is about as fast as accessing a constant), but the method slows down
even more:
[color=blue][color=green][color=darkred]
>>> t6 = timeit.Timer(st mt="gen.next()" , setup=[/color][/color][/color]
"""def g(n):
while 1: yield n
gen = g(42)
""")[color=blue][color=green][color=darkred]
>>> min(t6.timeit() for i in range(3))[/color][/color][/color]
0.4640550684514 4373[color=blue][color=green][color=darkred]
>>> t7 = timeit.Timer(st mt="func.next() ", setup=[/color][/color][/color]
"""class K:
def __init__(self, n):
self.n = n

def next(self):
return self.n

func = K(42)
""")[color=blue][color=green][color=darkred]
>>> min(t7.timeit() for i in range(3))[/color][/color][/color]
0.6742678189546 0408

[Steven D'Aprano]

Re: Generators vs. Functions?

On Sun, 05 Feb 2006 09:49:21 +0100, Fredrik Lundh wrote:
[color=blue]
> Steven D'Aprano wrote:
>[color=green]
>> So on the basis of my tests, there is a small, but significant speed
>> advantage to _calling_ a function versus _resuming_ a generator.[/color]
>
> now add state handling to your micro-benchmark, and see if the function
> example still runs faster.[/color]

¿Que Mr Fawlty?

Sorry, I'm not sure I follow what you mean. Do you mean, "Make the
function and generator do something significant"?

I expected that people would understand that I was talking only about the
overhead of calling the function or generator, not the overall time needed
to perform some useful task. Sorry for the less than clear explanation.

[color=blue]
> (hint: functions and generators do different things, and are designed
> for different use cases. they're not two different ways to do the same
> thing, and benchmarks that ignore that simple fact are pretty much use-
> less, except, perhaps, for a very small group of VM developers.)[/color]

I never meant to imply that generators were somehow "worse" than
functions. As you say, they have different purposes, and for the sort of
use case that generators are good for, the tiny extra overhead in
restoring a generator is a cost well worth paying.

But it is a cost. I personally don't believe it is a significant cost,
except maybe for the odd special case or two.


--
Steven.

[Neil Schemenauer]

Re: Generators vs. Functions?

Steven D'Aprano <steve@REMOVETH IScyber.com.au> wrote:[color=blue]
> Have you actually measured this, or are you just making a wild
> guess?[/color]

I haven't timed it until now but my guess it not so wild. I'm
pretty familiar with the generator implementation (having written
the initial version of it). In Python 2.3, resuming a generator
does a small amount of setup and then calls eval_frame(). Calling a
function does more setup work and then also calls eval_frame().
[color=blue]
> Here is my test, using Python 2.3. I've tried to make the test as
> fair as possible, with the same number of name lookups in both
> pieces of test code.[/color]

On my machine t4 is faster than t3. Your test is not so fair
because the generator is doing a "while" loop (executing more
bytecode instructions) while the function is just returning a value
(one instruction).

On your machine the function call may be faster due to CPU cache
effects or branch prediction. In any case, the difference you are
trying to measure is extremely small. Try adding some arguments to
the functions (especially keyword arguments).

What your test does show is that the speed difference should not
come into the decision of which construct to use.

Neil

[Steven D'Aprano]

Re: Generators vs. Functions?

On Sun, 05 Feb 2006 16:14:54 +0000, Neil Schemenauer wrote:
[color=blue]
> Steven D'Aprano <steve@REMOVETH IScyber.com.au> wrote:[color=green]
>> Have you actually measured this, or are you just making a wild
>> guess?[/color]
>
> I haven't timed it until now but my guess it not so wild. I'm
> pretty familiar with the generator implementation (having written
> the initial version of it).[/color]

Well I guess you're forgiven then *sheepish grin*
[color=blue]
> In Python 2.3, resuming a generator
> does a small amount of setup and then calls eval_frame(). Calling a
> function does more setup work and then also calls eval_frame().[/color]

It takes MORE setup to call a function than it takes to resume a
generator?

[color=blue][color=green]
>> Here is my test, using Python 2.3. I've tried to make the test as
>> fair as possible, with the same number of name lookups in both
>> pieces of test code.[/color]
>
> On my machine t4 is faster than t3. Your test is not so fair
> because the generator is doing a "while" loop (executing more
> bytecode instructions) while the function is just returning a value
> (one instruction).[/color]

A fair criticism, but then a generator with just one instruction is, well,
pointless.

[color=blue]
> On your machine the function call may be faster due to CPU cache
> effects or branch prediction. In any case, the difference you are
> trying to measure is extremely small. Try adding some arguments to
> the functions (especially keyword arguments).[/color]


Small in absolute terms, but significant in relative terms: as an order of
magnitude, a factor of about 1/10th.

Of course, I never expected that calling/resuming cost to be significant
for most real world uses. If I gave anyone that impression, it wasn't
intended.
[color=blue]
> What your test does show is that the speed difference should not
> come into the decision of which construct to use.[/color]

I never said it should.



--
Steven.

[Magnus Lycka]

Re: Generators vs. Functions?

Duncan Booth wrote:[color=blue]
> Steven D'Aprano wrote:[color=green]
>>So on the basis of my tests, there is a small, but significant speed
>>advantage to _calling_ a function versus _resuming_ a generator.[/color]
>
> I get the same, but the difference is much less on my system:[/color]

With Python 2.4? Doesn't surprise me a bit.

I tested with 2.3 (vanilla Red Hat EL4 install) and it seems Steven
used 2.3 as well. My little test was just an attempt to test a claim
that the setup time would be shorter for generator calls than for
function calls. It's so easy to test timing with Python, so it's
surprising that people speculate so much about theories with no
measurements.

Who knows what the call time ratios will be in Python 2.6?

I think the important point is the one Fredrik is making: You
won't have a function implementation or a generator implementation
with the same code body.

The other differences in the code will typically mean much more than
the call overhead. If we're in some nested loop where we call a
function so trivial that the call overhead makes performance suffer,
by all means, inline these few lines of code in the loop!

[Bengt Richter]

Re: Generators vs. Functions?

On Sun, 05 Feb 2006 19:14:29 +1100, Steven D'Aprano <steve@REMOVETH IScyber.com.au> wrote:
[color=blue]
>On Sun, 05 Feb 2006 03:31:24 +0000, Neil Schemenauer wrote:
>[color=green]
>> Peter Hansen <peter@engcorp. com> wrote:[color=darkred]
>>> More precisely, the state of the function is *saved* when a yield
>>> occurs, so you certainly don't *recreate* it from scratch, but merely
>>> restore the state, and this should definitely be faster than creating it
>>> from scratch in the first place.[/color]
>>
>> Right. Resuming a generator is faster than calling a function.[/color]
>
>Have you actually measured this, or are you just making a wild guess?
>
>According to a short test performed by Magnus Lycka, resuming a generator
>takes more time than calling a function. My own test agrees.
>
>Here is my test, using Python 2.3. I've tried to make the test as fair as
>possible, with the same number of name lookups in both pieces of test code.
>
># straight function, two name lookups
>[color=green][color=darkred]
>>>> import timeit
>>>>
>>>> t1 = timeit.Timer(st mt="func.next() ", setup=[/color][/color]
>... """class K:
>... pass
>...
>... def next():
>... return 1
>...
>... func = K()
>... func.next = next
>... """)[color=green][color=darkred]
>>>>
>>>> t1.timeit()[/color][/color]
>0.639803886413 57422
>
>
># generator, two name lookups
>[color=green][color=darkred]
>>>> t2 = timeit.Timer(st mt="gen.next()" , setup=[/color][/color]
>... """def g():
>... while 1: yield 1
>...
>... gen = g()
>... """)[color=green][color=darkred]
>>>>
>>>> t2.timeit()[/color][/color]
>0.820817947387 69531
>
>
># straight function, one name lookup
>[color=green][color=darkred]
>>>> t3 = timeit.Timer(st mt="f()", setup=[/color][/color]
>... """def f():
>... return 1
>... """)[color=green][color=darkred]
>>>>
>>>> t3.timeit()[/color][/color]
>0.472734928131 10352
>
>
># generator, one name lookup
>[color=green][color=darkred]
>>>> t4 = timeit.Timer(st mt="gnext()", setup=[/color][/color]
>... """def g():
>... while 1: yield 1
>...
>... gnext = g().next
>... """)[color=green][color=darkred]
>>>>
>>>> t4.timeit()[/color][/color]
>0.550854921340 94238
>
>
>So on the basis of my tests, there is a small, but significant speed
>advantage to _calling_ a function versus _resuming_ a generator.
>
>Of course the other advantages of generators often far outweigh the tiny
>setup cost each time you call one. In addition, for any complex function
>with significant execution time, the call/resume time may be an
>insignifican t fraction of the total execution time. There is little or no
>point in avoiding generators due to a misplaced and foolish attempt to
>optimise your code.
>[/color]
I show an advantage favoring generator resumption vs function call:
[color=blue][color=green][color=darkred]
>>> from time import clock
>>> def f(): return clock()[/color][/color][/color]
...[color=blue][color=green][color=darkred]
>>> def g(): yield clock(); yield clock()[/color][/color][/color]
...[color=blue][color=green][color=darkred]
>>> max(f()-f() for x in xrange(10000))[/color][/color][/color]
-9.2190462142316 409e-006[color=blue][color=green][color=darkred]
>>> max(f()-f() for x in xrange(10000))[/color][/color][/color]
-9.2190462139818 408e-006[color=blue][color=green][color=darkred]
>>> max(float.__sub __(*g()) for x in xrange(10000))[/color][/color][/color]
-7.5428559682677 587e-006[color=blue][color=green][color=darkred]
>>> max(float.__sub __(*g()) for x in xrange(10000))[/color][/color][/color]
-7.5428559682677 587e-006[color=blue][color=green][color=darkred]
>>> max(float.__sub __(*g()) for x in xrange(10000))[/color][/color][/color]
-7.5428559682677 587e-006

(It'll probably go ten times faster on a recent box ;-)

Regards,
Bengt Richter