How do you implement Coroutines in C++

I doubt it can be done portably, but are there any solutions out there? I think it could be done by creating an alternate stack and reseting SP,BP, and IP on function entry, and having yield save IP and restore SP+BP. Destructors and exception safety seem tricky but solvable.

Has it been done? Is it impossible?

Yes it can be done without a problem. All you need is a little assembly code to move the call stack to a newly allocated stack on the heap.

I would look at the boost::coroutine library.

The one thing that you should watch out for is a stack overflow. On most operating systems overflowing the stack will cause a segfault because virtual memory page is not mapped. However if you allocate the stack on the heap you don't get any guarantee. Just keep that in mind.

On POSIX, you can use makecontext()/swapcontext() routines to portably switch execution contexts. On Windows, you can use the fiber API. Otherwise, all you need is a bit of glue assembly code that switches the machine context. I have implemented coroutines both with ASM (for AMD64) and with swapcontext(); neither is very hard.

For posterity,

Dmitry Vyukov's wondeful web site has a clever trick using ucontext and setjump to simulated coroutines in c++.

Also, Oliver Kowalke's context library was recently accepted into Boost, so hopefully we'll be seeing an updated version of boost.coroutine that works on x86_64 soon.

There's no easy way to implement coroutine. Because coroutine itself is out of C/C++'s stack abstraction just like thread. So it cannot be supported without language level changes to support.

Currently(C++11), all existing C++ coroutine implementations are all based on assembly level hacking which is hard to be safe and reliable crossing over platforms. To be reliable it needs to be standard, and handled by compilers rather than hacking.

There's a standard proposal - N3708 for this. Check it out if you're interested.

You might be better off with an iterator than a coroutine if possible. That way you can keep calling next() to get the next value, but you can keep your state as member variables instead of local variables.

It might make things more maintainable. Another C++ developer might not immediately understand the coroutine whereas they might be more familiar with an iterator.

For those who want to know how they may leverage Coroutines in a portable way in C++ y̶o̶u̶ ̶w̶i̶l̶l̶ ̶h̶a̶v̶e̶ ̶t̶o̶ ̶w̶a̶i̶t̶ ̶f̶o̶r̶ ̶C̶+̶+̶1̶7̶ the wait is over (see below)! The standards committee is working on the feature see the N3722 paper. To summarize the current draft of the paper, instead of Async and Await, the keywords will be resumable, and await.

Take a look at the experimental implementation in Visual Studio 2015 to play with Microsoft's experimental implementation. It doesn't look like clang has a implementation yet.

There is a good talk from Cppcon Coroutines a negative overhead abstraction outline the benefits of using Coroutines in C++ and how it affects simplicity and performance of the code.

At present we still have to use library implementations, but in the near future, we will have coroutines as a core C++ feature.

Update: Looks like the coroutine implementation is slated for C++20, but was released as a technical specification with C++17 (p0057r2). Visual C++, clang and gcc allow you to opt in using a compile time flag.

Does COROUTINE a portable C++ library for coroutine sequencing point you in the right direction? It seems like an elegant solution that has lasted the test of time.....it's 9 years old!

In the DOC folder is a pdf of the paper A Portable C++ Library for Coroutine Sequencing by Keld Helsgaun which describes the library and provides short examples using it.

[update] I'm actually making successful use of it myself. Curiosity got the better of me, so I looked into this solution, and found it was a good fit for a problem I've been working on for some time!

I dont think there are many full-blown, clean implementations in C++. One try that I like is Adam Dunkels' protothread library.

See also Protothreads: simplifying event-driven programming of memory-constrained embedded systems in the ACM Digital Library and discussion in Wikipedia topic Protothread,

It is based on (cringe) macros, but the following site provides an easy-to-use generator implementation: http://www.codeproject.com/KB/cpp/cpp_generators.aspx

A new library, Boost.Context, was released today with portable features for implementing coroutines.

This is an old thread, but I would like to suggest a hack using Duff's device that is not os-dependent (as far as I remember):

C coroutines using Duff's device

And as an example, here is a telnet library I modified to use coroutines instead of fork/threads: Telnet cli library using coroutines

And since standard C prior to C99 is essentially a true subset of C++, this works well in C++ too.

I've come up with an implementation without asm code. The idea is to use the system's thread creating function to initialize stack and context, and use setjmp/longjmp to switch context. But It's not portable, see the tricky pthread version if you are interested.

https://github.com/tonbit/coroutine is C++11 single .h asymmetric coroutine implementation supporting resume/yield/await primitives and Channel model. It's implementing via ucontext / fiber, not depending on boost, running on linux/windows/macOS. It's a good starting point to learn implementing coroutine in c++.

Check out my implementation, it illustrates the asm hacking point, it works on x86, x86-64, aarch32 and aarch64:

