The difference between yield and yield-from

[Guido van Rossum]

I've been asked several times why PEP 3156 insists on using yield-from instead of yield, thereby apparently closing off the possibility of an easy backport to Python 3.2 or even 2.7. In fact, this is probably FAQ #1. I'll try to answer this once and for all, so I can refer to this post when it's being asked again. (I realize this post is too long. Consider it a first draft for an ultimate blog post on the topic. But editing it down would take the rest of the PyCon sprints... So I'm posting now.)

Clearly it's *possible* to write a frameworks like PEP 3156 tasks and futures using just yield. Some examples include Monocle, Twisted inlineCallbacks, and App Engine NDB (which I wrote). In these frameworks, every asynchronous call returns a future (Twisted calls it Deferred, Monocle calls it Callback, NDB calls it a Future), and whenever you want the result of a future, you yield it.

The way that's implemented is as follows. The function containing the yield is (obviously) a generator, so evidently there must be some code which is iterating over it. Let's call this the scheduler. Actually the scheduler isn't "iterating" in the classic sense (with a for-loop); instead, it maintains two collections of futures. I'll call the first collection the "runnable" queue. These are futures whose result is available. As long as this list isn't empty, the scheduler picks one item, and does one iteration step. This step calls the generator's .send() method with the result from the future (which could be some data that was just read from a socket); inside the generator, this result appears as the return value of the yield expression. When send() returns or exits, the schedule then analyzes the outcome (which may be StopIteration, another exception, or some object).

