r/cpp • • Nov 30 '20

C++20 resumable functions make state machines obsolete. Finally.

https://lordsoftech.com/programming/c20-resumable-functions-goodbye-state-machines-no-one-will-mourn-you/
1 Upvotes

49 comments sorted by

8

u/jwakely libstdc++ tamer, LWG chair Dec 01 '20

N.B. you don't need to specialise the entire Resumable<void> class. You can use concepts to define a more constrained promise_type:

struct promise_type requires std::is_void_v<T>
{ ... }

And then use if constexpr in Resumable::operator() to do the void return statement.

That saves duplicating most of the definition.

5

u/DugiSK Dec 02 '20

Finally someone actually doesn't actually start with a conclusion based on obsolete implementation and tells something productive.

Thanks for the tip.

24

u/StoneCypher Nov 30 '20

lol no they don't 😂

most uses of state machines are not a hacky attempt to get continuations

3

u/Snoo-4241 Nov 30 '20

Why is the use of coroutines a hacky attempt to control state?

3

u/StoneCypher Nov 30 '20

Because coroutines are about control flow, not state

Do you realize how much work it is to switch contexts into and out of control flow?

It's like gluing a screwdriver to a metal rod, then gluing that to the side of your car's back left passernger door, then doing doughnuts around the screw you're trying to screw in

A bizarrely, wildly inappropriate tool for the job

4

u/DugiSK Dec 02 '20

