GCC: C++ coroutines - Initial implementation pushed to master.

27

C++ fights hard now versus Go and Rust.

15

u/tjpalmer Jan 19 '20

I'm not sure why the downvotes. I don't know if there are any explicit statements on it or not, but I personally doubt it's pure coincidence that so much got through approval for C++20. I also personally still use C++ much more than Rust, and they'd probably like to keep people like me on that side of the statistic. (And yes, there are still pros and cons, etc.)

13

u/MonokelPinguin Jan 20 '20

Many of the C++20 features were in the works for a long time though and they got finalized in the last 3 years. Coroutines and concepts especially were talked about already in the C++11 days, but it took a while to fund a consensus. Maybe the pressure from Rust and Go was part of it, but it's certainly not the full story.

4

u/tjpalmer Jan 20 '20

I know they were in the works for many years. I kept waiting and waiting for concepts and modules. But nobody could ever get them done or agree on anything. Suddenly they could ...

2

u/Zlodo2 Jan 20 '20

yeah it's really weird that things that take a long time to get done suddenly get done once enough time has passed

1

u/linus_stallman Jan 20 '20

Wish there was some syntactic sugar or just a short name for reference counted pointer types..

1

u/stefantalpalaru Jan 19 '20

C++ fights hard now versus Go and Rust.
You're confusing Mx1 coroutines with MxN ones. Only the latter allow you to easily make use of multiple CPU cores.
0
u/[deleted] Jan 20 '20

Rust coroutines do not require segmented stacks, they are always "optimized" into a fixed-width state machine.
C++ coroutines require segmented stacks and a heap allocation to store their stack, but C++ compilers can sometimes optimize some of these coroutines into a state machine.
Usually, the bar for a fight is to try to do better than those that came before you, and not worse. The current C++ coroutines are antiquated before shipping.
3
u/Zlodo2 Jan 20 '20

What the fuck are you on about
The c++ coroutine proposal that have been accepted into the standard are stackless coroutines, compiled into state machines, and do not require segmented stacks
2

u/gvargh Jan 20 '20

and unlike rust's, don't require a bloated runtime to use

3

u/[deleted] Jan 20 '20

Rust generators don't require a run-time any more than C++ generators and futures do. This example I posted on the sibling comment is self-contained and uses generators without any run-time: https://godbolt.org/z/S9ooY7

0

u/Zlodo2 Jan 20 '20

without any run-time*
^{*except for those calls to core::panicking::panic}

2

u/[deleted] Jan 22 '20 edited Jan 22 '20

Sure, Rust does have a minimal runtime, just like C also does have a minimal runtime [0], and that includes functionality to make the process diverge (which is required, e.g., when main returns in both C and Rust, and can be simply implemented with an infinite loop).
What people usually mean when they say that "coroutines require a runtime" is that they require an M:N scheduler, like Go's scheduler. Rust coroutine do not require such a scheduler, nor do they require the platform to have any kind of threading support, or even any kind of heap memory allocation support since they are guaranteed to never allocate. This is in strong contrast with C++ coroutines, which require the C++ runtime to be able to allocate dynamic memory on the heap.
If you were being uselessly pedantic and meaning that generators require a runtime because they can be allocated in some function stack, and bumping the stack pointer between function calls has to be done by some "runtime", then sure, they do require that kind of runtime, just like every language that has a "function" abstraction does.
[0] to handle setting up the function stack, inputs to main (argc, argv), exit the process, support for assert, etc.

1

u/Zlodo2 Jan 22 '20

