kirit.com

Created 26th April, 2005 13:12 (UTC), last edited 22nd December, 2016 03:24 (UTC)

Writing about C++, Programming, Fost 5, the web, Thailand and anything else that catches my attention—with some photos thrown in

Yielding Generators

Created 15th July, 2017 05:28 (UTC), last edited 16th July, 2017 03:48 (UTC)

We've seen how the promise_type together with the coroutine return type handles the interactions between the caller and the coroutine itself.

Our target is to be able to do something pretty simple:

generator count() {
    std::cout << "Going to yield 1" << std::endl;
    co_yield 1;
    std::cout << "Going to yield 2" << std::endl;
    co_yield 2;
    std::cout << "Going to yield 3" << std::endl;
    co_yield 3;
    std::cout << "count() is done" << std::endl;
}

co_yield is actually very similar to our co_return example previously. There is really just one additional component, and one small change:

  1. Because our generator doesn't have any sort of return value there is an implicit return that produces nothing. This means that instead of return_value we are going to need to fill in a return_void method.
  2. For each value that is yielded the compiler will arrange to make a call to yield_value.

These two things together mean that we need to suspend at the yields (so the user of the generator gets a chance to read the value) and we know we're finished yielding values when the return_void promise method gets called.

Let's get started

Let's sketch out something that should look fairly familiar:

struct generator {
    struct promise_type {
    };
    using handle_type =
        std::experimental::coroutine_handle<promise_type>;
private:
    generator(handle_type h)
    : coro(h) {
        std::cout << "generator" << std::endl;
    }
    handle_type coro;
};

This should look fairly similar to our lazy and sync examples.

We can track the lifetime of the promise to help us see what's going on and we also suspend the coroutine both at its start and end, all by adding these members to our promise_type:

promise_type() {
    std::cout << "Promise created" << std::endl;
}
~promise_type() {
    std::cout << "Promise died" << std::endl;
}
auto initial_suspend() {
    std::cout << "Started the coroutine, let's pause!" << std::endl;
    return std::experimental::suspend_always{};
}
auto final_suspend() {
    std::cout << "Finished the coroutine" << std::endl;
    return std::experimental::suspend_always{};
}

We still need to return the generator object from our promise_type, and we also have to do something if an exception happens.

auto get_return_object() {
    std::cout << "Send back a generator" << std::endl;
    return generator{handle_type::from_promise(*this)};
}
void unhandled_exception() {
    std::cout << "Exception...." << std::endl;
    std::exit(1);
}

For our co_return based lazy and sync classes we also had to provide a mechanism for the co_return value to find its way to the caller. We actually still have to do this, but our coroutine example doesn't have a return statement, so now we have to implement the return_void member:

auto return_void() {
    std::cout << "return_void" << std::endl;
    return std::experimental::suspend_never{};
}

We're not going to suspend here because we want to just carry on and suspend at the final suspension point (where we will stop so the generator can clean up for us).

Yielding values

The last thing we need is to handle the yield itself. When the coroutines gets to a co_yield the compiler will call yield_value on our promise_type so we can see the value and decide what to do.

auto yield_value(int value) {
    std::cout << "Yielded " << value << std::endl;
    current_value = value;
    return std::experimental::suspend_always{};
}

It's also important that we suspend here. If we don't then our coroutine will carry on and run another co_yield. This will cause yield_value to be called again and we'll lose the value that was just given to us—it'll get overwritten by the new one.

As we saw before, we now have the coroutine performing its half of the control flow. The rest of the control flow that happens needs to be in the generator code because that is what our caller will interact with.

There is a dance between the generator and the promise_type to control the resumption of the coroutine and generation of values in exactly the right way. We need to make sure that we suspend and resume so that we get all of the values and don't skip any (especially easy at the start and end).

We need some sort of API that users of generator are going to use to fetch values. The obvious one is some sort of iterator based interface, but let's start with something a little bit simpler that involves less code.

int main() {
    auto g = count();
    while ( g.move_next() )
        std::cout << ">> " << g.current_value() << std::endl;
    return 0;
}

