WebAssembly techniques to speed up matrix multiplication
jott.live
jott.live
Another one I tried ages ago is to use a single loop counter and "de-interleave" the bits to get what would normally be 3 distinct loop variables. For this you need to modify the entry in the result matrix rather than having it write-only. It has the effect of accessing like a z-order curve but in 3 dimensions. It's a bit of overhead, but you can also unroll say 8 iterations (2x2x2) which helps make up for it. This ends up making good use of both caches and even virtual memory if things don't fit in RAM. OTOH it tends to prefer sizes that are a power of 2.
[0]: https://ocw.mit.edu/courses/electrical-engineering-and-compu...
I knew that the striding order benefits would only work on voxel data similar to the data I was testing on, and I wanted to generalize it so that it could be configured dynamically so each dataset could use the best striding order for that particular data. I tried setting up numpy ndarray so that you could configure the memory striding order independently of the array indices so that my code wouldn't have to change if the striding order changed, but I could never get it to work and unfortunately I wasn't able to convince numpy folks I interacted with that this feature would be helpful.
My question: will this kind of thing become more mainstream? I've seen the web emerge, go from static pages to entire apps being delivered and executed in the browser. The last bastion of native apps and libraries seems to be highly optimized algorithms but maybe those will also migrate to a deliver-from-the-web and execute in some kind of browser sandbox.
Java promised to deliver some version of native code execution but the Java app/applet idea never seemed to take off. In some ways it seems superior to what we have now but maybe the security concerns we had during that era held Java back too much. Or am I misunderstanding what WebAssembly can bring to the game?
'always' is certainly not true. Yes, with modern frameworks it is very easy to build websites which are slow. But it is also possible to build websites with butter smooth animations and instant responses.
I hope that in the future we will get frameworks that make it easier to create lightweight web apps, so that we will see more high performance apps.
One reason is the thread model. There are two main threads that need to be synchronized (browser main thread and JS main thread) which will always be slower than a single main thread.
Another reason is that layout and measurement of elements in HTML is really complicated. Native apps heavily encourage deferred measurement which lets the app measure and lay itself out once per render pass. In JavaScript, layouts may need to happen immediately based on what properties of the dom you’re reading and setting.
In general, 60fps is considered sufficient for smooth rendering and even 5 years ago, mobile hardware was fast enough for 60 fps web page rendering. However, many web pages a built in ways, that the browsers can't achieve that goal.
So yes, it is harder for developers to create a pleasant experience and as a result there are more bad apples in the web app basket.
Having said that, maybe a little less than 10 years ago, we achieved the desired performance with touch-screen dragging of DOM elements. I don’t remember specifics, but we didn’t use any frameworks.
How about a 240fps video of a 60Hz display, with 2 implementations
1. Qt
2. Web
Both times a finger dragging a slider from point A to point B?
Writing this out made me realize another limitation of the browser: the page unloads when navigating, so going “back” can be a pain / impossible depending on the circumstances.
However, you wrote that 'the page unloads when navigating' which made me wonder, how much you know about frontend development, because the pattern to prevent browsers from navigating is such a common topic and there are multiple solution patterns, all well understood by professional frontend developers:
- preventDefault
- return false
- use anchors
The 1000 item list is indeed a problem frontend developers have to be aware of. Modern flagship smartphones may have the capability to render such lists, but less powerful devices can't handle the load in a 60fps fashion. So you have to build list views that render only the visible part of the list. In the end, you have to do that anyway, because even for high-end devices there are limits to what they can show, but many web-components are not build with such scenarios in mind. And that is certainly one of the reasons why there are so many web apps with slow performance rendering.
Safari also generally uses a lot less memory and CPU for the same websites. Chrome in particular burns through my battery very quickly, and is basically completely incapable of keeping up with my browser use style (it just crashes when I try to open a few hundred tabs). Presumably nobody with authority at Google is a heavy laptop web-user or prioritizes client-side resource use: Google’s websites are also among the biggest browser resource hogs, even when sitting idle in a background tab.
Safari often takes a couple years longer than other browsers to implement cutting-edge features. This seems to me like a perfectly reasonable design decision; some web developers love complaining about it though, and some sites that were only developed against the most recent versions of Chrome don’t work correctly in Safari.
The browser can either dispatch the events asynchronously, leading to the events being handled in a noticeably delayed way, or the browser can block its main thread until the JS dispatch finishes, leading to fewer UI events being handled. Either way is an inferior experience.
Interestingly Safari is actually generally better than other browsers for running a responsive smooth UI. Not sure how much of that is the Safari engine and how much of it is better CPU on iPhones. But even on a first generation iPad or an iPhone 4 it was possible to get 60fps rendering fairly easily. The same could not be said for even higher end android phones of the time.
Sun/Java wanted badly to solve this problem, but tried to do too much too soon. Java gave devs in 1999 cutting edge OOP tools for doing GUIs (e.g. Swing) but distribution was always the problem. Installing and running browser plugins was always error prone, and it turned out the browser was itself just good enough to deliver value, so it won. (With the happy side-effect of giving the world-wide community of devs one of the gooeyist languages ever to express their fever dreams of what application code should be).
The question in my mind is whether there is enough demand for the kinds of software webasm enables, especially given that other routes of distribution (app stores) have filled in the gaps of what the web delivers, and are generally a lot more pleasant and predictable to native devs.
[1] https://en.wikipedia.org/wiki/Reduced_instruction_set_comput...
The real win here is when we can have both because of smart toolchains that can transform those high-level constructs and representations into the most efficient implementation for the hardware.
Posts like this demonstrate what's possible with the right optimizations so tools like compilers and assemblers are able to take advantage of these when given the high-level code. That way we can achieve what you're hoping for: the default being optimal implementations.
That's arguable at best. I for one am sick of 'developer productivity' being the excuse for why my goddamned supercomputer crawls when performing tasks that were trivial even on hardware 15 years older.
> The real win here is when we can have both because of smart toolchains that can transform those high-level constructs and representations into the most efficient implementation for the hardware.
That's been the promise for a long time and it still hasn't been realized. If anything things seem to be getting less and less optimal.
What you're "sick of" is mostly irrelevant unless you represent a market that is willing to pay more for a more efficient product. I use commercial apps every day that clearly could work a lot better than they do. But... would I pay a lot for that? No. They are too small a factor in my workday.
Saving money is part of engineering too.
No one I know has anything good to say about microsoft teams, for instance. And that's just one of the recent "dekstop apps" which are actually framed browsers.
The problem here is developer salaries. So long as developers are as expensive as they are the incentive will be to optimise for developer productivity over runtime efficiency.
It seems fairly reductive to dismiss the legitimate advantages of increased productivity. It's faster to iterate on ideas and products, we gain back time to focus on more complex concepts, and, more broadly, we further open up this field to more and more people. And those folks can then go on to invest in these kind of performance improvements.
Certainly there are some, but I think we passed the point of diminishing returns long long ago and we're now well into the territory of regression. I would argue that we are actually experiencing negative productivity increases from a lot of the abstractions we employ, because we've built up giant abstraction stacks where each new abstraction has new leaks to deal with and everything is much more complicated than it needs to be because of it.
[0] plenty of slow as fuck modern software doesn't handle it even close to 'flawlessly'
Come on now. Let's be honest here. The answer for >90% of projects is either a faster pace on new features, or to pocket the payroll savings. They'd never prioritize something that they've already determined can be ignored.
As far as I can tell, a slow computer is due to swapping from having a bunch of stuff open, or an inherently heavy background task and an OS that doesn't know how to allocate resources.
Sometimes there's some kind of network access bogging everything down, now that SASS is everywhere(In which case, we need more abstractions and developer productivity to enable offline work!).
Sometimes things are slow because we are doing a lot of heavy media processing. That's not inefficiency, it's just inherently heavy work. In fact, simplicity might actively slow things even more, because what you really need for that stuff is to use the GPU, and the "bloated mega library" you're avoiding might already do that.
Android is kind of the proof. Android is always pretty fast. Anything 15yo hardware could do trivially, Android can probably do faster. And Android is not lightweight.
There may be some slowness out there caused by abstraction layers, but as far as I can tell without digging into the code of every slow app I've ever seen, the real problem is the keep it simple mindset that discourages even basic optimization tricks like caching, and the NIH that makes people write things themselves and assume it's faster just because it's smaller.
Plus, the UNIXy pipeline mentality that did a number on computing. GUI workflows are not pipelines and there's lots of things that are very messy to do in a pipe style model, like changing one thing and selectively recomputing only what needs changing.
The "Data processing" way of thinking leads to producing a batch of stuff, then passing it to something that computes with it, instead of working directly with a state.
Did the software to perform those tasks stop working?
The GFLOP/s is 1/28th of what you'd get when using the native Accelerate framework on M1 Macs [1]. I am all in for powerful abstractions, but not using native APIs for this (even if it's just the browser calling Accelerate in some way) is just a huge waste of everyone's CPU cycles and electricity.
[1] https://github.com/danieldk/gemm-benchmark#1-to-16-threads
I do agree that we'd get fantastic performance out of our systems if we had the important layers optimized like this (or more), but it seems few (if any) have been pushing in that direction.
Spotify is slower to launch on my Ryzen 3900X than my operating system, and lacks many of the basic features that WinAmp had in 1998. Now you're thinking "Aha! But WinAmp just played mp3s, it didn't stream over the internet!", Yes it could. It was also by large developed by one guy, over the course of a couple of months.
I don't know where this superior developer productivity is going, but it sure doesn't seem to be producing particularly spectacular results.
As this was a group project, there were other hands on deck. One weekend I caught a nasty cold and I couldn't assist the weekly meeting to work on the project. Monday comes and we have to show our advances. The code was butchered. It took me a day to fix what had been broken (and keeping egos at bay, it would've been easier to just throw everything away and implement things from my last stable version).
Now I can fire up python, import numpy and scipy, and make far more complex simulations in a couple of minutes and a few lines of code. Sure, back then python and numpy did exist, I just didn't know about them. But you know what didn't exist 10-15 years ago? Pytorch, TensorFlow, JAX and all the deep learning ecosystem (probably scikit-learn did exstist, it's been around forever!). Thanks to those, I can program/train deep learning algorithms for which I probably wouldn't be able to code the lower-level abstractions to make them work. JAX comes with a numpy that runs on hardware "for free" (and there was PyCUDA before that if you had a compatible GPU).
That's the programmer productivity you're not seeing. Sure, these are very specific examples, but we have many more building blocks available to make interesting things without having to worry about the lower layers.
You can also complain about Electron being a bloated layer, and that's OK. There's your comparisson about how Spotify is slow and Winamp is/was fast.
How often are you actually launching spotify? I start it once when I boot and that's it until my next reboot, weeks/months later.
Now you might of course ask, "why isn't the velocity 6554x that of winamp, even when correcting for non-eng staff, management, overhead, etc". Well, they probably simply aren't allocating that much to the client development.
Also often times one dev who knows exactly what he is doing can be way more effective than a team; no bikeshedding, communication, PRs, etc. What happens when they get hit by a bus?
I agree that the software layer has become slow, crufy, bloated, etc. But it's still cheaper to get faster hardware (or wait a bit for it, see M1, Alder Lake, Zen 3, to name a few, and those are getting successors later on this year) than to get a good programmer to optimize your code.
And I know that we'd get much better performance out of current (and probably future) hardware if we had more optimized software, but it's rare to see companies and projects tackle on such optimization efforts.
Everything has a cost. If the developer is a slave to machine architecture, development is slow and error prone. If the machine is a slave to a abstraction, everything will run slowly. Unsurprisingly, the real trick is finding appropriate balance for your situation.
Of course you can make things worse, in both directions.
Let's say I want to interactively plot some complicated function without slowing down the rest. Can I do this in WebAssembly now?
You've been able to do that for a while now and it would likely be fast enough even in pure JavaScript. The things which tend to slow the web down come back to developers not caring about performance (and thus not even measuring) or the cross-purposes of things like ad sales where a significant amount of JavaScript is deployed to do things the user doesn't care about.
In addition, browsers have to fight all kinds of nefarious attackers, so it is a very hostile environment to develop in. For example, we can't even measure time accurately (or do proper multithreading with shared memory) in the browser thanks to the Spectre and Meltdown vulnerabilities. https://meltdownattack.com/
That being said, WebGL implements extremely gimped shaders. Yet, they are still more than enough to render all kinds of functions. For example, see https://www.shadertoy.com/ or https://glslsandbox.com/ which are huge collections of functions which take screen coordinates and time as input and compute pixel colors from that, i.e. f(x, y, t) -> (r, g, b). This might sound not very impressive on first glance, but people have been amazingly creative within this extremely constrained environment, resulting in all kinds of fancy 3D renderings.
Yep, with a Web Worker for the secondary thread. However the environment is still young and its' difficult to use heavy computation libraries. Besides for some reason SIMD instructions are present only for 128 bit units (2 doubles or 4 floats). Another problem is no matter what to do it is a layer over the hardware, so it will be slower than specialized machine code (if what you do is not in the JS API)
what do you mean? What's the blocker? Something like numpy for js would fill this role, calling wasm in the background. Just the missing SIMD-instructions? Some quick googling shows that one can't compile BLAS for wasm yet. This might be due to wasm64 not being available yet, i think? So would this help to tap into the existing ecosystem of optimised mathematical routines?
Ideally...I would leave js and just use python ;) It has the whole ecosystem at hands with numpy, scipy, statsmodels etc. But nobody is doing it and idk why. I think it might be due to fortran not compiling to wasm.
About numpy for js I believe js is still not comfortable enough for this kind of use, especially with the lack of operator overloading.
Anyway there are some builds of BLAS (or equivalents) to wasm and even of python. Check out pyodide and brython
If you can draw your plot in a shader then you can do it in WebGL very easily. You'd only need to update the input uniforms and everything else would happen on the GPU.
Which wouldn't be a bad thing
See also the history of Atlas, GotoBLAS, Intel MKL, etc.
Some benchmarks I've done has it beating out CUDA on my RTX 2070. I have to got a proper gflops number though
https://github.com/danieldk/gemm-benchmark#1-to-16-threads
tl;dr, the M1 can do ~1300 GFLOP/s and the M1 Pro up to ~2700GFLOP/s.
On the vanilla M1, that's 28 times faster than the best result in the post.
The difference (besides years of optimizing linear algebra libraries) is that Accelerate uses the AMX matrix multiplication co-processors through Apple's proprietary instructions.
Of course usually BLAS beats EIGEN, but for small, known-sized matrices, it might have a chance.
The issue is that threaded execution requires cross-origin isolation, which isn't trivial to integrate. (Example server that will serve the required headers: https://github.com/bwasti/wasmblr/blob/main/thread_example/s...)
Why not just compile OpenBLAS or another computer numerics library like that to WA?
46.78 GFLOP/s is not even that great on non-specialized hardware. E.g., a Ryzen 5900X, can do ~150 GFLOP/s single-threaded with MKL.
[1] https://github.com/danieldk/gemm-benchmark#1-to-16-threads
Unfortunately, the bar graphs at the bottom of the article have different y-axis scaling, but even so:
It's sad how Firefox' performance pales in comparison to Chrome.
Section baseline: What are N, M, K? 3 matrices or? Laid out as a flat array, or what? `c[m * N + n] += a[m * K + k] * b[k * N + n];`, ah, apparently a b and c are the matrices? How does this work?
Section body: What is the mathy "C′=αC+A⋅B"? derivative of a constant is the angle times the constant plus the dot product of A and B???
Please, if you write a public blog post, use your head. Not everybody will understand your terse notes.
Laying out matrices like that is pretty standard, especially for a post about vectorization.
Section baseline: What are N, M, K? 3 matrices or? Laid out as a flat array, or what? `c[m * N + n] += a[m * K + k] * b[k * N + n];`, ah, apparently a b and c are the matrices? How does this work?
Section body: What is the mathy "C′=αC+A⋅B"? derivative of a constant is the angle times the constant plus the dot product of A and B???
They are laid out, rather than nested arrays, as a single continuous collection of bytes that can be interpreted as having a matrix shape. That's where the `m * N + n` comes from (m rows down and n cols in)
C' = alpha C + A.B
JavaScript code is readable, at least.
Not trying to sound dismissive here but the core math the post is working with is actually a pretty straightforward matrix multiplication.
The bulk of the discussion focuses on optimizing the execution of that straightforward multiplication algorithm [triple-nested for loop; O(n^3)] rather than making algorithmic/mathematic optimizations.
And again, specific questions are easier to answer. :)