Replacing JavaScript Hot Path with WebAssembly
developers.google.com
developers.google.com
for (var y = 0; y < height; y++)
for (var x = 0; x < width; x++)
b[x + y*width] = a[y + (width - 1 - x)*height];
Although that's still far from the theoretical maximum throughput because the cache utilization is really bad. If you apply loop tiling, it should be even faster. This problem is closely related to matrix transpose, so there is a great deal of research you can build upon.EDIT: 0.07 seconds with loop tiling:
for (var y0 = 0; y0 < height; y0 += 64){
for (var x0 = 0; x0 < width; x0 += 64){
for (var y = y0; y < y0 + 64; y++){
for (var x = x0; x < x0 + 64; x++){
b[x + y*width] = a[y + (width - 1 - x)*height];- Move the "y * width" calculation outside of the "for x" loop.
- The multiply operators can be replaced with addition e.g. replace "y * width" with "counter += width" each y iteration and similarly for the x loop.
Optimising inner loops is really fun.
How much of the speed up in the article is because the JS engine can't figure out how to optimise it compared to the WebAssembly compiler?
EDIT: But it could also be that your computer is somewhat faster than theirs? Do you happen to have some very fast CPU? Can you say which? When I run C-like C++ versions of your code I get the speeds you get with node.js. However, you made overall much better results than they were able, it's still great work!
#include <stdio.h>
int main(int argc, char* argv[]) {
enum { height = 4096, width = 4096 };
unsigned* a = new unsigned[ height*width ];
unsigned* b = new unsigned[ height*width ];
if ( argc < 2 ) { // call with no params
// to measure overhead when just allocations
// and no calculations are done
printf( "%d %d\n", (int)a, (int)b );
return 1;
}
if ( argv[1][0] == '1' ) // call with 1 the fastest
for (unsigned y0 = 0; y0 < height; y0 += 64)
for (unsigned x0 = 0; x0 < width; x0 += 64)
for (unsigned y = y0; y < y0 + 64; y++)
for (unsigned x = x0; x < x0 + 64; x++)
b[x + y*width] = a[y + (width - 1 - x)*height];
else
for (unsigned y = 0; y < height; y++)
for (unsigned x = 0; x < width; x++)
b[x + y*width] = a[y + (width - 1 - x)*height];
return 0;
}https://stackoverflow.com/questions/5200338/a-cache-efficien...
But note that robko made an improvement even before making that.
Or maybe not: my short experiments with the simplified version based on their algorithm and his JavaScript versions gave some conflicting results. I haven't thoroughly verified them, this note is just to motivate the others to try.
OK, I get cca 80ms for my run with the parameter 1 on my main computer, and 200ms on N3150 Celeron.
> b is not used after being calculated
Earlier, I've never seen that any C compiler optimizes away the call to the allocator and the access to the so allocated arrays. Maybe it's different now? Hm, dead code elimination... I guess a random init of the few values before and read and print of a few values after the loop must be always safe... Now that I think, also filling the array with zeroes before.
Seems like a tricky goal for image algorithms in general where you're performing the same action over and over on millions of pixels. Obscure inner loop optimisations are pretty much required.
In these situations, I would sometimes keep the code for the naive but slow version around next to the highly optimised but difficult to understand version. You can compare the output of them to find bugs as well.
Why would non-1 for loop be slower in some browsers? Does the compiler add some sort of prefetch instruction in the faster browsers based on the loop increment?
My guess is that if you try to invoke initial whole code (before tiling) in a external loop (rotating images of exactly the same size), you will get similar perf boost (not that it has practical implication, but just to understand how optimization works).
WASM example would speed up as well using the same approach. Or C, Rust or whatever.
(Stride detecting prefetch can help, especially on the first iteration of a tile, but is not required for a speedup).
BTW this is the motivation for GPUs (and sometimes other graphics applications) using "swizzled" texture/image formats, where pixels are organised into various kinds of screen-locality preserving clumps. https://fgiesen.wordpress.com/2011/01/17/texture-tiling-and-...
I’ll definitely give tiling a spin (although at this point we are definitely fast enough™️)
Chrome: 248 ms vs 93 ms
Firefox: 552 ms vs 93 ms
MS Edge: 7486 ms vs 6186 ms
IE: 9590 ms vs 9156 ms
These are some WTF results, to be honest.
This is a cool technique but I can just imagine the looks on my team mates faces when I tell them it isn't react... :/
User robko here https://news.ycombinator.com/item?id=19167078 measured the code on node.js, and node.js is based on Chrome's V8 and he measured 1.5 sec vs article author's of around 2.7s, so it would seem that robko has some almost twice as fast CPU, and the other two (fast) JavaScripts are under 500 ms, and the slowest is 8 seconds, so V8 of Chrome remains the only candidate for the second worst performing of their example.
1) https://developer.mozilla.org/en-US/docs/Web/API/Performance
>Note: Due to legal concerns, I won’t name any browsers in this article.
Even worse if it were a pretext to not make Chrome look bad.
https://mrale.ph/blog/2018/02/03/maybe-you-dont-need-rust-to...
For very large values of "single", approaching "two". In the "Speed comparison per language" chart, Browser 3 is more than 5x slower than Browser 2 on JavaScript/WASM, and Browser 4 is slower still. So there are very significant improvements on two out of the four browsers tested.
Another factor is also that the WASM compilers for various languages (Rust, C/C++, etc) are obviously recent too and not super optimized.
My own tiny experiment is that WASM can already yield quite decent performance gain but with very compute intensive load, which is not a typical problem in frontend development. The size gain is also real, but you need to handcraft your WASM or forget about using the std and other stuff in the language you are compiling from (Rust generate very fat binary with a naïve implementation for example).
Still, I am quite optimistic about WASM. I was actually impressed that, even though it is quite recent, I can already compete with JS when it come to performance. When the various performance-related spec will be finalized and implemented and that browsers and compilers start heavily optimizing the WASM, we should really see some real-world gain.
https://github.com/alangpierce/sucrase/issues/216
So really, it depends a lot on the use case. In my case, it's often a short-lived node process that a user is directly waiting on, so compiling to wasm is probably useful. It also depends on what you're doing; some types of work (e.g. where you'd want careful memory management) are a lot harder for V8 to optimize from JS and can be expressed more nicely in AssemblyScript or another language that gives more memory flexibility.
You probably won't get 100x faster without SIMD, but 10x is certainly doable. Unfortunately, SIMD.js support has been removed from Chrome and Firefox a while ago, even though it is not available in wasm to this day.
Using their code on my Intel-based workstation at around 3ghz using GCC 7.3 it takes around 80-100ms to rotate a 4096x4096 buffer 90 or 270, and 14ms to rotate 180.
Max memory bandwidth of something like an i9-9900k is 41.2GB/s. This test reads & writes 128mib of data. So max theoretical achievable performance here is around 3-4ms. Max theoretical. So 100x is not really feasible. 10x, though, very much is, as the quick convert shows a peak time of 14ms with a 180* rotation.
Of course the major source of slowness here is that the reads/writes are not sequential, and the 90 & 270 rotations are achieving a fraction of the possible bandwidth they could as the input reads are jumping around, so every single one is a cache miss and the other 60 bytes in each cache line on the miss will be purged before it's used again.
Flipping it would mean the writes are never utilizing a full cache line, either, though. So you can't really "fix" that, not easily at least. So either your read or write bandwidth ends up tanking and you can only achieve roughly 6% of the max (only ever using 4 bytes of the 64-byte cache line) for that half of the problem. Without some clever magic to handle this your max theoretical on a 41.2GB/s CPU drops to around 50ms.
All that said it's clear that WASM is very far off from native levels of performance. ~5x slower isn't something to brag about. But hey maybe the test system was a potato, and the 500ms isn't as bad as it sounds.
But I get that really this was a how much can wasm help performance as % vs js - you could always write an “optimized” routine and compare those and theoretically achieve something similar.
That’s why there so much work being put into giving wasm a more typical (for a vm) typed heap. Similar issues occur with lifetime of objects - if you get anything from the dom, you have to keep it live if wasm references it, but wasm has no idea of what memory or a handle is.
These are solvable problems, but you’re not getting dom access until after they’re solved.
Because the wasm memory model doesn’t have typed memory - if you call a dom api and get a handle back, you need to store it. Then you need to be able to pass it back to the host vm.
So now your wasm code needs to make sure the handle stays live - wasm by design doesn’t interact with the host GC, so you have to manually keep the handle alive (refcounting apis or whatever), and the host VM has to have someway to deal with you trying to use the handle without having kept it alive.
Similarly because wasm is designed around storing raw memory in the heap the wasm code can treat the handles as integers. Eg an attacker can just generate spoof handles and try to create type-confusion bugs, or maybe manually over release things.
So the problem isn’t “how do we let wasm make these calls” but rather “how do we do that without making it trivially exploitable”.
Those that aren't have an extremely limited API - that would be logically not dissimilar from "untrusted wasm talks to more trusted JS".
https://github.com/WebAssembly/reference-types/blob/master/p...
https://github.com/WebAssembly/reference-types/blob/master/p...
https://hacks.mozilla.org/2018/10/webassemblys-post-mvp-futu...
> WebAssembly on the other hand is built entirely around raw execution speed. So if we want fast, predictable performance across browsers for code like this, WebAssembly can help.
So i wanted to see how i could use WebAssembly in a React webapps. I found this SO question sees the opposite:
> When running this [ WebAssembly] code in Chrome, I observe "pauses" that cause the app to be a bit jittery. Running the app in Firefox is a lot faster and smoother.
https://stackoverflow.com/questions/53584607/react-app-with-...
Same code, different browser, different performance. I'd love seeing a Google Developer answering that question in depth..
Shouldn't WA as a greenfield project with it's extremely basic memory model and lack of runtime or standard library be super easy to optimize?
After all, there is no point in having the bad ergonomics of assembly together with the awful performance of JS, right?
V8 has received decades of optimizations and it can easily compete with compiled languages in terms of speed.
I was hyped to death for WASM , but this is the tenth article I’m reading on this subject and I still ending on the same conclusion : there is no advantage for front end developers to use WASM.
Only Rendering Engine ( Unity , Adobe Products, Autodesk ) can really benefits from this.
> This confirms what we laid out at the start: WebAssembly gives you predictable performance. No matter which language we choose, the variance between browsers and languages is minimal
If you're not hyped about WASM, it's probably because your app and customer base's browser preferences are on the js engine's JIT happy-path, which could hold true for most apps. There could very easily be a js path that is significantly worse in performance on chrome, just saying, 70% market share is both a blessing and a curse.
Another major reason for WASM hype is for C#, Rust, C, C++, Go devs to reach parity with js in terms of web accessibility. Frameworks like Blazor (from MSFT) have taken all the best practices & advantages of React and made them available to C# devs.
The irony is that C# devs were the first to use reactive programming before React even existed.
This view seriously needs to die. It's honestly not that hard to test in two or three browsers, and the differences are minor enough that it isn't a pain. But the only way that's possible is through Web standardization, which only happens when there are diverse options.
As web developers, it's our duty to keep the web healthy, and that means not only optimizing for a single browser.
It needs to be repeated: at the time IE /was/ a good browser. Just like chrome today. And similar to chrome played fast and loose with web exposed features. Sometimes for the better (XHR was an IE invention), sometimes for worse (so was activeX).
Wasn't XMLHttpRequest an ActiveX object?
Standards are not about “anyone can just use that implementation” they are about “anyone can make a competing implementation”.
Looking at the sources is not a specification.
People only caring about one browser is exactly what caused ie6 to become such a problem - everyone had to reverse engineer whatever it was doing because nothing was specified.
No, IE would need be to be open source for that logic to be applicable there, since the idea is to use a well-developed open source code base instead of rolling your own thing.
> or it was a waste of time for webkit to exist as there was already khtml, or blink because webkit,
You actually undercut your own point with these examples: WebKit was a fork of KHTML, Blink was a fork of WebKit. The developers in question believed that it would have been a waste of time to start from scratch, and so they didn't!
This post is saying you only need to test chrome because it’s 80% of the market. Back in the day IE was more than 90% of the market.
If all you do is test on chrome you force every competitor to reverse engineer chrome (you can’t fork chrome to make a gpl browser). Alternatively you give up and just use chrome (skinned or not), and that dictates the features you get (I don’t see chrome getting built in tracker blocking any time soon).
You can’t use alternative browsers because the web is filled with sites that are only tested on chrome.
Congratulations you have recreated IE.
For example there was this app in C# that would convert images into 512 color palette and use dithering to retain some quality. I made a version in the browser, but because of js being too slow it didn't work for large images. Thing is, mine was far safer and accessible than the C# program.
Where it would be needed most
The logo on the front page you linked it the logo of Microsoft's other browser, Edge. There is no other mention of Microsoft or Internet Explorer on it.
But IE 11 has been given a stay of execution until 2025 I believe.
And sadly most of my users are still on it (government and healthcare)