5 ms·
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
by utopcell 3y ago
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].
[1] https://en.wikipedia.org/wiki/Duff%27s_device https://en.wikipedia.org/wiki/Duff%27s_device
[2] https://250bpm.com/blog:48/index.html https://250bpm.com/blog:48/index.html
- dividuum 3y agoThe 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)
- bxparks 3y agoDefinitely, "labels as values" (aka "computed gotos", https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html) is so much better than Duff's device. 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.
- mananaysiempre 3y ago(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.)
- weinzierl 3y agoSteve Wozniak's Integer BASIC (aka Apple BASIC) had computed-gotos too. Not sure about Microsoft BASIC, but Commodore BASIC had definitely lost this feature.
- benlivengood 3y agoOh come on, just rewrite it all in Go! It should only be a few billion line CR. Your SREs will thank you (eventually).
- Scubabear68 3y agoAh the C pre-processor, the gift that keeps on giving after all these years :-(
- agumonkey 3y agoI don't mind macro heavy C code, but this one made me freeze
- codemac 3y agoAs 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.
- mananaysiempre 3y ago> [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.)