Hacker News Reader

Comment by amelius | Hacker News Reader

One thread per CPU, and non-blocking I/O, that's sounds like the usual way to approach the problem. I'm surprised it uses state machines to handle the non-blocking I/O, because modern software engineering provides much more pleasant approaches such as using coroutines.

View on HN

Coroutines have the distinct disadvantage of needing a stack, much like threads. So-called 'stackless' coroutines aren't really so different to computed gotos in a state machine

stackless are regular coroutines except that there's 1 stack in the scheduler and when a coroutine yields, the current stack state is saved into the coroutine's structure to be restored later. The disadvantage is that you'll need to copy out/in every time a coroutine yields.

It's unrelated to gotos in a state machine.

Having a stack per coroutine is not a big deal, especially if the coroutine library regularly advises the kernel on the memory areas it isn't using (madvise).

What's stored on the stack usually needs to be stored somewhere else and ends up using a similar account of memory.

When you allocate a 1MB stack per coroutine, the kernel will not wire it all to ram, but only the pages that have been touched. When the stack shrinks back and the coroutine yields, the scheduler can call madvise and inform the kernel that the no longer used pages from the 1MB can be reclaimed.

For parsing html, you wouldn't need that large a stack. Further, you could make the stack grow dynamically at a very small cost. Also, I bet that even if stackless coroutines are close to FSMs, they are much easier to program.

You need green/user-space threads if you want to use co-routines effectively, because if a coroutine blocks, it would block off the entire OS thread from doing anything else.

What are stackless coroutines? What do they look like?

Read Adam Dunkels' paper on Protothreads.

Thanks for your comment.

I don't know how to feel about Protothreads. It's just syntatic sugar for using a state-machine to provide continuations. You're also not allowed to carry state over between continuations (although I can see how you can extend it to carry-over some struct of data or something). This greatly diminishes the usefulness of Protothreads.. so it feels more like a fun proof-of-concept.

Are there any popular/real-world use cases of Protothreads?

Yeah, that's how you end up doing this: store coroutine state in a struct, with an integer that lets you decide where to jump to when you resume the coroutine. With compiler support that can be pretty efficient (gcc has computed goto, for instance). Things get quite awkward in C but similar techniques are manageable in C++.

I've never used Protothreads before, but Contiki (the tiny operating system written by the same person) uses them for its process implementation.

Similar technique is also used by Putty as well: http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

nginx is written in C though - I know it's possible to do coroutine-type stuff with setjmp/longjmp, but isn't that considered risky?

setjmp()/longjmp() will work, but they're sort of inefficient as, at least under POSIX, they will save and restore the signal mask, which makes for two round-trips to the kernel just for a coroutine context switch.

My web server uses coroutines, and for x86 and x86-64 it uses open-coded assembly routines to yield/resume, with fallbacks to setjmp()/longjmp() on other architectures.

It works fairly well, performance-wise. In fact, it's one of the top-performing servers/frameworks in the TechEmpower's Web Framework benchmarks[1].

I wrote a similar article explaining how everything is put together here[2].

[1] https://www.techempower.com/benchmarks/ [2] http://tia.mat.br/blog/html/2014/10/06/life_of_a_http_reques...

Given the various efforts like libtask, lthread, boost coroutines, etc, it seems like the low-level assembly trickery ought to be isolated and standardized. Maybe some new methods (similar to the setcontext family) should be proposed to the glibc project. Something not at risk of deprecation.

The Boost guys factored the context switching and stack allocation stuff in to a separate library - Boost Context[0], which supports a bunch of architectures[1]. I'm sure their fcontext code could be lifted. They claim on modern x86-64 that a switch takes about 8ns[2]

The Boost Coroutine library is built on top, adds type safety, ensures the stack is unwound when contexts are destroyed, and enables propagation of exceptions across switches.

    $ ls -lh /usr/lib/libboost_context.so.1.58.0 
    -rwxr-xr-x 1 root root 55K May 30 09:58 /usr/lib/libboost_context.so.1.58.0

[0] http://www.boost.org/doc/libs/1_58_0/libs/context/doc/html/i...

[1] http://www.boost.org/doc/libs/1_58_0/libs/context/doc/html/c...

[2] http://www.boost.org/doc/libs/1_58_0/libs/context/doc/html/c...

Not sure if something like this should be part of glibc. Just recently there was an ABI break due to the fact that jmp_buf is exposed in the headers to allow embedding the struct[1].

[1] https://lwn.net/Articles/605607/

(Also, I ended up mixing up ucontext.h with setjmp.h in my comment above; Lwan uses ucontext.h as a fallback. There are coroutine implementations that will use setjmp/longjmp, or at the very least reuse the jmp_buf struct and roll their own asm, though.)

Glibc seems like a good place to put it to me. If everyone is preferring hand-coding assembly primitives that workaround suboptimal standard methods (ucontext), then my first instinct would be to look into making those existing methods more optimal.

(Note: in case it wasn't clear, I'm not suggesting we put all of coroutines into glibc, just the stack dancing stuff)

Reply on news.ycombinator.com