(If I've lost you here, you probably should read up on how generators work, in particular the .send() method. Maybe PEP 342 is a good starting point.)

Anyway, continuing the explanation how a framework using plain yield works, the second collection of futures maintained by the scheduler consists of those futures that are still waiting for some kind of I/O. These are somehow mapped to a select/poll/etc. wrapper that calls a callback when a specific file descriptor is ready for I/O. The callback actually performs the I/O operation requested by the future, sets the result value of the future to the outcome of that I/O operation, and moves the future into the runnable queue. Of course, the exact details are considerably more complex, but they don't really matter for this explanation.

Now we're getting to the interesting bits. Suppose you are writing some complex protocol implementation. Deep inside your protocol you are reading bytes from a socket using its recv() method. Those bytes go into a buffer. The recv() method is wrapped in an async wrapper that sets up the I/O and returns a future that will be completed when the I/O is done, as I explained above. Now suppose there's some other part of your code that wants to read data from the buffer one line at a time. Let's suppose you abstract this away by creating a readline() method. Assuming a buffer size that's quite a bit larger than the average line length, oftentimes your readline() method can just get the next line from the buffer, without blocking; but occasionally the buffer doesn't have a whole line, and now readline() must in turn call recv() on the socket.

Question: should readline() return a future or not? It wouldn't be very nice if it sometimes returned a byte string and other times a future, forcing the caller to do a type check and a conditional yield. So the answer is that readline() must always return a future. When readline() is called, it looks in the buffer, and if it finds at least a whole line there, it creates a future, sets the future's result to the line taken from the buffer, and returns the future. If there's no whole line in the buffer, it initiates the I/O and waits for it, and when the I/O is done it starts over from the top. Details left as an exercise for the reader. In practice there is often another level, where read() itself defers to a lower-level recv() call that actually performs socket I/O.

But now we're creating and yielding a lot of futures that don't need to block for I/O, but that still force a trip to the scheduler -- because readline() returns a future, its caller must yield, and that means going to the scheduler. The scheduler could bounce control right back into the coroutine if it sees that it yielded a future that is already complete, or it could put the future back in the runnable queue. The latter would really slow things down (assuming there's more than one runnable coroutine), since it not only has to wait at the end of the queue, but any memory locality (if there was any to begin with) is probably also lost. And even if the scheduler short-circuited this condition, that's still a fair amount of code in the scheduler.

The net effect of all this is that coroutine authors must be aware of the overhead of yield <future>, and hence there will be a larger psychological barrier to refactoring complex code into more readable subroutines -- much more so than the resistance that already exists because Python's function calls are rather slow. And I remember from talking to Glyph that in a typical async I/O framework, speed is important.

Now let's compare this to yield-from. In my PyCon keynote I hand-waved a lot about how exactly it works, and I've gotten a fair number of questions over time to suggest that it's pretty mysterious even to experienced Python developers who haven't thought much before about how coroutines and Python generators are implemented. So before I go into a detailed comparison I'd like to explain how yield-from really works.

You may have heard that "yield from S" is roughly equivalent to "for i in S: yield i". In the simplest case, that's true, sort of, but for the purpose of understanding coroutines this doesn't do it justice at all. Consider this (don't think of async I/O yet):

def driver(g):
    print(next(g))
    g.send(42)

def gen1():
    val = yield 'okay'
    print(val)

driver(gen1())

This code will print two lines, containing 'okay' and '42' (and then raise an unhandled StopIteration, which you can suppress by adding an extra yield to the end of gen1). You can see this code in action on pythontutor.com, here: http://goo.gl/Q5qpz

Now consider this:

def gen2():
    yield from gen1()

driver(gen2())

This behaves *exactly the same way* (http://goo.gl/rvOR1). Now think about it. How does it work? It cannot be using the naive expansion of yield-from into a for-loop, since in that case it would print None. (Try it: http://goo.gl/R19Jv) What happens is that the yield-from clause acts as a "transparent channel" between the driver and gen1. That is, when gen1 yields the value 'okay', it passes out of gen2, up through the yield-from, to the driver -- and when driver sends the value 42 back into gen2, that value passes back down through the yield-from into gen1 again (where it becomes the result of the yield).

The same would happen if the driver were to throw an exception into the generator: the exception passes down through the yield-from into the inner generator, which gets to handle it. For example:

def throwing_driver(g):
    print(next(g))
    g.throw(RuntimeError('booh'))

def gen1():
    try:
        val = yield 'okay'
    except RuntimeError as exc:
        print(exc)
    else:
        print(val)

    yield

throwing_driver(gen1())

This will print 'okay' and 'bah', and so will this:

def gen2():
    yield from gen1()  # unchanged

throwing_driver(gen2())

(You can see the latter here: http://goo.gl/8tnjk)

Att his point I'd like to introduce some simple (ASCII) graphics to be able to talk about this kind of code. I'm using [ f1 -> f2 -> ... -> fN ) to represent a stack with f1 at the bottom (oldest call frame) and fN at the top (newest call frame), where each item in the list is a generator and -> represent yield-from. Thus the first example, driver(gen1()), has no yield-from, but it has the generator gen1, so it is drawn like this:

[ gen1 )

The second example has gen2 calling gen1 using yield-from, so it is drawn like this:

[ gen2 -> gen1 )

I am using the mathematical notation for half-open interval here, [...), to suggest that another frame can be added to the right when the rightmost generator uses yield-from to invoke another generator, while the left end is more or less fixed. The left end is what the driver (i.e., the scheduler) sees.

I am now ready to go back to the readline() example. We can rewrite readline() as a generator, which invokes read(), another generator, using yield-from; this in turn invokes recv(), which does the actual I/O from the socket. At the very left we have the application, which we assume is also a generator, invoking readline(), again using yield-from. The diagram to describe this is:

[ app -> readline -> read -> recv )

Now the recv() generator sets up the I/O, links it to a future, and passes that future to the scheduler, by using *yield* (not yield-from!). The future bubbles left through both yield-from arrows to the scheduler (positioned to the left of the "["). Note that the scheduler doesn't know (and doesn't care) that it is holding a stack of generators -- all it knows is that it is holding the leftmost generator, and that it just burped up a future. When the I/O is complete, the scheduler sets the result on the future and also sends it back into the generator; the result travels right through both yield-from arrows to the recv generator, which now gets the bytes it wanted to read from the socket as the outcome of its yield.

In other words, the scheduler for a yield-from-based framework handles I/O exactly the same as the scheduler for a yield-base framework that I described before. *But:* it doesn't have to worry about optimizing the case when the future yielded is already complete, since the scheduler is not involved at all in the transfer of control between readline() and read(), or between read() and recv(), and back. So the scheduler is not involved at all when app() calls readline() and readline() can satisfy the request from the buffer (thus not calling read()) -- the interaction between app() and readline() in this case is entirely handled by Python's bytecode interpreter. The scheduler can actually be simpler, and moreover, the number of futures created and managed by the scheduler is smaller, because there are no futures being created and destroyed for every invocation of a subroutine. The only futures that are still necessary are those representing actual I/O, such as the one created by recv().

If you've read this far, you deserve a cookie. I've left out a lot of implementation details, but the above tale is in essence correct.

There's just one more thing I'd like to point out. We *could* make it so that things would work fine if some code used yield-from and some code used yield. But yield requires that there is an actual future at each link in the chain, rather than just a coroutine. Since there are several advantages to use yield-from, I want to make it so that the user doesn't have to remember whether to use yield or yield-from -- the rule is simply to always use yield-from. A simple trick enables even recv() can use yield-from to pass the I/O future to the scheduler: the future's __iter__ method is actually a generator that yields the future. Thus, the *only* place where yield is used in Tulip instead of yield-from, is inside the __iter__ method of its Future class: http://code.google.com/p/tulip/source/browse/tulip/futures.py#239. (Well, actually, there are two others. But those are in a generator used as a regular iterator.)

Oh. One more thing. (Sorry!) What is the return value of yield-from? It turns out it is the return value of the *outermost* generator. Or, more precisely, at each -> arrow, the function on the left of the arrow receives, as the return value of the yield-from represented by the arrow, the value that is returned, using an honest-to-god return statement, by the yield-from immediately to its right. So, while the arrows link the leftmost and rightmost frames together for the purpose of *yielding*, they also represent the transfer of ordinary return values in the usual manner, one stack frame at a time. Exceptions travel back up in the same way; of course you need a try/except at each level to catch them.

--
--Guido van Rossum (python.org/~guido)

[Yuval Greenfield]

I didn't even know 'return' did that with yield from.

The issue of less interaction with the scheduler could use an explicit example as it seems a huge upside to this approach. E.g.

def g():
    sock = yield connect()
    data = yield sock.recv(10)
    data2 = yield sock.recv(10)
   
The fact that every 'yield' would go to the scheduler while if it were 'yield from' some of those could short circuit - blows my mind. IIUC it's because a 'yield' doesn't interact with its argument at all, it just fires it up the stack regardless - whatever is yielded has no control over that.

How or where does one collect proverbial cookies?

Yuval Greenfield
Pardon my top posting from my phone

[Guido van Rossum]

Thanks for supplying the TL;DR (which was dearly missing :-).

On Tue, Mar 19, 2013 at 12:52 AM, Yuval Greenfield <ubers...@gmail.com> wrote:

I didn't even know 'return' did that with yield from.

The issue of less interaction with the scheduler could use an explicit example as it seems a huge upside to this approach. E.g.

def g():
    sock = yield connect()
    data = yield sock.recv(10)
    data2 = yield sock.recv(10)
   
The fact that every 'yield' would go to the scheduler while if it were 'yield from' some of those could short circuit - blows my mind. IIUC it's because a 'yield' doesn't interact with its argument at all, it just fires it up the stack regardless - whatever is yielded has no control over that.

Right. Whereas yield-from gives its argument more freedom, as it is an iterator.
 

How or where does one collect proverbial cookies?

You can get them at any bakery store.

--Guido

[Yuval Greenfield]

On Tue, Mar 19, 2013 at 5:23 PM, Guido van Rossum <gu...@python.org> wrote:

Right. Whereas yield-from gives its argument more freedom, as it is an iterator.

 

Great!

So then the only thing missing for me in the rationale is - why shoehorn iterators into coroutines? IIUC, with a "suspend this stack now" keyword/special-object we would have removed the need for all the "yield from"s. It seems as though this is a complicated way of achieving just that.

Yuval

[Guido van Rossum]

I guess you should have brought that up when we were discussing PEP 380. :-) People have chided me before for not calling it "await". But adding a new keyword is a lot harder than adding new syntax composed of existing keywords. And the superficial equivalence between "yield from X" and "for i in X: yield i" is occasionally useful. And of course there's the matter that we've got a much longer tradition of conflating iterators and coroutines, starting at least with PEP 342. So I say, meh, just deal with it.

[Dave Peticolas]

2013/3/19 Guido van Rossum <gu...@python.org>

I initially had a similar reaction to 'yield from' versus 'await', but after the explanation that started this thread (thank you), I think it is at least as good, and possibly better. Async programming requires careful attention to the points where you are returning control to the scheduler and thus the order of operations is no longer under the strict control of the code you are looking at right now. Since the 'yield' keyword has long implied that you are giving control to a higher-level context, 'yield from' might call that fact to mind better than 'await', which could be misconstrued as 'just wait for this thing on the right to finish, without doing anything else'. The 'yield' in 'yield from' points back to the older context, whereas the 'from' points to the new one.

--
--Dave Peticolas

[Steven Hazel]

As an aside, I couldn't agree more with "Async programming requires careful attention to the points where you are returning control to the scheduler" — sometimes when explaining monocle to programmers familiar with threading and mutexes, I like to say that "yield" also means "unlock EVERYTHING". The hint that "yield" or "yield from" provide vs "await" is a subtle one, but it can't hurt.

But on to my main point: While I think "yield from" is a neat feature for generators, I'm not sold on the idea that "yield from" is a better choice than "yield" for a framework like Tulip. Here are some points to consider:

- The speed advantages of working with "yield from" are small. We haven't seen this as a performance bottleneck in monocle. In fact, we discussed implementing our generator-iterating scheduler piece in C, which I think would be possible and roughly equivalent to the performance improvement from using "yield from", but we haven't gotten around to it because it hasn't been an issue. (This piece of monocle does almost exactly what the "yield from is semantically equivalent to..." code from PEP 380 does.)

- Returning Futures from coroutines has some advantages. They're easy to use from outside coroutine code, so they make libraries written in the coroutine style compatible without translation with libraries written using callbacks (especially if everyone starts standardizing on Futures). And they're clear values for introspection: if a function returns a generator, it's unclear whether that's a potential value to "yield from" in a coroutine, whereas a Future is a clear sign you're dealing with something yieldable.

- For users familiar with "yield from", it will be  apparent that at some low level a "yield" must be necessary.

A) If the lowest-level IO APIs are wrapped in such a way as to make "yield from" work, it will be unclear where that is happening. Users of the framework will have a sense that they don't understand it at the deepest level until they unravel this.

B) If the lowest-level IO APIs aren't wrapped, or if "yield" is used directly with low-level IO functions in some badly written code, then low-level IO will work differently from higher-level user IO functions, making it difficult to replace the low level of IO functions in code that expects to use them. This could be an issue, for example, in seamlessly using SSL with code originally written to work with a TCP socket.

- In general, because yield has to work with Futures, sometimes people will end up using it, making their code unusable with coroutine generators in the process. This will make it necessary to sometimes wrap coroutine generators in a Future. When they're not wrapped, "yield some_generator" will silently yield the wrong type of object and fail later, in an unclear way, in event loop code. On the other hand, "yield some_future" and "yield from some_future" both work. This also makes it tempting to *always* wrap coroutine generators in a Future.

tl;dr: I think yield and Futures make for a nicer-looking and more simply and transparently composable API.  I believe the speed issue with "yield" is not a major one, and can be dealt with in a way equivalent to the speedup experienced with "yield from". The remaining advantages of "yield from" seem to me to be about implementer convenience more than end-user convenience. All end users benefit from an implementation that goes out of its way to make things simple.

[Yuval Greenfield]

On Tue, Mar 19, 2013 at 10:19 PM, Guido van Rossum <gu...@python.org> wrote:

On Tue, Mar 19, 2013 at 1:02 PM, Yuval Greenfield <ubers...@gmail.com> wrote:

So then the only thing missing for me in the rationale is - why shoehorn iterators into coroutines? IIUC, with a "suspend this stack now" keyword/special-object we would have removed the need for all the "yield from"s. It seems as though this is a complicated way of achieving just that.

I guess you should have brought that up when we were discussing PEP 380. :-) People have chided me before for not calling it "await". But adding a new keyword is a lot harder than adding new syntax composed of existing keywords. And the superficial equivalence between "yield from X" and "for i in X: yield i" is occasionally useful.

