I've found myself at this webpage multiple times while trying to minimize the complexity of APIs in my C projects. I think it does a lovely job explaining control flow and it has helped me to think more explicitly about storage of state on and off the stack as well as the readability consequences of different approaches.
My conclusion for now is that the choice to use C coroutines is best left to the library user. For example: Mongoose (https://github.com/cesanta/mongoose) uses event callbacks to deal with asynchronousness. It is much more pleasant to wrap a library like this in whatever thread/task primitives your system has rather than try to port the mythical cross-platform C couroutine or worse, std::thread.
Slight divergence of topic here, but is there a word for this phenomenon? Namely, when you know of a person through two very different channels and find out they are the same person. It happens to me frequently enough that I feel like it deserves at least a neologism of some sort, but I don't have anything catchy.
(I find it especially happens with bands; I had listened to both Failure and Autolux for years before finding out they shared a guitarist, for instance.)
Oh wow... I have had the Android port of his puzzles (your second reference links to it) on my phone for a while. Had no idea the developer of Putty had anything to do with it!
Coroutines. What a lovely concept! It's a joy to watch all the CppCon videos about C++ coroutines, primarily by Microsoft folks. "Negative-cost abstraction" is such a nice hook phrase.
Friends at Meta mentioned to me a couple years ago that they started using c++ coroutines, which ended up being a big mistake because they had to face compiler implementation bugs, which must have been nasty to track down. At Google, we are eagerly waiting for the brilliant folks that are working on properly integrating them in google3/ to tell us when the time has come to use them.
This article uses Duff's device [1] to motivate structured gotos via macros as an implementation strategy for C coroutines. Duff wanted to loop-unroll this:
do {
*to = *from++;
} while (--count > 0);
which he did in this way (shortened for brevity) :
int n = (count + 3) / 4;
switch (count % 4) {
case 0: do { *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while (--n > 0);
}
That is to say, he realized that he could use `case` statements (almost) anywhere in a `switch` block. The connection with coroutines is simple: One can wrap the whole function body with a switch statement, use a static variable for holding the location of the latest coroutine return, and label all co-returns with a `case` statement:
#define coBegin static int state = 0; switch (state) { case 0:
#define coReturn(x) do { state = __LINE_; return x; case __LINE:; } while (0)
#define coFinish }
int function(void) {
static int i; // function state can't be local anymore.
coBegin;
for (i = 0; i < 10; ++i)
coReturn(i);
coFinish;
}
Sustrik's take on C coroutines might also be an interesting read [2].
As someone who moved from google3 -> fbcode in the last few years, I think there are weird upsides AND downsides to having async code littered through your C++ (aka co_yield, co_return, co_await, etc).
The advantage, compared to the internal stuff google3 was using, was that as you read code, the async nature of various parts was obvious. Some programmers at G would spend entire quarters+ not knowing what the threading model was, and cause serious bugs in retrospect.
The disadvantage is actually much dumber - a lot of code "could" be async, and over time becomes entirely async because that's the mode the programmer is in when writing the program.
The choice to use a spinlock vs. a mutex w/yields should be one based on the size of the critical section and the threading going on at the time. Unfortunately to make code more readable/uniform/etc you end up with entire projects doing one or the other.
I'd love to learn more about language implementations of threading that do not default either way, but instead could take a profile of the previous run, and make the next run more optimal, without having to change the code or causing bugs.
The alternative is to use the „labels as values“ feature of GCC. You can take the address of a label and later jump to it. I contributed the code that’s now in lc-addrlabels.h back in 2005 :-)
I also used the GCC local labels feature to completely avoid using __LINE__ anywhere, so you could have multiple coReturns in a single code line:
#define LC_SET(s)
do { ({ __label__ resume; resume: (s) = &&resume; }); }while(0)
Unfortunately, computed-gotos is not a C language standard. I don't understand why. I think FORTRAN had it in the 60s. It is so useful in some situations, like a coroutine, or a byte-code interpreter. Is it because some obscure DSP chip with a sizeof(char)==32 using 1's complement arithmetic can't support it? Then maybe make it implementation-defined and allow the rest of the world get nice things.
(For ease of reference—Fortran calls this an assigned GOTO: jump to label stored in a variable—as an integer number, as is Fortran’s way, not an address. A computed GOTO in Fortran is more like a switch statement in C: jump to the first label listed in the statement if the specified variable is one, to the second if it is two, ..., fall through to the next statement otherwise.)
Steve Wozniak's Integer BASIC (aka Apple BASIC) had computed-gotos too. Not sure about Microsoft BASIC, but Commodore BASIC had definitely lost this feature.
> [Duff] realized that he could use `case` statements (almost) anywhere in a `switch` block.
That’s likely true, in that it probably was a moment for realization for Duff (and many others reading him, including me); yet it’s almost certainly a completely intentional feature.
(As mentioned at the bottom of TFA, Duff also realized you could build coroutines on top of it but thought the idea “revolting”.)
There’s a temptation to think of C’s `switch` as a very inexpressive pattern match, and then the “fallthrough” seems like a bug and so on. It’s not. It’s a computed GOTO, in the vein of the one in Fortran but more convenient in that the values don’t have to be sequential, and also in that you don’t have to list all the labels at the top. (In fact, now that I’m writing this out, it’s more of a computed COMEFROM, then, isn’t it? However insane that sounds.)
Python was created in 1991; I imagine the "yield" keyword appeared either right then or not much later!
Also, the refinement at the end of the article: "We arrange an extra function parameter, which is a pointer to a context structure; we declare all our local state, and our coroutine state variable, as elements of that structure." sounds like implementing a closure to me. You make the callee a lambda which would use an outside var/context/state to determine what to do or with what value. Am I understanding this correctly?
as lmm pointed out, python didn't have generators and yield until 2.2. icon, which tim peters adapted the idea from, had them quite a bit earlier than that, but i think it's reasonable to describe icon as not being a commonly used language, then or now
(python's generators are closer syntactically to icon's generators than they are semantically)
The "switch" method isn't too uncommon, but usually people have an init function and "state" pointer that's passed into the coroutine function. I've used this method a lot in embedded projects, where one coroutine was handling motor acceleration/deceleration while the other would simply tell it what direction to go, but I've also used it for networked libraries[1]. Even the standard library has a coroutine function like this in "strtok()"[2]
You don't really need to introduce macro hell for it to be manageable, though I've never found reading switch/case flow to be very enjoyable.
Note that the underscore prefix thing often is still prone to shadowing. You need pretty ugly mangled names to avoid that, and for external-block macros (unlike expression-ish/statement-ish macros) it can't be avoided with GNU's/C23's hygienic macro hack.
Wait, was there any recent change to C23 that enabled a different solution than `__COUNTER__`? I realized you have mentioned but didn't fully define `CLEANSE_MACRO_VARS` in recent comments, is there any other pointer?
Yes, implementing `CLEANSE_MACRO_VARS` was left as an exercise for the reader. The real key improvement here is that C23 standardized C++-style `auto` (or GNU C `__auto_type`), though its improved support for variadic macros also helps a few corners.
The key observation is that, for expression-like (only with GNU statement expressions) or statement-like (using do-while, possibly emulating expression-like macros by specifying an output variable) macros, shadowing is perfectly okay as long as it doesn't happen before the evaluation of the macro argument expressions.
So what you do is define all the variables twice - first, with long and ugly names (which name is only generated/used deep inside the cleansing macro), to capture the expression, and then (after all the ugly definitions are done, not just some), as a simple copy of that with a nice name for use in the user's macro. So the resultant macro works like:
#define MAX(a_, b_) // omitting backslashes
({
auto _ugly_a = (a_);
auto _ugly_b = (b_);
// it's safe if the above arguments expand to contain unrelated `a` and `b`.
auto a = _ugly_a;
auto b = _ugly_b;
// in a statement expression, the last statement is the resulting value
a > b ? a : b;
})
There's no need to `__LINE__` for this particular problem, since all you need is a sufficiently long unique prefix to namespace it (which all C libraries assume anyway).
=====
Note also that the old `__typeof__` is not useless just because `__auto_type` exists. Besides things like `_Generic` and function definitions where there's no initializer allowed, it's also useful for safely forming pointers to a passed-in type which might be (a pointer to) an array or function, since, like `sizeof`, types are also valid for its argument. This is in fact in the documentation if anybody reads that.
Ah, I see. I thought the cleaning involved something like gensym, but you just meant that a new scope can introduce a variable of the same name without interfering with the original. You don't really forbid something like `MAX(&_ugly_a, &_ugly_b)` for example, that was why I was confused.
I wouldn't recommend doing any of this stuff at all, personally. It's just always amazed me though how much you can do with with just basic string substitution and no homoiconicity/no AST access.
Coroutines are fun, but in real code please consider using actual threads. Modern processors have many cores, but coroutines will (often) only use a single core.
Edit to add: This is a real world problem too. Until recently qemu, which extensively uses coroutines, would put a lot of its block device I/O through a single thread. This caused some performance issues. Kevin Wolf and others have spent years of effort fixing this so modern qemu will use many threads for I/O (this work will appear in RHEL 9.4).
The only connection between threads and coroutines is that some single-threaded language runtimes only have coroutines, so you might occasionally use them where threads would be a better choice.
Coroutines are a way of structuring single-threaded execution, and a useful one. The example in the Fine Article of a producer-consumer pattern is a good one, attaching a stream to a parser isn't a parallel algorithm so threads are useless for writing it.
Naturally, using a single-threaded paradigm for work which could be performed in parallel is inefficient, but coroutines aren't a poor man's parallelism, they're a control structure which functions on its own terms. They can be combined productively with threads, such as using an event loop in a web server to thread (as in needle) coroutines through various blocking events with a dispatcher, and the runtime can spin up a thread per core to parallelize this, which reduces per-thread coordination to checking the depth of each thread's work queue and farming the request to the least congested one.
Bob Nystrom makes this argument best, I think, in his two-parter on loops and iteration[1,2]. Looping over data structures is of course only one example of how one can apply coroutines, but a very established one. The canonical problem requiring coroutines[3] is also essentially about doing that.
Or for those who want something different there’s the elevator (and elevator-userbase) simulation from TAoCP volume 1, also an essentially concurrent problem with little to no parallelism or I/O to it.
It could be, but given the sometimes astonishing costs of the—effectively—network protocol we know as cache coherency (thousands of cycles if you’re not careful), it’d be a giant waste in many of the cases where stackless coroutines would be perfectly appropriate.
That's generally the desired behavior. If you have decoupled, parallel workloads they're going to naturally be working on disjoint data. The idea behind coroutines is that you have some kind of local workload with synchronous data that, for whatever reason, is easiest to express "inside out" with a function that gets to loop over something and "push" the results to its abstracted consumer whose code lives somewhere else, vs. the natural functional paradigm where the inner loop is a conceptual "pull" controlled by the caller.
There's often a sweet spot to be had in mixing threads and coroutines, where you have a coroutine scheduler instance per thread, and a thread created per core.
Then rarely, if ever, migrate coroutines across schedulers, and rarely, if ever, share data between coroutines on different schedulers.
Coroutines can enable an ergonomic concurrent programming style while avoiding the need for any locking at all via cooperative scheduling. You generally end up with higher scheduling latencies, but potentially quite high throughput by removing any need for atomics/locking overheads, and no timer constantly interrupting execution for preemptive scheduling.
"Consider using threads" is only safe advice if the person doing the considering knows how to dealt with the (usually unwanted) non-determinism threads introduce.
Only a small fraction do, but threads look so simple on the surface the rest don't realise they are walking into a mine field.
Real world and toy examples are very different. The example isn't like what people are using coroutines for in the real world. I'd urge you to look at how coroutines are used for inversion of control (quite correctly) in qemu.
> Coroutines are fun, but in real code please consider using actual threads.
Coroutines are lightweight and trivial to synchronize. They are perfect for small bits of incremental computation, like iterators and tokenizers. Maybe you're thinking of green threads?
I agree for typical async IO code which needs to wait for external events (like an IO operation to finish), but sometimes in other situations threads are not an option because there would be too much synchronization required.
For instance in my emulators, the CPU emulation is a switch-case state machine which is very similar to the coroutine approach described in the article, trying to move this idea to threading would require a synchronization between multiple threads on each emulator clock cycle which is somewhere between a few dozen and a few hundred host CPU clock cycles. That's not realistic, at least for emulating typical 8- and 16-bit home computers. For emulating 'modern systems' where the hardware components are not as tightly coupled as in old-school 8- and 16-bit machines, threading makes more sense though.
Coroutines are fun, but in real code please consider using actual threads. Modern processors have many cores, but coroutines will (often) only use a single core.
Threads and coroutines have different purposes. Coroutines are more about logical structure.
That seems like an orthogonal concern to structuring control flow, though it is much more difficult if you intend to use coroutines across multiple threads. There's nothing stopping you from using both threading and coroutines.
Coroutines are good for modelling concurrency which is different from parallelism. Concurrency is useful for abstraction and expressiveness. Parallelism is useful for making your code run faster by running parts of it in parallel on multiple cores. You could make concurrent programs run faster on multiple cores by distributing the coroutines which don't share state on multiple working threads in a thread pool, thus mixing concurrency and parallelism...but they are still two different things with different purposes.
Not just that, but the scaling problems with threads are usually massively overstated. It's true that thread switching has quite a bit more overhead, but it's been optimized a lot since the bad old days of 15+ years ago. (Plus, unless you're using a massive number of threads it's very unlikely that thread switching is going to be your bottleneck.)
It runs in millions of cars and other embedded systems, not that niche tbh. Your "exception" is the rule for a lot of engineers.
But yes, they took pride that process switching is as efficient as thread switching which is a slick way of selling that they never optimized threads to be better, unlike Linux. Until QNX8 there is also the "big kernel lock"...
> It runs in millions of cars and other embedded systems, not that niche tbh.
Linux (in some mutilated form) runs on billions of devices. Hell, even JavaME does; or at least did, not sure what current status is. That's not really a worthwhile comparison.
My 'niche' mention was in relation to number of devs who'd be familiar with it.
> Your "exception" is the rule for a lot of engineers.
Now, that's a fair comparison... but I wager "a lot" is still not nearly the number of engineers/devs that work with e.g. Linux. That's not to cast any aspersions, of course. After all it's often not really a choice of the engineer's part.
Threads with implicitly shared memory are more or less impossible to use safely, particularly in a language like C. Coroutines for concurrency, and multiprocessing with explicitly shared memory for parallelism, is a better approach.
A modular and safe way to achieve this is probably effect handlers. It's like python's yield but can return a value and is scoped like an exception, it's not local to a function call. If you're unfamiliar with it, this article is a good motivation.
Each function, written in direct style, can perform an "effect" when the function wants control to go somewhere else (for c=getchar() and emit(c) here).
Control then goes to the effect handler, in this case probably the caller of the two functions, which decides what to do next: decompressor emits a char? Let's resume the parser's code with the char until it asks for more, then resume decompressor again, etc.
Effects can be efficiently implemented, especially if the continuation is only allowed to be called once (which is the case in OCaml), and allow writing code in direct style, together with type/memory safety. They are also very helpful in a concurrent setting.
> Of course, this trick violates every coding standard in the book. […] I would claim that the coding standards are at fault here.
Thoroughly disagree here. The coding standards for not at fault for rejecting this code, but rather the code is merely a cute trick. Software engineering in the large is all about removing surprises and making code readable even to the sleep-deprived on caller waking up at 3am to debug this. You can't rely on programmers remembering the ground rules all the time (and there are four of them!)
> Coding standards aim for clarity. By hiding vital things like switch, return and case statements inside "obfuscating" macros, the coding standards would claim you have obscured the syntactic structure of the program, and violated the requirement for clarity. But you have done so in the cause of revealing the algorithmic structure of the program, which is far more likely to be what the reader wants to know!
It takes skill to write programs that see clear in both their syntactic structure and their algorithmic structure. This isn't it. (I am a fan of Rust creating implicit state machines from async functions and I think that should be the model here.)
Endlessly "dumbing down" lowest-common-denominator crap is what's responsible for the quality, or lack thereof, of most software today. Shunning knowledge and education will come back to bite you.
Seconded. Not everything is about the sleep deprived on call guy, not everything is about reducing surprises, not everything is about operations.
I had thought before that this "what about the guy at 3am arguments" push in the direction of mediocrity - happy to see I'm not the only one have these thoughts.
Feel free to write your artisanal code in your personal projects. But they don't belong in most companies' code base. You are a cog in the machine at these companies. Your role is to produce code that's easily understood by the next programmer. That's why coding guidelines exist.
that's why all those companies are using putty instead of their own ssh client; they're organizationally incapable of writing software of putty's quality
A lot of these companies don’t ship software at all, they write it only for internal use. It needs to be easily fixable by junior interns, not dependent on Bob the 100X programmer who decided to retire last week.
yeah, and of course you normally want as much as possible of your software to be easily fixable by junior interns in any case; that's always better when there's no compensating drawback
the implicit premise of your comment, however, seems to be that no such compensating drawback is possible, presumably because internal-use-only software isn't a competitive advantage. there are a lot of companies that think that way, but i think it's shortsighted; see https://news.ycombinator.com/item?id=39402299 for some examples of companies that discovered that it mattered a lot how good their internal-use-only software was
Having gone from C to C++, there's a stark difference between the communities in what is considered 'readable' i.e. what the future reader is expected to grok.
In C-world, ternary-ifs are too spicy and C99 is newfangled. In C++ world, the only reason you'd be pushed away from template metaprogramming is because the standard you're using lets you do it with constexpr.
Some longjmp implementations unwind the stack, so they can't be used for coroutine switching. Even if it works (it's technically undefined), you need to get a suitable stack from somewhere.
The next issue is that usually, applications want to resume coroutines on a thread different from the one it on which it was suspended. That runs into trouble because on some systems, compilers cache the address of thread-local variables in the local stack frame, assuming that the thread does not switch in a function mid-execution.
It makes longjmp useless for coroutine switching, although it does not result in other effects of stack unwinding (such as invoking C++ destructors).
On Windows, longjmp really unwinds the stack (and maybe this is something influenced by VMS): https://learn.microsoft.com/en-us/cpp/c-runtime-library/refe... “In Microsoft C++ code on Windows, longjmp uses the same stack-unwinding semantics as exception-handling code. It's safe to use in the same places that C++ exceptions can be raised.”
Well, things have changed since I looked last. Thanks for explaining.
FWIW, back in the nineties we just wrote our own setjmp/longjmp for VMS to avoid stack unwind - save registers / restore registers. We used it to implement coroutines in Modula 2, iirc.
No. The C standard says this about longjmp: "if the function containing the invocation of the setjmp macro has terminated execution in the interim [...] the behavior is undefined". So while you can longjmp out of functions, you can't longjmp back into them.
You can absolutely build coroutines out of a generalized context switch. So yes, in some sense. But note that the linked article doesn't use setjmp/longjmp, which is what makes it so clever.
FWIW: would I personally actually use this trick? Almost certainly not. C APIs aren't well suited to that level of abstraction IMHO, if you have an app that needs it leave the C stuff to the stuff C is good at and wrap a C++ or Rust or whatever layer on top for the subtleties.
In theory (but only possible in assembly right now), there could be coroutines that shared the stack of their caller. As long as the caller (who's calling from a normal function) finishes calling the coroutine and doesn't expect to be able to call it after they return, then you could use it to implement iterators, e.g. over a binary tree or a hash table, like generators in Python. It could work as long as the caller used the stack frame base pointer to refer to their saved local variables, since the stack pointer could be changed between yields to the coroutine. I'm genuinely surprised there hasn't been a compiled programming language to do that other than Sather and CLU[0] (both of which are long dead by now). Graydon Hoare originally wanted them in Rust [1], but LLVM didn't support it, so it was scrapped.
Ah, this page again! it's been more than two decades? since I saw this page last? It was fun to learn about coroutines from the author of PuttY the ssh client of choice on Windows those days.
I’ve used libaco in the past for coroutines in C. I found zlib a pain to use when using curl scheduled with libuv to fetch data. zlib expects a read loop to extract data, but libuv provides an evented push model. Saving all of the zlib state and building a state machine seemed tedious, but a coroutine made the zlib code look like the standard, blocking loop.
This was just code for my own amusement, and maybe used by a few people, for non-production work. I’d do it again, however, if I needed to.
The article says: "In many modern operating systems, you could do this using pipes between two processes or two threads. emit() in the decompressor writes to a pipe, and getchar() in the parser reads from the other end of the same pipe. Simple and robust, but also heavyweight and not portable. Typically you don't want to have to divide your program into threads for a task this simple."
I assume I'm missing that this a joke, it's honestly hard for me to tell.
But in the conclusion, the author talks about actually making this work by providing a context object to hold all of the intermediate state and providing this context object to the callee.
Once this is required, how does this approach compare to simply using an external iterator?
Seems to me like an iterator solves the lion's share of the problem here. It moves the state into the caller's stack (or above them), it's easy to understand, simple to implement and doesn't involve unenclosed and context-dependent macros.
C (particularly back when this was written) was a low level language. You could not simply use an external iterator - they didn't exist. And if you try to roll your own, you'll wind up dealing with a lot of complications around resource management in a language which lacks basic memory management.
But the proof is in the pudding. Back then it was common to want to telnet into a Unix machine from Windows. And the only two solutions that worked well enough to consider were installing Cygwin, or installing PuTTY. Cygwin was better if you needed a Unix environment on your Windows machine. Otherwise PuTTY was your answer. As the article comments, PuTTY was written with this technique.
When you've solved a problem that a lot of people had, and your solution is widely acknowledged as the best one out there, people get interested in how you think it should be solved. Which is why this article interested me when I first saw in many years ago on Slashdot.
> Seems to me like an iterator solves the lion's share of the problem here.
Iterator APIs are indeed aimed at the same kind of problem, but they're not the same solution. And often they're harder to write. If you have a component with a big list of stuff, it's generally easier to write and understand the idea of "iterate over my big list of stuff and emit one item at a time to my consumer" than it is "what state do I need to remember such that when I get called again I can emit the correct next item given the one I just emitted?".
Coroutines are a way of expressing the former. Iterators are the latter. If all you do is write the outer loop, iterators are absolutely just as good. If you need to write the iterator itself, it's more of a discussion.
My conclusion for now is that the choice to use C coroutines is best left to the library user. For example: Mongoose (https://github.com/cesanta/mongoose) uses event callbacks to deal with asynchronousness. It is much more pleasant to wrap a library like this in whatever thread/task primitives your system has rather than try to port the mythical cross-platform C couroutine or worse, std::thread.