8 ms·

C++ Coroutine Theory (2017)

190 points by squiguy7 9y ago

psyc 9y ago
Do C++ coroutines give you a sane call stack when chained? I’ve only worked with proprietary implementations that do not, and it is an utter catastrophe for maintenance once they have infested a large code base.
- paulddraper 9y ago
  IDK, but stack space is a big reason people say "threads are heavy". There is a trade-off.
  - vvanders 9y ago
    Threads are heavy because of the context switches and mutexes involved. Coroutines can be very lightweight(see Lua for instance).
    - BeeOnRope 9y ago
      It depends what you mean by "heavy", but the common example is something like thread-per-request or implementing async IO using threads that make blocking calls. In those context threads are primary "heavy" because each thread needs a dedicated stack, so there is a pretty low limit on the total number of threads you can have based on your available memory, so you run into scaling limitations whenever you'd naturally want to have 100 of thousands or millions of such threads. The CPU use of context switches is a secondary factor there and probably pales compared to IO costs - and some competing designs also have context switch costs. Threads were also heavy in the sense that if they are OS scheduled, the behavior often degrades with large numbers of threads, depending on the implementation. Recent scheduler designs are mostly able to mitigate this, however.
- gumby 9y ago
  Given the semantics of coroutines, what would you consider a sane call stack? Should each routine have its own stack? This is not a glib question, I genuinely don't know what the proper answer might be. Perhaps what's needed is a different debugger mechanism?
  - spc476 9y ago
    My own implementation of coroutines for C [1] requires each coroutine to have its own stack. It simplifies things quite a bit. [1] https://github.com/spc476/C-Coroutines https://github.com/spc476/C-Coroutines [2] [2] More of a "proof-of-concept" than something really meant for production.
- wahern 9y ago
  There's something truly perverse about the way languages are recapitulating the evolution of call stacks in the form of coroutines[1] and promises. Erlang, Go, Lua, and Scheme get this right. Stackless Python never caught on :( But Java may get proper stackful coroutines in the near future. [1] Stackless coroutines, which means you can't yield across nested function invocations. The unfortunately named Stackless Python actually implements stackful coroutines. "Stackless" in Stackless Python refers to not implementing the Python call stack on the C ABI stack. Stackful coroutines are basically threads (sometimes called microthreads or fibers to distinguish from C ABI/kernel thread construct) with a language-level construct for directly passing control to another thread.
  - Rusky 9y ago
    There's nothing about stackless coroutines that means you can't have good stack traces. For example, C# already does it, at least to some degree. Stackful coroutines are clearly a viable tool, but they don't work in all use cases. They require either segmented stacks, a precise GC, or memory usage comparable to kernel threads. They are tricky to implement correctly on Windows. Etc. In my ideal world, we'd have stackless coroutines with great debugger support everywhere, with languages free to experiment with the syntax- explicit suspension points, implicit suspension points, effect polymorphism to make it look like you're yielding across nested function calls, etc...
    - wahern 9y ago
      > They require either segmented stacks, a precise GC Which is _exactly_ what stackless coroutines and promises do in a very roundabout manner. Some languages are moving toward annotations to automate chaining, but the problem with having to explicitly annotate coroutines is that you no longer have (or can have) first-class functions; at best you now have multiple classes of functions that only interoperate seamlessly with their own kind, which is the opposite of first-class functions. Plus it's much slower than just using a traditional call stack. Implementing transparently growable or moveable stacks can be difficult, yes. Solving C ABI FFI issues is a headache. And languages that stack-allocate variables but cannot easily move them are in a real pickle. Though, they can do as Go and only stack-allocate variables that don't have their address taken, and in any event that only applies to C++ and Rust. There's no excuse for all the other modern languages. Languages like Python and JavaScript don't have stackful coroutines because of short-sighted implementation decisions that are now too costly to revisit. Similarly, Perl 6 doesn't officially have them because they prematurely optimized their semantics for targets like the JVM where efficient implementations were thought to be difficult. (Moar VM implements stackful coroutines to support gather/take, which shows that it was simply easier to implement the more powerful construct in order to support the less powerful gather/take construct.) If it were easy we wouldn't have stackless coroutines at all because they're objectively inferior in every respect, and absent external constraints (beholden to the C stack) can result in less memory usage and fewer wasted CPU cycles in both the common and edge cases. But both PUC Lua and LuaJIT do it properly and are among the fastest interpreted and JIT'd implementations, respectively, so I think the difficulty is exaggerated. I understand why these other constructs exist, but I still think it's perverse. At some point we should just revisit and revise the underlying platform ABI so we can get to a place where implementing stackful coroutines is easier for all languages. For example, the very same debugging information you might add to improve stack traces can be used by implementations to help, say, move objects. Make that mandatory as part of the ABI and a lot of cool things become possible, including easy reflection in compiled languages. DWARF is heavyweight and complex, but Solaris (and now FreeBSD and OpenBSD) support something called Compact C Type Format (CTF) for light-weight type descriptions, which shows how system ABIs could usefully evolve. Newer languages shouldn't be tying themselves to incidental semantics from 40 years ago. Rather, they should be doing what hardware and software engineers were doing 40 years ago when they defined the primary semantics--properly abstract call stacks/call state into a first-class construct (i.e. thread of control), while simultaneously pushing the implementation details down so they can be performant.
