5 ms·

These days the 'fashionable' way to implement async-await seems to be via compiler magic by transforming async functions into a 'switch-case state machine' and

These days the 'fashionable' way to implement async-await seems to be via compiler magic by transforming async functions into a 'switch-case state machine' and a hidden context pointer argument. In vanilla C (without compiler magic) I've mostly seen it implemented via 'green threads' aka 'fibers' aka 'stack-switching', but TBH I'm not sure if this can be implemented with the standard setjmp/longjmp, I've mostly seen it implemented without (and instead use two small assembly functions for the context switch). One downside of stack-switching is that it doesn't work on WASM.

chaosite 4y ago
stack switching with setjmp/longjmp can be implemented like this: https://stackoverflow.com/a/8817009/1116739 https://stackoverflow.com/a/8817009/1116739 But it's messy enough that you'd want a library/framework to help you handle it.
- mananaysiempre 4y ago
  POSIX pre-2008 had (and Linux/Glibc and {Free,Net,DragonFly}BSD still have) <ucontext.h> with proper stack switching functions, used as a fallback in a number of coroutine libraries. The fallback status is due to a self-inflicted inefficiency: they save and restore the signal mask, thus still need to go through the kernel (why e.g. Linux does not put signal mask manipulation in the vDSO, I don’t know). POSIX yanked them and now recommends rewriting to use POSIX threads instead, which is asinine.
  - gpderetta 4y ago
    And the 2008 was about the time that coroutines were gaining popularity again!
- Findecanor 4y ago
  Putting each tasklet's stack in different places on the actual stack and jumping between them is inherently unsafe and not portable. You must be sure that each tasklet does not consume too much stack so that it does not overwrite another. On BSD Unices, you can only longjump back up the stack. Otherwise, longjmp() will call longjmperror() and terminate the program.
  - chaosite 4y ago
    > Putting each tasklet's stack in different places on the actual stack and jumping between them is inherently unsafe and not portable. You must be sure that each tasklet does not consume too much stack so that it does not overwrite another. It's absolutely unsafe and a ridiculous to do, but what's the reasoning for it being unportable? Wouldn't it just be just as unsafe anywhere that C compiles? > On BSD Unices, you can only longjump back up the stack. Otherwise, longjmp() will call longjmperror() and terminate the program. The manpage claims that the semantics is not "only jump back up the stack", but rather that you can't longjmp to "[...] an environment that that has already returned". Technically, the tasklet the we're longjmp'ing to never terminates, right?
    - comex 4y ago
      In any case, you definitely can't do it on Windows and Emscripten (WebAssembly), where longjmp invokes the same stack unwinding behavior as C++ exception handling, rather than just setting some registers and jumping. Windows has its own APIs for tasklets (fibers); no such luck on Emscripten.
