Accelerated computations with WASM

[cshaa]

WebAssembly is a mature technology by now, which provides a significant performance boost to many web-based applications. Although a major undertaking, it might be beneficial to implement a WASM acceleration layer for math.js.

Original discussion in #2212 (reply in thread):
@m93a: Off-topic, but regarding WASM: don't you think it would be great to have some computation-intensive algorithms of math.js ported to WASM? If we used something like AssemblyScript for those, we could even provide two identical builds – one for modern environments with WASM and another in pure JS for legacy/restricted environments. This could give math.js a massive performance boost.

@gwhitney: Yes, I totally agree that for mathjs and/or its better successor you envision to be a "serious" compute engine, it would be best to write e.g. the guts of matrix algorithms in something like AssemblyScript. On the other hand, there have been projects like the (outdated) https://github.com/waylonflinn/weblas, so it seems to me that there will be some BLAS implementation in the browser we can just leverage... I don't much fancy porting it myself.

@m93a: Regarding the GPU-accelerated BLAS library, I would rather wait for the WebGPU standard to settle first. Computations on the GPU sound like the next logical step after having a WASM acceleration layer, as only highly parallelizable code would benefit from being run on the GPU, while virtually all computationaly intensive code would benefit from being in WASM.

Related: #1825, #2045

[kungfooman]

The issue with AssemblyScript is that it still doesn't support variadic arguments and therefore also fails to replicate JS behaviour of every variadic function in JS. So by necessity you end up having to manage two incompatible versions, because the assumption that you can just use good old JS and turn it into TS for AS is wrong.

I've been there myself for another JS project, but eventually running into issues like this one: AssemblyScript/assemblyscript#1501

(2 years later, not fixed)

And then JS JIT is extremely fast aswell, my AS version ended up being slower than pure JS JIT because of WASM-to-Javascript bridge performance loss.

So think twice before you uglify your TS code with all kinds of type annotations that AS requires and then it still doesn't give you what you hope for, but the introduced complexity is enormous (say hi to pointers and invalidated typed arrays after memory regrowth for example).

[cshaa]

Yes, that's definitely a very good remark. While I have first-hand experience with Rust compiled to WASM being orders of magnitude faster than the corresponding JS in my app, I am well aware that in many other scenarios the performance of WASM might be only marginally better, or even worse than pure JS. Deciding which codepaths to accelerate will require lots and lots of benchmarks.

I haven't used AssemblyScript yet, but I've noticed that it's still pretty barebones and its interop with TS is pretty shaky. However, being able to share code between WASM and non-WASM parts of the project would be really awesome and might still be worth the price of uglier / less expressive code. Remember, only the most expensive computations need to be done in WASM, so most of the library could be ordinary JS / TS.

That being said, many proofs-of-concept will have to be done before comitting to any specific solution, and it's possible that we'll find that AS is simply not worth the hassle and programming the accelerated functions in C / Rust / Zig / whatever is much better.

[josdejong]

Thanks. Yes WASM could be interesting

So think twice before you uglify your TS code with all kinds of type annotations that AS requires and then it still doesn't give you what you hope for, but the introduced complexity is enormous (say hi to pointers and invalidated typed arrays after memory regrowth for example).

I second that, we should first do a small proof of concept to figure out if there is much to gain and what the drawbacks are.

One approach could be to rewrite mathjs completely in WebAssembly. An other approach could be to have for example a new Matrix data type or numeric type written in WebAssembly, and import that into mathjs. Similarly, it could be interesting to look into typed arrays, see #43, or into utilizing WebGL for matrix computations.

[dvd101x]

I was doing some benchmarks with mathjs that might be helpful for this discussion.

language	code
mathjs	math.inv(math.random([200,200]))
numpy	np.linalg.inv(np.random.rand(200,200))
octave	inv(rand(200,200))

using	time [s]
mathjs in Safari	2.403
mathjs in Chrome	0.475
numpy in pyodide [wasm] in the browser	0.024
numpy in python 3.10 in the terminal	0.009
octave	0.005

Mathjs flexibility is unique and adds a lot of convenience, please take this only as quick comparison for consideration of the possible benefits of WASM.

[Lowclouds]