The implication here is that move_next will resume the coroutine until a co_yield or a return happens. If a co_yield happens we're going to return true, if the coroutine returns then we're going to return false to signal the end of the yielded sequence. Inside the loop we expect the current_value method to return the last value yielded.

The latter is very straight forward:

int current_value() {
    return coro.promise().current_value;
}

This is exactly as we had with the earlier sync and lazy examples. We store the last yielded value in the promise and can easily retrieve it through the coroutine handle we store in the generator.

For the sequence for fetching values we want this:

  1. Enter the coroutine, but suspend before doing anything.
  2. When the move_next is called resume the coroutine so that it can either return or yield a value.
  3. If the corotune is now done we didn't get a value so move_next returns false.
  4. If we're not done then return true so that move_next can be called again (going back to step 2).

Let's do that and also track what's going on:

bool move_next() {
    std::cout << "Moving to next" << std::endl;;
    coro.resume();
    std::cout << "Are we done? ";
    auto still_going = not coro.done();
    std::cout << (still_going ? "There is another" : "We're done") << std::endl;
    return still_going;
}

We now have enough to run:

Promise created
Send back a generator
generator
Started the coroutine, let's pause!
Moving to next
Going to yield 1
Yielded 1
Are we done? There is another
>> 1
Moving to next
Going to yield 2
Yielded 2
Are we done? There is another
>> 2
Moving to next
Going to yield 3
Yielded 3
Are we done? There is another
>> 3
Moving to next
count() is done
return_void
Finished the coroutine, brakes on
Are we done? We're done

Examining this we can see the dance between the two sides, the promise_type and the generator, play out in the right way.

  1. The promise creates and returns the generator.
  2. The coroutine is entered, but suspended.
  3. The generator's move_next is called and it advances the coroutine.
  4. The coroutine yields its first value
  5. move_next finds that the coroutine has yielded so returns true
  6. The value is printed
  7. Steps 3 to 7 are repeated another couple of times

The last time though is a bit different. The final move_next results in a call to return_void rather than yield_value and the coroutine ends up suspended at the final suspension point. coro.done() now returns true so we know that the coroutine has yielded everything it can (or wants to) and move_next returns false and we're all done.

To see the importance of getting this dance right let's change the initial_suspend to keep going:

auto initial_suspend() {
    std::cout << "Started the coroutine, keep going!" << std::endl;
    return std::experimental::suspend_never{};
}

Now we'll see this sequence:

Promise created
Send back a generator
generator
Started the coroutine, keep going!
Going to yield 1
Yielded 1
Moving to next
Going to yield 2
Yielded 2
Are we done? There is another
>> 2
Moving to next
Going to yield 3
Yielded 3
Are we done? There is another
>> 3
Moving to next
count() is done
return_void
Finished the coroutine, brakes on
Are we done? We're done

And because we didn't stop at the beginning we've resumed before the first value could be read. We can fix this by changing the way the generator is used:

int main() {
    std::cout << "coro3" << std::endl;
    auto g = count();
    do {
        std::cout << ">> " << g.current_value() << std::endl;
    } while ( g.move_next() );
    return 0;
}

Now we see all of our values:

Promise created
Send back a generator
generator
Started the coroutine, let's pause!
Going to yield 1
Yielded 1
>> 1
Moving to next
Going to yield 2
Yielded 2
Are we done? There is another
>> 2
Moving to next
Going to yield 3
Yielded 3
Are we done? There is another
>> 3
Moving to next
count() is done
return_void
Finished the coroutine, brakes on
Are we done? We're done

But of course we have another problem. The code that uses the generator now assumes that the generator must yield at least one value. Probably our first API is the best for a general use generator so let's put that back.

Fixing the leak

We still have a more subtle problem though. Notice we never see the “Promise died” message. This is because we're not managing the life time of the coroutine itself yet. We have the same issue that we saw with sync and lazy. We need to make the generator movable, but not copyable and then destroy the coroutine at the correct point in time.