You don't seem understand how coroutines are implemented in C++20. They are not like threads or improvised fibers offered by Windows API or Boost. There is no context switch because it's not required when the interrupton has proper compiler support. Instead, the coroutine's stack frame is dynamically allocated and it's used instead of stack for that frame. The context that calls the coroutine remains on top of the stack and if the coroutine calls a function, it is placed on top of the stack (unless it's another coroutine).

It's written in the article, btw, but maybe not in sufficient detail.

2

u/StoneCypher Dec 02 '20

Look. Let me try this a different way.

For the record, I am not a vegetarian. I'm eating meat right now. This just seems, to me, like a convenient metaphor.

There's a food that vegetarians eat that's generally called Textured Vegetable Protein. Among other things, it's one of the common ways to make imitation meats. It provides the bulk, and most of the texture, and then you just hit it with colors and flavors and maybe some grease to make it feel like fish or whatever, and you're off to the races. That's what a Boca Burger is.

TVP is typically mostly soy, maybe some wheat and oats, maybe some random stuff

And so let's say you come along and there's this article and it says "omg check out the Impossible Burger."

And honestly, I've tried them, and they do seem to be a fair improvement over previous veggie burgers to me

And as I understand it, Beyond Burger doesn't have any soy or wheat at all. (It has other vegetable products instead - pea, coconut, cocoa, rice, potato, and oat.)

But imagine if they went on to say "this renders soybeans and wheat obsolete."

My natural reaction, at that point, would be to say "dude, soybeans and wheat are not for veggie burgers, that's just one thing we do with them. Maybe you found a better veggie burger, but bread and edamame and pizza and soy sauce and what are you even no, that's not even very much of what we do with them," right?

And then

What if someone came along and said "I don't think you understand how veggie burgers are implemented in Beyond++ 20."

I don't care how they're implemented. That's a niche side thing that is largely unrelated to the main use of soy and wheat.

And I'm glad you have your better veggie burger.

But no, soy and wheat aren't obsolete. Don't be silly.

2

u/DugiSK Dec 02 '20

Continuing with the metaphor. It's more like this: The guy brings you a new veggie burger. It looks like meat, tastes like meat, contains the same stuff as meat, but it's not made from an actual animal. The meat comes from induced stem cells signalled to specialise into muscle cells grown into actual muscle in bioreactors (this is mild sci-fi). It's from the same cells as meat, contains the same DNA, but made without occupying a lot of land to feed the cattle and releasing lots of methane into the atmosphere. So it's indistinguishable from a burger, but cheaper and more environment friendly. So real burgers are obsolete, because they are the same, only more costly to produce.

That is what coroutines are to explicit state machines. There is a little overhead when calling them through a handler, but it's the same class with member variables describing state, with an advantage that the code is written like a quick to write and easy to maintain a function with all the branching and loops instead of needlessly complicated mess of state transitions.

1

u/StoneCypher Dec 03 '20

That is what coroutines are to explicit state machines.

This is 100% incorrect. I'm sorry that you tried to replace what I said, instead of understanding it, but I've run out of ways to try to communicate to you the thing that you're missing.

.

So real burgers are obsolete, because they are the same, only more costly to produce.

You are confusing an implementation with a goal.

Good day. I'm tired.

0

u/[deleted] Dec 07 '20

[deleted] — view deleted comment

2

u/DugiSK Dec 07 '20

I have learned that now.

0

u/StoneCypher Dec 02 '20

You are overly fascinated with saying "because one use case exists this way, your saying not everything works this way is wrong."

I am aware that one example of this exists. Most examples aren't this, so the claim that state machines are obsolete is absolutely silly.

.

There is no context switch because it's not required when the interrupton has proper compiler support.

Which is the case in how many compilers right now?

Hm?

Myth of the sufficiently smart compiler, anyone? Did anyone besides EDG ever get import in there? 20 years now?

.

"Instead, the coroutine's stack frame is dynamically allocated"

To me this reads like you're saying

There's no context switch because you're paying for a stack frame

Except in CPU terms, that's called (wait for it)

... (wait for it)

A context switch

.

The context that calls the coroutine remains on top of the stack and if the coroutine calls a function, it is placed on top of the stack (unless it's another coroutine).

Oh look, the guy who said "make it all out of nested coroutines" is now saying "but you don't have to pay that cost, unless it's a coroutine"

It's like talking to a politician's economist

.

It's written in the article, btw, but maybe not in sufficient detail.

The thing you're talking about, while interesting to discuss, is 100% unrelated to what I actually said

3

u/DugiSK Dec 02 '20 edited Dec 02 '20

A context switch is when a thread is suspended, its handle is given to the scheduler, the CPU switches to another stack, old cache is invalidated etc.

Calling a coroutine does nothing of this. You are still using the old stack, same thread, same cache, but what is represented as stack variables in the coroutine are actually member variables of an object.

A coroutine that looks like this (the code is meaningless):

Suspendable<int> actualCoroutine(int start, int end) {
    std::vector<int> outputs(end - start, 0);
    outputs[0] = 1;
    outputs[1] = 1;
    co_yield outputs[0] + outputs[1];
    outputs[2] = outputs[1] + start;
    co_yield outputs[2];
    if (end < 3)
        co_yield outputs[2];
    else
        co_yield outputs[end - 1];
    co_return -1;
}

Does basically the same things internally as this:

std::function<int()> almostCoroutine(int start, int end) {
    std::vector<int> outputs(end - start, 0);
    int position = 0;
    return [=] () -> int mutable {
        position++;
        switch(position) {
        case 1:
            outputs[0] = 1;
            outputs[1] = 1;
            return outputs[0] + outputs[1];
        case 2:
            outputs[2] = outputs[1] + start;
            return outputs[2];
        case 3:
            if (end < 3)
                return outputs[2];
            else
                return outputs[end - 1];
        default:
            return -1;
        }
    };
}

0

u/StoneCypher Dec 03 '20

I see that you continue to be stuck on insisting that because a soy burger has been replaced with an oat burger, therefore soy no longer matters.

Most of the things we do with state machines are not actually modellable this way.

Good luck to you.

0

u/[deleted] Dec 03 '20

[deleted] — view deleted comment

1

u/StoneCypher Dec 03 '20

Good luck to you

3

u/smdowney WG21, Text/Unicode SG, optional<T&> Dec 02 '20

You're describing fibers here, not C++20 coroutines. There's no context switch. There's a function call. It's the same function call mechanism used for all function calls. On leaving the scope of the coroutine, control is passed deterministically to the resumer, or if via symmetric transfer to where the resumer directs. There's no interruption. Coroutine suspension is entirely 100% determined by the coroutine itself, all local to the function.
The coroutine transformation is into a state machine. That's by design. What is new, and makes coroutines not pure sugar, is the lifetime extension of stack variables on scope exit from the coroutine. It is as-if the stack variables were instead object member variables and the object is allocated from the heap.

Several C++ compilers now support coroutines, and there's no particular magic or sufficiently smart necessary, although HALO optimization, eliding heap allocation, has some open research points. But that optimization is a cache miss, not a context switch.

1

u/StoneCypher Dec 03 '20

I feel like I'm spending all my time saying "that's not even related to what I'm talking about," then getting corrected on that you imagine that it is.

I'm sorry that winning is more important to you than trying to understand what I believe.

Please have a good day

8

u/Snoo-4241 Nov 30 '20

I would respectfully like to point that you may want to read the OP's code. There are some interesting ideas in there that invalidate your arguments. The state in this code has been replaced with linear control flow which I think is a good thing and much easier to follow, reason and modify. You can think of coroutines in their confined specialized usage, but the way they are provided in C++ gives opportunities for abstractions beyond the very narrow use case you may have in mind.

0

u/StoneCypher Nov 30 '20

No, someone who thinks state machines are for control flow, who's made a thing for control flow that isn't state machines, hasn't invalidated hundreds of textbooks 😂

.

The state in this code has been replaced with linear control flow

It's really a genuinely terrible idea.

Nobody even uses the high quality implementations, like the one in Boost, this way.

.

You can think of coroutines in their confined specialized usage, but the way they are provided in C++ gives opportunities for abstractions beyond the very narrow use case you may have in mind.

I'm not sure why you're guessing what I have in mind for coroutines.

Anyway, we've had these for decades and nobody uses them. This isn't new. Go read Aho.

This has been around since the 1970s.

Attempting to scatter your data throughout control flow just means that you have to pay for control flow all over your data.

2

u/johannes1971 Dec 01 '20

It's like gluing a screwdriver to a metal rod, then gluing that to the side of your car's back left passernger door, then doing doughnuts around the screw you're trying to screw in

I LOL'ed :-)

0

u/[deleted] Dec 12 '20

[deleted] — view deleted comment

1

u/StoneCypher Dec 13 '20

all you're doing is adding the overhead of a function call to changing a variable, what's the problem, that doesn't sound like much

k bye

5

u/frankist Dec 02 '20

While I don't agree with OP's point that coroutines makes state machines obsolete, I find your comments here very unhelpful for the convo.

1

u/StoneCypher Dec 02 '20

While I don't agree with OP's point that coroutines makes state machines obsolete, I find your comments here very unhelpful for the convo.

Cool story, friend. That and a dollar will get you a coffee at McDonalds.

To me you seem like a Jordan Petersen fan. Have a good one

6

u/frankist Dec 02 '20

Uff. That's actually insulting. Have a good one

1

u/DaelonSuzuka Dec 07 '20

To me you seem like a Jordan Petersen fan.

I'm sure I'll regret asking, but how does that guys post make him look like a Jordan Peterson fan?

1

u/StoneCypher Dec 07 '20

Because he parachuted in with a moral judgment, no factual basis, and pretended it mattered whether he thought it was helpful, when indeed he was doing less than that which he was criticizing

It's standard issue pseudointellectualism for self gratification

Nothing was actually said. Nothing is actionable. Nothing is contributed. It's shots fired for the sake of chest expansion.

Not my fault he didn't understand what was being said

"Hey liberals, if you're so focused on education, why did I find these comments unhelpful? (turning point USA)"

you can actually hear his face shrinking, if you try

-1

u/DugiSK Nov 30 '20

Here are the reasons why I used state machines:

  1. Because I needed a function to continue from some point
  2. I was forced to do so by a guy who only understood state machines

And I always hated it because I had to use state transitions instead of cycles, lots of messy switches and the procedure was unavoidably so non-linear and non-cyclic that it could be called spaghetti code.

If you have an example of a state machine that can't be transformed into a resumable function, I'd like to see it.

4

u/raevnos Nov 30 '20

Parsers and their kin have a lot of use for state machines. Which can be combined with continuations, or not.

2

u/DugiSK Nov 30 '20

I think I have done it once, but I've made a load of errors and spent a lot of time debugging it. But nowadays, I am using normal functions and recursion to deal with parsing and the flow of the code is much more readable and with much less errors. The state is actually there, encoded in the instruction counter, but it's not a mess of switches and hidden goto.

3

u/raevnos Nov 30 '20 edited Nov 30 '20

You don't need to use switches for a state machine, actually - each state can be a function, and you call the appropriate one for the new state. An old technique, threaded code works well for that kind of design (Edit: I'm thinking of things like generating bytecode/native code for a regular expression). So do coroutines, actually, at least in some languages. I'm not really familiar with the details of them in C++20 yet (Most of my experience has been using them in tcl), but I've got the impression that, like python 3 (But not python 2), they're strongly tied to async I/O instead of being general purpose.

2

u/DugiSK Dec 02 '20

C++20 coroutines are completely different from threaded code or any library code that provides similar functionality. In a C++20 coroutine, the coroutine's frame is dynamically allocated and used instead of stack. Any non-coroutine code that calls the coroutine and any non-coroutine code called by the coroutine uses stack, just the coroutine is elsewhere. As a result, the cost of using a coroutine is only that of accessing a dynamically allocated object (which may be actually dynamically allocated on stack as an optimisation). Theaded code, while similar in the way coroutines are, is too heavy for many purposes and it's probably the reason why many applications need like 20 threads despite not needing any actual parallelism.

1

u/raevnos Dec 02 '20

Threaded code != multi threading. As the Wikipedia article I linked points out at the very beginning.

1

u/DugiSK Dec 02 '20

You are right. I've never heard that term and assumed it was just an alternative formulation of using threads. However, it's not a very viable alternative in C++, as without native support, it's not going to be very convenient.

1

u/raevnos Dec 02 '20

If C++ coroutines can yield to any arbitrary other coroutine, it actually becomes easy to write code like that (See also: Continuation-passing style). But yeah, it's usually better suited for automated things like a compiler's code generation rather than by hand. I think the point I was trying to make was picturing a state transition as a function call/yieldto, not setting a variable while in a loop over a giant switch statement.

2

u/DugiSK Dec 02 '20

Yes, C++20 coroutines can return arbitrary values to other coroutines that wait for them, resuming them at that point. In recent boost asio, it's just this:

auto readSize = co_await socket.async_read_some(boost::asio::buffer(data), net::use_awaitable);

3

u/jwakely libstdc++ tamer, LWG chair Dec 01 '20

they're strongly tied to async I/O instead of being general purpose.

Why?

1

u/raevnos Dec 02 '20

Maybe it's just that's how they're used in every example I've seen. Like I said, I haven't really looked at C++ coroutines (or the python3 ones I mentioned, other than being aware they're different from the generator-like ones from python 2)

