-
Notifications
You must be signed in to change notification settings - Fork 19
I'm implementing a small language that compiles to wasm, and I'm wondering if this proposal would be helpful in implementing yield-based generators and await-based coroutines.
If possible, does it have any advantages in terms of size and performance compared to state machine transformation or continuation pass style transformation?
All reactions
The relative performance of stack switching vs a state machine transformation also is highly dependent on the concrete usage pattern. The state machine approach performs better as long as generators are shallow and consist of small functions with little state. But it is linear in the nesting depth of the intermediate call stack, i.e., the distance between generator loop and yield point. For example, a recursive generator (e.g., a tree traversal) performs much worse under the state machine approach than with direct stack switching, whose cost is roughly constant per yield. See e.g. Figure 9 in this paper, which measures C++ coroutines against a stack-switching mechanism across varying recu...
Replies: 2 comments
These are some of the 'core' uses cases anticipated for 'core stack switching'. There are several approaches to SS being considered, but, for all of them, asynchronous programming are high on the list of anticipated applications.
The primary anticipated benefits, compared to some version of CPS transform, are code size and performance. The code size would be significantly smaller (comparing with asyncify, which expands code size by some 30-100%, we would expect code size increase to be 'marginal').
As for performance, this is more nuanced. For a small yield-style generator there may be no performance benefit over a CPS transform. The reason being that switching stacks will incur some runtime penalties in many WebAssembly engines. On the other hand, a CPS transformed program will execute more slowly than a non CPS transformed one. In addition to an extra layers (such as additional function calls) a CPS transformed function is less likely to be able to make use of engine optimizations (such as using registers to hold arguments and local variables).
I hope that this helps.
All reactions
The relative performance of stack switching vs a state machine transformation also is highly dependent on the concrete usage pattern. The state machine approach performs better as long as generators are shallow and consist of small functions with little state. But it is linear in the nesting depth of the intermediate call stack, i.e., the distance between generator loop and yield point. For example, a recursive generator (e.g., a tree traversal) performs much worse under the state machine approach than with direct stack switching, whose cost is roughly constant per yield. See e.g. Figure 9 in this paper, which measures C++ coroutines against a stack-switching mechanism across varying recursion depth.
All reactions
-
👍 1