Motivation

[aykevl]

At the moment, the overview gives these goals:

Motivation

• Support for Asynch/await programming pattern.
• Support for green threads.
• Support for yield-style generators.

Of these, only green threads require any changes to WebAssembly:

• Async/await programming can relatively easily be implemented in the compiler. In particular, LLVM has implemented it as a series of passes, which you can read about here. In my experience, this works really well even in WebAssembly because after the passes have done their work, the code is converted to a form that looks like hand-written async code. No special features from the instruction set are required for this to work: the only requirement is the ability to call a function pointer.
• Yield-style generators are actually very similar to async/await and can also be implemented as a compiler pass. LLVM supports them using the same coroutine passes. Again, no special features are required from the instruction set.

While I've only mentioned LLVM above, other compilers do something similar. I believe Rust has a separate implementation of async/await (it doesn't appear to use LLVM coroutines). But an easier way to understand why async/await and yield-style generators do not need WebAssembly support is by realizing that they can all be implemented manually, by hand. And if it can be written by hand, a compiler can perform that transformation for you as a compiler pass.

What cannot be written by hand is stack switching. In particular, this is a problem in Go which uses stack switching extensively for goroutines (every blocking operation potentially results in a stack switch).
Therefore, I would propose that this proposal only focuses on the green threads use case, that requires stack switching (as evident from the name: stack-switching). Of course you could potentially use stack switching for async/await and yield-style generators, but I do not think we should focus on them as there are already ways to efficiently support them in WebAssembly.

[Pauan]

I believe the purpose of async/await is to efficiently interop with JavaScript Promises, which isn't possible for a compiler (it requires integration with the host). And similarly for JavaScript generators/iterators.

[kripken]

Of course you could potentially use stack switching for async/await and yield-style generators, but I do not think we should focus on them as there are already ways to efficiently support them in WebAssembly.

(emphasis mine)

We see around 50% size and speed overhead in practice when doing it in the toolchain. This is even with a whole-program analysis to instrument as little code as possible.

It is very hard to avoid that overhead. Control flow has far more branches, and suspend/resume points save/load all locals which extends live ranges in very bad ways. And that goes all the way up the stack from any possible pause (and even more so with indirect calls).

A 50% size overhead is, in practice, preventing a significant amount of users from using this feature atm. Fixing that is a goal here.

[aykevl]