~generator() {
    std::cout << "~generator "
        << (not coro ? "(empty)" : "(contains a coroutine)")
        << std::endl;
    if ( coro ) coro.destroy();
}
generator(const generator &) = delete;
generator(generator &&g)
: coro(g.coro) {
    g.coro = nullptr;
};

Now we can see the coroutine itself is destroyed when our generator goes out of scope:

Promise created
Send back a generator
generator
Started the coroutine, let's pause!
~generator (empty)
Moving to next
Going to yield 1
Yielded 1
Are we done? There is another
>> 1
Moving to next
Going to yield 2
Yielded 2
Are we done? There is another
>> 2
Moving to next
Going to yield 3
Yielded 3
Are we done? There is another
>> 3
Moving to next
count() is done
return_void
Finished the coroutine, brakes on
Are we done? We're done
~generator (contains a coroutine)
Promise died

Next we're going to convert this to an iterator, a straightforward enough procedure, but with a few things worth pointing out.


Categories:
Posted: 16th July, 2017 03:55 (UTC)
First announced.

Moved to HTTPS

Posted 14th July, 2017 12:06 (UTC), last edited 14th July, 2017 12:09 (UTC)

Thanks to the magic of Let's Encrypt, this site is now on HTTPS with a proper certificate. Yay :)

I've also dropped the www. part of the URL, which has long annoyed me.

A more realistic coroutine

Created 29th June, 2017 04:57 (UTC), last edited 15th July, 2017 05:39 (UTC)

Having gotten something working, we still have a small problem. We have a coroutine that we can start, and we can choose when to suspend it, but we can't yet resume it.

The coroutines TS describes a class std::experimental::coroutine_handle which is our interface to the coroutine itself. It's a template which is supposed to be told the promise_type we're using.

We can add the following to our sync class:

struct promise_type;
using handle_type = std::experimental::coroutine_handle<promise_type>;

We should store the handle in the sync object, so we can replace our default constructor with this:

sync(handle_type h)
: coro(h) {
    std::cout << "Created a sync object" << std::endl;
}
handle_type coro;

Now in our promise_type we will need to pass the correct handle when we create the sync object. The coroutine_handle has a static member that allows us to do this:

auto get_return_object() {
    std::cout << "Send back a sync" << std::endl;
    return sync<T>{handle_type::from_promise(*this)};
}

Now that we have that we should change our shared_ptr members. In the promise_type we'll replace ptr with with a plain T member called value, and we can now remove it totally from our sync object. This does mean our sync::get member needs to pull the value from the coroutine_handle, but there's an API for that:

T get() {
    std::cout << "We got asked for the return value..." << std::endl;
    return coro.promise().value;
}

We clearly also have to change the way we record the return value in the promise_type:

auto return_value(T v) {
    std::cout << "Got an answer of " << v << std::endl;
    value = v;
    return std::experimental::suspend_never{};
}

If we try to run this we'll find we still have a problem with the lifetimes. The sync instance still outlives our promise_type instance so we hit undefined behaviour. The lifetime issue can be solved by suspending before we run off the end of the coroutine:

auto final_suspend() {
    std::cout << "Finished the coro" << std::endl;
    return std::experimental::suspend_always{};
}

I've rather arbitrarily changed the final_suspend member here, but you could also change return_value. Just so long as the value in the promise_type gets filled in before we suspend we'll be fine.

Now it leaks again of course, but we can plug the leak by destroying the coroutine through its handle in the sync destructor:

~sync() {
    std::cout << "Sync gone" << std::endl;
    if ( coro ) coro.destroy();
}

Now everything lines up and it all works, although there is still a subtle problem. If we copy the sync object around then we're going to end up destroying the coroutine_handle from more than one place.

When we deal with a coroutine_handle we have to remember that this is a resource and needs to be managed properly. The simplest way to deal with this is to make our sync movable but not copyable.

sync(const sync &) = delete;
sync(sync &&s)
: coro(s.coro) {
    std::cout << "Sync moved leaving behind a husk" << std::endl;
    s.coro = nullptr;
}
~sync() {
    std::cout << "Sync gone" << std::endl;
    if ( coro ) coro.destroy();
}
sync &operator = (const sync &) = delete;
sync &operator = (sync &&s) {
    coro = s.coro;
    s.coro = nullptr;
    return *this;
}