samsquire 4y ago
I wrote an unrolled switch statement in Java to simulate eager async/await across threads. https://github.com/samsquire/multiversion-concurrency-control/blob/main/src/main/java/main/MultiAwait.java https://github.com/samsquire/multiversion-concurrency-contro... The goal is that a compiler should generate this for you. This code is equivalent to the following: task1: while True: handle1 = async task2(); handle2 = async task3(); print(await handle1) print(await handle2) task2: n = 0 while True: yield n++ task3: n = 0 while True: yield n++ It doesn't actually run task2 and task3 both eagerly, I've not got around to scheduling the tasks on DIFFERENT threads. They currently queue onto a single thread, so task2 and task3 are parallel to task1 (but maybe not at the same time) but task2 and task3 are not parallel to each other. This is my goal. I also ported the coroutines in this blog post https://blog.dziban.net/coroutines/ https://blog.dziban.net/coroutines/ to GNU Assembler https://github.com/samsquire/assembly/blob/main/coroutines.S https://github.com/samsquire/assembly/blob/main/coroutines.S This might be useful to someone who wants to port this to C. This uses the stack switching idea. So they are stackful coroutines. There's also Tina a header only coroutine library https://slembcke.github.io/Tina https://slembcke.github.io/Tina I also played with protothreads http://dunkels.com/adam/pt/ http://dunkels.com/adam/pt/ I also asked in a stackoverflow post how to use a thread pool with C++20 coroutines: https://stackoverflow.com/questions/74520133/how-can-i-pass-things-to-a-c20-coroutine-co-await-await-suspend-operator-funct https://stackoverflow.com/questions/74520133/how-can-i-pass-... Someone provided some example code, which seems to work with C++ coroutines :-)
duped 4y ago
The big problem with setjmp/longjmp for fibers is that a call to longjmp is undefined behavior if the `jmp_buf` argument was created by a call to `setjmp` on a different thread (1). That means fibers cannot be easily relocated onto a different thread, making M:N threading tricky to implement and erasing a lot of the benefit of fibers. And that said, implementing a super-fast setcontext/swapcontext is like twenty lines of assembly with not too many gotchas, if you don't care about saving a few things that require syscalls. But all that said the real downside of stack switching is that it's overkill for coroutines that can be implemented as a finite state machine, unless the runtime supports growable stacks (otherwise you pay a big cost on fiber creation, and eat a lot of memory for many fibers). There are a few languages that do this and it's super cool, but C isn't one of them. WASM will almost certainly support stack switching, iirc there have been proposals for wasmtime to support it already? (1) https://pubs.opengroup.org/onlinepubs/9699919799/functions/longjmp.html https://pubs.opengroup.org/onlinepubs/9699919799/functions/l...
- lstodd 4y ago
  > And that said, implementing a super-fast setcontext/swapcontext is like twenty lines of assembly with not too many gotchas, if you don't care about saving a few things that require syscalls. sigaltstack(2) wasn't all that prohibitive when I did that in Python 2.6 back then. Was it 2009? I seriously can't understand this obsession with FSMs. A naive setcontext()-based implementation outperfomed both greenlets (with its crazy legacy of memcpy-ing parts of stack from stackless) and Tornado/Twisted (with them being pure-python and therefore lacking any means to force some async on client libraries. which one does in C) while letting everyone write some nice clean synchronous-looking code. 10 years later we end up with half a language hacked up and still nowhere near the ease of use that was coded in a week or so.
  - duped 4y ago
    > I seriously can't understand this obsession with FSM It's the most optimal representation of the common-case (non-recursive asynchronous tasks), has the same overhead as a function call, plays very well with branch prediction, can be easily inlined by optimizers, and it's a lot easier to implement.

chaosite 4y ago

stack switching with setjmp/longjmp can be implemented like this: https://stackoverflow.com/a/8817009/1116739 https://stackoverflow.com/a/8817009/1116739 But it's messy enough that you'd want a library/framework to help you handle it.

mananaysiempre 4y ago
POSIX pre-2008 had (and Linux/Glibc and {Free,Net,DragonFly}BSD still have) <ucontext.h> with proper stack switching functions, used as a fallback in a number of coroutine libraries. The fallback status is due to a self-inflicted inefficiency: they save and restore the signal mask, thus still need to go through the kernel (why e.g. Linux does not put signal mask manipulation in the vDSO, I don’t know). POSIX yanked them and now recommends rewriting to use POSIX threads instead, which is asinine.
- gpderetta 4y ago
  And the 2008 was about the time that coroutines were gaining popularity again!
Findecanor 4y ago
Putting each tasklet's stack in different places on the actual stack and jumping between them is inherently unsafe and not portable. You must be sure that each tasklet does not consume too much stack so that it does not overwrite another. On BSD Unices, you can only longjump back up the stack. Otherwise, longjmp() will call longjmperror() and terminate the program.
- chaosite 4y ago
  > Putting each tasklet's stack in different places on the actual stack and jumping between them is inherently unsafe and not portable. You must be sure that each tasklet does not consume too much stack so that it does not overwrite another. It's absolutely unsafe and a ridiculous to do, but what's the reasoning for it being unportable? Wouldn't it just be just as unsafe anywhere that C compiles? > On BSD Unices, you can only longjump back up the stack. Otherwise, longjmp() will call longjmperror() and terminate the program. The manpage claims that the semantics is not "only jump back up the stack", but rather that you can't longjmp to "[...] an environment that that has already returned". Technically, the tasklet the we're longjmp'ing to never terminates, right?
  - comex 4y ago
    In any case, you definitely can't do it on Windows and Emscripten (WebAssembly), where longjmp invokes the same stack unwinding behavior as C++ exception handling, rather than just setting some registers and jumping. Windows has its own APIs for tasklets (fibers); no such luck on Emscripten.

