Progress toward phase 4

[tlively]

The phase 4 requirements are:

• Two or more Web VMs implement the feature.

  • Partially done. Chrome supports tail calls behind the #enable-experimental-webassembly-features flag. No other engines have implementations according to https://webassembly.org/roadmap/.

• At least one toolchain implements the feature.

  • Done. LLVM and Binaryen have complete support.

• The formalization and the reference interpreter are usually updated (though these two can be done as part of step 3 at the Working Group chair's discretion).

  • Done (AFAICT).

• Community Group has reached consensus in support of the feature.

  • Judging from the lack of open issues on this repo, this shouldn't be a problem.

Is there anything left to do besides get another web engine implementation?

[lars-t-hansen]

@tlively, do you feel that the lack of tail call support is blocking important work? Notably, is it or will it be blocking the work on wasm GC in any significant way, or to put it another way, will the j2cl and dart pipelines depend on tail calls for performance or significant functionality?

[rossberg]

Yes, spec, interpreter, and test suite have been done long ago. The second engine has been the main blocker for the last 2-3 years. I was hoping that JSC would be particularly motivated to implement this one. :)

@lars-t-hansen, I think this feature is independent of GC, and it has been requested from various sides. I of course understand the need for prioritisation, but it looks somewhat troublesome for the health of the Wasm process if a feature that is basically done and everybody agrees is wanted does not make any progress for years.

[lars-t-hansen]

@rossberg, this is simply a prioritization issue for us, as you already observed - small team, competing pressures, and a question of utility relative to other proposals and ongoing infrastructural work.

In general - this has come up in a couple of threads recently - I feel that a number of wasm proposals could be more explicit about their expected utility. The tail call proposal (not worse than any other in this regard!) doesn't even name a single concrete language that would benefit from this proposal, nor does it try to quantify, even informally, the amount of pain that would result from not having tail calls in wasm, for each specific such language (or other use case). We could all name such languages, but how interested are we in trying to understand the alternatives for translators from those languages, and would any of them actually have translators absent some other feature X that is also missing (frequently X = the GC feature)? I think that often, utility is discussed in meetings during the early stages of the proposals, but by capturing the claims of utility directly and in some detail in the proposal it would be easier to understand later why a proposal should be prioritized for implementation.

Consider Scheme, which requires proper tail calls. Several successful translators from Scheme to C were written that circumvent the lack of tail calls in C in various ways, either by some sort of fairly efficient trampoline+longjmp system and/or by translating calls that implement loops to actual loops and translating the remaining tail calls as non-tail calls. Static compilers would also use the larger (whole-module) context to make such a translation more effective. At least Stalin, Bigloo, Gambit-C, and Petit Larceny are examples of translators in this class; there were others (but it's such a long time ago and I've forgotten).

So if Scheme is one of the languages named in a list of languages that would benefit from proper tail calls, it would be appropriate to mention these techniques as some that could be used by Scheme translators in the absence of tail calls, along with the problems that using these techniques might create for the translator and/or language user, and some assessment of how bad those problems are in practice. And it might also be appropriate to mention that a successful Scheme translator would require many other things (GC, call tags, a very powerful variant of stack switching, and reasonable solutions for generic arithmetic and variable-length argument lists) and is therefore not a powerful driver for tail calls at this time.

[lars-t-hansen]

@tlively, I see you added this to tomorrow's meeting agenda. Unfortunately I'll miss that meeting, so a brief remark here. Our position is that the utility of tail calls is unclear enough that it is not a priority for us to implement it soon, nor would we want to speculate about when we might implement it.

[tlively]

Thanks, @lars-t-hansen! Your position that we should concretely motivate further work makes perfect sense. I started thinking about tail calls again because they came up in an Emscripten issue about supporting C++20 coroutines: emscripten-core/emscripten#10991. I don't know have firsthand knowledge about it yet, but according to that issue, Clang can use tail calls to make coroutines much more efficient.

Do you think that finding "X C++ workloads get faster by Y% with tail calls enabled" could be sufficient motivation (for some X and Y) to prioritize tail calls? Or would you want to see new languages, etc. rather than just performance improvement?

[tlively]

@tlively, do you feel that the lack of tail call support is blocking important work? Notably, is it or will it be blocking the work on wasm GC in any significant way, or to put it another way, will the j2cl and dart pipelines depend on tail calls for performance or significant functionality?

No, as far as I know this is orthogonal to the GC work.

[lars-t-hansen]

@tlively,

Do you think that finding "X C++ workloads get faster by Y% with tail calls enabled" could be sufficient motivation (for some X and Y) to prioritize tail calls? Or would you want to see new languages, etc. rather than just performance improvement?

Every bit helps, IMO. As always, the more use cases and the more compelling they are the more it makes sense to prioritize work on a feature. If real C++ code that we might want to run on the web improves significantly then that's an important fact to consider.

