17 ms·

WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

175 points by panic 8y ago

benj111 8y ago
"For the most part it’s an extremely well-designed specification. However, they are weighed down by WebAssembly’s legacy" Really? Wikipedia: "In March 2017, the design of the minimum viable product was declared to be finished and the preview phase ended." https://en.m.wikipedia.org/wiki/WebAssembly https://en.m.wikipedia.org/wiki/WebAssembly It was only announced in 2015. I'm not taking sides here, but either it's well designed, or getting weighed down by legacy in 2 (or 4) years.
- rkangel 8y ago
  Immediately following that 'legacy' sentence is an explanation of what they mean by it: > WebAssembly started out not as a bytecode, but more like a simplified binary representation for asm.js. Essentially it was originally designed to be source code, like JavaScript. WebAssembly itself is relatively new, but it wasn't a completely blank sheet of paper that they were starting with when they designed it.
  - benj111 8y ago
    Yes and the next sentence finishes: "and only at the last minute did it switch to stack-based encoding for the operators" Which kind of counts against it being well designed. To me, "weighed down" by legacy suggests some deep problem that shouldn't be manifesting in something so young. You could argue that 2 years is a long time in tech, I wouldn't say it's a long time in language development though. Maybe I'm just arguing semantics here? Is a library for a particular language weighed down by legacy because it's designed to run on one particular language?
- deleted 8y ago
  [deleted]
