10 ms·
Coroutines in one page of C
- rdpmc 13y agoYou can also implement a simple version of channels (go's concurrency model) on top of something like that, with just one more page of C: https://github.com/danluu/setjmp-longjmp-ucontext-snippets/blob/master/channels.c https://github.com/danluu/setjmp-longjmp-ucontext-snippets/b... https://github.com/danluu/setjmp-longjmp-ucontext-snippets/blob/master/channel_test.c https://github.com/danluu/setjmp-longjmp-ucontext-snippets/b...
- tikhonj 13y agoAnd, for a completely different take on the subject, coroutines in Haskell: http://random.axman6.com/blog/?p=231 http://random.axman6.com/blog/?p=231 This is a nice article that explains how they work pretty well. It's very different from the C approach.
- ginko 13y agoWouldn'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.
- ufo 13y agoOne 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...
- tel 13y agoLaziness 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 lines :: IO [String] lines = withFile path $ \h -> hReadLines h 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. [0] http://themonadreader.files.wordpress.com/2011/10/issue19.pdf http://themonadreader.files.wordpress.com/2011/10/issue19.pd...
- nanofortnight 13y agoThis can be implemented without assembly using setcontext/getcontext on POSIX-compatible systems, and GetThreadContext/SetThreadContext on Windows.
- cygx 13y agoNot if you care for performance.
- nanofortnight 13y agoget/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.
- vinkelhake 13y agoThe 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. [1] http://www.boost.org/doc/libs/1_54_0/libs/context/doc/html/context/performance.html http://www.boost.org/doc/libs/1_54_0/libs/context/doc/html/c...
- cygx 13y agoSee also the notes on various implementation mechanisms of libcoro ( http://cvs.schmorp.de/libcoro/coro.h http://cvs.schmorp.de/libcoro/coro.h )
- davidtgoldblatt 13y agogetcontext and setcontext also keep track of signal state, which involves a syscall.
- anon1385 13y agoExamples of that in the Io source: https://github.com/stevedekorte/io/blob/master/libs/coroutine/source/Coro.c https://github.com/stevedekorte/io/blob/master/libs/coroutin... https://github.com/stevedekorte/io/blob/master/libs/coroutine/source/context.c https://github.com/stevedekorte/io/blob/master/libs/coroutin...
- gte910h 13y agoCan people explain the fascination with Coroutines? I don't see what problem domain hits solutions that are best done with them all the time.
- jws 13y agoall the time is strong. 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.
- gte910h 13y agoCan I have an example here?
- spc476 13y agoHere'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).
- zzzcpan 13y agoIf you are interested in coroutines, take a look at GNU Portable Threads http://www.gnu.org/software/pth/ http://www.gnu.org/software/pth/ and this paper: http://www.gnu.org/software/pth/rse-pmt.ps http://www.gnu.org/software/pth/rse-pmt.ps
- NoodleIncident 13y agoBetter 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. http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
- fanf2 13y agoNote that Simon's coroutines are more like Python generators than full-blown coroutines, since only the top-level function can yield. You don't need asm to manipulate the stack and frame pointers in standard C - see http://fanf.livejournal.com/105413.html http://fanf.livejournal.com/105413.html or for some slightly more fleshed-out variants that do not require C99 see http://dotat.at/cgi/git/picoro.git http://dotat.at/cgi/git/picoro.git
- _yosefk 13y agoSo 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...)
- iambvk 13y agoGlad you mentioned this; to me, this is a very important requirement. I don't see lot of people understand the difference between YIELD and full-blown coroutines. IMO YEILD is not very useful; it doesn't compose well with non-yield function. OTOH full-blown coroutines are super awesome. Too bad C++11 still doesn't give full-blown coroutines.
- batguano 13y ago
- imurray 13y agoAn alternative approach, arguably with too much magic: http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
- nonane 13y agoActually, 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); }
- _yosefk 13y agoNo stack though, so you can't have arbitrary code running in several concurrently executing coroutines. As to debugging, I don't think setjmp/longjmp gets in the way of debuggers at all.
- halayli 13y agoor use lthread. http://github.com/halayli/lthread http://github.com/halayli/lthread
- ilink 13y agoMy coworker showed me this, great library!
- jvanenk 13y agoI'm reminded of protothreads (http://dunkels.com/adam/pt/ 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.
- _yosefk 13y agoThe 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).
- enqk 13y agoCare to explain further? In my experience of using protothreads, only the functions using the protothread macros need to be written in a special way: - passing a context object - being careful of variable initialization/blocks in order not to work on unitialized memory. while all the other ones can stay plain C functions.
- _yosefk 13y agoSure, 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.
- enqk 13y agoI 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.
- msteinert 13y agoI've always liked Russ Cox's solution [1] [1]: http://swtch.com/libtask/ http://swtch.com/libtask/
- bajsejohannes 13y agoWhat's the runtime overhead on this? Aren't setjmp and longjmp considered slow?
- ajross 13y agoset/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.
- miratom 13y agoGood luck debugging these!
- brianpgordon 13y ago> 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.
- ChuckMcM 13y agoWow, 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 :-)
- chmike 13y agoLibcoro[1] is a C library providing the primitives to implement yield. [1] http://software.schmorp.de/pkg/libcoro.html http://software.schmorp.de/pkg/libcoro.html