6 ms·

Lightweight concurrency library for C, featuring symmetric coroutines

76 points by albertzeyer 13y ago

eaxitect 13y ago
I also suggest libtask from Russ Cox http://swtch.com/libtask/ http://swtch.com/libtask/
- xal 13y ago
  That's really interesting how much Go can be traced back to this library.
  - eaxitect 13y ago
    Yes, actually check http://swtch.com/~rsc/thread/ http://swtch.com/~rsc/thread/ to trace back. It all starts with CSP from Hoare.
    - rubiquity 13y ago
      Wow, excellent link. Thank you for sharing.
    - mturmon 13y ago
      In that link, I learned: In 1980, barely two years after Hoare's paper, Gerard Holzmann and Rob Pike created a protocol analyzer called pan that takes a CSP dialect as input. [...] Holzmann reports that “Pan found its first error in a Bell Labs data-switch control protocol on 21 November 1980.” That dialect may well have been the first CSP language at Bell Labs, and it certainly provided Pike with experience using and implementing a CSP-like language, his first of many. [...] Holzmann's protocol analyzer developed into the Spin model checker and its Promela language. How cool. Gerard (http://gerard.holzmann.usesthis.com http://gerard.holzmann.usesthis.com) is now using Spin and several other verification tools to improve source code quality for space missions at JPL. I did not know about this connection of his work to CSP and, indirectly, to Go.
  - beagle3 13y ago
    If I am not mistaken, libtask emulates Plan9/Inferno/Limbo, and so does Go.
    - deleted 13y ago
      [deleted]
- fintler 13y ago
  If you plan on implementing anything with libtask, take a look at the version with epoll support. https://github.com/jamwt/libtask https://github.com/jamwt/libtask Mongrel2 is also an excellent example of how libtask can be used. On another note, alts and chans are underrated in libtask -- I wish the documentation promoted them more. To get an idea of what alts look like when used with a few chans, take a look at keyboardthread() from acme: http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/acme/acme.c http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/acme/ac... It's just... beautiful.
jheriko 13y ago
maybe i mis understand lightweight, but this looks enormous to me. wrapping the atomic int in a platform independent interface with maximal inlining and compiler understanding of what it is, as an example, is what i imagined from this.
- yoklov 13y ago
  Well, these are green threads, if you need to do actual concurrency you should probably look elsewhere. And, lighweight looks like it refers to the minimal amount of code in the library. Its a handful of fairly short files, enormous by no standards... Besides, if you're writing C, C11 has the atomics support you desire. Not to mention that most programmers should stick to higher level abstractions than atomics (like mutexes).
- chas 13y ago
  If you want low-overhead pseudo-concurrency for C, protothreads [1] are probably what you are looking for. [1] http://dunkels.com/adam/pt/ http://dunkels.com/adam/pt/
greesil 13y ago
How is this different from protothreads?
0x1997 13y ago
There is also https://github.com/halayli/lthread https://github.com/halayli/lthread which wraps common POSIX functions.
sovande 13y ago
I don't understand why co-routines, green threads or any other n:1 user-level threading model are of much interest in today's multi-core processor world? To utilise the computing power in front of you, you really need to use 1:1 kernel level threads in your program. This is also the biggest problem I have with node.js which is inherently single-threaded (libuv's thread-pool aside) and only uses a fraction of the CPU power available on your computer. [Edit]: A trivial, but practical example which demonstrate the power of using your machine's capabilities compared to just a fraction. If you use Make to build your project. Try 'make -j n' where n is 2 x cores on your machine. And observed the speed of building in parallel compared to serialised.
- wmf 13y ago
  Modern runtimes use M:N, not N:1.
- zackmorris 13y ago
  The main use I've found for them is converting state machines to coroutines. Logic that is tedious, cryptic or unmaintainable with state machines becomes trivial with coroutines: http://eli.thegreenplace.net/2009/08/29/co-routines-as-an-alternative-to-state-machines/ http://eli.thegreenplace.net/2009/08/29/co-routines-as-an-al... I agree though that someone needs to adapt coroutines to run concurrently. As long as there is no shared memory and you only use pipes to transmit messages (optimized with something like copy-on-write), there should be a way to partition the coroutines by the number of processors. I think it would work if you could switch the stack atomically. One thing to also consider is that if you use nonblocking system calls, you get very high CPU utilization you're just not going to get with threads and blocking. I imagine users goof this with node.js though. It would be nice to have pure nonblocking middleware..
- dilap 13y ago
  It just depends what you're doing / what you want. If you're doing N different things that are all actively using the CPU, then yeah, you want real threads. But if you maybe have a bunch of different things "in flight" that are mostly just sitting around waiting for something to else to happen to make progress, then something like coroutines or green threads could make sense 'cuz of lower startup and memory overhead. It can also be handy just for code structure. You want two things making forward progress at once, and instead of using callbacks and a bunch of variables to try to maintain state, you just use coroutines and the implicit state therein, but since you didn't go to real, executing-in-parallel threads, you don't have to worry about all the synchronization/race avoidance junk that comes from that (but of course, you also don't get the multi-core speedup).
halayli 13y ago
I think lthread (http://github.com/halayli/lthread http://github.com/halayli/lthread) is the only coroutine lib that allows you to block inside a coroutine and do heavy computation without affecting other coroutines. Example: void my_function(void* arg) { char buf[1024]; int ret = lthread_recv_exact(fd, buf, 1024, 0, timeout); lthread_compute_begin(); /* block as long as you wish, run heavy computation on buf, access your stack variables etc.. */ lthread_compute_end(); } Disclaimer: lthread author.
- jdmt 13y ago
  Why do you do things like: assert(doSomethingThatChangesState() == 0); throughout your code? I thought the point of assert was for debugging purposes and you should never change program state inside the assertion.
  - halayli 13y ago
    I prefer to fail as soon as possible. I use asserts in places where there is no good way to recover from a failed invariant.
    - jdmt 13y ago
      Failing immediately is certainly an easy way to handle unrecoverable errors. However, it seems as though your library assumes NDEBUG is never defined. Maybe you should make your own function rather than using assert()?
      - halayli 13y ago
        The asserts are in the .c files. Defining NDEBUG in your program won't change anything in lthread because the library was compiled without NDEBUG defined. If you want to define NDEBUG when compiling lthread, that's up to you.
        sebcat 13y ago
avdicius 13y ago
And this is mine: https://github.com/ademakov/MainMemory https://github.com/ademakov/MainMemory Though it's not a library, but it can be converted into one if needed. And it's not so lightweight already and I'm still working on more features.

76 points by albertzeyer 13y ago

eaxitect 13y ago

I also suggest libtask from Russ Cox http://swtch.com/libtask/ http://swtch.com/libtask/

xal 13y ago
That's really interesting how much Go can be traced back to this library.
- eaxitect 13y ago
  Yes, actually check http://swtch.com/~rsc/thread/ http://swtch.com/~rsc/thread/ to trace back. It all starts with CSP from Hoare.
  - rubiquity 13y ago
    Wow, excellent link. Thank you for sharing.
  - mturmon 13y ago
    In that link, I learned: In 1980, barely two years after Hoare's paper, Gerard Holzmann and Rob Pike created a protocol analyzer called pan that takes a CSP dialect as input. [...] Holzmann reports that “Pan found its first error in a Bell Labs data-switch control protocol on 21 November 1980.” That dialect may well have been the first CSP language at Bell Labs, and it certainly provided Pike with experience using and implementing a CSP-like language, his first of many. [...] Holzmann's protocol analyzer developed into the Spin model checker and its Promela language. How cool. Gerard (http://gerard.holzmann.usesthis.com http://gerard.holzmann.usesthis.com) is now using Spin and several other verification tools to improve source code quality for space missions at JPL. I did not know about this connection of his work to CSP and, indirectly, to Go.
- beagle3 13y ago
  If I am not mistaken, libtask emulates Plan9/Inferno/Limbo, and so does Go.
  - deleted 13y ago
    [deleted]
fintler 13y ago
If you plan on implementing anything with libtask, take a look at the version with epoll support. https://github.com/jamwt/libtask https://github.com/jamwt/libtask Mongrel2 is also an excellent example of how libtask can be used. On another note, alts and chans are underrated in libtask -- I wish the documentation promoted them more. To get an idea of what alts look like when used with a few chans, take a look at keyboardthread() from acme: http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/acme/acme.c http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/acme/ac... It's just... beautiful.

jheriko 13y ago

maybe i mis understand lightweight, but this looks enormous to me. wrapping the atomic int in a platform independent interface with maximal inlining and compiler understanding of what it is, as an example, is what i imagined from this.

yoklov 13y ago
Well, these are green threads, if you need to do actual concurrency you should probably look elsewhere. And, lighweight looks like it refers to the minimal amount of code in the library. Its a handful of fairly short files, enormous by no standards... Besides, if you're writing C, C11 has the atomics support you desire. Not to mention that most programmers should stick to higher level abstractions than atomics (like mutexes).
chas 13y ago
If you want low-overhead pseudo-concurrency for C, protothreads [1] are probably what you are looking for. [1] http://dunkels.com/adam/pt/ http://dunkels.com/adam/pt/

greesil 13y ago

How is this different from protothreads?

0x1997 13y ago

There is also https://github.com/halayli/lthread https://github.com/halayli/lthread which wraps common POSIX functions.

sovande 13y ago

I don't understand why co-routines, green threads or any other n:1 user-level threading model are of much interest in today's multi-core processor world? To utilise the computing power in front of you, you really need to use 1:1 kernel level threads in your program. This is also the biggest problem I have with node.js which is inherently single-threaded (libuv's thread-pool aside) and only uses a fraction of the CPU power available on your computer. [Edit]: A trivial, but practical example which demonstrate the power of using your machine's capabilities compared to just a fraction. If you use Make to build your project. Try 'make -j n' where n is 2 x cores on your machine. And observed the speed of building in parallel compared to serialised.

wmf 13y ago
Modern runtimes use M:N, not N:1.
zackmorris 13y ago
The main use I've found for them is converting state machines to coroutines. Logic that is tedious, cryptic or unmaintainable with state machines becomes trivial with coroutines: http://eli.thegreenplace.net/2009/08/29/co-routines-as-an-alternative-to-state-machines/ http://eli.thegreenplace.net/2009/08/29/co-routines-as-an-al... I agree though that someone needs to adapt coroutines to run concurrently. As long as there is no shared memory and you only use pipes to transmit messages (optimized with something like copy-on-write), there should be a way to partition the coroutines by the number of processors. I think it would work if you could switch the stack atomically. One thing to also consider is that if you use nonblocking system calls, you get very high CPU utilization you're just not going to get with threads and blocking. I imagine users goof this with node.js though. It would be nice to have pure nonblocking middleware..
dilap 13y ago
It just depends what you're doing / what you want. If you're doing N different things that are all actively using the CPU, then yeah, you want real threads. But if you maybe have a bunch of different things "in flight" that are mostly just sitting around waiting for something to else to happen to make progress, then something like coroutines or green threads could make sense 'cuz of lower startup and memory overhead. It can also be handy just for code structure. You want two things making forward progress at once, and instead of using callbacks and a bunch of variables to try to maintain state, you just use coroutines and the implicit state therein, but since you didn't go to real, executing-in-parallel threads, you don't have to worry about all the synchronization/race avoidance junk that comes from that (but of course, you also don't get the multi-core speedup).

halayli 13y ago

I think lthread (http://github.com/halayli/lthread http://github.com/halayli/lthread) is the only coroutine lib that allows you to block inside a coroutine and do heavy computation without affecting other coroutines. Example: void my_function(void* arg) { char buf[1024]; int ret = lthread_recv_exact(fd, buf, 1024, 0, timeout); lthread_compute_begin(); /* block as long as you wish, run heavy computation on buf, access your stack variables etc.. */ lthread_compute_end(); } Disclaimer: lthread author.

jdmt 13y ago
Why do you do things like: assert(doSomethingThatChangesState() == 0); throughout your code? I thought the point of assert was for debugging purposes and you should never change program state inside the assertion.
- halayli 13y ago
  I prefer to fail as soon as possible. I use asserts in places where there is no good way to recover from a failed invariant.
  - jdmt 13y ago
    Failing immediately is certainly an easy way to handle unrecoverable errors. However, it seems as though your library assumes NDEBUG is never defined. Maybe you should make your own function rather than using assert()?
    - halayli 13y ago
      The asserts are in the .c files. Defining NDEBUG in your program won't change anything in lthread because the library was compiled without NDEBUG defined. If you want to define NDEBUG when compiling lthread, that's up to you.
      - sebcat 13y ago

avdicius 13y ago

And this is mine: https://github.com/ademakov/MainMemory https://github.com/ademakov/MainMemory Though it's not a library, but it can be converted into one if needed. And it's not so lightweight already and I'm still working on more features.