Libaco: A fast and lightweight C asymmetric coroutine library

And to http://libdill.org as well

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.

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

to be fair you should point out that libco is written in c++, where as OP is actually written in c

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).

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.

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.

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.

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 ); ... }

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.

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.

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.

Libmill is stack-unsafe https://github.com/sustrik/libmill/issues/167

You have to look if the thread context register GS is stored and restored in the assembler part.

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.