Generators vs. Functions?

[Wolfgang Keller]

Hello,

in <[email protected]>, Magnus Lycka <[email protected]> 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-representativeness 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]

If this is actually also true in the general case, and not due to eventual
non-representativeness 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?

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]

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?

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.

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

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

--Max

 

[Peter Hansen]

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?

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]

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.

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

Neil

 

[Steven D'Aprano]

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

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
.... """class K:
.... pass
....
.... def next():
.... return 1
....
.... func = K()
.... func.next = next
.... """)0.63980388641357422


# generator, two name lookups
.... """def g():
.... while 1: yield 1
....
.... gen = g()
.... """)0.82081794738769531


# straight function, one name lookup
.... """def f():
.... return 1
.... """)0.47273492813110352


# generator, one name lookup
.... """def g():
.... while 1: yield 1
....
.... gnext = g().next
.... """)0.55085492134094238


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.

 

[Fredrik Lundh]

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

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]

0.82081794738769531

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

I get the same, but the difference is much less on my system:
0.46473169075954956

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:
"""class K:
pass

def next(self):
return 1

func = K()
""")0.58508302032805659


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:
"""def g(n):
while 1: yield n
gen = g(42)
""")"""class K:
def __init__(self, n):
self.n = n

def next(self):
return self.n

func = K(42)
""")0.67426781895460408

 

[Steven D'Aprano]

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

¿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.

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

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.

 

[Neil Schemenauer]

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

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

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.

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]

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

Well I guess you're forgiven then *sheepish grin*

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

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

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

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

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

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.

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

I never said it should.

 

[Magnus Lycka]

I get the same, but the difference is much less on my system:

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]

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

... """class K:
... pass
...
... def next():
... return 1
...
... func = K()
... func.next = next
... """)
0.63980388641357422


# generator, two name lookups

... """def g():
... while 1: yield 1
...
... gen = g()
... """)
0.82081794738769531


# straight function, one name lookup

... """def f():
... return 1
... """)
0.47273492813110352


# generator, one name lookup

... """def g():
... while 1: yield 1
...
... gnext = g().next
... """)
0.55085492134094238


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.

I show an advantage favoring generator resumption vs function call:
-7.5428559682677587e-006

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

Regards,
Bengt Richter