Wow, that dominator tree algorithm I wrote as an intern (https://bugzilla.mozilla.org/show_bug.cgi?id=666426) seems to have lasted 13 years! At the time we assumed that graphs would be small enough to not warrant the constant factor against Lengauer-Tarjan. ...And of course, browser-based apps have gotten much bigger since then.
Semi-NCA hadn't even been published yet and seems like the clear choice nowadays, so I'm glad to see it in place! Great work!
Safari seems slightly faster in all benchmarks. I did not run motionmark because it takes forever :-/. The page says JetStream2 is what you want if you want to benchmark wasm.
How this relates to TFA, no idea ... is not really easy to tell which version of SpiderMonkey is running on the installed Firefox.
Spidermonkey just follows Firefox version numbering, so far as I know, and the linked bugs in the article seem to have landed in a mix of the 132 and 133 milestones, so you'll have to wait a couple of release cycles for the full effect.
Is there any AOT WebAssembly compiler that can compile Wasm used by websites? I tried locally compiling the Photoshop Wasm module mentioned in the article but the compilers I tried (Wasmtime, wasm2c, WAMR) all complained about some unsupported Wasm extension/proposal being required (exceptions seems like the blocker on wasmtime, and the others gave cryptic error messages).
Is it really the case that browsers have default-enabled all sorts of extensions that are not yet widely supported by the rest of the ecosystem?
> Is it really the case that browsers have default-enabled all sorts of extensions that are not yet widely supported by the rest of the ecosystem?
I don't know the answer, but it would be hard to blame them for following normal browser development practices on the standard they created for the purpose of being in browsers.
Fair enough. I think it would be unfortunate if the WebAssembly language in browsers were a significantly different language than WebAssembly outside of browsers (just referring to language itself, not the overall runtime system). I don't think that has quite happened, and the outer ecosystem can probably catch up, but it worries me.
Non-browser environments are a little behind on the Wasm standard, but not by much. E.g. wasmtime has now landed support for Wasm GC. AFAIK they implement all phase 4 proposals. Wizard implements all the Phase 4 proposals as well. The Wasm 3.0 spec will be out soon, which will be a big milestone to motivate Wasm engines outside the Web to catch up.
No, I think most of the AOT compilers in practice are a bit behind V8 and/or Spidermonkey for newer features. Realistically, most development driving new WASM features is motivated by website-ish use cases. Exception handling in particular is still not standardized so I guess it's expected that the browser engines would be the one to have the most evolving support (and the ability to test it thoroughly) because people want that platform as their inevitable target anyway.
> Is there any AOT WebAssembly compiler that can compile Wasm used by websites?
This doesn't really make sense, given that the wasm used by websites is going to import a bunch of JS functions as dependencies. You're not going to have those available in any native environment.
> Is it really the case that browsers have default-enabled all sorts of extensions that are not yet widely supported by the rest of the ecosystem?
Yes
Photoshop in particular is a good example of a bleeding edge wasm app - browsers had to relax restrictions on things like function pointer table size in order for it to work. So I wouldn't expect it to build and run anywhere outside of v8 or spidermonkey.
I think one of the interesting aspects of WebAssembly compared to JavaScript is that it can be efficiently AOT-compiled. I've been interested in investigating AOT compilation for a browser (perhaps there is a distant/alternative future where web browsing does not require a JIT), but maybe Wasm AOT compilers aren't really there yet.
Functionally what browsers do under the hood is AOT compilation but not in the way that i.e. Wasmtime is. The following is my knowledge that may no longer be accurate, but this is the sort of model we planned for when designing WASM to begin with:
Browsers do a on-demand 'first tier' compilation for fast startup, and in the background using threads they do a high quality AOT compilation of the whole module. That high quality AOT compilation is cached and used for future page loads.
It is possible to use a JIT model for this but AFAIK it is typically not done. In some configurations (i.e. lockdown mode) WASM is interpreted instead of AOT compiled.
> It is possible to use a JIT model for this but AFAIK it is typically not done.
Isn't this what the last line of the article is hinting at?
> our WebAssembly team is making great progress rearchitecting the Wasm compiler pipeline. This work will make it possible to Ion-compile individual Wasm functions as they warm up instead of compiling everything immediately.
It's definitely the case that in many scenarios, the right data structure is an array, since you'll have work dominated by gets and sets.
However, the OP has one scenario where the opposite was true - they were using a dense bitset that needed to be obscenely huge because of degenerate code in the wasm module, so swapping to a sparse container was a win.
In the end you just have to profile and understand your data.
To your point, profile your data as you would your code.
A sorted array of bit locations would represent a sparse bit set well enough to start, with O(N) storage and O(log N) access. Once the sets became large and/or dense, another data structure could be considered.
Wow, that dominator tree algorithm I wrote as an intern (https://bugzilla.mozilla.org/show_bug.cgi?id=666426) seems to have lasted 13 years! At the time we assumed that graphs would be small enough to not warrant the constant factor against Lengauer-Tarjan. ...And of course, browser-based apps have gotten much bigger since then.
Semi-NCA hadn't even been published yet and seems like the clear choice nowadays, so I'm glad to see it in place! Great work!
> extremely large functions > quadratic behavior
*High five*
I fixed several of these during my time as a compiler engineer too.
It's true what they say, quadratic is the worst possible time complexity. Fast enough to work on all your test cases, slow enough to explode in prod.
In modern times I seldom reach for a linked list... cache friendly data structures almost always win.
If anyone have a comparison with V8 that would be great!
Not sure what kind of comparison you mean, but you can compare desktop browsers with [1].
I just ran it on my mac M2 Max and got:
Safari seems slightly faster in all benchmarks. I did not run motionmark because it takes forever :-/. The page says JetStream2 is what you want if you want to benchmark wasm.How this relates to TFA, no idea ... is not really easy to tell which version of SpiderMonkey is running on the installed Firefox.
--
1: https://browserbench.org/
Spidermonkey just follows Firefox version numbering, so far as I know, and the linked bugs in the article seem to have landed in a mix of the 132 and 133 milestones, so you'll have to wait a couple of release cycles for the full effect.
https://arewefastyet.com/ has various comparisons between Firefox and Chrome, the script oriented ones are basically Spidermonkey vs V8
Is there any AOT WebAssembly compiler that can compile Wasm used by websites? I tried locally compiling the Photoshop Wasm module mentioned in the article but the compilers I tried (Wasmtime, wasm2c, WAMR) all complained about some unsupported Wasm extension/proposal being required (exceptions seems like the blocker on wasmtime, and the others gave cryptic error messages).
Is it really the case that browsers have default-enabled all sorts of extensions that are not yet widely supported by the rest of the ecosystem?
> Is it really the case that browsers have default-enabled all sorts of extensions that are not yet widely supported by the rest of the ecosystem?
I don't know the answer, but it would be hard to blame them for following normal browser development practices on the standard they created for the purpose of being in browsers.
Fair enough. I think it would be unfortunate if the WebAssembly language in browsers were a significantly different language than WebAssembly outside of browsers (just referring to language itself, not the overall runtime system). I don't think that has quite happened, and the outer ecosystem can probably catch up, but it worries me.
Non-browser environments are a little behind on the Wasm standard, but not by much. E.g. wasmtime has now landed support for Wasm GC. AFAIK they implement all phase 4 proposals. Wizard implements all the Phase 4 proposals as well. The Wasm 3.0 spec will be out soon, which will be a big milestone to motivate Wasm engines outside the Web to catch up.
No, I think most of the AOT compilers in practice are a bit behind V8 and/or Spidermonkey for newer features. Realistically, most development driving new WASM features is motivated by website-ish use cases. Exception handling in particular is still not standardized so I guess it's expected that the browser engines would be the one to have the most evolving support (and the ability to test it thoroughly) because people want that platform as their inevitable target anyway.
> Is there any AOT WebAssembly compiler that can compile Wasm used by websites?
This doesn't really make sense, given that the wasm used by websites is going to import a bunch of JS functions as dependencies. You're not going to have those available in any native environment.
> Is it really the case that browsers have default-enabled all sorts of extensions that are not yet widely supported by the rest of the ecosystem?
Yes
Photoshop in particular is a good example of a bleeding edge wasm app - browsers had to relax restrictions on things like function pointer table size in order for it to work. So I wouldn't expect it to build and run anywhere outside of v8 or spidermonkey.
I think one of the interesting aspects of WebAssembly compared to JavaScript is that it can be efficiently AOT-compiled. I've been interested in investigating AOT compilation for a browser (perhaps there is a distant/alternative future where web browsing does not require a JIT), but maybe Wasm AOT compilers aren't really there yet.
Functionally what browsers do under the hood is AOT compilation but not in the way that i.e. Wasmtime is. The following is my knowledge that may no longer be accurate, but this is the sort of model we planned for when designing WASM to begin with:
Browsers do a on-demand 'first tier' compilation for fast startup, and in the background using threads they do a high quality AOT compilation of the whole module. That high quality AOT compilation is cached and used for future page loads.
It is possible to use a JIT model for this but AFAIK it is typically not done. In some configurations (i.e. lockdown mode) WASM is interpreted instead of AOT compiled.
> It is possible to use a JIT model for this but AFAIK it is typically not done.
Isn't this what the last line of the article is hinting at? > our WebAssembly team is making great progress rearchitecting the Wasm compiler pipeline. This work will make it possible to Ion-compile individual Wasm functions as they warm up instead of compiling everything immediately.
Moral of the story:
First, use an array. If an array doesn't work, try something else.
It's definitely the case that in many scenarios, the right data structure is an array, since you'll have work dominated by gets and sets.
However, the OP has one scenario where the opposite was true - they were using a dense bitset that needed to be obscenely huge because of degenerate code in the wasm module, so swapping to a sparse container was a win.
In the end you just have to profile and understand your data.
To your point, profile your data as you would your code.
A sorted array of bit locations would represent a sparse bit set well enough to start, with O(N) storage and O(log N) access. Once the sets became large and/or dense, another data structure could be considered.
It's too bad the title prefix "75x Faster" got dropped.