Implementing coroutines, channels, message passing, etc.
C Assembly C++ Makefile
Failed to load latest commit information.
benchmark Add bogus partial benchmark. Nov 8, 2015
libtask @ 4cd1bfc Added libtask as submodule Mar 20, 2013
siphash benchmark the bit rotation! Mar 26, 2013
.gitmodules Added libtask as submodule Mar 20, 2013
Hack and Tell coroutine presentation.key Document coroutine_test Oct 21, 2013
LICENSE Add apache license. Aug 2, 2014
Makefile Fix optimization, PHONY Dec 28, 2013
README.md Simplification Apr 18, 2013
assembly.c indentation Mar 21, 2013
assembly64.c fix PC-relative addressing issue (Mac OS X specific) Mar 20, 2013
assembly_stuff.S o Mar 21, 2013
assembly_stuff_64.S fix PC-relative addressing issue (Mac OS X specific) Mar 20, 2013
channel_test.c rename function to document its function Mar 19, 2013
channels.c fix formatting issues caused by using .emacs settings from work Mar 19, 2013
channels.h implemented channels Mar 18, 2013
coop.c setjmp/longjmp snippets Mar 16, 2013
coroutine_test.c Document coroutine_test Oct 22, 2013
coroutines.c Refactor most of coro_allocate into grow_stack Mar 21, 2013
coroutines.h forgot to add this Mar 18, 2013
exception.c setjmp/longjmp snippets Mar 17, 2013
heapros.c Document heapros Oct 21, 2013
jit-debugging.c Try gdb with a JIT Apr 10, 2013
makecontext-64.c extra comment Mar 19, 2013
rdpmc.h Maybe do rdpmc Dec 24, 2013
rdtsc.h My RDTSC routines, because.... Mar 18, 2013
setjmp.c setjmp/longjmp snippets Mar 17, 2013
sigaltstack.c Switch to SIGLARM, to allow seamless gdb usage Apr 8, 2013
stack_engine_ubenchmark.c Let the power of statistics be with us! Mar 18, 2013
stddev.h Let the power of statistics be with us! Mar 18, 2013
ucontext_from_manpage.c example from the manpage Mar 19, 2013

README.md

This was originally a one-day project to explore implementing concurrency in C. This is all exploratory code which isn't even close to production ready. On the first day, we tried implementing the most naive possible implemenation of coroutines, allocating a fixed amount of extra stack space, fixing a particular amount of stack space for each coroutine, giving each coroutine EXTRA_SPACE / N stack space, for some fixed N.

On top of that, we implemented channels (for something resembling Go style concurrency), again using the dumbest possible implementation. A send or receive on a channel simply marks a coroutine unrunnable in the channel scheduler until the channel sees the inverse operation.

A few days later, we spent half a day creating the second simplest coroutine implementation we could think of: allocate space on the heap for each coroutine, and swap stacks when switching between coroutines. Turns out, this is what the Julia language does, so this idea turned out to be more practical than we realized.

A possible improvement would be to allocate a seperate stack space for each coroutine. The most obvious way to do that would be to use ucontext, but that doesn't appear to have good cross-platform support. In particular, the Mac OS X implementation seems to be fundamentally broken. I played around with sigaltstack as an alternative. That ought to work, and I may try implementing coroutines on top of sigaltstack at some point.

  • coroutines.*: Implementation of coroutines using setjmp and longjmp
  • coroutine_test.c: Simple usage of above
  • heapros.c: Implementaion of coroutines using setjmp and longjmp, with stack copying to heap
  • channels.: Implementation of channels, on top of coroutines.
  • channel_test.c: Sieve of Eratosthenes using channels
  • stack_engine_ubenchmark.c: Silly benchmark to figure out if manually messing with stack will cause performance degradation, by causing sync uops to be inserted to keep Intel's "stack engine" in sync with back-end stack registers
  • sigaltstack.c: Use sigaltstack to change stack
  • setjmp.c, exception.c, coop.c: Setjmp/longjmp examples from wikipedia

Run:

git submodule update --init