- jayd16 9y ago
  >I’ve only worked with proprietary implementations that do not Hmm, what does this mean? I've used coroutines in Unity and to that respect, yielding functions in C# as well as generators in Python. The stacks are sane in the sense that they include the current running iteration. Is that tricky to implement? Are you expecting something different? Seems pretty straight forward to me.
- ioquatix 9y ago
  In my experience it depends on the tooling - both the compiler needs to allow for insertion of the necessary debugging symbols, and the debugger needs to interpret them correctly. I'd like to improve this situation, right now the following markers are commented out because I've had issues with them. https://github.com/kurocha/concurrent/blob/8334ecf758b43eac3de6b379edfdd91fdccc1da9/source/Concurrent/coro.c#L92-L101 https://github.com/kurocha/concurrent/blob/8334ecf758b43eac3...
steveklabnik 9y ago
The visualization here is excellent; exactly the kind of thing I've been meaning to look up.
KeepFlying 9y ago
Dumb question, but is this something that a dev would expect the compiler to do for us automatically depending on what is deemed most efficient or is this something that a developer can write directly into the code to make it work this way? I want to be sure I understand what is going on here to be sure. Can someone offer an example of where this ability would be particularly useful?
- gumby 9y ago
  Read the wikipedia page on coroutines first. It's a fairly basic concept in computer science. It's a different model of control structure, primarily when you have a thing that produces data and a thing that consumes it. It could be in multiple threads, multiple machines, or just a single thread, so is often included in multiprocessing portions of designs, standards and instruction.
  - ioquatix 9y ago
    Actually, a coroutine is just a more generalised function - it's a function which retains it's state over multiple calls. I recommend watching this video, which has a great overview. https://www.youtube.com/watch?v=_fu0gx-xseY https://www.youtube.com/watch?v=_fu0gx-xseY
- Twisol 9y ago
  Coroutines are quite nice for managing sessions with asynchronous events, like stateful GUIs or client-server interactions. If you're familiar with the tendency of callbacks in e.g. JavaScript to nest deeply, you can think of coroutines as a way to recover a flat, procedural style. I'm a particular fan of how coroutines work in Lua. Here's an article that helps explain them a bit in that context: http://leafo.net/posts/itchio-and-coroutines.html http://leafo.net/posts/itchio-and-coroutines.html
  - vvanders 9y ago
    Yeah, they're awesome for doing sequences of events that can have temporal gaps in the middle. We used to use them(Lua) in games to do scripted sequences and AI. Was simple enough that even our designers could edit/extend them.