devbug 8y ago
As someone in the midst of building a game in C for 7 platforms, with WebAssembly being one of them, my main disappointment is with the lack of coroutines (or lack of control over the stack to implement them.) It hinders how wide my engine can go since I'm limited to a fork-and-join model for splitting work across threads. Poor code generation is also another pain point, but I fully expect that to improve drastically over the coming year. Overall, I'm pretty excited for WASM and the implications of it, but it does feel like the web has regressed in the ability to deliver games.
- ljackman 8y ago
  Most common coroutine implementations, such as JavaScript's and Python's, are delimited or "symmetric". This means the most obvious implementation is in terms of compiler transformations in the source language. It seems out of WASM's scope to do this. Undelimited "asymmetric" coroutines, like Lua's, could be an interesting addition. That still seems to me to be too high level a feature for a "portable assembly language" specification though.
  - wahern 8y ago
    I think you might be conflating characteristics regarding delimited and symmetric coroutines. But let's step back. JavaScript's and Python's choice of coroutine styles was constrained and effectively dictated by runtime limitations. CPython, V8, and similar implementations mix their C and assembly callstacks with their logical language callstacks. Because the host runtimes didn't readily support multiple stacks without a complete rewrite, this bled into the language runtime. There was a path dependency whereby early implementation choices directed the evolution of the language semantics. WASM is recapitulating the same cycle. Which is understandable because time is limited and you can't make the perfect the enemy of the good, but you still have to recognize it for what it is--a vicious cycle of short sightedness. If WASM doesn't provide multiple stacks as a primitive resource, then things like stackful coroutines, fibers, etc, will have to be emulated (at incredible cost, given WASM's other constraints regarding control flow). And if they have to be emulated they'll be slow, which means languages will continue avoiding them.
pizlonator 8y ago
Recomputing liveness is not really a big deal. Can be quite cheap, especially over a register based IR. I think that this article overstates the impact of all of this.
- tom_mellior 8y ago
  Yes. The article is obsessed with the code quality generated by streaming compilers, which is probably the wrong thing to focus on. A real high-performance backend has no trouble reconstructing SSA form and using it for optimizations. But forcing frontends to emit SSA would be a burden on them. (LLVM bitcode formally requires SSA form as well, but this can be worked around by using allocas.) It might, however, make sense to have another standard "SSA WebAssembly" program representation. There could then be standard tooling to compile vanilla WebAssembly to the SSA form, frontends could choose which variant they want to emit, and backends preferring SSA as input could still be made happy.
  - pizlonator 8y ago
    SSA is a really strange form to send over a wire. It’s got poor space efficiency. It’s also annoying to interpret and not super cheap to turn into machine code. So, I don’t see the point of sending SSA over the wire.
    - titzer 8y ago
      Agree. SSA requires deconstruction, which would slow down a streaming compiler.
    - nonsince 8y ago
      Author here: I'm not advocating for an SSA register machine like LLVM, I'm just advocating for a format that makes it trivial to reconstruct SSA form on-the-fly. A pure stack machine with a statically-determinable stack depth and type at any given place in the program would give you the same information as SSA form in a more-compact way.
      - 8y ago
titzer 8y ago
[one of the original Wasm designers here] Responding to the OP, since there is no comment section on the site. First off, this rant gets the history of Wasm wrong and the facts of Wasm wrong. I wouldn't unload on a random person on the internet generally, but I would like to point a sentence like: > Not only that, but for the most part the WebAssembly specification team were flying blind. It's an ad hominem. This really just impugns people and invites an argument. It might be cathartic, but generally it doesn't advance the conversation to cast aspersion like this. And it's not true. I can tell you from first hand experience that a baseline compiler was absolutely on our minds, and Mozilla already had a baseline compiler in development throughout design. The Liftoff design that V8 shipped didn't look too different from the picture in our collective heads at the time. And all of us had considerable experience with JIT designs of all kinds. As for the history. The history is wrong. The first iteration of Wasm was in fact a pre-order encoded AST. No stack. The second iteration was a post-order encoded AST, which we found through microbenchmarks, actually decoded considerably faster. The rub was how to support multi-value returns of function calls, since multi-value local constructs can be flattened by a producer. We considered a number of alternatives that preserved the AST-like structure before settling on that a structured stack machine is actually the best design solution, since it allowed the straightforward extension to multi-values that is there now (and will ship by default when we reach the two-engine implementation status). As for the present. Wasm blocks and loops absolutely can take parameters; it's part of the multi-value extension which V8 implemented already a year ago. Block and loop parameters subsume SSA form and make locals wholly unnecessary (if that's your thing). Locals make no difference to an optimizing compiler like TurboFan or IonMonkey. And SSA form as an intermediate representation is not as compact as the stack machine with block and loop parameters which is the current design, as those extra moves take space and add an additional verification burden. A final point. Calling Wasm "not a stack machine" is just a misunderstanding. All operators that work on values operate on the implicit operand stack. This is the very the definition of a stack machine. The fact that there is additional mutable local storage doesn't make it not a stack machine. Similarly, the JVM has mutable typed locals and yet is a stack machine as well. The JVM (prior to 6) allowed completely unstructured control flow and use of the stack, leading to a number of problems, including a potentially cubic verification time. We fixed that. All that said, there might be a design mistake in Wasm bytecode. Personally, I think we should have implicitly loaded arguments to a function onto the operand stack, which would have made inlining even more like syntactic substitution and further shortened the bodies of very tiny functions. But this is a small thing and we didn't think about it at the time. [edit: Perhaps "ad hominem" is a bit strong. It feels different to be on the receiving of a comment like "flying blind"--it doesn't mean the same thing to the sender and receiver--especially when this was really not the case, as I state here.]
garganzol 8y ago
Huh? Web assembly is a stack machine and locals do not pose a problem whatsoever. Yes, the author just needs more work to be done. But it's perfectly doable, although it has a complexity. Like everything in the world of compilers. There are no free lunches.
- nonsince 8y ago
  Yes compilers are hard, but why make them harder? There is literally no reason to require rebuilding this information. The compiler emitting Wasm has that information and already uses it, having locals and disallowing blocks to take/return values actually means more complexity in both the compilers generating Wasm and the runtimes generating native code from Wasm. That's the entire premise of the article.
  - pizlonator 8y ago
    Even if carrying that information was the thing that you needed (I don’t think it is but there’s a separate thread about that), it’s definitely not the thing that other implementations need.
bogomipz 8y ago
The author states: >"This means that you have overhead associated with compilation - knowing the liveness of variables is extremely important for generating efficient assembly, but instead of the liveness being calculated when creating the IR and stored as a part of it you have to recalculate this data every time." Can someone say what is involved in calculating "liveliness"? What is the procedure for doing so?
- tom_mellior 8y ago
  You iterate over the program (every individual function, really) backwards. A use of a variable means that it is "live" before that point; a definition (i.e., a write into) a variable means that it is "dead" before that point. That is, at any point, a variable being "live" means that its value at that point may be used in the future. Liveness is especially important for register allocation: If two variables are both live at some program point (and cannot be proved to have the same value), the compiler must place them in different registers or stack slots. As an aside, liveness is also useful for some other things. For example, a variable that is live at the start of a function is one that may be used without being initialized, and the compiler can emit a warning for it. https://en.wikipedia.org/wiki/Live_variable_analysis https://en.wikipedia.org/wiki/Live_variable_analysis Edit: BTW, it really is "liveness", not "liveliness".
afiori 8y ago
One thing I dislike about how criticism of WebAssembly are formulated is that often they refer to the MVP as final product. Tail calls are important but not essential, many functional languages have a C runtime; the point is if they (or an equivalent alternative) can be added properly or if the standard is not flexible enough.
- pjmlp 8y ago
  Me too, it is as if people stop learning how compilers are implemented.
- wahern 8y ago
  The issue is that if the VM doesn't support tail calls or alternatives like unstructured goto then you're going to end up with two layers of emulation for such languages, rather than one. That's incredibly slow. Which is all fine and dandy, but people need to realize that WASM will not be nearly as performant as claimed, particularly when hosting other language runtimes.
Osiris 8y ago
In Part 1, the author claims that WebAssembly is not a stack machine. In Part 2, when discussing `goto`, he says, "WebAssembly is a stack machine." Part 2 contains no explanation about the contradiction with Part 1.

175 points by panic 8y ago

"For the most part it’s an extremely well-designed specification. However, they are weighed down by WebAssembly’s legacy" Really? Wikipedia: "In March 2017, the design of the minimum viable product was declared to be finished and the preview phase ended." https://en.m.wikipedia.org/wiki/WebAssembly https://en.m.wikipedia.org/wiki/WebAssembly It was only announced in 2015. I'm not taking sides here, but either it's well designed, or getting weighed down by legacy in 2 (or 4) years.

rkangel 8y ago
Immediately following that 'legacy' sentence is an explanation of what they mean by it: > WebAssembly started out not as a bytecode, but more like a simplified binary representation for asm.js. Essentially it was originally designed to be source code, like JavaScript. WebAssembly itself is relatively new, but it wasn't a completely blank sheet of paper that they were starting with when they designed it.
- benj111 8y ago
  Yes and the next sentence finishes: "and only at the last minute did it switch to stack-based encoding for the operators" Which kind of counts against it being well designed. To me, "weighed down" by legacy suggests some deep problem that shouldn't be manifesting in something so young. You could argue that 2 years is a long time in tech, I wouldn't say it's a long time in language development though. Maybe I'm just arguing semantics here? Is a library for a particular language weighed down by legacy because it's designed to run on one particular language?
deleted 8y ago
[deleted]

devbug 8y ago

As someone in the midst of building a game in C for 7 platforms, with WebAssembly being one of them, my main disappointment is with the lack of coroutines (or lack of control over the stack to implement them.) It hinders how wide my engine can go since I'm limited to a fork-and-join model for splitting work across threads. Poor code generation is also another pain point, but I fully expect that to improve drastically over the coming year. Overall, I'm pretty excited for WASM and the implications of it, but it does feel like the web has regressed in the ability to deliver games.

ljackman 8y ago
Most common coroutine implementations, such as JavaScript's and Python's, are delimited or "symmetric". This means the most obvious implementation is in terms of compiler transformations in the source language. It seems out of WASM's scope to do this. Undelimited "asymmetric" coroutines, like Lua's, could be an interesting addition. That still seems to me to be too high level a feature for a "portable assembly language" specification though.
- wahern 8y ago
  I think you might be conflating characteristics regarding delimited and symmetric coroutines. But let's step back. JavaScript's and Python's choice of coroutine styles was constrained and effectively dictated by runtime limitations. CPython, V8, and similar implementations mix their C and assembly callstacks with their logical language callstacks. Because the host runtimes didn't readily support multiple stacks without a complete rewrite, this bled into the language runtime. There was a path dependency whereby early implementation choices directed the evolution of the language semantics. WASM is recapitulating the same cycle. Which is understandable because time is limited and you can't make the perfect the enemy of the good, but you still have to recognize it for what it is--a vicious cycle of short sightedness. If WASM doesn't provide multiple stacks as a primitive resource, then things like stackful coroutines, fibers, etc, will have to be emulated (at incredible cost, given WASM's other constraints regarding control flow). And if they have to be emulated they'll be slow, which means languages will continue avoiding them.

pizlonator 8y ago

Recomputing liveness is not really a big deal. Can be quite cheap, especially over a register based IR. I think that this article overstates the impact of all of this.

tom_mellior 8y ago
Yes. The article is obsessed with the code quality generated by streaming compilers, which is probably the wrong thing to focus on. A real high-performance backend has no trouble reconstructing SSA form and using it for optimizations. But forcing frontends to emit SSA would be a burden on them. (LLVM bitcode formally requires SSA form as well, but this can be worked around by using allocas.) It might, however, make sense to have another standard "SSA WebAssembly" program representation. There could then be standard tooling to compile vanilla WebAssembly to the SSA form, frontends could choose which variant they want to emit, and backends preferring SSA as input could still be made happy.
- pizlonator 8y ago
  SSA is a really strange form to send over a wire. It’s got poor space efficiency. It’s also annoying to interpret and not super cheap to turn into machine code. So, I don’t see the point of sending SSA over the wire.
  - titzer 8y ago
    Agree. SSA requires deconstruction, which would slow down a streaming compiler.
  - nonsince 8y ago
    Author here: I'm not advocating for an SSA register machine like LLVM, I'm just advocating for a format that makes it trivial to reconstruct SSA form on-the-fly. A pure stack machine with a statically-determinable stack depth and type at any given place in the program would give you the same information as SSA form in a more-compact way.
    - 8y ago

titzer 8y ago

[one of the original Wasm designers here] Responding to the OP, since there is no comment section on the site. First off, this rant gets the history of Wasm wrong and the facts of Wasm wrong. I wouldn't unload on a random person on the internet generally, but I would like to point a sentence like: > Not only that, but for the most part the WebAssembly specification team were flying blind. It's an ad hominem. This really just impugns people and invites an argument. It might be cathartic, but generally it doesn't advance the conversation to cast aspersion like this. And it's not true. I can tell you from first hand experience that a baseline compiler was absolutely on our minds, and Mozilla already had a baseline compiler in development throughout design. The Liftoff design that V8 shipped didn't look too different from the picture in our collective heads at the time. And all of us had considerable experience with JIT designs of all kinds. As for the history. The history is wrong. The first iteration of Wasm was in fact a pre-order encoded AST. No stack. The second iteration was a post-order encoded AST, which we found through microbenchmarks, actually decoded considerably faster. The rub was how to support multi-value returns of function calls, since multi-value local constructs can be flattened by a producer. We considered a number of alternatives that preserved the AST-like structure before settling on that a structured stack machine is actually the best design solution, since it allowed the straightforward extension to multi-values that is there now (and will ship by default when we reach the two-engine implementation status). As for the present. Wasm blocks and loops absolutely can take parameters; it's part of the multi-value extension which V8 implemented already a year ago. Block and loop parameters subsume SSA form and make locals wholly unnecessary (if that's your thing). Locals make no difference to an optimizing compiler like TurboFan or IonMonkey. And SSA form as an intermediate representation is not as compact as the stack machine with block and loop parameters which is the current design, as those extra moves take space and add an additional verification burden. A final point. Calling Wasm "not a stack machine" is just a misunderstanding. All operators that work on values operate on the implicit operand stack. This is the very the definition of a stack machine. The fact that there is additional mutable local storage doesn't make it not a stack machine. Similarly, the JVM has mutable typed locals and yet is a stack machine as well. The JVM (prior to 6) allowed completely unstructured control flow and use of the stack, leading to a number of problems, including a potentially cubic verification time. We fixed that. All that said, there might be a design mistake in Wasm bytecode. Personally, I think we should have implicitly loaded arguments to a function onto the operand stack, which would have made inlining even more like syntactic substitution and further shortened the bodies of very tiny functions. But this is a small thing and we didn't think about it at the time. [edit: Perhaps "ad hominem" is a bit strong. It feels different to be on the receiving of a comment like "flying blind"--it doesn't mean the same thing to the sender and receiver--especially when this was really not the case, as I state here.]

garganzol 8y ago

Huh? Web assembly is a stack machine and locals do not pose a problem whatsoever. Yes, the author just needs more work to be done. But it's perfectly doable, although it has a complexity. Like everything in the world of compilers. There are no free lunches.

nonsince 8y ago
Yes compilers are hard, but why make them harder? There is literally no reason to require rebuilding this information. The compiler emitting Wasm has that information and already uses it, having locals and disallowing blocks to take/return values actually means more complexity in both the compilers generating Wasm and the runtimes generating native code from Wasm. That's the entire premise of the article.
- pizlonator 8y ago
  Even if carrying that information was the thing that you needed (I don’t think it is but there’s a separate thread about that), it’s definitely not the thing that other implementations need.

bogomipz 8y ago

The author states: >"This means that you have overhead associated with compilation - knowing the liveness of variables is extremely important for generating efficient assembly, but instead of the liveness being calculated when creating the IR and stored as a part of it you have to recalculate this data every time." Can someone say what is involved in calculating "liveliness"? What is the procedure for doing so?

tom_mellior 8y ago
You iterate over the program (every individual function, really) backwards. A use of a variable means that it is "live" before that point; a definition (i.e., a write into) a variable means that it is "dead" before that point. That is, at any point, a variable being "live" means that its value at that point may be used in the future. Liveness is especially important for register allocation: If two variables are both live at some program point (and cannot be proved to have the same value), the compiler must place them in different registers or stack slots. As an aside, liveness is also useful for some other things. For example, a variable that is live at the start of a function is one that may be used without being initialized, and the compiler can emit a warning for it. https://en.wikipedia.org/wiki/Live_variable_analysis https://en.wikipedia.org/wiki/Live_variable_analysis Edit: BTW, it really is "liveness", not "liveliness".

afiori 8y ago

One thing I dislike about how criticism of WebAssembly are formulated is that often they refer to the MVP as final product. Tail calls are important but not essential, many functional languages have a C runtime; the point is if they (or an equivalent alternative) can be added properly or if the standard is not flexible enough.

pjmlp 8y ago
Me too, it is as if people stop learning how compilers are implemented.
wahern 8y ago
The issue is that if the VM doesn't support tail calls or alternatives like unstructured goto then you're going to end up with two layers of emulation for such languages, rather than one. That's incredibly slow. Which is all fine and dandy, but people need to realize that WASM will not be nearly as performant as claimed, particularly when hosting other language runtimes.

Osiris 8y ago

In Part 1, the author claims that WebAssembly is not a stack machine. In Part 2, when discussing `goto`, he says, "WebAssembly is a stack machine." Part 2 contains no explanation about the contradiction with Part 1.