Libaco: A fast and lightweight C asymmetric coroutine library(github.com)
github.com
Libaco: A fast and lightweight C asymmetric coroutine library
https://github.com/hnes/libaco
57 comments
the most starred co-routine C is:
https://github.com/Tencent/libco
It's said golang learned from libtask:
https://github.com/jamwt/libtask
And something else:
https://github.com/baruch/libwire
https://github.com/halayli/lthread (multi-core friendly)
https://github.com/Tencent/libco
It's said golang learned from libtask:
https://github.com/jamwt/libtask
And something else:
https://github.com/baruch/libwire
https://github.com/halayli/lthread (multi-core friendly)
Disappointing that Tencent took my library's name. I'd been using the name since 2006 or so. I guess you can't expect a two-letter lib* name to remain unique. My luck that theirs would become the most well known in this space, though.
hi byuu, are you going to add arm64 support? or considering C99?
if I have multiple cores, what's the best way to leverage that along with libco? will cpu affinity help?
if I have multiple cores, what's the best way to leverage that along with libco? will cpu affinity help?
Aarch64 support will show up as soon as I can get a Linux distro running on it to test the implementation with. My understanding is the ARM ABI isn't as well defined, and you tend to need slightly different implementations per device, so it may not be as useful as simply using the setjmp version.
You can set -DLIBCO_MP to get the co_active handle to be multi-threaded. Each preemptive thread would then have its own set of cooperative threads.
You can set -DLIBCO_MP to get the co_active handle to be multi-threaded. Each preemptive thread would then have its own set of cooperative threads.
Hi Byuu! You're a cool guy and I hope I can be like you one day!
Having done a bunch of work on PuTTY, I have to say I am a fan of Simon Tatham's C co-routines [0] (basically, a C preprocessor meta-programmed super Duff's device).
[0] https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
[0] https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
to be fair you should point out that libco is written in c++, where as OP is actually written in c
A maybe naive question here, and also maybe slightly off-topic but: is there ever a reason to use co-routines when you have full-fledged multi-threading available?
As much as multi-threading can quickly become a headache wrt robustness and provable behaviour, I've always felt that a complex co-routine based codebase - even if you can theoretically reason about it using FSMs - is harder to "fit in head".
As much as multi-threading can quickly become a headache wrt robustness and provable behaviour, I've always felt that a complex co-routine based codebase - even if you can theoretically reason about it using FSMs - is harder to "fit in head".
I use coroutines in C++ frequently as well as threads; they solve different problems. There are two major use cases for coroutines in my experience: they are a much faster concurrency primitive in some cases and they make the design of some complex concurrency problems much simpler. Using coroutines, which are functional in nature, seem complicated until you grok them and at which point the design of such code becomes clear and obvious (like functional programming generally).
The large performance advantage of coroutines comes from two main areas. First, context-switching in coroutines is at least a thousand times faster than with threads. On modern processors for software with fine-grained locking requirements, it is common to see multithreaded applications spending more CPU time on context-switching than actually running application code. Database engines were early adopters of the coroutine model because they have this problem in a major way. Second, you have complete control of the execution schedule ensuring that your code is always doing the best possible thing at the best possible time; schedule-based optimization offers a large throughput improvement by allowing you to dynamically select the task that is most optimal to run in the current context rather than selecting randomly. For a simple example from the database world, most atomic units of work are applying a scan operators to a data page, which are generally very fast -- access latency is a major fraction of the total cost. If you have a thousand queries running concurrently, many of them will touch the same pages at different times. In a coroutine model, when one coroutine pulls a data page into L2 cache, it is inexpensive to immediately schedule the other queries that will need to eventually access that data page to run their operator on the same page at the same time, switching between them sequentially. In multithreaded environments, you tend to end up churning the CPU cache for almost every single page operation. The overhead of most schedule-based optimization in threaded environments is prohibitive, so it largely isn't done.
The simplicity advantage for complex concurrency problems is that you don't need locks, which is the bane of multithreaded programming, with the caveat that all your operations need to be non-blocking. The full state of the various tasks is available to you so conflicts can be eliminated by scheduling the coroutine execution so that they never occur. For all practical purposes, code correctness is evaluated in a single-threaded context. You can design multithreaded code primitives that can inspect their own lock graphs to ensure that deadlocks and other conflicts can always be resolved automatically, database engines tend to use these structures pervasively, but they are both complex and computationally expensive. The disadvantage of coroutines here is that all of your I/O interactions must be non-blocking. Most I/O these days should be non-blocking as a matter of performant design but if you are using coroutines then using blocking I/O is not a sensible option for the developer.
Architecturally, coroutines lead to a model where virtually all data is private to a thread whereas in a multithreaded model most data tends to be shared between threads. There are many concurrency and complexity advantages to making data non-shared but it comes with one major downside -- you need to figure out how to balance compute load in such a model, which is perfectly solvable but not trivial like the multithreaded case. Distributed systems have the same load balancing problem (though few attempt to solve it in a robust way).
The large performance advantage of coroutines comes from two main areas. First, context-switching in coroutines is at least a thousand times faster than with threads. On modern processors for software with fine-grained locking requirements, it is common to see multithreaded applications spending more CPU time on context-switching than actually running application code. Database engines were early adopters of the coroutine model because they have this problem in a major way. Second, you have complete control of the execution schedule ensuring that your code is always doing the best possible thing at the best possible time; schedule-based optimization offers a large throughput improvement by allowing you to dynamically select the task that is most optimal to run in the current context rather than selecting randomly. For a simple example from the database world, most atomic units of work are applying a scan operators to a data page, which are generally very fast -- access latency is a major fraction of the total cost. If you have a thousand queries running concurrently, many of them will touch the same pages at different times. In a coroutine model, when one coroutine pulls a data page into L2 cache, it is inexpensive to immediately schedule the other queries that will need to eventually access that data page to run their operator on the same page at the same time, switching between them sequentially. In multithreaded environments, you tend to end up churning the CPU cache for almost every single page operation. The overhead of most schedule-based optimization in threaded environments is prohibitive, so it largely isn't done.
The simplicity advantage for complex concurrency problems is that you don't need locks, which is the bane of multithreaded programming, with the caveat that all your operations need to be non-blocking. The full state of the various tasks is available to you so conflicts can be eliminated by scheduling the coroutine execution so that they never occur. For all practical purposes, code correctness is evaluated in a single-threaded context. You can design multithreaded code primitives that can inspect their own lock graphs to ensure that deadlocks and other conflicts can always be resolved automatically, database engines tend to use these structures pervasively, but they are both complex and computationally expensive. The disadvantage of coroutines here is that all of your I/O interactions must be non-blocking. Most I/O these days should be non-blocking as a matter of performant design but if you are using coroutines then using blocking I/O is not a sensible option for the developer.
Architecturally, coroutines lead to a model where virtually all data is private to a thread whereas in a multithreaded model most data tends to be shared between threads. There are many concurrency and complexity advantages to making data non-shared but it comes with one major downside -- you need to figure out how to balance compute load in such a model, which is perfectly solvable but not trivial like the multithreaded case. Distributed systems have the same load balancing problem (though few attempt to solve it in a robust way).
> by allowing you to dynamically select the task that is most optimal to run in the current context rather than selecting randomly
thanks for the very complete explanation, and this sentence is the crux afaic.
[edit]: what do you use to do coroutines in C++?
thanks for the very complete explanation, and this sentence is the crux afaic.
[edit]: what do you use to do coroutines in C++?
> First, context-switching in coroutines is at least a thousand times faster than with threads.
You misunderstand how context switching works. It doesn't matter how many threads you have -- 5 or 5000. Your OS will switch contexts at a constant rate.
What you perceive as 'context switch overhead' is really process scheduling being too smart for its own good.
99% of the time the problem is solved with a simple round-robin process scheduler. (Called a 'realtime' scheduler in Linux.)
> it is common to see multithreaded applications spending more CPU time on context-switching than actually running application code
No. Like I said, context switching is constant-time overhead for your OS.
You misunderstand how context switching works. It doesn't matter how many threads you have -- 5 or 5000. Your OS will switch contexts at a constant rate.
What you perceive as 'context switch overhead' is really process scheduling being too smart for its own good.
99% of the time the problem is solved with a simple round-robin process scheduler. (Called a 'realtime' scheduler in Linux.)
> it is common to see multithreaded applications spending more CPU time on context-switching than actually running application code
No. Like I said, context switching is constant-time overhead for your OS.
Certain tasks cannot be performed in parallel. For instance, if you are trying to emulate multiple CPUs, and the order of operations is important, you have to single-step each CPU an instruction (or cycle of an instruction) at a time.
Cooperative threads can (and should) be implemented in userland, allowing you to perform tens of millions of thread switches a second. Doing this with preemptive threads will be vastly slower, usually by two orders of magnitude (mostly due to no longer being userland), and there is no actual SMP benefit since we are constantly waiting on other threads.
Cooperative threads can also be used in place of preemptive threads that could execute in parallel, if you would favor completely eliminating the possibility of race conditions at the cost of only being able to utilize a single CPU core.
State machines also work in place of cooperative threads, but the managing of control flow becomes explicit (on the heap with variables and switch-cases) instead of implicit (on the stack frames.) I find state machines are increasingly error-prone and slower as the complexity of control flow increases. Still, if you only need a single switch case for control flow, state machines will be faster, as swapping out the stack pointer on modern CPUs is not kind to their speculative execution models. The drawback here is that you can serialize and unserialize a state machine context. Doing so with threads (cooperative or preemptive) is vastly more difficult.
In my opinion, symmetric coroutines are preferable to asymmetric coroutines. With asymmetric, if A calls B, and you need to get to C, you have to first return from B and then have A call C. It's less efficient. Technically, you can implement either concept using the other, but I'd rather implement the asymmetry on top of a symmetric library than the reverse for the aforementioned reason.
Cooperative threads can (and should) be implemented in userland, allowing you to perform tens of millions of thread switches a second. Doing this with preemptive threads will be vastly slower, usually by two orders of magnitude (mostly due to no longer being userland), and there is no actual SMP benefit since we are constantly waiting on other threads.
Cooperative threads can also be used in place of preemptive threads that could execute in parallel, if you would favor completely eliminating the possibility of race conditions at the cost of only being able to utilize a single CPU core.
State machines also work in place of cooperative threads, but the managing of control flow becomes explicit (on the heap with variables and switch-cases) instead of implicit (on the stack frames.) I find state machines are increasingly error-prone and slower as the complexity of control flow increases. Still, if you only need a single switch case for control flow, state machines will be faster, as swapping out the stack pointer on modern CPUs is not kind to their speculative execution models. The drawback here is that you can serialize and unserialize a state machine context. Doing so with threads (cooperative or preemptive) is vastly more difficult.
In my opinion, symmetric coroutines are preferable to asymmetric coroutines. With asymmetric, if A calls B, and you need to get to C, you have to first return from B and then have A call C. It's less efficient. Technically, you can implement either concept using the other, but I'd rather implement the asymmetry on top of a symmetric library than the reverse for the aforementioned reason.
You can easily have 1 million coroutines in-flight (my humble testing was showing that PyPy Stacklet on i4980hq has speed around 10-20 million switches/per second/per core). While with native threads I think it's in ballpark of hundred running threads, maybe single digit thousands. After that it looks like performance degrades too much.
But it all depends on an usecase, spawning a thread per user in a webserver would be slower than thread per core.
But it all depends on an usecase, spawning a thread per user in a webserver would be slower than thread per core.
Hundreds of thousands of OS threads is viable on Linux. There's a couple of gotchas - you need to tweak the max pid and max memory map limits, but otherwise this is an approach that works just fine.
This is wrong. 1 million threads is doable, though 4 million is the max Linux supports.
Coroutines are basically just user-space threads, so they scale the same way. You need to keep around a stack for each and swap it in and out of cache.
See for example: https://stackoverflow.com/questions/1900165/how-long-does-it...
Coroutines are basically just user-space threads, so they scale the same way. You need to keep around a stack for each and swap it in and out of cache.
See for example: https://stackoverflow.com/questions/1900165/how-long-does-it...
Its possible now, with current hardware and address space size. With coroutines you could to that 15 years ago on 32 bit machines.
> so they scale the same way
The difference is the within user space context switch vs kernel space/user space context switch.
> so they scale the same way
The difference is the within user space context switch vs kernel space/user space context switch.
Just microbenchmarking thread creation is different case, the issue is usually letting OS scheduler to decide what to run and when while coroutines give you explicit access. Coroutines are quite a different thing than OS-level schedulable entities.
> Coroutines are basically just user-space threads
Except you don't have preemption, so you may get e.g. latency issues.
Except you don't have preemption, so you may get e.g. latency issues.
Whereas with threads you don't get latency issues?
With threads, latency problems are spread out more evenly by design.
Ah well, experience tells us that scheduling latency under load with Linux is a difficult topic.
[deleted]
With coroutines you know when your task switches. You have clear explicit points in your program for that. That makes resources sharing and error handling way easier and predictible.
In threads, anything goes. Anywhere. That's basically goto, but worse because you can't know when the goto happens or where.
Even nurseries, which work great to scope coroutine execution, are nowhere as straightforward with threads.
In threads, anything goes. Anywhere. That's basically goto, but worse because you can't know when the goto happens or where.
Even nurseries, which work great to scope coroutine execution, are nowhere as straightforward with threads.
>With coroutines you know when your task switches.
Yes, obviously.
>That makes resources sharing and error handling way easier and predictible.
I am actually not so sure about that. With threads, you code knowing fully that your code can be pre-empted anywhere. It's uniform and simple. With co-routines, you have to think about the additional logic of when to yield, and that's very distracting. As a matter of fact, I tend to create more deadlocking code in a co-routine environment than in a threaded one, because - among other things - I'm permanently tempted to get clever.
Yes, obviously.
>That makes resources sharing and error handling way easier and predictible.
I am actually not so sure about that. With threads, you code knowing fully that your code can be pre-empted anywhere. It's uniform and simple. With co-routines, you have to think about the additional logic of when to yield, and that's very distracting. As a matter of fact, I tend to create more deadlocking code in a co-routine environment than in a threaded one, because - among other things - I'm permanently tempted to get clever.
> I am actually not so sure about that. With threads, you code knowing fully that your code can be pre-empted anywhere. It's uniform and simple.
The model of threads is fairly simple, but that does not mean that it is simple to program for. In practice developers don't do very well at reasoning about locking.
The model of threads is fairly simple, but that does not mean that it is simple to program for. In practice developers don't do very well at reasoning about locking.
For front-end UI code I'd just use threads, but if you want to do a lot of concurrent network calls on a constrained server, coroutines will use your resources a lot better. Using boost::asio you can use a yield_context to write code without callbacks and makes it a lot less complex to keep in your head (looks just like normal code!). You might be able to use something like this in threads, but I love the format for writing server code.
void doSomething( yield_context& yc ){ auto db_res1 = doDatabaseCall( "SELECT * FROM tops", yc ); auto db_res2 = doNetworkThing( yc ); ... }
void doSomething( yield_context& yc ){ auto db_res1 = doDatabaseCall( "SELECT * FROM tops", yc ); auto db_res2 = doNetworkThing( yc ); ... }
>coroutines will use your resources a lot better
Maybe, but I'm not actually sure why. Worker threads are pretty darn cheap on modern OS's.
Also - may it's just me - but I've always found co-routine based apps harder to debug: your stack is a weird tangle of unrelated things and figuring out what's going on is harder than with threads.
Maybe, but I'm not actually sure why. Worker threads are pretty darn cheap on modern OS's.
Also - may it's just me - but I've always found co-routine based apps harder to debug: your stack is a weird tangle of unrelated things and figuring out what's going on is harder than with threads.
> Maybe, but I'm not actually sure why.
Mainly because stackless coroutines do not require separate stacks for each thread of execution. The default stack size in Linux is iirc 2 MB but grows as required, of course.
Mainly because stackless coroutines do not require separate stacks for each thread of execution. The default stack size in Linux is iirc 2 MB but grows as required, of course.
That's not a good reason. That is virtual address space, not physical memory, and processes have plenty of it, usually about 280TB.
You have a very small number of values that can stay in L2 cache on a 2 MiB boundary, 12 on Skylake. The data TLB is only 4 way. Modern high performance software is about cache management, and spreading your data across swaths of page-aligned memory without strong control of when you get scheduled out underutilizes that most precious resource on the CPU.
My preference is to use an asynchronous, shared-nothing actor model. Spinning one thread per core, it is extremely efficient. But, that requires more work to track state in a smart way. I suppose it matters how similar the coroutine's logic is to each other. In some systems with low latency requirements, you want control to minimize thrashing in the cache.
One example that comes in mid is that it can provide cooperative multitasking in user space. That gives you light speed context switching over potentially thousands of threads. It can make some software architecture (like actor models) much simpler to express.
Not sure how the second sentence follows from the first here ...
As for context switching speed, you may well be right, but I was under the impression that thread context switching in Linux is really cheap these days, almost as fast as userland coroutines.
As for context switching speed, you may well be right, but I was under the impression that thread context switching in Linux is really cheap these days, almost as fast as userland coroutines.
Coroutine switching can be as fast as a dozen or so ns. Meanwhile a thread context switch will still take a microsecond at least.
You can use coroutines to implement generators (+), and as such they are a very useful software engineering instrument.
(+) This is a pattern similar to laziness and blocking semantics.
(+) This is a pattern similar to laziness and blocking semantics.
>You can use coroutines to implement generators
Yes, and threads as well, so back to my original question.
Yes, and threads as well, so back to my original question.
The main difference is the low speed of threads (100 slower context switches) and the problems of parallelism: deadlocks, races.
Thats why you use threads for CPU bound tasks, and coros for IO bound tasks. With IO you don't need much CPU, you mostly wait. Coros provide fast switching back and forth until your IO is ready.
Thats why you use threads for CPU bound tasks, and coros for IO bound tasks. With IO you don't need much CPU, you mostly wait. Coros provide fast switching back and forth until your IO is ready.
The use of generators does not imply concurrency, and that's why the use of threads for this purpose is considered overkill (threads require relatively expensive kernel involvement).
Sometimes it's easier to reason about the problem as a bunch of actors acting independently. You only have to model the individual actor and basic interactions as a apposed to a bunch of loops and switch statements trying to model everything. It really depends on the problem.
> Sometimes it's easier to reason about the problem as a bunch of actors acting independently
For me, this is typically when I'd pick thread over co-routines.
For me, this is typically when I'd pick thread over co-routines.
The fastest C co-routine library is going to be inside PuTTY [0].
[0] https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
[0] https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
[deleted]
Comparison to libmill/libdill?
Libmill is stack-unsafe
https://github.com/sustrik/libmill/issues/167
Does anyone know if this plays well with multiple threads with a separate coroutine machine on each simultaneously?
Does anybody feel like adding some define black magic to sugar coat the syntax?
This looks nice. It's always good to see formal proofs!
I suggest using setjmp/longjmp instead of copying registers manually.
How would you do that? longjmp let's you jump back to the parent coroutine but after that you cannot jump back to the child to continue where it left off.
By using different stacks for each coroutine. But it's still not trivial.
- [0] https://github.com/mozillazg/pypy/tree/master/rpython/transl...
- [1] https://github.com/boostorg/context/tree/develop/src/asm