Coroutines in C (2000) | Hacker News Reader

Coroutines in C (2000)

chiark.greenend.org.uk

181 pointswooby59 comments

A really good library that we use is libco[0], it supports different architectures and mechanisms. We use it extensively on Fluent Bit[1] to manage async IO network operations (epoll + coroutines).

- [0] https://byuu.org/library/libco/

- [1] https://fluentbit.io

Do you use https://github.com/Tencent/libco or https://byuu.org/library/libco/ ?

https://byuu.org/library/libco/

A cool library that implements C coroutines, available for both idiomatic C (http://libdill.org/) and in the same style as Go (http://libmill.org/) with line by line translations

For those wondering how it works, libdill keeps track of context between function calls and does some clever stack modification in assembly.

I wonder if it would work from Rust. I was looking at something minimal like this.

I haven't used it at all, but doesn't Rust have experimental support for coroutines?

https://github.com/rust-lang/rust/issues/43122

libdill and co implement stackful coroutines. Each coroutine has a native call stack which gets swapped out by a userspace scheduler. Rusts proposed coroutines and async functions are stackless. They are implemented as pure Compiler Transformations, and don’t allow to yield at arbitrary points.

Rust actually had stackless coroutines in the past (libgreen), but moved from it due to the overhead it brought for code that didn’t require it.

I ran with this idea last year and wrote a proof of concept library that wraps libev using using this concept to allow you to write async C code inline. It's about 250 lines of macro abuse and the resulting code looks pretty funky but it ultimately works. I have a simple echo server example here: https://github.com/jeremycw/zasync/blob/master/echo_server.c

As an OOP dev this kind of horrifies me, even though it works okay (though it's surely not thread-safe?)

Nevertheless, even in C, I'd find it conceptually simpler to understand if the functions were written as pure functions, returning a tuple with (c, state) and passing the state back into the caller. Using non-idiomatic tricks and macros in this way is harder to read and understand.

Here's a POSIX compliant portable getopt() routine I wrote which uses this style. Is this hard to read? Note that it's several times shorter than every other implementation I've ever seen, and if I do say so myself I think it's eminently readable.

  static int
  u_getopt_r(int argc, char *const argv[], const char *shortopts, struct u_getopt_r *K)
  {
    K->optarg = NULL;
    K->optopt = 0;
  
    GETOPT_ENTER;
  
    while (K->optind < argc) {
      K->cp = argv[K->optind];
  
      if (!K->cp || *(K->cp) != '-' || !strcmp(K->cp, "-")) {
        break;
      } else if (!strcmp(K->cp, "--")) {
        K->optind++;
        break;
      }
  
      for (;;) {
        char *shortopt;
  
        if (!(K->optopt = *++K->cp)) {
          K->optind++;
          break;
        } else if (!(shortopt = strchr(shortopts, K->optopt))) {
          getopt_err(argc, argv, shortopts, K, "illegal option -- %c\n", K->optopt);
          GETOPT_YIELD('?');
        } else if (shortopt[1] != ':') {
          GETOPT_YIELD(K->optopt);
        } else if (K->cp[1]) {
          K->optarg = &K->cp[1];
          K->optind++;
          GETOPT_YIELD(K->optopt);
          break;
        } else if (K->optind + 1 < argc) {
          K->optarg = argv[K->optind + 1];
          K->optind += 2;
          GETOPT_YIELD(K->optopt);
          break;
        } else {
          getopt_err(argc, argv, shortopts, K, "option requires an argument -- %c\n", K->optopt);
          K->optind++;
          GETOPT_YIELD((*shortopts == ':')? ':' : '?');
          break;
        }
      }
    }
  
    GETOPT_LEAVE;
  
    return -1;
  }

Here's macro magic, the complexity of which is more than made up for by the readability of the core code:

  #define GETOPT_ENTER \
    do { \
    static const int pc0 = __LINE__; \
    switch (pc0 + K->pc) { \
    case __LINE__: (void)0
  
  #define GETOPT_SAVE_AND_DO(do_statement) \
    do { \
      K->pc = __LINE__ - pc0; \
      do_statement; \
      case __LINE__: (void)0; \
    } while (0)
  
  #define GETOPT_YIELD(rv) \
    GETOPT_SAVE_AND_DO(return (rv))
  
  #define GETOPT_LEAVE \
    GETOPT_SAVE_AND_DO(break); \
    } \
    } while (0)

And here is my C++ version of Simon's idea, C++ generators in 10 lines header file:

https://www.codeproject.com/Tips/29524/Generators-in-C

We tried to implement coroutines based on the CoroutineTS here: https://github.com/LoopPerfect/conduit

CoroutineTS uses coroutines that are implemented on the LLVM-IR level, as a result they get optimized away in many cases.

Unfortunately the CoroutineTS has also some design flaws around allocations and ownership

I thought this was going to be an article about setjmp() and longjmp(), which can be used to implement this kind of mechanism.

Has anyone used these to write interrupt service routines? Seems like there's an opportunity here. You can take your existing synchronous code and not have to rewrite it into something like continuation-passing style. This is a source of a lot of bugs.

I have, it's not pretty either: https://github.com/nraynaud/webgcode/blob/gh-pages/interpola...

i have done cps plumbing in C with poor mans closures for the entire interrupt path, and given its natural event-like nature, it really all comes out pretty nice.

If its possible would love to learn from it. Any chance of taking a look at it ?

the actual work was done under contract as in proprietary, but the closure library is the interesting part, is owned by me, and something i can send you.

accountname @gmail.com

if you're interested we can go over the interrupt path, its pretty straightforward at that point. by flipping the control flow around, the virtio virtqueue support for example becomes nice and self-contained. it provides an interrupt continuation to the interrupt layer, and each queue is initialized with a continuation to call on a dequeue. vector assignment is still a bit cross-cutting.

Thanks that is extremely generous of you.

I would still encourage that you put it up somewhere with a license of your choice. Many would get an opportunity to learn a thing or two.

Isn't this just an application of a protothread[1]?

There are implementations that use the GCC goto and label pointer, which then avoid the need for a switch statement.

[1] http://dunkels.com/adam/pt/

Answered here https://news.ycombinator.com/item?id=19109008 by VygmraMGVl

In lining the answer.

> Protothreads is a library implementation of this trick. In fact, the protothreads creator even references the linked site in their explanation of protothreads (very last paragraph)

Rather, the protothreads library is an application of this style of coroutine.

What's the purpose of this code in the original decompressor? Assuming c is an uchar, aren't EOF and 0xFF equal?

  if (c == 0xFF) {
    len = getchar();
    c = getchar();
    while (len--)
    emit(c);
  }

Decompression, the first byte is the number of repeats and the second is the byte to repeat.

Ah, thanks!

Specifically this is known as "Run Length Encoding".

c should not be a char or unsigned char, because the return type of getchar() is "int". If you put it into a char-width variable then you lose the distinction between EOF (which is -1) and the byte 0xff. Getting the type of 'c' wrong is quite a common bug, because the API makes it an easy mistake to make. In this case, if you look down at the eventual transformed code in the "Evaluation" section you'll see that 'c' is indeed correctly declared with 'int' type.

getchar() returns an int to accommodate 257 different values: all byte chars + EOF (typically -1).

The code snippet itself is run length encoding with 0xff as an escape.

I guess one of the applications of Coroutines could be WebAssembly. When you run WebAssembly on a website which needs 100% of the CPU for more than a few ms, you have to use the "setTimeout(fn, 0)" trick to prevent the "this website stopped responding" message. That means you have to store the current state at some point and continue in the function fn (after waiting 0 ms). Languages which support coroutines out of the box would help a lot here.

Aren't Web Workers (which can run WASM) supposed to fill that role?

The web worker helps a little bit. You can send data to the UI thread whenever you want. However on the receiving side you have the same problem. The web worker only receives data when it is idle. For example if you want to send key presses to the web worker, the web worker has to idle. The utilization of the CPU to 100% with simultaneous responsiveness is quite difficult to implement. Actually you have to play an endless game of message ping pong so that the message queue is always filled.

Several previous discussions: https://hn.algolia.com/?query=Coroutines%20in%20C%20points%3...

I really like that trick. It's very powerful. But I wonder what the difference is between this and protothreads?

Protothreads is a library implementation of this trick. In fact, the protothreads creator even references the linked site in their explanation of protothreads (very last paragraph) [1].

[1] http://dunkels.com/adam/pt/expansion.html

You could use thread_local variables these days for re-entrancy instead of the ctx->i idea.

Thread-local variables make it thread-safe, but still not re-entrant. That's ok, if you don't need more than one state per thread.

You’re right. Thanks.

That page uses very simple HTML. Just paragraphs of text divided into sections with headings. Some code examples laid out side-by-side with a table. Tiny stylesheet. No JS. Loads quickly, easy to read. Warms the cockles of my heart.

Well, it was written in 2000. Call me nostalgic, but there's something to be said about how simple the internet was back then.

> easy to read.

Not on 27" with browser in full screen.

You probably shouldn't have your browser in full screen mode on a 27" screen

why?

Because unless you are using huge fonts there is probably a better use case for all they screen space.

I have a 24" (16:9) screen turned 90°, which works wonders for full screen web pages.

Because it's not ergonomic. You don't need the browser to take up your entire screen, you just need it big enough so you can fit the content comfortably.

Admittedly we would all lose this habit quicker if resizing windows wasn't such a finicky process in most OSs

I'm using this application: https://github.com/aarmea/WindowGroomer

sadly abandoned it seems, and not well-known, but is well-working in both win7 and win10. With a keyboard shortcut it's easy to resize any window and at the same time position them on the screen.

Also makes it easy to "save" windows that have slightly bad size or position so it's hard to position the mouse pointer in the resize corner.

On my wish list is that after bringing up the application, instead of using the mouse to select grid, I should be able to use eg arrow keys and shift to select them.

It really shouldn't be the web designer's job to pick a width that the content will display as and impose that unilaterally on everyone.

That way it's easy for everyone to make their own choices. If you want 27" wide lines of text, go ahead and full-screen that browser and have at it. If you want the text you're reading to take up less horizontal real estate than that, then you can easily make the browser itself as wide or narrow as you like.

This is an "it depends" thing.

If you're viewing documents, they're typically more vertically than horizontally oriented. That is, the parts you need to see more of are above/below of the viewable portion, not left/right of the viewable portion. So a browser being used for reading is often more useful when it takes up maybe half the screen on a high-res/large monitor.

If you're accessing webapps, that have more objects arranged horizontally, then going fullscreen may be more useful (think Trello boards and other things).

Aka "you're using it wrong."

CTRL and + to zoom in on Windows/Linux

CMD and + to zoom in on Mac

or CTRL/CMD and scroll wheel to zoom in/out depending on direction scrolled.

Or are you using an ancient browser without zoom?

This page is written by the creator of PuTTY. They could probably release this as a straight TXT file and still get the readership they deserve. Simon Tatham know's what he's doing!

The only issue of these websites is the width: using the full width of the screen is just too much for reading.

If you add {max-width: 60em; margin: auto;} to the body tag it looks much better.

Back in the day, we had multiple windows on the screen at one time, so this wasn't a problem. I think it was Windows which defaulted to full-screen, and led to the plague of sites assuming that the browser would be full-width on a landscape screen, but I could be wrong.

Although I love using a tiling window manager now, I kinda miss my old System 8 Macintosh setup, with Netscape open in one window & Think C (or was it CodeWarrior?) open in another.

On a Mac, Spectacle gets you pretty much there.

I haven't found something similar for Windows, but I'm sure there is one.

I'm a very happy user of Amethyst, a tiling WM https://github.com/ianyh/Amethyst Makes OSX actually usable.

Not too wide for my browser windows, which are a bit under 50% of screen width.

Likewise I would say not enough people put their monitors in portrait. It's amazing for coding.

I like landscape — I can comfortably fit 3 80-column code tabs with linter columns (vim :vsplit) in landscape mode, or a vertical term (with 2 80-col code tabs, uncomfortably) and browser side by side.

And it also works when I want to play games, or watch anything recorded in landscape, which is most media.

python has this:

  def function():
      for i in range(10):
           yield i

Reply on news.ycombinator.com