[KronicDeth]

Lumen (an AOT compiler for Erlang) that we’re building to support Erlang, Elixir, Gleam and other languages that work on BEAM will be heavily dependent on tail calls as all those languages write their code assuming that tail calls are cheap and do not extend the stack. They also assume that tail calls don’t have to be recursive tail calls.

Lumen also would use the stack switching protocol to implement Erlang processes.

[TerrorJack]

Asterius (experimental haskell-to-wasm compiler) is also heavily dependent on tail calls, since the Haskell stack is managed explicitly as heap data, and we do need the guarantee that control flow transfer has O(1) memory overhead. We emulate tail calls via trampolines by default for now, no concrete numbers on how much performance gain tail calls will bring, but it's surely an upstream feature we wholeheartedly welcome.

[tlively]

@TerrorJack, would you be able to measure the performance overhead of the trampoline approach? Binaryen (if you use it) supports tail calls with --enable-tail-call and V8/Node supports them with --experimental-wasm-return-call. Chrome supports them (IIRC) if you enable chrome://flags/#enable-experimental-webassembly-features.

[lorenzleutgeb]

I tried to implement a compiler from CakeML (or rather, some much simpler intermediate language in the CakeML compiler) to WebAssembly. While a trampoline approach might be possible to implement, it's too hard to verify (CakeML is a verified compiler). Relying on tail calls would be easier.

Edit: So probably you should not only think in terms of improvements that tail calls will yield for existing code, but also what it would enable.

[unicomp21]

@lars-t-hansen looking at the performance benchmarks for Seastar and Redpanda, which are pretty breath taking, they both rely heavily on co_await, which relies on tail calls. We could do some pretty incredible webassembly stuff. Even the chirp guys have been asking for tail calls in their efforts.

http://seastar.io/http-performance/

Until recently, I didn't realize what a massive impact tail calls could make when it comes to co_await and the compiler optimizations which come from it.

[unicomp21]

I'd suggest getting the change released on chrome asap. Once webassembly workloads start showing up which only run fast on chrome, others will follow.

[unicomp21]

emscripten-core/emscripten#10991 (comment)

[yuri91]

@unicomp21 indeed we (Leaning Technologies) are interested in tail calls for CheerpX.

We use them to implement X86 indirect jumps.

The alternative is a trampoline-like solution, but it is quite slower. We tried really hard to avoid the problem altogether in many cases (by "devirtualizing" the jumps), but it is not always possible of course (see here for some more info).

I don't have numbers at hand, but since we have a flag to toggle tail call support in our JIT, I could try to set up some benchmarks.

We are even considering to implement it in JSC or SpiderMonkey ourselves to move things forward.

[lars-t-hansen]

@yuri91,

Thanks for the input. (Thanks also goes to everyone else on the thread.) Now we can hopefully count on @tlively to summarize these (and other) findings into the proposal's overview ;-)

We are even considering to implement it in JSC or SpiderMonkey ourselves to move things forward.

If you're planning anything for SpiderMonkey we'd appreciate knowing about it beforehand, as we are implementing other large changes to the ABI and there would be an inevitable conflict with tail calls if these changes were to happen concurrently without synchronization.

[yuri91]

@lars-t-hansen Good to know! We haven't seriously looked into doing this yet, but if/when we do we will get in touch for sure.

[mshinwell]

Some work has started on a compilation strategy from the OCaml language to WebAssembly. This work unfortunately had to be paused due to the pandemic, but hopefully it's not too far away from restarting. OCaml relies heavily on tail calls (both direct tail calls where the callee is known and indirect tail calls where it is not) for loops involving one or more functions. Within approximately the next year we should be in a position to have an optimiser that can compile some of these situations to loops, via contification, but it is likely that tail calls will remain important. As such it would be very welcome if there were to be further progress on the implementation of tail calls within the WebAssembly ecosystem.

[KronicDeth]

indirect tail calls where it is not

apply(module, function, arguments) and apply(anonymous_function, arguments) also occur in tail position in Erlang and Elixir.

[unicomp21]

@lars-t-hansen these might be useful ...

https://github.com/scylladb/seastar/blob/9cb2d51ed19b63cd81d25ba9efa512f5ca01f500/doc/tutorial.md

https://github.com/vectorizedio/redpanda/search?q=co_await

https://github.com/chriskohlhoff/asio/search?q=co_await

https://github.com/search?q=org%3Afacebook+co_await&type=code

my understanding is co_await leverages tail calls heavily.

Per the last link, perhaps we could get facebook to start asking for tail call support in webassembly? I'm guessing they would be interested in having them for all the meta stuff going on.

[wingo]