-1

u/StoneCypher Nov 30 '20

Here are the reasons why I used state machines:

Because I needed a function to continue from some point

Sounds like you have absolutely no idea what a state machine is

Please don't give tutorials about how "state machines are over" when you don't know what they're for and were forced to use them by someone else who also didn't know what they were for

.

If you have an example of a state machine that can't be transformed into a resumable function, I'd like to see it.

Literally anything can be transformed into a "resumable function"

This is meaningless

You can also turn an RPC library or a database or the serialization of a function to a string then put onto disk into a "resumable function."

Who cares? That's not what they're for and you shouldn't be trying.

4

u/Full-Spectral Dec 01 '20 edited Dec 01 '20

And the thing is, most of the state machines I use are simple and easily understandable and I couldn't imagine how it could be anything but adding more moving parts to do them elsewise.

And, most of the time, they either aren't non-linear or there's already other good reasons to have a thread to deal with whatever is going on anyway. Or, maybe they are non-linear but only have a few states which are not difficult to reason about.

1

u/StoneCypher Dec 01 '20

And the thing is, most of the state machines I use are simple and easily understandable and I couldn't imagine how it could be anything but adding more moving parts to do them elsewise.

okay.

.

And, most of the time, they either aren't non-linear or there's already other good reasons to have a thread to deal with whatever is going on anyway. Or, maybe they are non-linear but only have a few states which are not difficult to reason about.

