Coroutines in C, revisited

Linux threads are impressively optimized for what they do. The way to beat them is to not do as much. Specifically, to not do a kernel transition. Many coroutine switch implementations are not much more expensive than function calls. For example https://news.ycombinator.com/item?id=13199581

That's a good question, and the answer has to do with, obviously, the cost of spawning OS threads/processes, context-switching among them, and how all that affects caches (cache hit/miss ratio dominates most workloads nowadays, more so than actual CPU instructions execution). Context switching can be cost on average 30micros of CPU overhead, but can reach as high as 1500micros. (You can reduce that by pinning threads to core, but the savings will likely get may be as much as 20% - maybe). Thankfully now, at least on Linux, AFAIK, a context switch doesn't result in a TLB flush - back in the day that was quite expensive. Whenever the OS scheduler needs to context switch, it needs to save old state(including regs), and restore another state and perform some other kind of book-keeping. This is more expensive and convoluted than doing it yourself -- you also usually don't need to care for all possible registers, so you can reducing switching costs by e.g not caring about SSE registers. Apps that create too many threads are constantly fighting for CPU time - you will end up wasting a lot of cpu cycles practically cycling between threads.

Another hidden cost that can severely impact server workloads is that, after your thread has been switched out, even if another process becomes runnable, it will need to wait in the kernel's run queue until a CPU core is available for it. Linux kernels are often compiled with HZ=100, which means that processes are given time slices of 10ms. If your thread has been switched out, but becomes runnable almost immediately, and there are 2 thread before your threads before it in the run queue waiting for CPU time, your thread may have to wait upto 20ms in a worse case scenario to get CPU time. Depending on the average length of the run queue (reflected in sys.load average), and how length threads typically run before getting switched out again, this can considerable affect performance.

Also, kernels don't generally do a good job at respecting CPU affinity -- even on an idle system. You can control that yourself.

If you are going to represent ‘jobs’ or tasks as threads, and you need potentially 100s or 1000s of those, it just won’t scale - the overhead is too high.

If you control context-switching on your application (in practice that’s about saving and restoring a few registers) -- cooperative multitasking -- you can have a lot more control on how that works, when its appropriate to switch etc, and the overhead is far lower.

Oh, and on average its 2.5-3x more expensive to context switch when using virtualisation.

Operating system threads have two big disadvantages. You also design the code differently, since one schedule is cooperative and the other is preemptive.

First, OS context switching is much more expensive in terms of overhead compared to lightweight contexts like fibers. A highly optimized user-controlled context-switching scheme can be barely more expensive than a function call. Context switching OS threads, even when highly optimized, is much more expensive than you might assume, microseconds compared to a few dozen clock cycles, which adds up if you need to switch contexts frequently. In many software systems, the computational cost of the OS context switch can be higher than the computational cost of the real work done during that time slice (i.e. >50% CPU overhead due to context switching) and you end up doing a lot of optimization work trying to avoid this situation, often by implementing something that looks suspiciously like user-space coroutines.

Second, and I would argue more importantly, the operating system provided thread schedule, through no fault of its own, is often pretty terrible for concurrent/distributed/parallel systems. The operating system simply lacks the runtime context to optimally determine (1) when to switch contexts and (2) the right thread to switch to. In practice, this leads to a lot more context switching, and wasteful context switching, with its high overhead than would ever occur if you designed your own schedule. The impact is not small at all, a poor schedule can seriously damage CPU cache locality.

It's not, they're two separate things. Unfortunately, nobody can agree on terminology for this stuff. I try not to ever use the word 'coroutine' anymore because of this.

libco is what I call a cooperative threading library. It allocates a stack for each thread. This means that thread A can call six functions deep into helper functions, and suspend in the middle of a helper function, and then resume right back at that same point.

Thus, you program libco very similarly to how you do preemptive threading, only you don't ever need any locks, and you have to do your own scheduling (which can be as simple as "co_call and co_return", or "co_jump" in assembly terms.)

The CORO #define wrappers in the article is what I would call a very simple state machine. There is no thread, there is no state machine, there is no user-space context switching going on. You only get the call/ret style behavior, and you can't ret from a subroutine called inside of it. It's far, far less useful.

However, when you can get away with it, CORO will be about ten times faster on average. libco is optimized as much as possible with pure assembler. On ARM, it's literally three instructions. On x86, it's ten. The entirety of the burden is because modern CPUs do not enjoy having their stack pointer changed. Go to older CPUs and the overhead drops substantially, but few people are coding on a 68000 anymore. This also means that libco is not ISO C. It requires an assembly implementation or a platform that lets you poke at jmpbuf from setjmp/longjmp to work. In practice, it'll work anywhere you'd reasonably want. x86, amd64, ppc, ppc64, arm, mips, sparc, alpha; Windows, macOS, Linux, *BSD, Haiku; etc have all been tested. And even if you find something crazy obscure, you only have to write about twenty lines of code to port it.

The magic of libco is that it's about 100 times faster than preemptive threading would be for the context switching overhead. So when you actually need subroutines, and when you don't want to be swamped in locks/semaphores/critical sections, it can eliminate giant swaths of nested state machines (switch tables) by keeping all that state inside each local stack frame, transparently and out of your codebase. Deeply nested state machines are a serious pain in the ass to reason about and maintain, trust me.

Also ... both of these methods have a serious flaw (as does preemptive threading): serialization. If you want to save the state of your program in the middle of working, and restore to that position later (think save states in an emulator) ... it'll be a bit tricky with libco. But since the state is hidden by the #define, it'll be absolutely impossible with CORO, unless you redesigned it to use external state, which would make it even clunkier to use.

In conclusion: both complement each other. I feel C++20 or whatever should add CORO-style stackless state machine wrappers to the language for convenience. But it should definitely leave stack-based cooperative threading out, because that can easily be done as a library. (It can include library functions for that purpose, but it doesn't need language-level primitives.)

There's a hundred cooperative threading libraries, by the way. My aim with libco was to make a library that has four functions (co_create, co_delete, co_active, co_switch) and zero types/structs. As simple and fast as possible, supplying as many optimized backends as possible. Then let people build on top of that. The downside is most people still choose to write their own libraries from scratch, so there's a lot of wheel reinventing going on.

I know, I know. Why is it so important that someone else did something conceptually similar once upon a time? Can't you see the value in standing on their shoulders and try to reach further in some direction? We're all in the same boat here, you can't own ideas. In this case I was aiming to simplify API and usage while keeping the performance, and I feel I managed to take at least a few steps in that direction.