I like the names `yield` and `yield from`, I'm asking about a different functionality - one that can freeze the entire stack I'm on. I.e. converting any python stack into a generator/coroutine. That way you wouldn't need a "transparent channel" because you could have a "direct channel". The naive approach would be more efficient, O(1) instead of O(stack_size). You can say that you prefer it clearly visible that a function might pause - which `yield from` does clearly signal, and I'd be content I think. Also, we could short-circuit chained `yield from`s behind the scenes.

 

And of course there's the matter that we've got a much longer tradition of conflating iterators and coroutines, starting at least with PEP 342. So I say, meh, just deal with it.

I reread the pep to see if this was discussed and found a minor bug in the trampoline, so I assume it's pseudo code-ish:

    def schedule(self, coroutine, stack=(), value=None, *exc):

        def resume():

            try:

                if exc:

                    value = coroutine.throw(value,*exc)

                else:

                    value = coroutine.send(value)

UnboundLocalError: local variable 'value' referenced before assignment

I'd replace the top with:

    def schedule(self, coroutine, stack=(), val=None, *exc):

        def resume():

            value = val

Yuval

[Guido van Rossum]

On Tue, Mar 19, 2013 at 11:54 PM, Steven Hazel <s...@awesame.org> wrote:

As an aside, I couldn't agree more with "Async programming requires careful attention to the points where you are returning control to the scheduler" — sometimes when explaining monocle to programmers familiar with threading and mutexes, I like to say that "yield" also means "unlock EVERYTHING". The hint that "yield" or "yield from" provide vs "await" is a subtle one, but it can't hurt.