I think I should clarify something. I believe the three goals above describe two very different things: stack switching and futures/promises/generators/however-you-like-to-call-them (I'll just call them promises from now on).

• Stack switching is for switching a whole call stack. What I'm talking about here is something like getcontext/setcontext in some POSIX systems. Essentially, it allows to create a whole new call stack and switch between them. This means that most code is entirely unaware of stack switching: it does not separate between red and blue functions. Only some special code is able to create a new stack and switch between these stacks.
• Promises (and the like) introduce a new way of programming. They require that code is written in an asynchronous style, and suffer from the red/blue function problem. However, many people seem to prefer this style. One big advantage of this is that it does not require special support from the instruction set: the compiler will convert the code into a state machine. Examples are JavaScript promises and async/await in many other popular programming languages (C++, Rust, C#, ...).

We see around 50% size and speed overhead in practice when doing it in the toolchain. This is even with a whole-program analysis to instrument as little code as possible.

You are talking here about stack switching, which indeed is very expensive today in WebAssembly and requires advanced transformations to be sort-of usable. Asyncify is certainly a great piece of work, but it still is a workaround. My proposal is to fix just that, and ignore promises for now.

What I'm talking about in the quote ("as there are already ways to efficiently support them in WebAssembly") are what I call promises. Many languages implement them and they generally don't need special support from the instruction set.

I believe the purpose of async/await is to efficiently interop with JavaScript Promises, which isn't possible for a compiler (it requires integration with the host). And similarly for JavaScript generators/iterators.

Isn't this just an issue of WebAssembly<->JavaScript interaction? Existing compilers prove that it's possible to efficiently implement async/await on WebAssembly (examples: C++ coroutines and Rust async/await, I'm not talking about asyncify). But JavaScript doesn't know about them and so can't directly interact with promises written in these languages. I believe it's best to leave this JavaScript<->WebAssembly interaction out of this stack switching proposal, perhaps it's a better fit for the interface types proposal.

[Pauan]

Isn't this just an issue of WebAssembly<->JavaScript interaction?

The problem is that in order to run a Promise in user-land you need some sort of closure (e.g. .then). It would be nice if we could do better than that, and have a more direct and efficient way to wait for Promises without needing closures.

The compiler can convert async/await into .then calls, but it's still internally using closures, even if the user doesn't see any closures.

I believe it's best to leave this JavaScript<->WebAssembly interaction out of this stack switching proposal, perhaps it's a better fit for the interface types proposal.

Interface types will not fix this at all, because the problem is that WebAssembly needs a way to wait for a Promise to finish without using closures. That's completely outside of the scope of interface types.

[kripken]

@aykevl

Sorry, I may have misunderstood you, then. Yes, the goal Asyncify solves is to allow a wasm module to wait on a JS Promise. As you said, that requires stack switching in wasm. And I agree that is the one thing this proposal should do.

Perhaps the use cases are not described well enough in the overview. I understood async/await there to mean awaiting a JS Promise, and also, to allow wasm to implement async/await using stack switching, etc. I agree the overview could be clearer.

[aykevl]

Right. I think I better understand the issue now. So the goal is to be able to interact from WebAssembly with JavaScript APIs that use promises and are thus asynchronous? If so, it becomes a bit more complicated and needs to interact with the JavaScript event loop somehow.

I have a design in mind that might work for this purpose. I'll make a strawman proposal.

[kripken]

@aykevl Yes, the JS interaction is not trivial.

We've actually done a lot of discussion on this in the stack switching meetings,

https://github.com/WebAssembly/meetings/tree/main/stack/2021

Have you attended those? If not, there are notes for them in that link.

Regardless, more ideas and designs would of course be welcome!

[aykevl]

Oh I'm sorry, I wasn't aware of that. I must have missed quite a bit!

[aykevl]

Ok, I've quickly skimmed most of the notest. It would have been useful if there was a link at the top of the README to that list of notes (and possibly to the agenda as well for future meetings). Unfortunately I can't be at the next meeting.

Indeed there has been quite a bit of discussion already! So now I feel like my design idea might not be as great as I originally thought.

Context: I've written TinyGo, which is a Go implementation. It has a custom runtime and thus scheduler. For most platforms, it relies on stack switching to switch between goroutines (if you don't know Go: goroutines are a kind of green threads and behave much like regular threads but are somewhat lighter weight). Unfortunately, stack switching is not currently supported on WebAssembly. There is asyncify, but I didn't want to have it as a dependency. Instead, I've worked around this in a somewhat similar way to asyncify using LLVM coroutines.

My idea is basically to provide only the low-level stack switching primitives, essentially making stacks a kind of object that can be interacted with:

• A way to create a new stack, with an initial function and parameter. I'll call this stack.new.
• A way to switch to a particular stack. This won't return, unless some stack switches back to the caller stack. I'll call this stack.switch(id).

I believe this is enough for interacting with JavaScript promises. Essentially, I realized that there is no way to wait for a JS promise to finish from WebAssembly, you have to return all the way back to JavaScript and let the event loop run until the promise is settled. Therefore, I think it's unavoidable that such a WebAssembly program will require some sort of scheduler.

In pseudocode, this is what it would look like from JavaScript:

var instance;
WebAssembly.instantiate(...).then((result) => {
    instance = result.instance;
    instance.start();
})

function fetchWrapper(url) {
    fetch(url).then(response => {
        // resume the blocked task
        instance.notifyFetchResult(response.json());
        // run scheduler until there are no more runnable tasks
        instance.scheduler();
    })
    // not bothering with error handling here
}

And from WebAssembly:

// this is part of the runtime
func start() {
    var id = stack.new(main);
    runqueue.add(new Task(id));
    scheduler()
}
func scheduler() {
    while tasks in runqueue {
        var task = runqueue.pop();
        stack.switch(task.id)
    }
    // all runnable tasks have run, so return now
}

// this is the user code
func main() {
    result = doFetch(some url);
    print(result) // do something with it, seemingly synchronously
}

// this is library code
// globals only used for ease of understanding
var fetchingTask;
var fetchResult;
func doFetch(url) {
    // Start the fetch, and suspend the current task.
    fetchingTask = getCurrentTask();
    call JavaScript fetchWrapper(url);
    stack.switch(0); // switch  back to the main stack (which contains the scheduler)
    return fetchResult
}
func notifyFetchResult(result) {
    // Store the fetch result and queue the task that did the fetch in the runqueue.
    // Don't run it yet.
    fetchResult = result;
    runqueue.push(fetchingTask);
}

I hope this makes sense. In this implementation, only the raw stack switching primitives are exposed to WebAssembly and the language/compiler/runtime take care of switching between these stacks. This is roughly what I already use for TinyGo except that it needs an asyncify-like transform to be usable in a JS context.

In this example, the behavior is as follows:

• main creates a new task with a new stack
• scheduler runs, switches to the main function
• doFetch queues a fetch and switches back to the scheduler, waiting to be activated again once the fetch completes
• the scheduler doesn't have more tasks to run, so returns.
• the WebAssembly.instantiate callback is finished and returns, letting the JS event loop run
• the fetch operation is resolved
• fetchWrapper calls notifyFetchResult with the result
• notifyFetchResult stores the result and adds the task that started the fetch to the runqueue
• fetchWrapper runs the scheduler
• the scheduler switches back to the doFetch function, which was running but was suspended. It resumes after the stack.switch(0) call. It returns back to main
• main prints the result

Possible issues:

• It depends on some sort of stack switching. It doesn't literally have to be stack switching: there are other ways to achieve the same (visible) result. I've seen quite a bit of discussion on this but didn't read it in detail.
• It's very low level. I see this as a plus, but other people might want to see something more high level.
• It doesn't directly interact with JavaScript promises, instead it assumes there is glue code that will handle it.
• Stack switching is probably not possible across web workers (e.g. resume a stack on a different worker than the one that started it). This makes it hard or impossible to implement M:N scheduling like the Go runtime does. I think being able to exploit parallelism is important.
• I haven't thought much about exceptions, but I suppose they will need to be caught at the lowest level (in the function that is passed to stack.new).

If this makes sense and is any good, I can work on a proper (more formal) proposal. I've relatively quickly written this comment to roughly explain what I had in mind.

[fgmccabe]

I would encourage you to attend the subgroup meetings.
We meet every two weeks.
The agenda are a mix of specific issues around our effort on 'stack switching' and reports "from the field" from language implementors who describe their issues and their solutions.
We are planning on having a presentation from Google's go-lang team (hopefully today) and in the future hopefully form other mainstream languages such as Swift.
As for technical constraints, we are driven by our requirements note.
Looking forward to you contributions...

[aykevl]

I will try to be at a meeting but I should note that monday evenings (in my timezone, GMT+2) don't work well for me. But maybe I can make a short presentation what I would like to see from a TinyGo perspective (which might be slightly different from what upstream Go would want to see).

[woodsmc]

I just wanted to add this here; within the Embedded world, we're looking at ways to interrupt a running WASM application and invoke an event handler; think a traditional interrupt event handler, or even a Unix / Linux signal handler, This would entail the WASM VM being interrupted, forcing a stack switch and a specific function being invoked.

I'm not sure if there are similar requirements within the browser world too?

[fgmccabe]

You can do something like this today: use a designated location in linear memory that the host writes into. The wasm code has to poll it of course.
Doing more than that in a standards compliant way is going to be tricky.