eptcyka 9y ago
Seems like this would be more like tokio for Rust rather than Go's goroutines.
- steveklabnik 9y ago
  Yes, and we're exploring a similar thing in Rust right now, though we call them "generators." A key question right now is, can we have an implementation where the heap allocations that occur here don't have to? It's not 100% clear.
  - tmandry 9y ago
    The post says that if a compiler can prove "that the lifetime of the coroutine is indeed strictly nested within the lifetime of the caller", it would be able to avoid heap allocations. It makes it sound like an optional optimization, though. I think Rust clearly has an advantage here: since lifetimes are well-defined concept in the language itself, it should also be well-defined whether a generator can be allocated on the stack. Of course, I'm probably missing some hairy edge cases here. Another aspect I found interesting was the ability to define custom code which runs every time a certain coroutine is suspended, or returns. In my reading, this allows for the coroutine to e.g. manage its own membership in a resume queue. Tokio tackles this problem differently, but is this more powerful than Rust coroutines? Is there a mechanism by which a generic type could be used to wrap a generator and provide this functionality in a similar way? Asking partly as a point of conversation, and partly as someone who isn't fully steeped in Rust's type system yet.
    - steveklabnik 9y ago
      Yes, the issue here is what happens on moves? https://boats.gitlab.io/blog/post/2018-01-25-async-i-self-referential-structs/ https://boats.gitlab.io/blog/post/2018-01-25-async-i-self-re... and the two follow up posts are the latest thinking on this topic, and by latest, I mean "posted in the last few days". This is cutting-edge stuff! The intention is for this stuff to support Tokio; that is, generators make asyc/await work, which lets you write futures code more easily, to be run with Tokio.
pokoleo 9y ago
Waterloo's CS 343 (concurrency) course uses coroutines as a stepping block towards understanding concurrent programming. Notes from the course are fantastic, coroutines start here: https://www.student.cs.uwaterloo.ca/~cs343/documents/notes.pdf#page=33 https://www.student.cs.uwaterloo.ca/~cs343/documents/notes.p...
- 3uclid 9y ago
  Would you recommend CS 343? I'm disappointed the course teaches μC++ rather than referencing C++11 threading support.
  - z0r 9y ago
    i vaguely remember the course being fine when i took it about a decade ago. teaching concurrency using such a unique language is a little strange but the reasoning is transferable. in practice you'll probably end up having to learn the specifics of whatever platform you might use if you end up professionally writing concurrent code.
  - setheron 9y ago
    I liked that course a lot. Many of the ideas were easily transferable. I would love to have applied test driven development to my courses.
  - AnthonyCalandra 9y ago
    If it helps I had the same reservation about the course but ended up enjoying uC++. Some things like coroutines, monitors, etc. do not have C++ equivalents yet so there's part of the reason. I found uC++ to be a really useful learning tool.
  - legojoey17 9y ago
    It has been one of my favourite courses because it really dives into the fundamentals and implementation of how concurrency models work, is very learnable but still applicable. The primitives uC++ make it very easy to form the concurrency models that are present in other languages and these days the prof does exactly that and shows exactly how to implement common models, such as channels, actors, and a few others. Everything done is very mappable to how other languages provide concurrency.
jnordwick 9y ago
Does anybody know if there has been some research and experimentation with inlining? It is probably the most important part of an optimizing compiler, and coroutines would seem to make that very difficult or impossible.
- lucozade 9y ago
  I'd recommend looking at the work the LLVM team have done on this. [0] for example and there is a Youtube video from one of the LLVM confs if I recall correctly. In a nutshell they are still researching this but their general approach is to split the coroutine up and devirtualise/inline the parts where they can. [0] https://llvm.org/devmtg/2016-11/Slides/Nishanov-LLVMCoroutines.pdf https://llvm.org/devmtg/2016-11/Slides/Nishanov-LLVMCoroutin...
RajuVarghese 9y ago
Modula-2, one of the early languages with coroutines, had a pretty simple implementation. With NEWCOROUTINE a new coroutine was created (including the heap memory that would function as a workspace for that coroutine), TRANSFER to transfer control from one coroutine to another and IOTRANSFER to do the same but for interrupts. With these one could design a scheduler and off you went! I had built a coroutine system for a Pascal environment by implementing NEWCOROUTINE and TRANSFER. Both turned out to be pretty simple in assembly language. The workspace contained an area for the CPU registers and the stack. So TRANSFER involved saving the registers of one coroutine in the workspace and restoring the registers from the second.