But on to my main point: While I think "yield from" is a neat feature for generators, I'm not sold on the idea that "yield from" is a better choice than "yield" for a framework like Tulip. Here are some points to consider:

- The speed advantages of working with "yield from" are small. We haven't seen this as a performance bottleneck in monocle. In fact, we discussed implementing our generator-iterating scheduler piece in C, which I think would be possible and roughly equivalent to the performance improvement from using "yield from", but we haven't gotten around to it because it hasn't been an issue. (This piece of monocle does almost exactly what the "yield from is semantically equivalent to..." code from PEP 380 does.)

- Returning Futures from coroutines has some advantages. They're easy to use from outside coroutine code, so they make libraries written in the coroutine style compatible without translation with libraries written using callbacks (especially if everyone starts standardizing on Futures). And they're clear values for introspection: if a function returns a generator, it's unclear whether that's a potential value to "yield from" in a coroutine, whereas a Future is a clear sign you're dealing with something yieldable.

- For users familiar with "yield from", it will be  apparent that at some low level a "yield" must be necessary.

A) If the lowest-level IO APIs are wrapped in such a way as to make "yield from" work, it will be unclear where that is happening. Users of the framework will have a sense that they don't understand it at the deepest level until they unravel this.

B) If the lowest-level IO APIs aren't wrapped, or if "yield" is used directly with low-level IO functions in some badly written code, then low-level IO will work differently from higher-level user IO functions, making it difficult to replace the low level of IO functions in code that expects to use them. This could be an issue, for example, in seamlessly using SSL with code originally written to work with a TCP socket.