Just as a data point, for the Guile implementation of Scheme, tail calls would be useful but not necessary to enable Scheme on wasm and not sufficient on their own for high performance. Because of varargs and multiple return values, we end up having to pass arguments and return values via tables anyway, in the general case. Because we want to capture multi-shot delimited continuations, we also have to CPS-convert and push return continuations on an explicitly-managed stack also, converting all calls and returns to tail calls, implemented via a trampoline loop. At least we can contify loops & control flow without calls.

Tail calls in wasm would do away with the need for the trampoline loop but is just one piece. See https://lists.gnu.org/archive/html/guile-devel/2021-06/msg00005.html for a further discussion.

[rossberg]

@wingo, I'm curious why multiple return values are an issue, given that Wasm has them, too. Does that have to do with the untyped nature of Scheme?

[wingo]

@rossberg yes it is the lack of types. same issue as varargs, really.

[lars-t-hansen]

@tlively and @rossberg,

Community Group has reached consensus in support of the feature.

  * Judging from the lack of open issues on this repo, this shouldn't be a problem.

The overview lists one open issue, all the way down at the bottom:

Can tail calls across module boundaries guarantee tail behaviour?

There isn't an open or closed github issue whose title speaks to that problem; possibly a resolution lurks in a discussion somewhere. In any case, can we either have that open issue removed / clarified in the overview if it has been resolved, or a github issue opened for discussion and eventual resolution otherwise? Thanks.

[unicomp21]

Aren't they already adding it to chrome? @lars-t-hansen

https://bugs.chromium.org/p/v8/issues/detail?id=7431

[unicomp21]

https://leaningtech.com/extreme-webassembly-2-the-sad-state-of-webassembly-tail-calls/

[rossberg]

@lars-t-hansen, yes, good question. My recollection of the state of that debate is that multiple implementers were positive that this could be implemented just fine, e.g. using auxiliary stubs or pushing custom stack frames. But I don't know if that has actually been proven in practice, e.g., in V8.

@lukewagner, @titzer, @jakobkummerow

[thibaudmichaud]

Cross-module tail-calls should work just fine in chrome. The only difference with regular tail-calls is that we pass the target instance to the callee instead of the current instance, like we do for regular import calls.
However the implementation is still unstable and we don't have plans to enable it by default yet.

[unicomp21]

@gahaas is there an eta on phase 4?

[gahaas]

I don't know more than what is mentioned in #15 (comment). @rossberg what are your plans on moving tail calls to phase 4?

[rossberg]

@gahaas, nothing new, the lack of a second implementation still is the (only) blocker as per our process requirements. I intend to push to phase 4 as soon as that's out of the way, i.e., either JSC or SpiderMonkey have finished their's. @tomoliv30, having high hopes for your work. ;)

[alexp-sssup]

A second implementation of Wasm tail calls has been merged into WebKit [1] and enabled by default [2].

@rossberg can you take from here?

[1] WebKit/WebKit@5ee0680
[2] WebKit/WebKit@57da434

[RyanBrewer317]

Yay! Is there any expected ETA at this point? I'm quite excited for more functional languages working with/compiling to web assembly :)

[titzer]

I've created a PR to add a Phase 4 poll to tomorrow's meeting agenda.

[tomoliv30]

@titzer @dschuff any chance to have the poll on next week's agenda?

[unicomp21]

@tomoliv30 does chrome have tail call support yet?

[gahaas]

@unicomp21 The tail call proposal is completely implemented in Chrome.

[unicomp21]

Thanks @gahaas ! Which version?

[unicomp21]

@tlively does this mean emscripten can now support co_await in the above chrome version?

[gahaas]

@unicomp21 Tail calls in Chrome are shipped behind the flag chrome://flags/#enable-experimental-webassembly-features, already since version 87 or so.

[unicomp21]

@gahaas is there a GA version and date?

[gahaas]

@unicomp21 No, we will ship it as soon as the proposal reaches Phase 4.

[tlively]

@tlively does this mean emscripten can now support co_await in the above chrome version?

Yes, if you pass -mtail-call to Emscripten and enable tail call support in the browser, co_await should work. I don't remember if I've tried it myself, though. If you try it out and it doesn't work, let me know.

[dschuff]

let's put it on the agenda for next week: WebAssembly/meetings#1196

[titzer]

Today the CG voted to advance to Phase 4! Woohoo!

[unicomp21]

@gahaas ship date? chrome version?

[thibaudmichaud]

@unicomp21 we're aiming for chrome 112, no guarantees yet.

[unicomp21]

thanks @thibaudmichaud !

[unicomp21]

@thibaudmichaud I guess everything should work now? in chrome? are there tests I can run?

[dschuff]

My understanding is that it shipped in 112. This is also what https://webassembly.org/roadmap/ says.
If you want to test whether your browser supports a feature, you can also use the "Your browser" column on that page. It runs the tests from https://github.com/GoogleChromeLabs/wasm-feature-detect directly.