This final version deals correctly with all lifetime issues and outputs something along these lines:

Promise created
Send back a sync
Created a sync object
Started the coroutine, don't stop now!
Thinking deep thoughts…
Got an answer of 42
Finished the coro
Sync gone
Got a coroutine, let's get a value
We got asked for the return value…
And the coroutine value is: 42
Sync gone
Promise died

A lazy coroutine

We now have a working coroutine that executes its body when it's entered. Let's instead see if we can make a lazy coroutine that doesn't execute its body until it gets asked for the value.

Our general strategy is going to be this:

  1. Start the coroutine
  2. Return the lazy instance that will co-ordinate the return value.
  3. Suspend the coroutine.
  4. When the value in the lazy object is asked for, resume the coroutine.
  5. Suspend the coroutine after the co_return.
  6. The lazy object will return the value.
  7. Destroy the coroutine when the lazy is destructed.

There aren't actually that many changes we need to make. First of all just duplicate the sync class and call it lazy—we'll refactor this at the end.

Just to check nothing boneheaded happened first alter answer to return a lazy<int> rather than the sync and make sure we observe the same behaviour.

In order to delay the execution of the coroutine body we need to return suspend_always from initial_suspend:

auto initial_suspend() {
    std::cout << "Started the coroutine, put the brakes on!" << std::endl;
    return std::experimental::suspend_always{};
}

Now when we run it the coroutine body is never run so we don't see the proper value.

Promise created
Send back a lazy
Created a lazy object
Started the coroutine, put the brakes on!
Lazy gone
Got a coroutine, let's get a value
We got asked for the return value…
And the coroutine value is: 0
Lazy gone
Promise died

Luckily the coroutine_handle has a member that allows us to resume the execution of the coroutine at a time of our choosing.

T get() {
    std::cout << "We got asked for the return value..." << std::endl;
    coro.resume();
    return coro.promise().value;
}

With this additional change we now get the right result again, and we can see that things happen when we wanted them to:

Promise created
Send back a lazy
Created a lazy object
Started the coroutine, put the brakes on!
Lazy gone
Got a coroutine, let's get a value
We got asked for the return value…
Thinking deep thoughts…
Got an answer of 42
Finished the coro
And the coroutine value is: 42
Lazy gone
Promise died

Control the return type, control the coroutine

This describes the general pattern when working with coroutines. The way that the coroutine works in detail is fully described by the way that its return type controls the coroutine machinery provided the language. This has the unfortunate side effect of rendering useless auto type deduction for the return types. Oh well.

Notice how in both our sync and lazy examples the body of answer not changed at all. In both cases the literal 42 is returned (an int), but we wrap in something that controls how that value finds it way to the caller of answer.

Now that we understand that, we can refactor our code to remove the redundancy and highlight the important differences between the two implementations.

With that done it's easy to see that the promise types for two differ in whether they suspend or not at the initial suspend point, they also (obviously) differ in the types of object returned by get_return_object. And the final place they differ is in the get implementation which for lazy must also resume the coroutine:

template<typename T>
struct sync : public coreturn<T> {
    using coreturn<T>::coreturn;
    using handle_type = typename coreturn<T>::handle_type;
    T get() {
        std::cout << "We got asked for the return value..." << std::endl;
        return coreturn<T>::get();
    }
    struct promise_type : public coreturn<T>::promise {
        auto get_return_object() {
            std::cout << "Send back a sync" << std::endl;
            return sync<T>{handle_type::from_promise(*this)};
        }
        auto initial_suspend() {
            std::cout << "Started the coroutine, don't stop now!" << std::endl;
            return std::experimental::suspend_never{};
        }
    };
};


