Wow, that takes me back. That was _exactly_ how the original Java Virtual Machine did threading. I ported it to the new model used by Solaris (from its SunOS 4.x roots) and that begat the term 'hello hello hello world world world' which is, as you might imagine, getting the threaded version of helloworld.c running :-)
Better yet: coroutines in three macros. I found this page googling "yield in c++", not really expecting to find anything. I ended up not using it, but it's still my favorite bit of hackery.
So you allocate a coroutine stack by allocating a large array on the caller's stack, so that when you longjmp back to the setjmp'd context, you can safely overwrite that reserved space. F* me plenty.
Good stuff. One reason my inline asm serves my specific needs better is that my host OS has stack protection - a thread can only access its own stack; and I send coroutines around threads - yield in thread A, resume in thread B - and so I have to allocate my stacks outside the stacks of either A or B. I'll add a link to your implementation in my article, and perhaps Wikipedia should, too, if it didn't already (it has a lengthy list of coroutine implementations in C...)
Didn't see your comment til now. So, here is the difference I see:
Full-blown coroutines give us a way to write fully asynchronous code without using callbacks. For example, I could define ASYNC macro as follows:
#define ASYNC(blocking_function_call) \
do { \
auto io_pool = GetIOThreadPool(); \
auto cpu_pool = GetCurrentThreadPool(); \
\
Detach_The_Thread_and_Enqueue_Coroutine_For_IO(io_pool); \
\
blocking_function_call; \
\
Detach_The_Thread_and_Enqueue_Coroutine_For_CPU(cpu_pool); \
} while (0)
Now, I can make any blocking operation asyncrhonous. For example, open() or readdir() functions do not have asynchronous interfaces, but I can make them asynchronous by simply wrap it with ASYNC(...) macro.
It works as follows: When we need to do a blocking operation, we suspend the coroutine and we enqueue it into a thread-pool that is designated to do blocking calls; the cpu thread is now free, so it can start executing other cpu-bound coroutines. When io thread has finished the job, it will enqueue the coroutine back to the CPU thread pool.
What we have now is a fully asynchronous system where cpu threads can be kept busy with only cpu-bound work and io threads can be kept with io-bound work. This gives us full control over the concurrency. We could be confident that CPU threads are always available for compute work.
get/setcontext do not copy stack, but use an allocated bit of memory space for the stack and swaps stack pointers just like this implementation. I don't see how that's a performance hit.
I do not pretend to know about Windows internals so I won't comment on Windows.
The author of boost.context did some benchmarking[1] and found that get/setcontext was an order of magnitude slower than a custom solution. Whether this matters is an entirely different question, but it's clear that get/setcontext has some overhead.
I'm reminded of protothreads (http://dunkels.com/adam/pt/). I used protothreads some time ago on an embedded project to implement a (very small) HTTP server in only a few KB or RAM.
The trouble with them is they're stackless, which means you can't have arbitrary functions thoughtlessly coded by someone unaware of threading called inside many different protothreads. Coroutines are easier to combine with code not written to account for their existence (of course stack overflow is a big concern though, which can be somewhat mitigated through memory protection depending on the OS and the hardware).
Sure, if none of these C functions tries to yield, or calls a library function trying to yield. In fact, the problem isn't that they can't be plain C functions, but that they must be plain C functions :)
Why would functions called by "lightweight threads"/"coroutines"/whatever want to yield? One example is, they want to wait for an event - an I/O request completion or a computation offloaded to an accelerator or whatever - without having to return all the way back to the event loop.
I must admit that this property attracted me to protothreads, since there is a clear demarcation between coroutines (through the presence of a protothread argument) and plain C functions.
The main benefit of coroutines is avoiding inversion of control flow.
A classic example is iterators. Its very natural to write an iterator like
for(i=0; i<10; i++){
yield i
}
But to program the same thing without coroutines you need to keep all the control flow state explicitly and write the logic inside out like a state machine:
i = 0
int getNext(){
if(i >= 10){
return Done
}else{
temp = i
i = i + 1
return temp
}
}
This inversion of control gets worse the more complicated your control flow is. For example if you have a recursive structure
then you suddenly need to also keep a bunch of stacks as your control flow state instead of just a single integer. I wont even try to write it because its just that ugly!
---------
One way to prevent the inversion of control is to use internal iterators, where you pass a code block to the iterator:
This works just fine sometimes but there are limitations: you cant't break out of the iteration at the middle and you cant interweave to iterations in parallel. Another situation where you see this kind of limitation is Javascript. Using callbacks to do async IO is better than writing everything inside out with all state in global variables (like you would do in C) but its a PITA to do simple things like chaining async calls one after the other inside a loop For example, with coroutines you could do something looking like
foreach(url in list){
var x = await getUrl(url)
console.log(x)
}
restOfTheCode();
while in regular JS you need to use recursive functions instead:
I find them useful when conjoining function A with produces a sequence of results and function B which consumes the sequence†. Without coroutines you either have to turn one of the functions inside out to use it as a callback or break into threads and pass data between them.
With coroutines you can leave the functions in a more readable form and keep your cache footprint small by consuming the result as soon as it is produced.
␄
† I don't mean that I call A or B for each element of the sequence. A and B may have internal state and fill produce or consume the whole sequence in a single call. They could be organized to have a create function, a context structure, a "do one" call, and a destroy function… but that is a lot of noise and a lot of places for someone to make a mistake using them. A coroutine is cleaner.
Here's a Lua-esque (since Lua supports coroutines) example. I want to run a simple TCP echo server, so the main code that handles a connection ideally would look like this:
function echo(socket)
local remote,data = socket:read()
if remote == nil then -- no data
socket:close()
return
end
socket:write(remote,data)
return echo(socket) -- Tail call, this is a goto
end
Normally, such code would need to be run in a separate process or thread but that's too much overhead. You can use an event-based method (say, with poll() or epoll()) but then the code becomes inverted (or involves callbacks---which in this case isn't too bad, but imagine trying to implement, say, SMTP). With coroutines, we can still use an event-based mainloop, but still keep the imperative style of the original function above. Our event loop would look something like:
function mainloop()
local events = select:events()
for i = 1 , #events do
local err,keepgoing = coroutine.resume(events[i].code,events[i].socket,events[i].remote)
if not keepgoing then
select:remove(events[i].socket)
events[i].socket:close()
end
end
return mainloop()
end
and we would need to change our function just a bit:
function echo()
local socket,remote = coroutine.yield(true)
local data = socket:read()
if data == nil then
return false
end
socket:write(remote,data)
return echo()
end
Oh, and don't forget the coroutine to accept new connections:
function echoconnection()
local socket = coroutine.yield(true)
local connection,remote = socket:accept()
select:insert(connection,{ read = true } ,{ code = echo,remote = remote })
return echoconnection()
end
You can, of course, rewrite it such that socket:read() does the call to coroutine.yield(), but here I wanted to make it more explicit (as well as a shorter example) to fully hide the implementation (this is based on a working implementation I have in about 224 lines of Lua, which also handles signals and hides the coroutine calls from the main functions---the first example in this post would run as-is in the fully-blown implementation).
Well, it's finicky. You'll need to install several custom written Lua modules [1]. These have been tested under Linux and Solaris. You will definitely have to edit the Makefile to exclude building some of the modules like org.conman.tcc [2] because of dependency issues (TCC isn't for the faint of heart). If you are on another Unix system, you'll probably be able to get most of it built (at the least, you'll need org.conman.process, org.conman.net and org.conman.pollset). You will also need to install LPeg [3]. Once all those are installed, then you'll be able to run the code: http://pastebin.com/ZBq5gSbS
[2] It's a Lua interface to the TCC library, which is a C compiler-as-a-library. Not used in the same code I posted, but it is something I find immensely useful, but I would classify as "advanced."
very informally, they're good for the kind of problem where it would be nice to structure your code as if you're using threads, but you have a simple sequence of actions so don't need the asynchronous aspect of threads or the worry that goes with them + mutable state.
for example, in the matasano crypto challenge i needed to simulate a message protocol between various actors (and then break it). i could have written client and server as separate threaded entities, but it was simpler to just have them each be a coroutine.
think of them like thread, state and bi-directional queue, in one easy package.
another example is lazy sequences. you could start up a separate thread that generates the sequences, but then you need to talk to it, throttle it in some way, and close it down. using a generator (a simple co-routine) you can still have your code for generating the sequence in one clean place, but it's easier to call and control.
if you've ever thought "it would be kinda cool if threads were simple, so i could structure my code like..." then you probably would have appreciated a coroutine.
Cool, I've been expecting a chance to do coroutine-based modeling of crypto protocols in those challenges, but haven't been able to devote any time to going through them.
Some people think that async code phrased as though it was blocking code is easier to read, write, and modify. This is because the workflow for writing async code with callbacks is basically
1. Imagine the control flow you actually want.
2. Manually perform some subset of a CPS transform around the parts that would block.
3. Write the result of 2 and check it in.
And then the workflow for updating it is
a. Read the code.
b. Attempt to reconstruct a mental model of the originally-desired control flow from the mess.
c. goto 1.
If you have some simulation/game in which many entities need to interact, you can use coroutines and write each entity's routine(s) imperatively. For example, BulletML lets you do this by embedding a suspendable domain-specific language in your project. If you check out http://www.youtube.com/watch?v=uK_YTyhj7T4, every bullet that either fires other bullets or changes velocity has one or more functions attached to it, and they are all running concurrently. It might be even better to do this without using an extra language, though.
In addition to inversion of control mentioned elsewhere, consider situations where you could have used threads and synchronization points (mutexes etc.). In such situations co-routines can offer a much lighter weight alternative to full blown threads (for single core execution), as the points where control should switch can be explicitly known, and the "context switch" can often be done with far less data shuffling.
As with so many programming techniques, there is nothing that can only be done with a coroutine approach, so bear in mind that any example that fits in a little text box probably also fits into a little text box with conventional functions. Practical differences only appear at scale.
Further, "coroutine", like so many other programming terms, has suffered from a certain fuzziness. There's a reasonably precise term used by programming language researchers, which very few languages have. Things like Python's generators do not conform entirely to this definition, but you get people calling them coroutines anyhow, along with so many other things.
So, rather than try to justify the exact PL-research definition, let me try to explain the interesting thing about the more sloppy, broad definition. In a nutshell:
When you call a function, you pass in certain arguments. Then you start at the beginning, generating state or values in response to the input, before finally returning some more values. You then discard all the intermediate state the function generated. The idea here is that there are times when you may want to not discard the state, and/or you may want to be able to not start the function at the beginning. You may also want to pass fresh values into the middle of the function.
One of the most clear examples of where this is useful is when you create a pipeline of functions within your code. Using "functions" that can get more input as they go along, and generate output without discarding all their intermediate state, makes it very easy to compose functions together into a pipeline that only know they are in a pipeline. You can take input from a user, apply a "coroutine" that then parses their input into numbers, feed that into a "coroutine" that groups them together into a run-length delimited format, then feed that into a coroutine that writes the results to a file. Each of these routines holds on to a little bit of state, instead of discarding it. Each of these routines is "pluggable"; you can take the same pipeline, pop the "user input" bit off the front, and read from a file, or stream from the network, and the same for all the little bits. You get a composable system of functions that all know just barely enough to function (which is what makes composition easy), instead of a set of functions that knows "A ha, I'm going to get this sort of linked list, traverse it, do 'my thing', and then return a new sort of linked list", which doesn't work on network streams, or hash tables, etc. This also is an easy way to operate on a "stream" without having to have the whole stream loaded into memory, and is more cache/memory-bandwidth friendly because you're only traversing it once.
Of course, if you work at it enough, you can do this with conventional functions. But you're going to write a lot of boilerplate, you're going to get it wrong, and it probably still won't be as composable in the end. Or you'll end up manually re-implementing "coroutine"ish things yourself.
This is only one example, but it's one of the clearer ones where having things able to retain state without being forced into the strict call hierarchy that conventional function stacks require is obviously a good idea.
(Pendant note: I've tried to keep this comment very language agnostic. There's a world of difference between Haskell and Python here, for instance. I'm going for the essence of the pattern in general, not in a particular language.)
> A coroutine is a function that you can jump back into after returning from it - and it remembers where it was in the code, and all the variables.
This is actually called a continuation. Coroutines are a control flow idiom for skipping back and forth between two blocks of code, which can depend on continuations.
Wouldn't you implement coroutines in Haskell by just generating a stream that is lazily evaluated? You can seed something like this with the iterate function for instance.
One of the biggest reasons for using coroutines in Haskell is when you want to mix them with effects. For example, using lazy streams to do IO can lead to unpredictable resource usage so many people use coroutine libraries to do the IO in a more predictable manner (piper / conduits / io-streams / etc).
Finally, while lazy streams go a long way, in terms of preventing the inversion of control that you usually need to use coroutines for, there are still some situations where coroutines are useful. For example try writing that consumer/producer example from the blog post he linked using only lazy streams...
Laziness is pretty implicit and while it enables all kinds of optimizations and reasoning it can be hard to understand the sequencing of effects. In particular, laziness and IO lead to code where handle opening and closure is difficult to understand. For instance
will generate a lazy stream of strings in an IO action without actually reading those lines. You can either close the handle immediately and get a runtime error later when you force those lines OR leave it open and leak a file handle.
Explicit coroutines help to ensure that you know exactly what to expect from effect interleaving.
Mario Blazevic's article [0] is the quintessential treatment and forms the basis of the Pipes library today.
Actually, the link you've posted is much simpler than the parent post: no assembly voodo required and no longjump shenanigans. It's also much easier to debug under a debugger. I've successfully used this in production code. It effectively boils down to these 3 defines:
#define COR_BEGIN(stateVar) switch(stateVar) { case 0:;
#define COR_END(stateVar) }; stateVar = -1;
#define COR_RETURN(stateVar) do { stateVar=__LINE__; return; case __LINE__:;} while (0)
void dofunc(int* pstate)
{
COR_BEGIN(*pstate);
while (computation1)
COR_RETURN(*pstate);
while (computation2)
COR_RETURN(*pstate);
COR_END(*pstate);
}
set/longjmp are full context switches, so they need to write out all relevant registers to memory. More to the point the "context" being saved here is the full C stack, so in addition to the space for the registers you also need to allocate memory for the stacks to which you are going to swtich.
With a more constrained language, the compiler would be able to do cleaner analysis to save off only the subset of closed-over data. Most functions like this don't ever need to return all the way up to the thread top, they just work with a few local variables.
That said, saving/restoring a few hundred bytes of registers and allocating a page for a small stack are hardly "slow" operations, so I wouldn't view performance as a real issue here.
