Speeding Up the Webcola Graph Viz Library with Rust and WebAssembly
cprimozic.net
cprimozic.net
The thing about optimization work is that it's incredibly addicting once you get into it. Seeing consistent, measurable improvement and watching the frame times shrink is so satisfying, plus the process itself is really enjoyable in and of itself.
I definitely agree that the optimizations here are overkill for the actual application itself. However, it served as a great learning experience for me personally and allowed me to write this blog post as well!
While this might be a bit overkill, I wish more developers spent at least 10% as much effort as here, the modern world of software really feels bloated often. The core engines are getting faster and the cpus are getting faster but the web feels slower.
And another important factor is that more and more software runs on battery powered portable devices in some form. Instructions saved is battery saved = happier users :)
I'd be amazed to see what this level of profiling skill could do on a fancier algorithm.
The SIMD spec is quite lacking. Many algorithms take advantage of the chips ability to do multiple things at once in one instructions. Rounding, saturation, and truncation are the main ones I see that wasm does not support out of box, and you have to emulate them. Minus add_sat, that one does saturation.
So far aarch64 is lovely to port, but x86 is terrible. As noted in OP's blog here one single f64.max instruction ends up being 5-6 instructions on x86. While aarch64 and armhf just package it in a singular instruction.
I hope there is more work being done to remedy this so we can bring more algorithms at great performance in the browser. compiler work is above my abilities currently.
If you are interested to bring more SIMD instructions, you can participate in the SIMD subgroup. What's needed is interest in suggesting new instructions, working on a proposal (following the process) and pushing it through. Compiler expertise not required :)
for (i=0; i<...; i++) {
this.g[i][u]...
H[i][u][v]...
If this can be inverted to:
this.g[u][i]...
H[u][v][i]...
The rust code may have the same potential since it's iterating `array[i*n+...]` and `array[i*n*n...]` in a few places.
i've done my share of optimizations and benchmarking of various charting libs [1] but this goes deeper still.
SVG is not a good choice for large raw datasets when you need performance.
I'll definitely be trying out uPlot for my next project - those performance metrics are stunning!
[1] https://developer.mozilla.org/en-US/docs/Web/API/OffscreenCa...
The sprites also look janky when zooming in, because they remain low res.
In physics simulations when we're dealing with the distance formula we often just skip the square root part. This works if you're dealing in relative distances. I bet this algorithm could skip the sqrt altogether.
There are components of it like this:
2. * weight * (distance - ideal_distance) / (ideal_distance_squared * distance)
Looking at the perf metrics for the full function's disassembly[2], square root-related instructions only account for a tiny amount of the program's runtime anyway.
That all being said, thank you so much for taking the time to read the post closely enough to come up with this idea!
[1] https://github.com/Ameobea/webcola-wasm/blob/master/src/wasm... [2] https://ameo.link/u/91u.html
let gs =
2. * weight * (distance - ideal_distance) /
(ideal_distance_squared * distance);
let distance_cubed =
distance_squared * distance;
unsafe {
*self.g.get_unchecked_mut(
i * n + u) += distance * gs };
}
let hs =
2. * -weight /
(ideal_distance_squared * distance_cubed);
let idk = hs
* (2. * distance_cubed
+ ideal_distance * (distance * distance - distance_squared));
(distance * distance - distance_squared) =
(distance_squared - distance_squared) = 0
in the same spirit of the above comment, the webcola core seems to be doing O(n^2) comparisons. probably somewhere in the top 10 for cool foundational scientific computing algorithms that people like here are barnes hut, which cuts the comparisons to O(n log n), and fancier, fast multipole. basically, no need to precisely compare far apart things, which are most of them. by the time of something like interactive UIs over 100K+ nodes, the asymptotics costs start dominating everything, and 2-8X C/SIMD speedups get overwhelmed if you don't scale the core alg. this is at the heart of many modern ML algorithms as well: many need to iteratively compare vectors, such as knn and umap.
pretty neat as well is that barnes hut + multipole are also SIMD friendly, and even better, GPU friendly. it is a bit trickier b/c now dealing with ideas like SIMD/GPU tree construction, but still works! for graphistry, our engine prototype had a multicore wasm frontend impl, gpu webcl frontend impl, and gpu opencl backend impl, and just by adding that, got some pretty cool #'s. nowdays we do a bit wilder and focus more on other layers like interactive analytics, bigger-than-memory, connectors/collaboration/embedding/etc, but all are logical steps building on what is being described here. bravo!
edit: it's good the blogpost included rendering. rendering gets pretty fun with graphs b/c while points are ~easy, edges get at (a) dynamic geometry (b) that can span the screen and (c) blow up in count pretty quick. ouch! the pathfinder project for vector text rendering is a fun related effort for what it takes to speed that up with simd/gpu. if someone is interested in a webgl contract around helping our users explore bigger interactive graphs (webgl/react client <-apache arrow-> python/CUDA server), ping build@graphistry.com !