template<typename T>
struct lazy : public coreturn<T> {
    using coreturn<T>::coreturn;
    using handle_type = typename coreturn<T>::handle_type;;
    T get() {
        std::cout << "We got asked for the return value..." << std::endl;
        this->coro.resume();
        return coreturn<T>::get();
    }
    struct promise_type : public coreturn<T>::promise {
        auto get_return_object() {
            std::cout << "Send back a lazy" << std::endl;
            return lazy<T>{handle_type::from_promise(*this)};
        }
        auto initial_suspend() {
            std::cout << "Started the coroutine, put the brakes on!" << std::endl;
            return std::experimental::suspend_always{};
        }
    };
};

The common part is now:

template<typename T>
struct coreturn {
    struct promise;
    friend struct promise;
    using handle_type = std::experimental::coroutine_handle<promise>;
    coreturn(const coreturn &) = delete;
    coreturn(coreturn &&s)
    : coro(s.coro) {
        std::cout << "Coreturn wrapper moved" << std::endl;
        s.coro = nullptr;
    }
    ~coreturn() {
        std::cout << "Coreturn wrapper gone" << std::endl;
        if ( coro ) coro.destroy();
    }
    coreturn &operator = (const coreturn &) = delete;
    coreturn &operator = (coreturn &&s) {
        coro = s.coro;
        s.coro = nullptr;
        return *this;
    }
    struct promise {
        friend struct coreturn;
        promise() {
            std::cout << "Promise created" << std::endl;
        }
        ~promise() {
            std::cout << "Promise died" << std::endl;
        }
        auto return_value(T v) {
            std::cout << "Got an answer of " << v << std::endl;
            value = v;
            return std::experimental::suspend_never{};
        }
        auto final_suspend() {
            std::cout << "Finished the coro" << std::endl;
            return std::experimental::suspend_always{};
        }
        void unhandled_exception() {
            std::exit(1);
        }
    private:
        T value;
    };
protected:
    T get() {
        return coro.promise().value;
    }
    coreturn(handle_type h)
    : coro(h) {
        std::cout << "Created a coreturn wrapper object" << std::endl;
    }
    handle_type coro;
};

A final problem

There is one final thing we need to think about. What happens if we fetch the answer from the coroutine more than once? We can change main like this:

int main() {
    std::cout << "coro1" << std::endl;
    auto a = answer();
    std::cout << "Got a coroutine, let's get a value" << std::endl;
    auto v = a.get();
    std::cout << "And the coroutine value is: " << v << std::endl;
    v = a.get();
    std::cout << "And the coroutine value is still: " << v << std::endl;
    return 0;
}

On my machine I get this output:

Promise created
Send back a lazy
Created a coreturn wrapper object
Started the coroutine, put the brakes on!
Coreturn wrapper moved
Coreturn wrapper gone
Got a coroutine, let's get a value
We got asked for the return value…
Thinking deep thoughts…
Got an answer of 42
Finished the coro
And the coroutine value is: 42
We got asked for the return value…

And then it crashes. What happens of course is that we resume a coroutine which is already at its final suspension point, which means we run off the end of it and it's automatically destroyed for us. This ends badly.

What we need to do is make sure we only resume the coroutine the first time get is called. Luckily there is a simple way to do this:

T get() {
    std::cout << "We got asked for the return value..." << std::endl;
    if ( not this->coro.done() ) this->coro.resume();
    return coreturn<T>::get();
}

done will return true only when the coroutine is at its final suspension point (the one after the body is exited). With that change we have a nice reliable lazy function that will only ever be evaluated once.


Next time we're going to extend this further and start to look at the co_yield mechanism which will allow us to build some generators.


Categories:
Posted: 2nd July, 2017 16:12 (UTC)
First announced.

My first coroutine

Created 27th June, 2017 11:44 (UTC), last edited 1st July, 2017 11:57 (UTC)

There are more and more examples coming out of how to convert things like the use of futures into coroutines, and you may be forgiven for thinking that there is also some magic that happens in boost::future or std::future that lets this work, but that's not the case.

In C++ a coroutine is any function that contains one of the coroutine keywords in its body, that is any of co_return, co_yield or co_await.

What we're going to do is to write a very basic mechanism that allows us to use co_return to return a value from a coroutine. Coroutines are really a generalisation of a function call, and what this is going to allow us to do is to treat a coroutine as a function call. If we can't do this then we don't stand much chance of doing anything more interesting with them, but it will give us a good starter on how the machinery works.