- In general, because yield has to work with Futures, sometimes people will end up using it, making their code unusable with coroutine generators in the process. This will make it necessary to sometimes wrap coroutine generators in a Future. When they're not wrapped, "yield some_generator" will silently yield the wrong type of object and fail later, in an unclear way, in event loop code. On the other hand, "yield some_future" and "yield from some_future" both work. This also makes it tempting to *always* wrap coroutine generators in a Future.

tl;dr: I think yield and Futures make for a nicer-looking and more simply and transparently composable API.  I believe the speed issue with "yield" is not a major one, and can be dealt with in a way equivalent to the speedup experienced with "yield from". The remaining advantages of "yield from" seem to me to be about implementer convenience more than end-user convenience. All end users benefit from an implementation that goes out of its way to make things simple.

Steven, thanks for your feedback, but I'm not convinced. Anybody who fears coroutines can use Tulip's @task decorator instead of its @coroutine decorator, and get the effect you are asking for. Also, I actually have rigged things so that if you use plain yield with a Future, it will give you a nice error message. (Future.__iter__() sets a special flag to prevent this error from happening when it uses "yield self" to reach out to the scheduler; the scheduler resets the flag.)

I would recommend that we postpone judgment on this until we have had much more experiencing writing real apps using the yield-from style -- there is very little experience so far (although nothing indicating problems), so I think it's too soon to start worrying.