190 points by squiguy7 9y ago

psyc 9y ago

Do C++ coroutines give you a sane call stack when chained? I’ve only worked with proprietary implementations that do not, and it is an utter catastrophe for maintenance once they have infested a large code base.

paulddraper 9y ago
IDK, but stack space is a big reason people say "threads are heavy". There is a trade-off.
- vvanders 9y ago
  Threads are heavy because of the context switches and mutexes involved. Coroutines can be very lightweight(see Lua for instance).
  - BeeOnRope 9y ago
    It depends what you mean by "heavy", but the common example is something like thread-per-request or implementing async IO using threads that make blocking calls. In those context threads are primary "heavy" because each thread needs a dedicated stack, so there is a pretty low limit on the total number of threads you can have based on your available memory, so you run into scaling limitations whenever you'd naturally want to have 100 of thousands or millions of such threads. The CPU use of context switches is a secondary factor there and probably pales compared to IO costs - and some competing designs also have context switch costs. Threads were also heavy in the sense that if they are OS scheduled, the behavior often degrades with large numbers of threads, depending on the implementation. Recent scheduler designs are mostly able to mitigate this, however.
gumby 9y ago
Given the semantics of coroutines, what would you consider a sane call stack? Should each routine have its own stack? This is not a glib question, I genuinely don't know what the proper answer might be. Perhaps what's needed is a different debugger mechanism?
- spc476 9y ago
  My own implementation of coroutines for C [1] requires each coroutine to have its own stack. It simplifies things quite a bit. [1] https://github.com/spc476/C-Coroutines https://github.com/spc476/C-Coroutines [2] [2] More of a "proof-of-concept" than something really meant for production.
wahern 9y ago
There's something truly perverse about the way languages are recapitulating the evolution of call stacks in the form of coroutines[1] and promises. Erlang, Go, Lua, and Scheme get this right. Stackless Python never caught on :( But Java may get proper stackful coroutines in the near future. [1] Stackless coroutines, which means you can't yield across nested function invocations. The unfortunately named Stackless Python actually implements stackful coroutines. "Stackless" in Stackless Python refers to not implementing the Python call stack on the C ABI stack. Stackful coroutines are basically threads (sometimes called microthreads or fibers to distinguish from C ABI/kernel thread construct) with a language-level construct for directly passing control to another thread.
- Rusky 9y ago
  There's nothing about stackless coroutines that means you can't have good stack traces. For example, C# already does it, at least to some degree. Stackful coroutines are clearly a viable tool, but they don't work in all use cases. They require either segmented stacks, a precise GC, or memory usage comparable to kernel threads. They are tricky to implement correctly on Windows. Etc. In my ideal world, we'd have stackless coroutines with great debugger support everywhere, with languages free to experiment with the syntax- explicit suspension points, implicit suspension points, effect polymorphism to make it look like you're yielding across nested function calls, etc...
  - wahern 9y ago
    > They require either segmented stacks, a precise GC Which is _exactly_ what stackless coroutines and promises do in a very roundabout manner. Some languages are moving toward annotations to automate chaining, but the problem with having to explicitly annotate coroutines is that you no longer have (or can have) first-class functions; at best you now have multiple classes of functions that only interoperate seamlessly with their own kind, which is the opposite of first-class functions. Plus it's much slower than just using a traditional call stack. Implementing transparently growable or moveable stacks can be difficult, yes. Solving C ABI FFI issues is a headache. And languages that stack-allocate variables but cannot easily move them are in a real pickle. Though, they can do as Go and only stack-allocate variables that don't have their address taken, and in any event that only applies to C++ and Rust. There's no excuse for all the other modern languages. Languages like Python and JavaScript don't have stackful coroutines because of short-sighted implementation decisions that are now too costly to revisit. Similarly, Perl 6 doesn't officially have them because they prematurely optimized their semantics for targets like the JVM where efficient implementations were thought to be difficult. (Moar VM implements stackful coroutines to support gather/take, which shows that it was simply easier to implement the more powerful construct in order to support the less powerful gather/take construct.) If it were easy we wouldn't have stackless coroutines at all because they're objectively inferior in every respect, and absent external constraints (beholden to the C stack) can result in less memory usage and fewer wasted CPU cycles in both the common and edge cases. But both PUC Lua and LuaJIT do it properly and are among the fastest interpreted and JIT'd implementations, respectively, so I think the difficulty is exaggerated. I understand why these other constructs exist, but I still think it's perverse. At some point we should just revisit and revise the underlying platform ABI so we can get to a place where implementing stackful coroutines is easier for all languages. For example, the very same debugging information you might add to improve stack traces can be used by implementations to help, say, move objects. Make that mandatory as part of the ABI and a lot of cool things become possible, including easy reflection in compiled languages. DWARF is heavyweight and complex, but Solaris (and now FreeBSD and OpenBSD) support something called Compact C Type Format (CTF) for light-weight type descriptions, which shows how system ABIs could usefully evolve. Newer languages shouldn't be tying themselves to incidental semantics from 40 years ago. Rather, they should be doing what hardware and software engineers were doing 40 years ago when they defined the primary semantics--properly abstract call stacks/call state into a first-class construct (i.e. thread of control), while simultaneously pushing the implementation details down so they can be performant.
