Troubles.md

It's great you emphasise it and I would generalise it even further. Any perf optimisation should be considered after reliably measuring (controlling for hot/cold cache, overall system load among others) its effect, instead of blindly adding unsafe everywhere. Similar to people who sprinkle their Cpp code with inline thinking it will force the compiler to inline. In fact, sometimes you can improve perf by adding an additional safe operation to your code! http://troubles.md/rust-optimization/#assert-conditions-beforehand The key takeaway from all perf optimisation articles to me is the methodology used for realiably verifying the effect of suggested changes. It's awesome to see the author include failed experiments.

Concerning stephen's item (2). The stricter set of rules was laid out by Richard C. Waters in Optimization of Series Expressions: Part I: User's Manual for the Series Macro Package, page 46 (document page 48). See reference Waters(1989a). The paper's language is a bit different than contemporary (2023) language. `map()` is called `map-fn`. `reduce()` a.k.a. `fold` seems to be `collect-fn`, although `collecting-fn` also seems interesting. sorting, uniqueness and permutation seem to be covered by `producing`. Just think of McIlroy's famous pipeline in response to Donald Knuth's trie implementation[mcilroy-source]: tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed $ {1}q As far as pipeline or stream processing diagrams are concerned, the diagram on page 13 (document page 15) of Waters(1989a) may also be worth a closer look. What the SERIES compiler does is pipeline the loops. Think of a UNIX shell pipeline. Think of streaming results. Waters calls this pre-order processing. This also seems to be where Rich Hickey got the term "transducer" from. In short it means dropping unnecessary intermediate list or array allocations. Shameless self-plug: Eliminated unnecessary allocations in my JavaScript code by adding support for SERIES to the PARENSCRIPT Common Lisp to JavaScript compiler. The trick was (1) to define (series-expand ...) on series expressions so that they can be passed into (parenscript:ps ...) and (2) the parenscript compiler…

It's not having a runtime that's the problem, it's limitations in WASM's control flow constructs: https://github.com/WebAssembly/design/issues/796#issuecomment-40131036… And WASM has this limitation as a consequence of limitations in the V8 and SpiderMonkey engines. See http://troubles.md/posts/why-do-we-need-the-relooper-algorithm-again and https://news.ycombinator.com/item?id=19997091 And those engines have those limitations because they're a reasonable design tradeoff in the context of executing JavaScript. I think even if WASM gets a limited goto sufficient to resolve the most problematic performance issues, languages like Go that use more sophisticated control flow constructs (e.g. stackful coroutines) will always be at a disadvantage relative to C or Rust when it comes to WASM as absence of other various low-level constructs (e.g. ability to directly handle page faults) will incur higher relative penalties. The same thing could be said about Rust's new async/await--WASM will compound the costs of the additional indirect branching in async-compiled functions (not to mention the greater number of function invocations, which is at least 2x even if a function never defers). That said, I don't think anybody uses Go for the insane performance, so as long as the performance impact isn't too severe (and limited goto support will help tremendously) it shouldn't be much of an issue. OTOH, these sorts of tradeoffs are why "native" code will always have a significant place.…

But how do you handle arguments or loop index variables? Your liveness is the entire function? You have to compile all the WASM chunks together in order to do any optimization? That seems ... problematic. Edit: Yep. In article referenced from the original: http://troubles.md/posts/wasm-is-not-a-stack-machine/ Double edit: Some of this has already been fixed in WASM: https://github.com/WebAssembly/multi-value

One issue with Wasm is you essentially can't target it with a single-pass compiler, unlike just about any real machine. Wasm can only represent reducible control flow, so you have to pass your control-flow graph through some variation of the Relooper[1,2]. I don't know if upstream tcc can do that (there are apparently some forks?..). [1] http://troubles.md/why-do-we-need-the-relooper-algorithm-again/ [2] https://medium.com/leaningtech/solving-the-structured-control-flow-pro…

There are some comments now... I guess a lot of people (like me) are interested in WASM, but most don't have enough knowledge to say anything "authoritative" about it. When I read "It is a stack machine, no registers", I remembered this other article http://troubles.md/wasm-is-not-a-stack-machine/ and thought "Ok now, these can't both be right at the same time, right?". But apparently they can - as another comment here states, "WebAssembly is not exactly a stack machine but a stack machine encoding of an instruction tree". To that I say, if I can use the stack as I'm used to from other systems, I don't really care if it's a "real" stack machine. But I'm not really sure of that either...