This version isn't going to be really useful for much, but we'll fix that in the next article.

Let's start off with a coroutine that just returns a value:

sync<int> answer() {
    std::cout << "Thinking deep thoughts..." << std::endl;
    co_return 42;
}

In order for us to be able to use answer we have to write a suitable implementation of sync that interacts in the right way with the compiler so we can do this:

int main() {
    auto a = answer();
    std::cout << "Got a coroutine, let's get a value" << std::endl;
    auto v = a.get();
    std::cout << "And the coroutine value is: " << v << std::endl;
    return 0;
}

Obviously we need an implementation of sync to use here—that's what we're going to write, but first we need to understand some stuff about what's going to happen here.

When the compiler sees a coroutine it's going to take our function and split it up into parts. How these parts then get executed is what we get to control through the way that sync works.

If answer were a normal function it would be entered at the top, the body would run and the return would be used to construct the sync<int> instance. Coroutines work inside out:

  1. The coroutine is set up in a way that allows the body to be run at any time, now or later. The return value (which represents the coordination between the coroutine and its caller) needs to be created here at the start.
  2. The body gets run later on, actually at a time of our choosing.
  3. The co_return value turns up at the end of the body execution so we have to put it where the caller can get it.
  4. Was there anything else we needed?

The control for this is through a promise_type which needs to conform to a particular API. The API is somewhat fluid and the details of what it needs to look like exactly depend on the details of the machinery and the facilities that you want to be able to deal with inside the coroutine.

There's two classes involved here, promise_type and sync. The promise_type represents a part of the coroutine itself (actually part of its stack frame), and the sync handles how the coroutine interacts with its caller, and ultimately the return value.

For this first version we're only going to support co_return and not co_yield or co_await—we'll get to those later on. We also aren't actually going to do anything asynchronously to start with, we'll be happy if we can get anything at all.

