7 ms·
Coroutines in C (2000)
- pieterr 3y agoFrom the same author: Simon Tatham's Portable Puzzle Collection https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
- anymouse123456 3y agoI 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.
- syncurrent 3y agoProto-Activities have this context to store the state in the caller. https://github.com/frameworklabs/proto_activities https://github.com/frameworklabs/proto_activities
- ajross 3y ago> 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.
- btilly 3y agoWhy would you assume that this is a joke? 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. So absolutely not a joke.
- rwmj 3y agoCoroutines 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).
- c-smile 3y ago> please consider using actual threads. Bad advice in general. Why would you run separate thread if you only want is to iterate over nodes in a tree (as an example of non flat collection).
- rwmj 3y agoReal 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.
- cylon13 3y agoIt’s never bad advice to consider something.
- klyrs 3y agoTo the contrary, consideration takes time, and rules of thumb are valuable to mitigate overthinking.
- a1369209993 3y agoNo, it's frequently bad advice to consider something. See eg https://www.xkcd.com/1445/ https://www.xkcd.com/1445/.
- rstuart4133 3y ago"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.
- omoikane 3y ago> no commonly used high level language supports the coroutine This might have been the case back in 2000, but these days many languages do support it, including C++20, Lua, Python, Ruby, etc.
- perbu 3y agofwiw, Simula67 had coroutines. Not the first to do so, but IIRC it was the first major language to do so.
- esfandia 3y agoPython 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?
- lmm 3y ago> Python was created in 1991; I imagine the "yield" keyword appeared either right then or not much later! Nope. It was introduced 10 years later, as part of PEP 255, released in Python 2.2.
- kragen 3y agoyour note about closures is correct, yes 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)
- deleted 3y ago[deleted]
- paulddraper 3y ago(2000)
- DriftRegion 3y agoI'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 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.
- chongli 3y agoIt’s Simon Tatham’s website. He’s well known for being the author of PuTTY [1] and his puzzle collection [2]! [1] https://www.chiark.greenend.org.uk/~sgtatham/putty/ https://www.chiark.greenend.org.uk/~sgtatham/putty/ [2] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
- hnfong 3y agoI've known about the two projects for literally 20+ years, but wow I never knew it was the same person behind them....
- smrq 3y agoSlight 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.)
- abhgh 3y agoOh 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!
- DenisM 3y agoSetjmp/longjump are the built-in coroutines in C, no?
- dkjaudyeqooe 3y agoThese are stackless coroutines, if you use longjump you have to create a stack for the coroutine. There are pros and cons for each style.
- trealira 3y agoIn 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. [0]: https://dl.acm.org/doi/pdf/10.1145/800127.804079 https://dl.acm.org/doi/pdf/10.1145/800127.804079 (the third PDF page, page 125) [1]: https://graydon2.dreamwidth.org/307291.html https://graydon2.dreamwidth.org/307291.html (search "non-escaping coroutine")
- ajross 3y agoYou 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.
- fweimer 3y agoSome 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.
- gkbrk 3y agoI've used this for some embedded/IoT projects before. They work really well.
- c-smile 3y agoC++ version of the approach: https://www.codeproject.com/Tips/29524/Generators-in-C https://www.codeproject.com/Tips/29524/Generators-in-C I am using this in my Sciter, just in case. Works quite well and convenient.
- vinay_ys 3y agoAh, 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.
- utopcell 3y agoCoroutines. 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)
- 3y ago
- deleted 3y ago[deleted]
- dang 3y agoRelated: Coroutines in C (2000) - https://news.ycombinator.com/item?id=37357673 https://news.ycombinator.com/item?id=37357673 - Sept 2023 (1 comment) Coroutines in C (2000) - https://news.ycombinator.com/item?id=36639879 https://news.ycombinator.com/item?id=36639879 - July 2023 (2 comments) Coroutines in C - https://news.ycombinator.com/item?id=23293835 https://news.ycombinator.com/item?id=23293835 - May 2020 (1 comment) Coroutines in C (2000) - https://news.ycombinator.com/item?id=19106796 https://news.ycombinator.com/item?id=19106796 - Feb 2019 (59 comments) Coroutines in C, revisited - https://news.ycombinator.com/item?id=13199245 https://news.ycombinator.com/item?id=13199245 - Dec 2016 (36 comments) Coroutines in C - https://news.ycombinator.com/item?id=13138673 https://news.ycombinator.com/item?id=13138673 - Dec 2016 (1 comment) Coroutines in C (2000) - https://news.ycombinator.com/item?id=11051004 https://news.ycombinator.com/item?id=11051004 - Feb 2016 (11 comments) Show HN: Libconcurrent – Coroutines in C - https://news.ycombinator.com/item?id=10887071 https://news.ycombinator.com/item?id=10887071 - Jan 2016 (24 comments) Coroutines in C with Arbitrary Arguments - https://news.ycombinator.com/item?id=9402314 https://news.ycombinator.com/item?id=9402314 - April 2015 (22 comments) Coroutines in C (2000) - https://news.ycombinator.com/item?id=8615501 https://news.ycombinator.com/item?id=8615501 - Nov 2014 (27 comments) Coroutines in C (2000) - https://news.ycombinator.com/item?id=6244994 https://news.ycombinator.com/item?id=6244994 - Aug 2013 (1 comment) Coroutines in one page of C - https://news.ycombinator.com/item?id=6243946 https://news.ycombinator.com/item?id=6243946 - Aug 2013 (60 comments) Coroutines in C (Simon Tatham, 2000) - https://news.ycombinator.com/item?id=1380044 https://news.ycombinator.com/item?id=1380044 - May 2010 (16 comments) Coroutines in C - https://news.ycombinator.com/item?id=835849 https://news.ycombinator.com/item?id=835849 - Sept 2009 (16 comments) Co-routines in C - https://news.ycombinator.com/item?id=794157 https://news.ycombinator.com/item?id=794157 - Aug 2009 (1 comment)
- anfilt 3y agoBunki, a C Coroutine library https://news.ycombinator.com/item?id=35133095 https://news.ycombinator.com/item?id=35133095
- mtlmtlmtlmtl 3y agoIf you think this is some C black magic, try reading this by the same author on creating arbitrary control structures with macros: https://www.chiark.greenend.org.uk/~sgtatham/mp/ https://www.chiark.greenend.org.uk/~sgtatham/mp/
- o11c 3y agoNote 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.
- mtlmtlmtlmtl 3y agoI 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.
- lifthrasiir 3y agoWait, 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?
- o11c 3y agoYes, 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.
- mid-kid 3y agoThe "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. [1]: https://github.com/REONTeam/libmobile/blob/master/relay.c#L346 https://github.com/REONTeam/libmobile/blob/master/relay.c#L3... [2]: https://manpages.debian.org/bookworm/manpages-dev/strtok.3.en.html https://manpages.debian.org/bookworm/manpages-dev/strtok.3.e...
- rurban 3y agoAlso related, the C++ lambda fuckup: https://news.ycombinator.com/item?id=33084431 https://news.ycombinator.com/item?id=33084431
- whiterknight 3y agoUNIX pipes solve this problem. Both reader and writer are driving their respective process.
- esfandia 3y agoThe 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."
- whiterknight 3y agoThanks. I have read this article a few times and somehow missed that was acknowledged. “Heavyweight” is where I disagree. It’s exactly whats needed to be able to write sequential code on each side.
- anfilt 3y agoI honestly like stackful coroutines if you don’t mind allocating memory for a stack. https://github.com/Keith-Cancel/Bunki https://github.com/Keith-Cancel/Bunki
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- kccqzy 3y ago> 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.)
- userbinator 3y agoEndlessly "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.
- bdjsiqoocwk 3y agoSeconded. 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.
- furyofantares 3y ago> quality, or lack thereof, of most software today. Also the incredible quantity software today, and how dang cheap it is.
- kccqzy 3y ago
- jonhohle 3y agoI’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.
- crabmusket 3y agoI was so sure this was about protothreads til I remembered its name. https://dunkels.com/adam/pt/ https://dunkels.com/adam/pt/
- jijji 3y agohow does this compare to using Go goroutines?
- Levitating 3y agoThere is an RFC[1] for coroutines in rust: https://doc.rust-lang.org/beta/unstable-book/language-features/coroutines.html https://doc.rust-lang.org/beta/unstable-book/language-featur... [1]: https://github.com/rust-lang/rfcs/pull/2033 https://github.com/rust-lang/rfcs/pull/2033
- xjm 3y agoA 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. An example here : https://effekt-lang.org/docs/casestudies/lexer https://effekt-lang.org/docs/casestudies/lexer