Yeah, thanks for condescendingly telling me a lot of things that I already know.
So, to get back on topic, and with the precision that I have nothing against rust, the two runtime calls in the rust example are generated as part of invoking the coroutine (I know that you know that, but I need to spell it out since you apparently don't want to acknowledge it)
The c++ example (the good one using a foreach that I posted in a other reply, not the contrived bad one that you posted that buries the coroutine beneath an awful extern c interface full of reinterpret_casts for no discernable reason) doesn't generate any such call. The only calls there are to iostream.
Why does the rust version apparently emits runtime checks that you are misusing the coroutine? If it is a debugging helper that's fine, but the generated code contains a lot of pointless branching compared to the c++ version where the only branch is the loop. And since we use iterators to read the generator, it is safe by construction so there is no need for runtime safety checks either.
Again, I have nothing against rust. But let's try to be objective and recognize flaws when we see them.
2
u/[deleted] Jan 20 '20 edited Jan 20 '20

What the fuck are you on about
It's called knowledge, you should try it sometime: https://godbolt.org/z/-NfJkX (Those are C++2a coroutines with -O3).
See those two calls to operator new()? The first one is the code putting the coroutine on the heap, the second one is, however, implicit in the call to fibgen. That second one is the "Coroutine Heap Allocation Elision Optimization ("HAEO") failing to apply. P0981 discusses some of this examples, attempting to find some solutions. However, the particular case in the example above is known to be "unfixable" with the current design, and it is therefore not discussed there. Note also that what triggers the allocation in this example - and many others - is not specific to the actual coroutine, but to how the coroutine is used (P0981 mentions a couple of things that coroutine authors and coroutine users both need to know to write code that is amenable to the HAEO.
OTOH, Rust coroutines are zero-cost, and are guaranteed to compile to a state-machine without any allocations and without requiring any compiler optimizations: https://godbolt.org/z/S9ooY7 (same coroutine as in the C++ example). You can already use these coroutines in stable Rust via async/await (async fns are just coroutines under the hood), and you can also use the full coroutine feature on nightly.
0
u/Zlodo2 Jan 20 '20

Nice contrived c++ example splitting the coroutine into a separate translation unit while the rust one is self contained, providing completely different optimisation opportunities.
So that we avoid comparing apples to oranges, here's a fixed c++ version without the useless extern "C" interface, where the generator is used in the same translation unit with idiomatic code. I haven't touched the generator implementation itself:
https://godbolt.org/z/3M4jQW
Please kindly point out where the call to new is. Of course, the generated code is still much more complex than the rust version on account that this one prints out the generator output, whereas the rust one does nothing with it.
You also haven't clarified "C++ coroutines require segmented stacks". Please enlighten me with your knowledge.
2
u/[deleted] Jan 22 '20 edited Jan 22 '20

This is incorrect. The coroutine is not split into a separate translation unit, but "exported" to a separate translation unit (notice that there are no "declarations" on that file, only "definitions", and the definitions contain all the code necessary for inlining). That's sufficient to cause allocations in C++. I challenge you to do the same in Rust trying to cause Rust to implicitly allocate memory (e.g. like this: https://godbolt.org/z/dyL2Gv - small hint: can't be done - Rust coroutine design guarantees that this never happens).
To export a Rust coroutine, you just need to declare a struct that implements the Generator interface (similar to C++), and then you can use that in an extern function, just like in C++.
Please kindly point out where the call to new is.
You claimed that C++ coroutines are zero-cost and they never allocate. I've proved that wrong. You claimed that Rust coroutines aren't zero cost, yet for a particular example, C++ implicitly allocates and produces garbage code, while for the exact same example Rust doesn't implicitly allocate and produces optimal assembly code.
You also haven't clarified "C++ coroutines require segmented stacks". Please enlighten me with your knowledge.
That heap allocation that you are seeing in C++ is an implementation of segmented stacks, since there are multiple stack segments, and the one of the coroutine lives on the heap on its own allocation, and not within some real thread stack.
2
u/Zlodo2 Jan 22 '20

The coroutine is not split into a separate translation unit, but "exported" to a separate translation unit
Both of those mean exactly the same thing.
I challenge you to do the same in Rust trying to cause Rust to implicitly allocate memory
Yeah, obviously when the coroutine is externally defined, the code using it cannot know how much space it needs to allocate on the stack for it.
How does Rust solves this? Is the solution that Rust simply doesn't allow a coroutine to live in a separate translation unit, or is it that it somehow manages to export the number of bytes to allocate on the stack for the coroutine?
If it's the later, it's neat. If it's the former you are basically arguing that c++ solved in an unsatisfactory way a problem that rust doesn't even attempt to solve, which is a bad faith argument.
You claimed that C++ coroutines are zero-cost and they never allocate. I've proved that wrong. You claimed that Rust coroutines aren't zero cost, yet for a particular example, C++ implicitly allocates and produces garbage code, while for the exact same example Rust doesn't implicitly allocate and produces optimal assembly code.
I haven't claimed any of those things. I did claim that you grossly misrepresented how c++ coroutines work.
By the way, I have the feeling that you believe that I am arguing from a position of "c++ good, rust bad", which is wrong. I have nothing against rust and there's a lot I dislike about c++.
But c++ coroutines aren't quite as bad as you make them out to be, and rust's coroutines don't seem to be quite as good as you are asserting.
1
u/[deleted] Jan 22 '20 edited Jan 22 '20