So, to start with we have this (with some tracking for creation and destruction to help us see what's going on):

template<typename T>
struct sync {
    sync() {
        std::cout << "Created a sync object" << std::endl;
    }
    sync(const sync &s) {
        std::cout << "Copied a sync object" << std::endl;
    }
    ~sync() {
        std::cout << "Sync gone" << std::endl;
    }
    void get() {
        std::cout << "We got asked for the return value..." << std::endl;
    }
    struct promise_type {
        promise_type() {
            std::cout << "Promise created" << std::endl;
        }
        ~promise_type() {
            std::cout << "Promise died" << std::endl;
        }
    };
};

What step 1 above means in practice is that when the coroutine is first entered we have to remember all the stuff it needs somewhere so it'll be available no matter when the body is run. This happens by allocating a single stack frame in the heap which contains the promise_type in it together with all of the local variables that are used. Right now everything is empty so that's simple enough.

Because we could run the body of the coroutine at any time and any place, we need to make the sync instance at the start of the function call and not at the end. We tell the promise_type how to construct the sync object that the coroutine returns:

auto get_return_object() {
    std::cout << "Send back a sync" << std::endl;
    return sync<T>{};
}

This just returns an empty one. The next thing we need to explain to the compiler is whether we want to start on the body straight away or not. Because we want to emulate a normal function the promise_type needs to answer “yes”:

auto initial_suspend() {
    std::cout << "Started the coroutine, don't stop now!" << std::endl;
    return std::experimental::suspend_never{};
}

This takes care of steps 1 and 2. Next we're going to hit the co_return and we'll find out what the result of our coroutine actually is. Our promise_type gets told the value, which we'll just print for now:

auto return_value(T v) {
    std::cout << "Got an answer of " << v << std::endl;
    return std::experimental::suspend_never{};
}

Notice that we're also answering the question of whether or not we want to suspend the coroutine after it returns a value to us. We just keep going on to step 4.

Now that we've finished the coroutine, we need to say whether we want to stop here or not. If we don't then we run out of coroutine to execute and that stack frame that was allocated in step 1 is automatically freed for us.

auto final_suspend() {
    std::cout << "Finished the coro" << std::endl;
    return std::experimental::suspend_never{};
}

There is one last thing the compiler needs to know before it'll let us run anything. What should happen if an exception tries to escape from the coroutine? To start with we're just going to give up and bomb out:

void unhandled_exception() {
    std::exit(1);
}

Running the coroutine

With all of that done, we now have something that we can actually run.

Promise created
Send back a sync
Created a sync object
Started the coroutine, don't stop now!
Thinking deep thoughts…
Got an answer of 42
Finished the coro
Promise died
Copied a sync object
Sync gone
Got a coroutine sync object, let's get a value
We got asked for the return value…
And the coroutine value is: 0
Sync gone

This is all well and good, but we still haven't actually managed to get the return value. We do have a problem with that. Look carefully at the order of the messages.

You can see that the promise type is created first, then the return value holder (the sync instance) is created. The promise then dies and finally the sync goes. There's an extra sync to account for the one that gets copied when get_return_object returns.

The control flow is something like this:

  1. Enter main, enter the coroutine.
  2. Create the return value.
  3. Because initial_suspend returns suspend_never we enter the body of the coroutine.
  4. We hit the co_return whose value gets passed to our return_value method, which also tells the coroutine to continue executing.
  5. Because we've now finished the coroutine we hit the final_suspend and just keep going.
  6. The coroutine is now dead and its stack frame is removed, which destroys the promise_type.
  7. Execution moves back up to the call site of the coroutine which hands over the sync object returned in step 2.
  8. Finally we get the value from our sync object and display it.

You can play around with this, for example, change initial_suspend to return suspend_always.

auto initial_suspend() {
    std::cout << "Started the coroutine, put the brakes on!" << std::endl;
    return std::experimental::suspend_always{};
}

You'll now see this:

Promise created
Send back a sync
Created a sync object
Started the coroutine, put the brakes on!
Copied a sync object
Sync gone
Got a coroutine sync object, let's get a value
We got asked for the return value…
And the coroutine value is: 0
Sync gone

The control flow is now this:

  1. Enter main, enter the coroutine.
  2. Create the return value.
  3. Because initial_suspend return suspend_always we return control to the call site in main.
  4. We get the sync value created in step 2.
  5. Finally we get the value from our sync object and display it.

Notice that the coroutine body never runs, it's never given an opportunity to return the real value and just as bad, the promise_type never gets destructed because we've leaked the coroutine stack frame.

In the next article we'll solve all of this properly, but for now we'll put initial_suspend back to what it was and add a std::shared_ptr to bridge the difference in lifetimes and make the correct value available.

Our complete sync class now looks like this:

template<typename T>
struct sync {
    std::shared_ptr<T> value;
    sync(std::shared_ptr<T> p)
    : value(p) {
        std::cout << "Created a sync object" << std::endl;
    }
    sync(const sync &s)
    : value(s.value) {
        std::cout << "Copied a sync object" << std::endl;
    }
    ~sync() {
        std::cout << "Sync gone" << std::endl;
    }
    T get() {
        std::cout << "We got asked for the return value..." << std::endl;
        return *value;
    }
    struct promise_type {
        std::shared_ptr<T> ptr;
        promise_type()
        : ptr(std::make_shared<T>()) {
            std::cout << "Promise created" << std::endl;
        }
        ~promise_type() {
            std::cout << "Promise died" << std::endl;
        }
        auto get_return_object() {
            std::cout << "Send back a sync" << std::endl;
            return ptr;
        }
        auto initial_suspend() {
            std::cout << "Started the coroutine, don't stop now!" << std::endl;
            return std::experimental::suspend_never{};
        }
        auto return_value(T v) {
            std::cout << "Got an answer of " << v << std::endl;
            *ptr = v;
            return std::experimental::suspend_never{};
        }
        auto final_suspend() {
            std::cout << "Finished the coro" << std::endl;
            return std::experimental::suspend_never{};
        }
        void unhandled_exception() {
            std::exit(1);
        }
    };
};

And it outputs this:

Promise created
Send back a sync
Started the coroutine, don't stop now!
Thinking deep thoughts…
Got an answer of 42
Finished the coro
Promise died
Created a sync object
Got a coroutine sync object, let's get a value
We got asked for the return value…
And the coroutine value is: 42
Sync gone

We got our value, and a little quirk. I guess because our sync object is now doing something more obviously useful the compiler has also worked out it can elide the copy so we now only have a single sync object.

In the next article we'll find out the proper solution to handling this lifetime issue which will get us to a fully proper working coroutine.


Categories:
Posted: 2nd July, 2017 16:11 (UTC)
First announced.

How C++ coroutines work

Created 23rd June, 2017 05:21 (UTC), last edited 15th July, 2017 05:29 (UTC)

If you look at coroutines in other language, JavaScript or Python for example, you'll see that the language documents how the coroutines work. How you can use co_yield and co_await etc. (however they're spelled) and what the language does for you with them. This is all very useful, and lets you do a lot of cool things with them, but always within the confines of what the language runtime allows.

