6
Python 3.6.8 (default, Oct  7 2019, 12:59:55) 
Type 'copyright', 'credits' or 'license' for more information
IPython 7.9.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: def yield_from_generator(): 
   ...:     yield from (i for i in range(10000)) 
   ...:                                                                                                                                    

In [2]: def yield_from_list(): 
   ...:     yield from [i for i in range(10000)] 
   ...:                                                                                                                                    

In [3]: import timeit                                                                                                                      

In [4]: timeit.timeit(lambda: list(yield_from_generator()), number=10000)                                                                  
Out[4]: 5.3820097140014695

In [5]: timeit.timeit(lambda: list(yield_from_list()), number=10000)                                                                       
Out[5]: 4.333915593000711

I run yield from generator and yield from list many times. List version gives always better performance, while my intuition tells me rather opposite conclusions - making list requires i.e. memory allocation at startup. Why we can notice such performance differences?

pt12lol
  • 2,332
  • 1
  • 22
  • 48
  • 4
    The fact that a list takes more **memory** does not mean that it should have better **time** performance. Calling `next()` (and potentially handing `StopIteration`) can be expensive – DeepSpace Feb 10 '20 at 13:03
  • Sure, but this is an example operation that extra happens while we build a list. There certainly happen something else while yielding from generator, or yielding from list doesn't build it in fact. – pt12lol Feb 10 '20 at 13:06
  • @DeepSpace Is `yield from mylist` somehow special-cased? Does that not do `next`/`StopIteration`? I also tried `yield from iter([i for i in range(10000)])` (i.e., with explicit `iter(...)`) and that didn't make it any slower... – Kelly Bundy Feb 10 '20 at 13:08
  • @DeepSpace Could you tell more? What calls what, what happens then and why one is faster than another? Also - is it actually a comment, not an answer? – pt12lol Feb 10 '20 at 13:10
  • There was a bit similar question recently and I've then noticed that byte code for generator expression is longer then list comprehension: https://stackoverflow.com/questions/59995236/why-passing-a-list-as-a-parameter-performs-better-than-passing-a-generator#comment106105748_59995236 I haven't really dug more into exact reason and mechanics though. – Ondrej K. Feb 10 '20 at 13:17
  • To make things even more muddy, compare `def yield_from_generator(): yield from range(10000)` and `def yield_from_list(): yield from list(range(10000))` :-) – Błotosmętek Feb 10 '20 at 13:18
  • Can you clarify why you think the list should be slower? You have only given a reason why it should be *larger*. Note that the behaviour is implementation dependent - on PyPy3, the generator case duration is only 73% of the list case. – MisterMiyagi Feb 10 '20 at 13:25
  • 2
    You can't see the cost of allocating the list of 10000 items because that only happens on the first call to yield from list and is diluted across 9999 subsequent yields from the list which are (presumably) very quick. – DisappointedByUnaccountableMod Feb 10 '20 at 13:40
  • To address @barry 's question: try creating the list at method compile time by defining as a named arg, then yield from the named arg, like this: `def yield_from_list(lst=list(range(10000))): yield from lst` – PaulMcG Feb 10 '20 at 13:44
  • @MisterMiyagi as for my thought about memory allocation, I think that barny caught the point. I didn't take into account other Python implementations. Anyway, both operations sound similar to me, while the result performance significantly differ. – pt12lol Feb 10 '20 at 13:51
  • 1
    note that on Python 3.8 `yield_from_generator` is (slightly) faster – Sam Mason Feb 10 '20 at 13:54
  • @SamMason For my 3.8.1 it's *slower* (about factor 1.2). – Kelly Bundy Feb 10 '20 at 14:00
  • 1
    I'm using python-3.8.1, and the generator is still slower. The `yield from` is irrelevant - a plain `return` gives essentially the same result. This question seems to be a duplicate of this one: https://stackoverflow.com/questions/11964130/list-comprehension-vs-generator-expressions-weird-timeit-results. – ekhumoro Feb 10 '20 at 14:02
  • huh, I must admit I was testing something that I thought was equivalent but wasn't (I'd not added the "redundant" `i for i in` which saved a `genexpr` and sped things up). @ekhumoro I agree with that dup – Sam Mason Feb 10 '20 at 14:13
  • @pt12lol You seem to be asking why list comprehensions are sometimes faster than generator expressions, which has been asked and answered before on SO. Is there any reason why I shouldn't close your question as a dup? – ekhumoro Feb 10 '20 at 14:14
  • @ekhumoro I disagree with that dup. That other question is not about iterating the list/generator "from the outside" but uses the `in` operator on it, which is handled by the `__contains__` method and thus iterates "from the inside". – Kelly Bundy Feb 10 '20 at 14:18
  • @ekhumoro providing that `yield from` doesn't play a role (what I am not sure about), yes that's a dup. – pt12lol Feb 10 '20 at 14:18
  • 4
    That old dupe target is discussing Python 2 stuff; apart from `yield from` not existing in Python 2, list comps are slightly different in Python 3: they now create their own scope, but IIRC some improvements have been made so that having their own scope doesn't have a big impact on speed. So I'm hesitant to dupe-close this question to a Python 2 dupe target. – PM 2Ring Feb 10 '20 at 14:25
  • @PM2Ring Perhaps a better dup would be this: https://stackoverflow.com/q/46080263/984421. – ekhumoro Feb 10 '20 at 14:35
  • thinking more I don't think it's either of those dupes, it's to do with the surface syntax looking similar but actually doing something different at the bytecode level – Sam Mason Feb 10 '20 at 14:36
  • @ekhumoro Actually that's even unfair, as a generator doesn't have a `__contains__` method and the `in` operator` falls back to "from the outside" iteration. – Kelly Bundy Feb 10 '20 at 14:37
  • @ekhumoro That looks good to me, and Martijn's analysis is accurate (as usual). – PM 2Ring Feb 10 '20 at 14:40
  • OTOH, that question doesn't touch on `yield from`, which has distinct advantages over `yield` in a Python loop. – PM 2Ring Feb 10 '20 at 14:46
  • @HeapOverflow The underlying cause of the difference is the same. The issues regarding `__contains__` are separate from that, which is reflected in the two answers given. – ekhumoro Feb 10 '20 at 14:47
  • @PM2Ring In my timings, `yield from` adds extra overhead, but it affects list-comps and generators in exactly the same way - so I don't think it has any real relevance to the question. – ekhumoro Feb 10 '20 at 14:52

1 Answers1

3

the short answer is that the surface syntax makes them look more similar than they are

I'll break down a series of functions in more detail (the dis module is helpful for this), I'll separate things out into a setup cost and a cost per yielded value. we start with:

def yield_from_generator():
    yield from (i for i in range(10000))

the costs are:

  • setup: create the range object and invoke the embedded generator expression
  • per-yield: yield from the genexpr, which also invokes a next on the range iterator. note that there are two context switches here

next we look at:

def yield_from_list():
    yield from [i for i in range(10000)]

costs are:

  • setup: create a new list and populate it using a list comprehension. this uses special list op-codes so will be fast
  • per-yield: just resumes the list's iterator so is fast

next we look at a similar function:

def yield_from_list2():
    yield from list(i for i in range(10000))

this doesn't use the special list op-codes and has the double nesting of generators so is slow again. costs are:

  • setup: create a new generator expression and pass it to the list constructor, this will iterate over the generator expression that iterates over the range object
  • per-yield: uses the list's iterator so is fast again

and finally a fast version just stressing yield from:

def yield_from_generator2():
    yield from range(10000)

costs are:

  • setup: create a range object
  • per-yield: resume range iterator directly

timings of all of these on my laptop are:

yield_from_generator  639 µs
yield_from_list       536 µs
yield_from_list2      689 µs
yield_from_generator2 354 µs

hopefully it's a bit clearer now. another version is:

def yield_from_list3():
    yield from list(range(10000))

that runs in 401 µs but hopefully it's more obvious why this sits in the middle, performance wise

Sam Mason
  • 15,216
  • 1
  • 41
  • 60
  • @HeapOverflow I was using the term "generator expression" to mean hidden embedded function. this isn't correct (and have change the term) but not sure how to explain it or what a good reference would be – Sam Mason Feb 10 '20 at 14:58