Hacker News Reader

Comment by saagarjha | Hacker News Reader

WebAssembly makes a number of strange choices that seemingly fly in the face of convention; this is one of them. It would be really nice if it someone took some time it make a FAQ on the website to answer questions like “why doesn’t WebAssembly do x like everything else”, because otherwise it just seems that they’re just doing things differently because they can…

View on HN

A lot of those bad WebAssembly decisions are carried over from Emscripten/Asm.js and don't have any real rationale behind them beyond that.

Obviously, since JS doesn't support arbitrary control flow, Emscripten/Asm.js would need to convert to some simplified form of control flow (although not necessarily fully structured). It seems that this solution was carried over to WebAssembly without much deep thought given.

There does seem to be some backwards association with Java's bytecode verification complexity issues (which are the result of a bad design, not unstructured control flow). In the big GitHub Issue (https://github.com/WebAssembly/design/issues/796) on the topic, one of the core V8 developers even claims that the Java experience justifies the WebAssembly decision. However, the funclets proposal for WebAssembly (https://github.com/WebAssembly/funclets/blob/master/proposal...) shows that you can support arbitrary control flow with linear time verification if you choose a different design than Java.

WASM is a typed bytecode format where the stack state must be validatable at compile-time, guaranteeing that no validated program can mess up the stack at runtime. Having unstructured control flow would make it pretty much impossible to do that, wouldn't it?

Not impossible, as in the JVM there'd be a pass which verifies that the stack usage is deterministic along all program paths. It's nice not having to do that verifying step, but stack usage still has to be checked anyways, so whether it's actually a win is debatable

Nah. I made a low-level VM in 2001 similar to this funclets proposal cwzwarich linked to (Hi, Cameron), and verification was a fast local check. Each funclet had a signature, you collect the signatures before you start verifying the code, and then track changes to the stack as you walk through the code, using the signatures for the effects of any calls you encounter, and finally insisting that the funclet match its declared effect. Control flow within a funclet is reducible. (I didn't call them funclets, but it sounds like the same basic scheme on glancing through. One simplification: my VM could loop only through the tail calls.)

To get linear time validation, you need conditions at each control flow transfer that can be checked locally but together imply that stack usage in the function is well-formed.

The funclet approach (in more ordinary terminology) is to ensure that the stack difference from function invocation upon entry to a basic block is the same across entries to that basic block, and that those additional stack entries all have the same (statically specified) type in each invocation. This is very natural when generating code from an SSA optimizer.

Java bytecode traditionally didn't contain any of this branch target or type information, and required the bytecode verifier to do an iterative combined control/data-flow analysis. Even now that they added some of that type information with stack maps, it's still more complicated than it needs to be due to the historical legacy of this approach.

Completely unstructured, yes. However, there are many stack-based VMs with both gotos and verification. Generally speaking, the constraint is that for any label that is a jump target, the stack must have the same count and type of elements for all possible origins. It's not hard to verify.

There are other ones that can't reasonably be because of legacy, though; for example, the lack of memory permissions.

By memory permissions, do you mean setting page-level permissions, like mprotect on Unix? I’d love to see WebAssembly add support for those, along with mmap-like functionality. But there at least, unlike with control flow, there are some fundamental portability issues to consider. The only performant way to implement page-level permissions is using the native MMU. But different targets have different page sizes: most Unix systems have 4kb pages, but iOS has 16kb pages; Windows has 4kb pages which can be protected individually, but separate memory mappings can only be on 64k aligned boundaries; and Linux can be configured with multiple page size options. And some little microcontrollers don’t have an MMU at all, yet there are people trying to run WebAssembly on microcontrollers for some strange reason.

> By memory permissions, do you mean setting page-level permissions, like mprotect on Unix?

Yes, exactly.

> But different targets have different page sizes: most Unix systems have 4kb pages, but iOS has 16kb pages; Windows has 4kb pages which can be protected individually, but separate memory mappings can only be on 64k aligned boundaries; and Linux can be configured with multiple page size options.

I haven't looked into it much, but perhaps WASI could abstract some of this, or make this information available to applications?

> And some little microcontrollers don’t have an MMU at all, yet there are people trying to run WebAssembly on microcontrollers for some strange reason.

It might be a little bit overhyped ;)

> It seems that this solution was carried over to WebAssembly without much deep thought given.

That's definitely not true - a lot of thought was given at the time to this. I'm not saying the optimal conclusion was arrived at (nor am I saying the opposite), but it definitely wasn't for lack of effort and consideration.

I don't remember all the details, but some of the factors were:

* Experience with structured control flow in compilers like Emscripten, Mandreel, and Cheerp, that showed it's pretty easy to re-structure a CFG in the toolchain, and there aren't significant downsides when the VM receives that output.

* VM people concerned about the efficiency and complexity of non-structured control flow, and preferring the structural approach that has known simple ways to construct SSA etc. (see titzer's comment for more details)

* Not having a proposal like funclets on the table. (The idea for that came much later.)

I assume that important design criteria is to enable slim and fast verification and single-pass WASM to SSA or JIT backends and native compilers. To do that you want reducible flow graph.

This will become more important especially if WebAssembly is moving beyond the browser.

Reply on news.ycombinator.com