In C++ they're quite different. The compiler provides a scaffolding on which you can decide how things work. This means that C++ doesn't provide generators, but it provides you a way to write a ton of different generators that work in different ways depending on your needs.

This is what this series of articles is going to be about. Not how to use or write coroutines that work according to some pre-established pattern, but how the underlying machinery allows you to customise the way that the coroutines work.

Let's start by looking at just one of the things we can use coroutines for, generating values.

We can write a simple function that prints prime numbers like this (I'm going to presuppose we have a suitable is_prime function):

void primes1(std::size_t max) {
    for ( unsigned int number = 2; number < max; ++number ) {
        if ( is_prime(number) ) {
            std::cout << number << " is prime" << std::endl;
        }
    }
}

primes1(30);

But what if we don't want to print them, we want to do something else with them? The obvious thing, at least for modern C++ code, is to use a callback:

template<typename L>
void primes2(std::size_t max, L found) {
    for ( unsigned int number = 2; number < max; ++number ) {
        if ( is_prime(number) ) found(number);
    }
}

primes2(30, [](auto n) {
    std::cout << n << " is prime" << std::endl;
});

Callbacks are great, but they have a problem in that we now need to write inside out code when we want to get prime numbers.

The older solution to this problem, writing an iterator, solves this for the consumer of the prime numbers (they don't have inversions of control and inside out code), but it makes the implementation of the iterator much more complex (because now that has to be inside out):

class prime_iterator {
    unsigned int number = 2;
public:
    auto operator * () const {
        return number;
    }
    prime_iterator &operator ++ () {
        for ( ++number; not is_prime(number); ++number );
        return *this;
    }
};

for ( prime_iterator p; *p < 30; ++p ) {
    std::cout << *p << " is prime" << std::endl;
}

This particular iterator implementation is quite incomplete, but it does show that the logic we want is spread out and inside out. From the client code's perspective though consumption of the values is very simple and idiomatic, although this code is too simple to be usable in a ranged for loop.

What we've had to do is to split the generation of the prime numbers up into three parts:

  1. The state for which prime number we're at—the number member.
  2. The return of the prime number value—operator *
  3. Finding the next prime number—operator ++

For prime numbers this isn't too bad, but for more complex calculations this transformation can be very hard to visualise and implement, and is the source of many bugs.

What we really want is to have something as easy to write as the first example, but is as easy to use the last one—maybe even easier if we can get it.

It turns out that this is exactly what co_yield is made for, and it allows us to implement and use this:

generator primes3(std::size_t max) {
    for ( unsigned int number = 2; number < max; ++number ) {
        if ( is_prime(number) ) {
            co_yield number;
        }
    }
}

for ( auto v : primes3(30) )
    std::cout << v << " is prime" << std::cout;

All we have to do is to learn how to implement classes like generator so that things work.

Pages

  1. My first coroutine
  2. A more realistic coroutine
  3. Yielding Generators

Categories:
Posted: 1st July, 2017 08:50 (UTC)
First announced after the first two pages are done.