Replying to myself here... Jacob Holm wrote:
I think I can actually see a way to do it that should be fast enough, but I'd like to work out the details first. If it works it will be O(1) with low constants as long as you don't build trees, and similar to traversing a delegation chain in the worst case.
All this depends on getting it working using delegation chains first though, as most of the StopIteration and Exception handling would be the same.
I have now worked out the details, and it is indeed possible to get O(1) for simple cases and amortized O(logN) in general, all with fairly low constants. I have implemented the tree structure as a python module and added a trampoline-based pure-python implementation of "yield-from" to try it out. It seems that this version beats a normal "for v in it: yield v" when the delegation chains get around 90 generators deep. This may sound like much, but keep in mind that this is all in python. I expect a C implementation of this would break even much sooner than that (hoping for <5). If you (or anyone else) is interested I can post the code here. (Or you can suggest a good place to upload it). Regards Jacob