https://github.com/user1095108/cr2/

Most of hand-rolled coroutine implementations are variants of the setjmp/longjmp pattern or the ucontext pattern. Since these work on a variety of architectures, the coroutine implementations themselves are widely portable, you just need to provide some basic assembly code.

Based on macros as well (Duff's device, fully portable, see http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html ) and inspired by the link posted by Mark, the following emulates co-processes collaborating using events as synchronization mechanism (slightly different model than the traditional co-routines/generator style)

// Coprocess.h
#pragma once
#include <vector>

class Coprocess {
  public:
    Coprocess() : line_(0) {}
    void start() { line_ =  0; run(); }
    void end()   { line_ = -1; on_end(); }
    virtual void run() = 0;
    virtual void on_end() {}; 
  protected:
    int line_;
};

class Event {
  public:
    Event() : curr_(0) {}

    void wait(Coprocess* p) { waiters_[curr_].push_back(p); }

    void notify() {
        Waiters& old = waiters_[curr_];
        curr_ = 1 - curr_; // move to next ping/pong set of waiters
        waiters_[curr_].clear();
        for (Waiters::const_iterator I=old.begin(), E=old.end(); I != E; ++I)
            (*I)->run();
    }   
  private:
    typedef std::vector<Coprocess*> Waiters;
    int curr_;
    Waiters waiters_[2];
};

#define corun()   run() { switch(line_) { case 0:
#define cowait(e) line_=__LINE__; e.wait(this); return; case __LINE__:
#define coend     default:; }} void on_end()

An example of use:

// main.cpp
#include "Coprocess.h"
#include <iostream>

Event e;
long sum=0;

struct Fa : public Coprocess {
    int n, i;
    Fa(int x=1) : n(x) {}
    void corun() {
        std::cout << i << " starts\n";
        for (i=0; ; i+=n) {
            cowait(e);
            sum += i;
        }
    } coend {
        std::cout << n << " ended " << i << std::endl;
    }   
};

int main() {
    // create 2 collaborating processes
    Fa f1(5);
    Fa f2(10);

    // start them
    f1.start();
    f2.start();
    for (int k=0; k<=100; k++) { 
        e.notify();
    }   
    // optional (only if need to restart them)
    f1.end();
    f2.end();

    f1.start(); // coprocesses can be restarted
    std::cout << "sum " << sum << "\n";
    return 0;
}

WvCont is a part of WvStreams that implements so-called semi-coroutines. These are a little easier to handle than full-on coroutines: you call into it, and it yields back to the person who called it.

It's implemented using the more flexible WvTask, which supports full-on coroutines; you can find it in the same library.

Works on win32 and Linux, at least, and probably any other Unix system.

You should always consider using threads instead; especially in modern hardware. If you have work that can be logically separated in Co-routines, using threads means the work might actually be done concurrently, by separate execution units (processor cores).

But, maybe you do want to use coroutines, perhaps because you have an well tested algorithm that has already been written and tested that way, or because you are porting code written that way.

If you work within Windows, you should take a look at fibers. Fibers will give you a coroutine-like framework with support from the OS.

I am not familiar with other OS's to recommend alternatives there.

I've tried to implement coroutines myself using C++11 and threads:

#include <iostream>
#include <thread>

class InterruptedException : public std::exception {
};

class AsyncThread {
public:
	AsyncThread() {
		std::unique_lock<std::mutex> lock(mutex);
		thread.reset(new std::thread(std::bind(&AsyncThread::run, this)));
		conditionVar.wait(lock); // wait for the thread to start
	}
	~AsyncThread() {
		{
			std::lock_guard<std::mutex> _(mutex);
			quit = true;
		}
		conditionVar.notify_all();
		thread->join();
	}
	void run() {
		try {
			yield();
			for (int i = 0; i < 7; ++i) {
				std::cout << i << std::endl;
				yield();
			}
		} catch (InterruptedException& e) {
			return;
		}
		std::lock_guard<std::mutex> lock(mutex);
		quit = true;
		conditionVar.notify_all();
	}
	void yield() {
		std::unique_lock<std::mutex> lock(mutex);
		conditionVar.notify_all();
		conditionVar.wait(lock);
		if (quit) {
			throw InterruptedException();
		}
	}
	void step() {
		std::unique_lock<std::mutex> lock(mutex);
		if (!quit) {
			conditionVar.notify_all();
			conditionVar.wait(lock);
		}
	}
private:
	std::unique_ptr<std::thread> thread;
	std::condition_variable conditionVar;
	std::mutex mutex;
	bool quit = false;
};

int main() {
	AsyncThread asyncThread;
	for (int i = 0; i < 3; ++i) {
		std::cout << "main: " << i << std::endl;
		asyncThread.step();
	}
}