Libaco: A fast and lightweight C asymmetric coroutine library

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

dmytroi2• 8 years ago

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.

charliesome• 8 years ago

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.

akvadrako2• 8 years ago

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

brobdingnagians• 8 years ago

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

ur-whale8• 8 years ago

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.

fla• 8 years ago

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.

ur-whale8• 8 years ago

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.

sametmax2• 8 years ago

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.

ur-whale8• 8 years ago

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.

amelius4• 8 years ago

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.

ur-whale8• 8 years ago

You can use coroutines to implement generators

Yes, and threads as well, so back to my original question.

tcbawo• 8 years ago

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.

jandrewrogers• 8 years ago

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

ur-whale8• 8 years ago

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++?

otabdeveloper2• 8 years ago

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.

byuu3• 8 years ago

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.

snarfy• 8 years ago

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.

ur-whale8• 8 years ago

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.

stevefan1999• 8 years ago

I suggest using setjmp/longjmp instead of copying registers manually.

ufo• 8 years ago

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.

cryptonector3• 8 years ago

By using different stacks for each coroutine. But it's still not trivial.

ausjke2• 8 years ago

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)

byuu3• 8 years ago

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.

skolemtotem• 8 years ago

Hi Byuu! You're a cool guy and I hope I can be like you one day!

ausjke2• 8 years ago

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?

petee• 8 years ago

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

cryptonector3• 8 years ago

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

cryptonector3• 8 years ago

The fastest C co-routine library is going to be inside PuTTY [0].

[0] https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

ComputerGuru• 8 years ago

Does anyone know if this plays well with multiple threads with a separate coroutine machine on each simultaneously?

rurban3• 8 years ago

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

rurban3• 8 years ago

Oops, FS stores the TIB, not GS

rijoja• 8 years ago

Does anybody feel like adding some define black magic to sugar coat the syntax?

Libaco: A fast and lightweight C asymmetric coroutine library

Related Stories