Happening across this really late, but thought this might be useful. I came across a WASM library called Eigen.js which had some benchmarks including Mathjs (here: https://bertrandbev.github.io/eigen-js/#/benchmark). Mathjs fared quite badly, even against other JS libraries like Lalolib, and made me start to rethink my use of Mathjs. But then, I ran the same tests switching from Firefox to Chrome and got radically different results: Mathjs is still relatively slow, but more than 10x faster in Chrome. Re-doing a few of the tests in the console reinforced how much faster Chrome is for at least some Mathjs operations. I guess the bottom line is that it may just depend.

[gwhitney]

Thanks for the input. We actually have some clue where the slowness of mathjs in javascript terms comes from -- repeated indirection in passing arguments into more basic functions -- and hope to address it. Not saying that by itself would make mathjs a "serious compute engine" but should reduce its relative disadvantage somewhat.

[josdejong]

Thanks for your input @Lowclouds.

I've added eigen-js to the matrix_operations benchmark in the mathjs repo: 7f02ba2

Here are the outputs that I get:

matrix operations mathjs (number) A+A         5.14 µs   ±0.60%
matrix operations mathjs (number) A*A        29.24 µs   ±0.21%
matrix operations mathjs (number) A'          2.49 µs   ±1.46%
matrix operations mathjs (number) det(A)    218.70 µs   ±1.37%
matrix operations mathjs (generic) A+A       10.75 µs   ±1.00%
matrix operations mathjs (generic) A*A       37.19 µs   ±3.30%
matrix operations mathjs (generic) A'         2.41 µs   ±0.61%
matrix operations mathjs (generic) det(A)   199.31 µs   ±0.51%
matrix operations sylvester A+A               4.59 µs   ±1.21%
matrix operations sylvester A*A              39.92 µs   ±0.39%
matrix operations sylvester A'                3.86 µs   ±1.71%
matrix operations sylvester det(A)           78.66 µs   ±2.85%
matrix operations numericjs A+A               1.25 µs   ±1.00%
matrix operations numericjs A*A              13.52 µs   ±0.39%
matrix operations numericjs A'                0.95 µs   ±0.82%
matrix operations numericjs det(A)            6.23 µs   ±1.10%
matrix operations ndarray A+A                 1.69 µs   ±0.32%
matrix operations ndarray A*A                22.86 µs   ±0.03%
matrix operations ndarray A'                  0.75 µs   ±0.02%
matrix operations ndarray det(A)              1.09 µs   ±1.12%
matrix operations eigen-js A+A                2.21 µs   ±0.16%
matrix operations eigen-js A*A                5.31 µs   ±0.05%
matrix operations eigen-js A'                 2.58 µs   ±0.36%
matrix operations eigen-js det(A)             3.96 µs   ±0.20%

I think we should not over analyse this limited benchmark, but some remarks:

1. In mathjs, it can make a big difference whether you create a generic matrix (which can have mixed contents like numbers, units, complex numbers), or a matrix which contains numbers only. There is room to improve the type inference further.
2. It's a long time issue that det is very slow in mathjs. Looking at other libraries, it is definitely possible to improve on this
3. it looks like eigen-js is extremely fast with multiplication, faster than all other libraries. The performance mathjs for multiplication is in the same order of magnitude as other math libraries though, so it is not the case that the performance of mathjs is particularly bad for multiplication. It would be interesting to figure out what makes multiplication of eigen-js so fast to see whether we can do something similar.
4. eigen-js is slower for addition, transpose, and determinant compared to some other libraries like ndarray. It is not the case that eigen-js is magically fast as in an order of magnitude faster than other JS libaries. Now, this micro benchmark is of course a rough and limited comparison, it would be better to have a reald world example of a series of calculations and compare that using different libraries.
5. It took me some effort to get this benchmark running at all, because eigen-js gave errors running out of memory. After switching to a different benchmark tool that allows a bit more control over how long the benchmark runs, I managed to get it working. Apparently we need to be careful with this when using a WASM library like eigen-js 🤔.
6. Again: there is definitely room in mathjs to improve the performance, any help is welcome :)

UPDATE: I've replaced the benchmark output with better readable numbers after refactoring all of the benchmarks.