PS. What do you do in Monocle to produce reasonable tracebacks when an uncaught error passes through several levels of coroutines? In NDB I had to do a lot of work to make the right stack frames (and only those!) appear in the traceback. With yield-from, the interpreter does this work for you: when an exception passes through several layers of yield-from the tracecback ultimately printed looks completely natural. So far I have not had any trouble reading stack traces, even though I haven't had the time to do anything special about them.

[Guido van Rossum]

On Wed, Mar 20, 2013 at 7:27 AM, Yuval Greenfield <ubers...@gmail.com> wrote:

On Tue, Mar 19, 2013 at 10:19 PM, Guido van Rossum <gu...@python.org> wrote:

On Tue, Mar 19, 2013 at 1:02 PM, Yuval Greenfield <ubers...@gmail.com> wrote:

So then the only thing missing for me in the rationale is - why shoehorn iterators into coroutines? IIUC, with a "suspend this stack now" keyword/special-object we would have removed the need for all the "yield from"s. It seems as though this is a complicated way of achieving just that.

I guess you should have brought that up when we were discussing PEP 380. :-) People have chided me before for not calling it "await". But adding a new keyword is a lot harder than adding new syntax composed of existing keywords. And the superficial equivalence between "yield from X" and "for i in X: yield i" is occasionally useful.

I like the names `yield` and `yield from`, I'm asking about a different functionality - one that can freeze the entire stack I'm on. I.e. converting any python stack into a generator/coroutine. That way you wouldn't need a "transparent channel" because you could have a "direct channel". The naive approach would be more efficient, O(1) instead of O(stack_size). You can say that you prefer it clearly visible that a function might pause - which `yield from` does clearly signal, and I'd be content I think. Also, we could short-circuit chained `yield from`s behind the scenes.

What you're suggesting here is what greenlets do, and hence that's how gevent works. But I don't like it -- I think I explained in my keynote what the problem is: there is no guarantee that there won't be unexpected task switches, because a task switch could be invoked by any call, even any overloaded operation. This is why I like the explicitness of yield-from. There has been some work on the implementation of yield-from to do the short-circuit you're talking about -- I don't recall its status, I believe it was in the original patch, but it was removed because there were problems with it; perhaps it has been put back already after addressing those problems, perhaps the fix is still languishing somewhere in a tracker issue.

 

And of course there's the matter that we've got a much longer tradition of conflating iterators and coroutines, starting at least with PEP 342. So I say, meh, just deal with it.

I reread the pep to see if this was discussed and found a minor bug in the trampoline, so I assume it's pseudo code-ish:

    def schedule(self, coroutine, stack=(), value=None, *exc):

        def resume():

            try:

                if exc:

                    value = coroutine.throw(value,*exc)

                else:

                    value = coroutine.send(value)

UnboundLocalError: local variable 'value' referenced before assignment

I'd replace the top with:

    def schedule(self, coroutine, stack=(), val=None, *exc):

        def resume():

            value = val

Good one. I'll fix that.

[Steve Dower]

> Steven Hazel wrote:
> [snip]

>
> - The speed advantages of working with "yield from" are small. We haven't seen
> this as a performance bottleneck in monocle. In fact, we discussed implementing
> our generator-iterating scheduler piece in C, which I think would be possible
> and roughly equivalent to the performance improvement from using "yield from",
> but we haven't gotten around to it because it hasn't been an issue. (This piece
> of monocle does almost exactly what the "yield from is semantically equivalent
> to..." code from PEP 380 does.)
>

> [snip]

While I agree with most of your points and have made them before, I've already lost this argument so I'm not going to wade into it again :)

But, I have actually implemented the generator-iterating scheduler piece in C myself, expecting to see a similar reduction in overhead to using yield from. While I didn't spend a lot of time tuning it, there just wasn't the order-of-magnitude speedup that we often expect when porting Python to C.

Cheers,
Steve

[Antoine Pitrou]

> But, I have actually implemented the generator-iterating scheduler piece
> in C myself, expecting to see a similar reduction in overhead to using
> yield from. While I didn't spend a lot of time tuning it, there just
> wasn't the order-of-magnitude speedup that we often expect when porting
> Python to C.

Porting to Python to C only yields (!) an order of magnitude speedup
when you convert your code to native C idioms (custom types and data
structures), not it you merely write the C-API equivalent of the original
Python code.

Regards

Antoine.

[Steve Dower]

Thanks. That's a much clearer way of saying what I was trying to imply :)


Steve