jayd16 9y ago
>I’ve only worked with proprietary implementations that do not Hmm, what does this mean? I've used coroutines in Unity and to that respect, yielding functions in C# as well as generators in Python. The stacks are sane in the sense that they include the current running iteration. Is that tricky to implement? Are you expecting something different? Seems pretty straight forward to me.
ioquatix 9y ago
In my experience it depends on the tooling - both the compiler needs to allow for insertion of the necessary debugging symbols, and the debugger needs to interpret them correctly. I'd like to improve this situation, right now the following markers are commented out because I've had issues with them. https://github.com/kurocha/concurrent/blob/8334ecf758b43eac3de6b379edfdd91fdccc1da9/source/Concurrent/coro.c#L92-L101 https://github.com/kurocha/concurrent/blob/8334ecf758b43eac3...

steveklabnik 9y ago

The visualization here is excellent; exactly the kind of thing I've been meaning to look up.

KeepFlying 9y ago

Dumb question, but is this something that a dev would expect the compiler to do for us automatically depending on what is deemed most efficient or is this something that a developer can write directly into the code to make it work this way? I want to be sure I understand what is going on here to be sure. Can someone offer an example of where this ability would be particularly useful?

gumby 9y ago
Read the wikipedia page on coroutines first. It's a fairly basic concept in computer science. It's a different model of control structure, primarily when you have a thing that produces data and a thing that consumes it. It could be in multiple threads, multiple machines, or just a single thread, so is often included in multiprocessing portions of designs, standards and instruction.
- ioquatix 9y ago
  Actually, a coroutine is just a more generalised function - it's a function which retains it's state over multiple calls. I recommend watching this video, which has a great overview. https://www.youtube.com/watch?v=_fu0gx-xseY https://www.youtube.com/watch?v=_fu0gx-xseY
Twisol 9y ago
Coroutines are quite nice for managing sessions with asynchronous events, like stateful GUIs or client-server interactions. If you're familiar with the tendency of callbacks in e.g. JavaScript to nest deeply, you can think of coroutines as a way to recover a flat, procedural style. I'm a particular fan of how coroutines work in Lua. Here's an article that helps explain them a bit in that context: http://leafo.net/posts/itchio-and-coroutines.html http://leafo.net/posts/itchio-and-coroutines.html
- vvanders 9y ago
  Yeah, they're awesome for doing sequences of events that can have temporal gaps in the middle. We used to use them(Lua) in games to do scripted sequences and AI. Was simple enough that even our designers could edit/extend them.

eptcyka 9y ago

Seems like this would be more like tokio for Rust rather than Go's goroutines.