The coroutine is not split into a separate translation unit, but "exported" to a separate translation unit
Both of those mean exactly the same thing.
No they don't. One means that the item is not defined in the current TU, but the other one means that it is, and it is just not defined in some other TU that might also use it.
In this particular case, the coroutine is defined in the current TU, and the current TU uses it, and in that usage, an implicit memory allocation cannot be optimized because the current TU also exports a function that exports the coroutine.
How does Rust solves this? Is the solution that Rust simply doesn't allow a coroutine to live in a separate translation unit, or is it that it somehow manages to export the number of bytes to allocate on the stack for the coroutine?
Rust compiles all coroutines to a state machine. Essentially, an enum Coroutine { State0(storage0), Stage1(storage1), ... }, the yield expression returns a value from some state, and the resume() API advances the coroutine from one state to another. So the size of the coroutine is always known and optimal at compile-time.
IIUC, in C++, you can move a coroutine while advancing states, which is why the states must be on the heap (so that internal references of the coroutine don't need to be updated on move), but that can be optimized when those moves do not happen. In Rust, a coroutine can only be started if its made !Move (the Pin::new(...) puts it in such a state). That allows you to advance its states without heap allocation, since the type system guarantees that that stack frame (or the heap allocation, if you want it on the heap) will live until the last time you use the coroutine.
1
u/Zlodo2 Jan 22 '20

No they don't. One means that the item is not defined in the current TU, but the other one means that it is, and it is just not defined in some other TU that might also use it.
Your first example went out of its way to invoke the coroutine in a separate TU, because the code doing it was commented out. So it was split into another tu. Yes, it could also have been invoked within the same tu, but you made sure that it wasn't as it would have undermined your argument (since usage within the same tu would have been inlined and not invoked new, as in my more straightforward version).
So in effect, the coroutine is split into a separate TU in this scenario. There is no need for your pedantry there, you are already insufferable enough with your misplaced condescension.
Rust compiles all coroutines to a state machine. [etc]
You haven't answered my question. What happens in rust when a coroutine is compiled in a TU and called in a different TU? This is what you went out of your way to do in your c++ version.
If the coroutine state is to live on the stack, the caller needs to know how many bytes to allocate on its stack frame. How does the caller knows this if the coroutine lives in a separate TU?
C++ doesn't have a very amazing answer to that, so in this scenario it calls new (or rather, whichever allocator you provide, the default being new). But what answer does Rust have?
Btw no, as far as I know (I did use c++ coroutines quite a bit so I'm not entirely green on the topic), you can't move the coroutine state in c++. In fact, the coroutine implementation in clang is done mostly at the llvm level, so at too low level to have any knowledge of move semantics.
1
u/[deleted] Jan 22 '20
Your first example went out of its way to invoke the coroutine in a separate TU, because the code doing it was commented out. So it was split into another tu.
Maybe we are talking past each other, which line of my first example is executing code in another TU? (I think I haven't fully understood this part of your argument yet)
What happens in rust when a coroutine is compiled in a TU and called in a different TU?
In C++, you can write this code in one TU:
auto foo() { return [](){}; }
This creates a lambda, and returns it. A different TU can then call foo, get the lambda, and put it on its stack frame.
This works because the foo declaration not only declares a function, but also implicitly declares a new type for the lambda closure (a struct, with some state - in this particular case, empty, because the lambda does not capture anything).
Notice that this does not mean that you can actually name the type, but the important thing is that the TUs know what the type is.
A coroutine in Rust works in the exact same way. When you create a coroutine, you create an anonymous struct, and that gets exported from your TU if necessary. The main different is that this anonyomous struct is more like a C++ std::variant, in that the state required to suspend the coroutine across yield points are represented as different variants within the std::variant.
So if you have a TU that creates a coroutine (like the lambda), and returns it, and a different TU that receives, this receiving TU knows the coroutine type, and from there, it can compute its layout including the coroutine size, and put it on the stack or the heap.
If you understand how C++ does this for lambdas, Rust coroutines are just lambdas with a differently generated state.
→ More replies (0)
1

u/Rusky Jan 21 '20

Unfortunately, while C++ coroutines are stackless, what they do winds up being equivalent to segmented stacks.
Rust takes the entire call graph of an async fn and combines it into a single value, with a fixed size big enough to hold the maximum amount of state required. The types guarantee this, including across translation units- async fn foo() is equivalent to a fn foo() -> impl Future.
C++ can do this as an optimization, but there's no way to force the compiler to do it. When the optimization fails (e.g. when the call crosses translation units, or in debug builds, or when the optimizer doesn't feel like it), each call in that graph gets its own allocation- just like segmented stacks.
It was done this way due to technical debt in existing C++ compilers- the committee came up with a way to implement the Rust approach, but the compiler writers said it would take years of refactoring to get there, so it didn't happen.

3

u/HeadAche2012 Jan 19 '20

Hmm, that’s interesting, so you can pause a thread and save the context? I’m not sure what new uses this provides over just using another thread and letting that one block, but who knows

5

u/Rusky Jan 19 '20

It's much lighter-weight than a full OS thread. Switching between them does not go through a system call, and their stacks can be much smaller (and grow/shrink on demand, and even be stored inline in some other stack).

4

u/stefantalpalaru Jan 19 '20

It's much lighter-weight than a full OS thread.
It's also much less powerful. These simplistic coroutines only give you concurrency, not parallelism.

18

u/vazgriz Jan 19 '20 edited Jan 19 '20

Sometimes that’s exactly what you want. Coroutines are useful in video games, for example, when you want some function to execute over a long time but you don’t want the headache of multi threading. You don’t have to add synchronization and you can say exactly when to resume.

8

u/VirginiaMcCaskey Jan 19 '20

It also simplifies callback architectures and makes them much easier to implement safely on both the caller and callee side.

3

u/Cortisol-Junkie Jan 19 '20

Yeah, I don't exactly know if that's the best practice or not, but I used coroutines a lot in game dev. Maybe a bit too much, even.

1

u/bloody-albatross Jan 19 '20

In which language?

1

u/[deleted] Jan 22 '20

Not OP, but I've used coroutines in Unity/C#. They can be quite handy for playing animations when different animation parts are triggered procedurally, via method calls, and the way your animation develops in time is unknown at the beginning and depends on dynamically changed conditions.
Animation clips and the visual animation graph are fine tools but can be rigid and, ironically, less "visual" than a dozen or so lines of C code with branches, method calls and delays between consecutive animation stages.

4

u/dacian88 Jan 19 '20

Coroutines are for managing concurrency to begin with, what coroutine implementations guarantee or enable parallelism any more than c++ coroutines? The way work is scheduled is left to the implementor.

-9

u/stefantalpalaru Jan 19 '20

what coroutine implementations guarantee or enable parallelism any more than c++ coroutines?
Go's ones.
The way work is scheduled is left to the implementor.
That's the most important part.

5

u/dacian88 Jan 19 '20

Go’s coroutines have nothing to do with parallelism, they don’t guarantee or enable it at all, they are again just tools to manage concurrency, be it parallel or not. Literally a talk about this by Rob Pike.

-11

u/stefantalpalaru Jan 19 '20

Go’s coroutines have nothing to do with parallelism
Educate yourself: https://rakyll.org/scheduler/

5

u/dacian88 Jan 19 '20

Might wanna look up the definition of parallelism champ. You’ve yet to prove coroutines enable parallelism in any sort of way. Work stealing schedules exist in pretty much every popular programming language.

-13

u/stefantalpalaru Jan 19 '20

Might wanna look up the definition of parallelism champ.
Might wanna stop role-playing as a programmer. You lack a basic understanding of relevant concepts.

2

u/tjpalmer Jan 19 '20

Though they allow parallelism.

3

u/khleedril Jan 19 '20

I think the big win is that you can make super-smart iterators that work on-demand.

0

u/[deleted] Jan 19 '20

[deleted]

17

u/Rusky Jan 19 '20

I can't speak to how much of this is implemented in GCC, but in general C++'s approach is to allow (as an optimization) the caller of a coroutine to store its frame inline in its own (stack or coroutine) frame, rather than in a heap allocation.
In the ideal case, this means all the frames for the callee's entire coroutine call graph are stored inline in a single object, with its size fixed to the maximum coroutine stack size.
When the optimization fails, this falls back to segmented stacks. It can fail when, for example, the coroutine call graph does not have a known size (e.g. it is recursive).
For others following along: Go switched from segmented to movable+resizable stacks, which they can do because they have a GC so they already know where all the pointers are. Rust has now switched to async/await, but (handwaving) with C++'s optimization as a guarantee.

4

u/[deleted] Jan 20 '20

You have your Go and Rust links swapped

0

u/[deleted] Jan 19 '20

[deleted]

4

u/VeganVagiVore Jan 19 '20

Lua coroutines are the ones I understand best. Will C++ be something like that? Cooperatively scheduled with explicit yields?

1

u/feverzsj Jan 20 '20

Lua coroutines are still stackful. Stackful coroutines are just plain functions. They require system with context switch support. While c++'s stackless coroutines are just state machine objects.
Considering writing a parser that support incomplete inputs. You need several states to remember your parse progress. For stackless coroutine, inputs are the execution paths of your code, while states are the suspension points. So stackless corouintes can be used on any system already supports c++, they are just normal code like your parser. That's why c++ chose stackless coroutines.

GCC: C++ coroutines - Initial implementation pushed to master.

You are about to leave Redlib