After this gained prominence I took a hard read of Koopman's Stack Computers: The New Wave intent on writing an interpreter. I sought some optimization properties that would apply to the modern requirements for ILP, OoE and parallelization at low core frequencies -- none are offered. This manifests in WASM, and the criticism was elaborated very well: http://troubles.md/posts/wasm-is-not-a-stack-machine/ > This essentially makes WebAssembly a register machine without liveness analysis, but not only that, it’s a register machine that isn’t even in SSA form - both of the tools at our disposal to do optimisation are unavailable. In a true, optimising compiler we can recreate that information, but WebAssembly was already emitted by a compiler that generated that information once.

"Everything Old is New Again: Binary Security of WebAssembly" https://www.usenix.org/conference/usenixsecurity20/presentation/lehman… "WebAssembly Troubles" http://troubles.md/wasm-is-not-a-stack-machine/

I get the impression WASM is really a very clunky representation, far from what any greenfield project would ever have arrived at. That is to say, its decisions aren't just tradeoffs that people disagree about, they're simply inappropriate for what it's trying to do. More than once I've encountered comments and blog-posts lamenting its fundamentals, e.g. [0]. [0] http://troubles.md/wasm-is-not-a-stack-machine/

http://troubles.md/posts/why-do-we-need-the-relooper-algorithm-again/ "There is one thing that may have been a major factor to the decision not to adopt arbitrary CFGs for WebAssembly control flow. I believe that V8 is an exception to most compilers in that it doesn’t represent code as a CFG at all - it maintains roughly JS-compatible control flow all the way from front-end to codegen. In order to support this V8 would have to be converted to use CFGs, they’d have to implement something like Relooper internally, or they’d have to write a new WebAssembly runtime from scratch. Google was and is a major roadblock to getting this implemented as they have multiple people on the committee in charge of WebAssembly who have veto power."

If you can't watch the video, there's a blog post writeup of Lightbeam by the presenter here - http://troubles.md/posts/lightbeam/

One pretty annoying thing with WASM is that it is pretty hard to generate due to requiring a structured control flow so anyone generating it must implement relooper och stackifier. Is there any work on solving this issue? http://troubles.md/posts/why-do-we-need-the-relooper-algorithm-again/

http://troubles.md/posts/wasm-is-not-a-stack-machine/ wasm is already tainted by the legacy of javascript. It was intended as a replacement for asm.js and carries the burden of being too intended to be with javascript and as a way to get "faster javascript" due to how poor javascript is at executing efficiently. The result is what I'd consider a poor mans java bytecode. The legacy of java was bloat connected to the runtime and its massive standard library coupled with nasty Sun then Oracle burden. And Oracle again being Oracle with what feels like more more lawyers than engineers to threaten. So we tossed out a standard library and made a poor man's java virtual machine model. This is java again, it just has massive hype because its better than javascript at actually running efficiently. But it can still be worse than any given other virtual machines out there.

LLVM _is_ the backend for Mono. It's easier for LLVM to produce better code if it doesn't have to go via a register based bytecode VM like WebAssembly. Was discussed here not so long ago: http://troubles.md/posts/wasm-is-not-a-stack-machine/

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-algorithm-again/

WASM isn't particularly low-level, in that it's a compiler's IR, with a few concomitant restrictions on how control flow is allowed to work. Here's a piece on those restrictions, and how they make implementation more difficult: http://troubles.md/why-do-we-need-the-relooper-algorithm-again/ > WebAssembly isn’t designed as a front-end language for general programming though, so what’s the problem? Well, WebAssembly does have some constraints, specifically it must produce code that is valid. WebAssembly is a stack machine, and you can’t jump to just any label since that label might point to code that pops too many values off the stack, or pops the wrong types off the stack, or pushes too many values onto the stack. Also, to summarize another part, when a compiler targeting WASM sees control flow WASM can't directly express, it has to implement it in a loop-and-switch form, something called the Relooper algorithm; therefore, compilers taking WASM down to native code have to understand that, and undo it back into a performant form. This adds up to a lot of work most VMs don't require, hence the proposal to move WASM towards a control-flow model friendlier to tail-call optimization, which would bring it more in line with physical hardware.