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

41–50 of 63 posts

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

#41

Post by nonsince »

garganzol wrote: post #16

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.

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.

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

#42

Post by afiori »

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.

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

#43

Post by pizlonator »

nonsince wrote: post #39
pizlonator wrote: post #38

Earlier quoted context omitted.

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.

It’s not guaranteed that using the liveness implicit in the SSA that falls out of a stack language is going to give you better code in less time than a block-local register allocation with locals live at block boundaries spilled to the stack.

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

#44

Post by pjmlp »

afiori wrote: post #42

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.

Me too, it is as if people stop learning how compilers are implemented.

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

#45

Post by BeeOnRope »

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.

It is not an ad hominem in any sense! For one thing, this part isn't even an attack - here the author is trying to explain and essentially forgive why the (allegedly) sub-optimal design was chosen: that there wasn't enough information at the time to make a fully informed decision! He's saying "it wasn't their fault they designed it like so, at the time it probably seemed like the best decision".

Second, even if it were some form of attack - it wouldn't be an ad hominem because it is not an _irrelavant_ personal attack. It is directly relevant whether some group made decisions based on sufficient existing information etc. The author might be totally wrong about the facts, but at least he believes and offers evidence regarding the situation at the outset of development.

It hurts to have your work criticized, and I can't comment on the factual accuracy of the timeline and other claims, but the piece does not come off at all badly-intentioned, personal or otherwise unreasonable: it comes off mostly as purely technical criticism.

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

#46

Post by jdemler »

nonsince wrote: post #40
jdemler wrote: post #26

Earlier quoted context omitted.

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.

Thanks for the pointer!

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

#47

Post by titzer »

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:/…

Years ago, I thought a single-tier design of an (offline) compiler was best (OVM). And then I thought a heavy offline compiler and two tiers of of the same JIT was best (Jikes). Then I thought an interpreter with an an optimizing JIT was best (HotSpot server). Then I thought a slightly less optimizing JIT was best (HotSpot client). Then I thought that two JITs were best (V8 w/ Crankshaft). Then two JITs with a super heavy optimizing JIT was best (V8 w/ TurboFan). Then I thought a single tier for Wasm was best (V8 w/ TurboFan). Then I thought an interpreter and a heavy optimizing JIT was best (V8 w/ Ignition and TurboFan). Then I thought two JITs for Wasm was best (V8 w/ Liftoff and TurboFan).

I've seen a single baseline compiler go through a metamorphosis from essentially streaming (HotSpot client V1) to full SSA-based with register allocation (HotSpot client today).

In other words, prepare for change. A single tier is probably not going to be your final design.

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

#48

Post by titzer »

pizlonator wrote: post #43
nonsince wrote: post #39

Earlier quoted context omitted.

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.

It’s not guaranteed that using the liveness implicit in the SSA that falls out of a stack language is going to give you better code in less time than a block-local register allocation with locals live at block boundaries spilled to the stack.

Indeed, and for good spilling decisions, you'll want to have next-use distance information for values. While a stack machine gives you an approximation of this (deeper in the stack is farther in the future), for best results I imagine you'll want to do two passes anyway, so locals are no worse for this, other than at block boundaries, if you lack liveness you have to spill them.

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

#49

Post by arcticbull »

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 unfortunate that you felt attacked, because I didn't read the article that way at all. I'm neither a fan of JS nor particularly WASM, and I read the authors article as quite supportive and appreciative, and pointing out a potential area for improvement / documenting experiences -- and I'd love your thoughts on it!

To me, it broke down as:

(1) SSA form would allow for substantially simpler compilers. Adding block/loop parameters while maintaining support for locals as an extension doesn't address that, as compilers would then still have to implement full support for both modes of operation.

(2) The magnitude of the performance impact of this design decision.

I have some limited experience in compiler design but not enough to really have an understanding of the implications.

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

#50

Post by pizlonator »

nonsince wrote: post #37
pizlonator wrote: post #15

Earlier quoted context omitted.

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.

I keep forgetting that some people actually like the reducible control flow constraint. To me, if you have that constraint then it’s not really ssa. You literally can’t represent everything that llvm IR or B3 IR could. I think you should make sure you add that caveat when making equivalence claims.

That said, the key reason for my push back is the suitability of SSA for fast backends. If you can afford to run some coalescing then SSA is at least perf-neutral. If you can’t then compiling from SSA will result in crappy code. As in, probably worse than block local RA.

So your best bet is to somehow avoid having to coalesce. But that probably means using SSA only for extracting liveness and then running the world’s dumbest linear scan. Even that may not be as good as block local RA.

Post reply on HN