`yield from` generator vs `yield from` list performance [duplicate]

Question

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?

Commutative

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 – Sprague

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. – Commutative

@Sprague 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... – Scevour

@Sprague 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? – Commutative

There was a bit similar question recently and I've then noticed that byte code for generator expression is longer then list comprehension: #59995736 I haven't really dug more into exact reason and mechanics though. – Cajeput

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)) :-) – Sheathbill

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. – Vano

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. – Fawnia

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 – Delanos

@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. – Commutative

note that on Python 3.8 yield_from_generator is (slightly) faster – Nanette

@SamMason For my 3.8.1 it's slower (about factor 1.2). – Scevour

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: #11964630. – Ivers

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). @Ivers I agree with that dup – Nanette

@Commutative 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? – Ivers

@Ivers 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". – Scevour

@Ivers providing that yield from doesn't play a role (what I am not sure about), yes that's a dup. – Commutative

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. – Epithalamium

@PM2Ring Perhaps a better dup would be this: https://mcmap.net/q/1914896/-why-converting-list-to-set-is-faster-than-converting-generator-to-set/984421. – Ivers

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 – Nanette

@Ivers 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. – Scevour

@Ivers That looks good to me, and Martijn's analysis is accurate (as usual). – Epithalamium

OTOH, that question doesn't touch on yield from, which has distinct advantages over yield in a Python loop. – Epithalamium

@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. – Ivers

@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. – Ivers

Answer 1

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

Nanette

@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 – Nanette