samsquire 4y ago

I wrote an unrolled switch statement in Java to simulate eager async/await across threads. https://github.com/samsquire/multiversion-concurrency-control/blob/main/src/main/java/main/MultiAwait.java https://github.com/samsquire/multiversion-concurrency-contro... The goal is that a compiler should generate this for you. This code is equivalent to the following: task1: while True: handle1 = async task2(); handle2 = async task3(); print(await handle1) print(await handle2) task2: n = 0 while True: yield n++ task3: n = 0 while True: yield n++ It doesn't actually run task2 and task3 both eagerly, I've not got around to scheduling the tasks on DIFFERENT threads. They currently queue onto a single thread, so task2 and task3 are parallel to task1 (but maybe not at the same time) but task2 and task3 are not parallel to each other. This is my goal. I also ported the coroutines in this blog post https://blog.dziban.net/coroutines/ https://blog.dziban.net/coroutines/ to GNU Assembler https://github.com/samsquire/assembly/blob/main/coroutines.S https://github.com/samsquire/assembly/blob/main/coroutines.S This might be useful to someone who wants to port this to C. This uses the stack switching idea. So they are stackful coroutines. There's also Tina a header only coroutine library https://slembcke.github.io/Tina https://slembcke.github.io/Tina I also played with protothreads http://dunkels.com/adam/pt/ http://dunkels.com/adam/pt/ I also asked in a stackoverflow post how to use a thread pool with C++20 coroutines: https://stackoverflow.com/questions/74520133/how-can-i-pass-things-to-a-c20-coroutine-co-await-await-suspend-operator-funct https://stackoverflow.com/questions/74520133/how-can-i-pass-... Someone provided some example code, which seems to work with C++ coroutines :-)

duped 4y ago

The big problem with setjmp/longjmp for fibers is that a call to longjmp is undefined behavior if the `jmp_buf` argument was created by a call to `setjmp` on a different thread (1). That means fibers cannot be easily relocated onto a different thread, making M:N threading tricky to implement and erasing a lot of the benefit of fibers. And that said, implementing a super-fast setcontext/swapcontext is like twenty lines of assembly with not too many gotchas, if you don't care about saving a few things that require syscalls. But all that said the real downside of stack switching is that it's overkill for coroutines that can be implemented as a finite state machine, unless the runtime supports growable stacks (otherwise you pay a big cost on fiber creation, and eat a lot of memory for many fibers). There are a few languages that do this and it's super cool, but C isn't one of them. WASM will almost certainly support stack switching, iirc there have been proposals for wasmtime to support it already? (1) https://pubs.opengroup.org/onlinepubs/9699919799/functions/longjmp.html https://pubs.opengroup.org/onlinepubs/9699919799/functions/l...

lstodd 4y ago
> And that said, implementing a super-fast setcontext/swapcontext is like twenty lines of assembly with not too many gotchas, if you don't care about saving a few things that require syscalls. sigaltstack(2) wasn't all that prohibitive when I did that in Python 2.6 back then. Was it 2009? I seriously can't understand this obsession with FSMs. A naive setcontext()-based implementation outperfomed both greenlets (with its crazy legacy of memcpy-ing parts of stack from stackless) and Tornado/Twisted (with them being pure-python and therefore lacking any means to force some async on client libraries. which one does in C) while letting everyone write some nice clean synchronous-looking code. 10 years later we end up with half a language hacked up and still nowhere near the ease of use that was coded in a week or so.
- duped 4y ago
  > I seriously can't understand this obsession with FSM It's the most optimal representation of the common-case (non-recursive asynchronous tasks), has the same overhead as a function call, plays very well with branch prediction, can be easily inlined by optimizers, and it's a lot easier to implement.