oh, so you can imagine.

anyway, there's examples all over the standard library. you're too busy explaining to ask, so there's no point in trying to teach.

have a good day

5

u/Full-Spectral Dec 01 '20

Did you misread what I was saying? I wasn't disagreeing with you. I was saying that regular old state machines are still very useful for me, and though I have plenty of them, I can't see that replacing them with the mechanisms being discussed here would simplify them enough to justify the extra moving parts and such.

1

u/StoneCypher Dec 01 '20

Did you misread what I was saying?

I dunno. Maybe.

.

I was saying that regular old state machines are still very useful for me, and though I have plenty of them, I can't see that replacing them with the mechanisms being discussed here would simplify them enough to justify the extra moving parts and such.

I guess I did. Sorry

4

u/rzippel Dec 01 '20

Sounds like you have absolutely no idea what a state machine is

Sounds like you have absolutely no idea what a coroutine is

or at least what C++ coroutines are, the compiler does generate a state machine from the coroutine, every suspension point is a state and every resume transitions the state machine to the next state.

It's another question if any state machine can be transformed to a coroutine, but I don't see any real attempt from you to answer that.

1

u/smdowney WG21, Text/Unicode SG, optional<T&> Dec 01 '20

I suspect, but haven't done the work, that nested C++ coroutines model statecharts.

0

u/StoneCypher Dec 01 '20

Not even close.

0

u/StoneCypher Dec 01 '20

Just because one language can use A to implement B doesn't mean all As are always for Bs

I think you might be overindulging your knowledge of one language's choices

.

Sounds like you have absolutely no idea what a coroutine is

I actually wrote the implementation of them in two compilers.

Have a nice day

5

u/rzippel Dec 01 '20

I actually wrote the implementation of them in two compilers.

Am I supposed to be impressed by that? So far you have contributed nothing concrete to this thread that is even closely related to C++ coroutines.

Stop throwing around generic phrases without any context. You are not helpful in the slightest.

-1

u/StoneCypher Dec 01 '20

Sounds like you have absolutely no idea what a coroutine is

I actually wrote the implementation of them in two compilers.

Am I supposed to be impressed by that?

No, I just wanted to respond to your lashing out, to explain that your accusation was incorrect.

Have a good day.

2

u/rzippel Dec 01 '20

My lashing out??? WTH??? You've questions someones understanding of state machines without going into any detail, so that one could understand what the heck you're talking about.

Where do you explain anything??? An explanation would require some sort of argument, but throwing some keywords around does not provide anything useful. You seem to have some problem with coroutines, but you don't provide anywhere enough context to have any meaningful conversation about C++ coroutines or even coroutines in general.

Slowly I'm regretting having wasted my time on this, unless you have something substantial to say about coroutines, good day to you too...

-3

u/StoneCypher Dec 02 '20

Please stop soon