steveklabnik 9y ago
Yes, and we're exploring a similar thing in Rust right now, though we call them "generators." A key question right now is, can we have an implementation where the heap allocations that occur here don't have to? It's not 100% clear.
- tmandry 9y ago
  The post says that if a compiler can prove "that the lifetime of the coroutine is indeed strictly nested within the lifetime of the caller", it would be able to avoid heap allocations. It makes it sound like an optional optimization, though. I think Rust clearly has an advantage here: since lifetimes are well-defined concept in the language itself, it should also be well-defined whether a generator can be allocated on the stack. Of course, I'm probably missing some hairy edge cases here. Another aspect I found interesting was the ability to define custom code which runs every time a certain coroutine is suspended, or returns. In my reading, this allows for the coroutine to e.g. manage its own membership in a resume queue. Tokio tackles this problem differently, but is this more powerful than Rust coroutines? Is there a mechanism by which a generic type could be used to wrap a generator and provide this functionality in a similar way? Asking partly as a point of conversation, and partly as someone who isn't fully steeped in Rust's type system yet.
  - steveklabnik 9y ago
    Yes, the issue here is what happens on moves? https://boats.gitlab.io/blog/post/2018-01-25-async-i-self-referential-structs/ https://boats.gitlab.io/blog/post/2018-01-25-async-i-self-re... and the two follow up posts are the latest thinking on this topic, and by latest, I mean "posted in the last few days". This is cutting-edge stuff! The intention is for this stuff to support Tokio; that is, generators make asyc/await work, which lets you write futures code more easily, to be run with Tokio.

pokoleo 9y ago

Waterloo's CS 343 (concurrency) course uses coroutines as a stepping block towards understanding concurrent programming. Notes from the course are fantastic, coroutines start here: https://www.student.cs.uwaterloo.ca/~cs343/documents/notes.pdf#page=33 https://www.student.cs.uwaterloo.ca/~cs343/documents/notes.p...

3uclid 9y ago
Would you recommend CS 343? I'm disappointed the course teaches μC++ rather than referencing C++11 threading support.
- z0r 9y ago
  i vaguely remember the course being fine when i took it about a decade ago. teaching concurrency using such a unique language is a little strange but the reasoning is transferable. in practice you'll probably end up having to learn the specifics of whatever platform you might use if you end up professionally writing concurrent code.
- setheron 9y ago
  I liked that course a lot. Many of the ideas were easily transferable. I would love to have applied test driven development to my courses.
- AnthonyCalandra 9y ago
  If it helps I had the same reservation about the course but ended up enjoying uC++. Some things like coroutines, monitors, etc. do not have C++ equivalents yet so there's part of the reason. I found uC++ to be a really useful learning tool.
- legojoey17 9y ago
  It has been one of my favourite courses because it really dives into the fundamentals and implementation of how concurrency models work, is very learnable but still applicable. The primitives uC++ make it very easy to form the concurrency models that are present in other languages and these days the prof does exactly that and shows exactly how to implement common models, such as channels, actors, and a few others. Everything done is very mappable to how other languages provide concurrency.

jnordwick 9y ago

Does anybody know if there has been some research and experimentation with inlining? It is probably the most important part of an optimizing compiler, and coroutines would seem to make that very difficult or impossible.

lucozade 9y ago
I'd recommend looking at the work the LLVM team have done on this. [0] for example and there is a Youtube video from one of the LLVM confs if I recall correctly. In a nutshell they are still researching this but their general approach is to split the coroutine up and devirtualise/inline the parts where they can. [0] https://llvm.org/devmtg/2016-11/Slides/Nishanov-LLVMCoroutines.pdf https://llvm.org/devmtg/2016-11/Slides/Nishanov-LLVMCoroutin...

RajuVarghese 9y ago

Modula-2, one of the early languages with coroutines, had a pretty simple implementation. With NEWCOROUTINE a new coroutine was created (including the heap memory that would function as a workspace for that coroutine), TRANSFER to transfer control from one coroutine to another and IOTRANSFER to do the same but for interrupts. With these one could design a scheduler and off you went! I had built a coroutine system for a Pascal environment by implementing NEWCOROUTINE and TRANSFER. Both turned out to be pretty simple in assembly language. The workspace contained an area for the CPU registers and the stack. So TRANSFER involved saving the registers of one coroutine in the workspace and restoring the registers from the second.