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".
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.
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.
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.
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 );
...
}
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.
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.
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.
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.
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.
>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.
> 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 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).
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.
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.
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).
> 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.
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.
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.
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.
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.
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.
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).
57 comments
[ 3.2 ms ] story [ 97.5 ms ] thread- [0] https://github.com/mozillazg/pypy/tree/master/rpython/transl...
- [1] https://github.com/boostorg/context/tree/develop/src/asm
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".
But it all depends on an usecase, spawning a thread per user in a webserver would be slower than thread per core.
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...
Except you don't have preemption, so you may get e.g. latency issues.
> so they scale the same way
The difference is the within user space context switch vs kernel space/user space context switch.
void doSomething( yield_context& yc ){ auto db_res1 = doDatabaseCall( "SELECT * FROM tops", yc ); auto db_res2 = doNetworkThing( yc ); ... }
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.
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.
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.
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.
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.
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.
Agreed. But my point is I am not convinced they fare any better in a coroutine environment once the codebase gets large enough.
(+) This is a pattern similar to laziness and blocking semantics.
Yes, and threads as well, so back to my original question.
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 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).
thanks for the very complete explanation, and this sentence is the crux afaic.
[edit]: what do you use to do coroutines in C++?
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.
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.
For me, this is typically when I'd pick thread over co-routines.
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)
if I have multiple cores, what's the best way to leverage that along with libco? will cpu affinity help?
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.
[0] https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
[0] https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html