Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

troubles.md

Post reply on HN
Print view View original

31–40 of 63 posts

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#31

Post by nonsince »

devbug wrote: post #6

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…

The inability to implement coroutines is addressed in the second article in the series here http://troubles.md/posts/why-do-we-need-the-relooper-algorit...

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#32

Post by RubenSandwich »

tomxor wrote: post #19
titzer wrote: post #8

[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 rea…

> 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. Ignoring any factual incorrectness, I can not see how the author could have made his point in a more respectful way. He clearly has great enthusiasm for WASM and respect for it's authors, I am struggling to see how anyone could have interp…

I think this is a really great example of how even a simple phrase can detract from a whole argument[1]. While reading the paragraph in whole, which I included below[2], makes it clear that the blog author does respect the WebAssembly team it is important to remember to be very careful with words when being critical of work. We all inject a bit of ourselves into our work, so criticism is often taken very personally. So err on the side of grace and assume the creator knows as much as you do, if not more.

[1]: I understand that the comment author has other concerns besides the phrasing, but I'm only focusing on the phrasing right now.

[2]: The developers of the WebAssembly spec aren’t dumb. For the most part, it’s an extremely well-designed specification. However, they are weighed down by WebAssembly’s legacy. 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. It would be a more-efficient representation thereof but it still wasn’t a proper virtual machine instruction set. Then, it became a register machine, and only at the last minute did it switch to stack-based encoding for the operators. At that point, concepts like locals were quite entrenched in the spec. Not only that, but for the most part the WebAssembly specification team were flying blind. No streaming compiler had yet been built, hell, no compiler had yet been built. It wasn’t clear that having locals would be problematic - after all, C gets by just fine using local variables that the compiler constructs the SSA graph for.

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#33

Post by bogomipz »

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?

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#34

Post by nonsince »

titzer wrote: post #8

[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 rea…

Author here:

I'm sorry that you felt attacked by that line, I really tried my hardest to phrase it in a way that didn't assign any blame. I wasn't trying to imply that the team wasn't thinking about these issues, just that real-world implementations of this kind of VM didn't exist yet and so many of the practical issues were difficult to see in advance.

Many of your other issues I directly address in the article itself, for example that optimising compilers can recalculate the information lost when using locals (tl;dr: why recalculate this information when you could include it in the format) and that Wasm started as an AST machine. The JVM works similarly to Wasm, true, but it is generally considered a hybrid stack/register machine. I'd define Wasm as a similar hybrid.

As for the multi-value extension, although that improves codegen for streaming compilers it doesn't reduce complexity unless locals are also deprecated. Something that I don't talk about in the article but that seems like it may be a problem going forward is that Wasm seems to have no mechanism in the format for major version bumps/breaking changes. Unnecessary things like locals and structured control flow (see the second article in the series) cannot be removed even when they are subsumed by more-general features.

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#35

Post by nonsince »

tom_mellior wrote: post #12
pizlonator wrote: post #7

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.

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 s…

Author here:

I'm obsessed with the quality of streaming compiler-emitted code for a few reasons. Firstly, I'm working on an optimising streaming compiler. Secondly, I work for a blockchain company and we can realistically only allow linear-time compilation, this doesn't necessarily mean streaming compilation but we might as well make it both (I explain why we need linear-time compilation in a different article http://troubles.md/posts/why-wasm/). Thirdly, anything that gives streaming compilers more information also means that non-streaming compilers have to reconstruct less information, and lastly in this particular case there is no reason (except for backwards compatibility constraints) why we can't preserve more of the information from the front-end and have streaming compilers emit better code.

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#36

Post by tom_mellior »

bogomipz wrote: post #33

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?

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

Edit: BTW, it really is "liveness", not "liveliness".

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#37

Post by nonsince »

pizlonator wrote: post #15
tom_mellior wrote: post #12

Earlier quoted context omitted.

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 s…

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.

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.

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#38

Post by pizlonator »

nonsince wrote: post #35
tom_mellior wrote: post #12

Earlier quoted context omitted.

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 s…

Author here: I'm obsessed with the quality of streaming compiler-emitted code for a few reasons. Firstly, I'm working on an optimising streaming compiler. Secondly, I work for a blockchain company and we can realistically only allow linear-time compilation, this doesn't necessarily mean streaming compilation but we might as well make it both (I explain why we need linear-time compilation in a different article http:/…

A streaming compiler can emit really great code even without liveness. It’s not clear to me what optimizations you’re hoping to get from this. To do most SSA optimizations you need a backend that can lower from SSA, which is not linear afaik. Register allocation might be helped a bit by liveness, but you can get block-local liveness information in linear time already - so for your thing to be better you’d have to prove that there is something sweet about having a non-SSA compiler that does register allocation using imperfect liveness information, which was provided by an adversary. Then you’d have to prove that this is ok - that an adversary can’t force you to do more work than you want by lying about liveness. It’s probably not ok; for worst case perf you’re almost certainly better off not trusting provided liveness info and reconstructing it yourself on a block-local basis.

Anyway. I could tell you a lot more about how to design compilers but I have to take my kid to school.

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#39

Post by nonsince »

pizlonator wrote: post #38
nonsince wrote: post #35

Earlier quoted context omitted.

Author here: I'm obsessed with the quality of streaming compiler-emitted code for a few reasons. Firstly, I'm working on an optimising streaming compiler. Secondly, I work for a blockchain company and we can realistically only allow linear-time compilation, this doesn't necessarily mean streaming compilation but we might as well make it both (I explain why we need linear-time compilation in a different article http:/…

A streaming compiler can emit really great code even without liveness. It’s not clear to me what optimizations you’re hoping to get from this. To do most SSA optimizations you need a backend that can lower from SSA, which is not linear afaik. Register allocation might be helped a bit by liveness, but you can get block-local liveness information in linear time already - so for your thing to be better you’d have to pro…

A statically-typed stack machine like Wasm is homomorphic to SSA form with liveness, and it's impossible to lie about liveness in this format. Most of the complexity in the streaming compiler that I'm working on is around producing good code for locals when we have no liveness information for them. I explain why this is in the article.

Re: WebAssembly Troubles Part 1: WebAssembly Is Not a Stack Machine

#40

Post by nonsince »

jdemler wrote: post #26
titzer wrote: post #8

[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 rea…

I would love to work on Wasm (compiler or tooling). Do you know a way to get such a job?

The only companies that I know (outside of the big players) hiring people to work on WebAssembly are Perlin Network and Parity Technologies, both blockchain companies. I work for Parity on Wasm stuff.
Post reply on HN