Delegating computationally expensive tasks to WebAssembly O(N³).

Parikshit Joon
Dec 31, 2019 · 6 min read

WebAssembly or wasm, is low level code, which can execute in the browser, Details. Being binary code wasm is neither human readable nor written by hand. But is compiled from other languages, popular ones include C/C++ or and rust. There are two major advantages that it directly gives us

  • The capacity to bring in capabilities from other languages, think of the image processing libraries which are written only for C++, they can be ported to WASM and run directly in the browser.
  • Major performance gains can be achieved as this is a low level instruction format and is capable of directly converting to machine code.

In this article I would be touching basics of compiling to WASM and loading to the browser. Which may be helpful for beginners.

Compiling to WASM

For this example, I will be using C and loading the compiled WASM to browser. A great tool for doing that simply is wasmFiddle : https://wasdk.github.io/WasmFiddle/

Once in wasmFiddle we can simply write code in C, build it and download the .wasm file. Which may be subsequently loaded to the browser.

Consider the following snipet written in C++.

int adder(int a,int b)
{
return (a+b);
}
int main() {
return 42;
}

This on building converts to the following wast (readable format of WebAssembly)

(module
(table 0 anyfunc)
(memory $0 1)
(export "memory" (memory $0))
(export "adder" (func $adder))
(export "main" (func $main))
(func $add (; 0 ;) (param $0 i32) (param $1 i32) (result i32)
(i32.add
(get_local $1)
(get_local $0)
)
)
(func $main (; 1 ;) (result i32)
(i32.const 42)
)
)

As may be noticed the add function from the C++ code is automatically exported and thus would be available when we load the code on browser.

Loading WASM to browser

Once program.wasm has been downloaded the next step is to serve it to the browser. For that, I am using a simple express server. Making sure the mime type of the served file is ‘application/wasm’. Without this you will not be able to load the file.

const path = require("path");const express = require("express");const app = express();app.use(express.static("public")); // Exposing the path which contains wasm fileexpress.static.mime.types["wasm"] = "application/wasm";app.listen(3000, () => {console.log("Server running at 3000");});

The only other file present in public folder would be index.html

With the following code:

<html><head><script type="text/javascript">WebAssembly.instantiateStreaming(fetch('program.wasm'), {}).then(wasmObj => console.log(wasmObj.instance.exports))</script></head></html>

I am using JS’s WebAssembly API (WebAssembly[instantiateStreaming]) to load wasm file to the browser. The instantiateStreaming method takes two parameters

  • Source promise, fetching the WebAssembly file in our case.
  • An import object which we’ll be sending blank for now.

The resolution of this promise return the result object, which comprises of the exported functions which we saw above (wast).

On logging instance.exports you’ll see the following output on console

  • Memory (represents wasm’s shared memory with JS)
  • adder (our exported function)
  • main (exported automatically)

Calling exported function

Once we’ve been able to load wasm file, calling the exported function is fairly simple.

WebAssembly.instantiateStreaming(fetch('program.wasm'), {}).then(wasmObj => console.log(wasmObj.instance.exports.adder(1,2)))
// Outputs 3

As expected, you’ve now called a function from C++, which was compiled to wasm.

Passing Data structures

Adding two digits is fairly simple, however it’s of little practical importance.

The current WebAssembly implementation poses a restriction on the kind of data which can be transacted between the 2 run times for now only float and integer data types are supported.

However to be of significance, we would be required to send and receive data structures. There’s no straightforward way to achieve this however an intuitive thing to do would be the capability of writing directly to wasm’s memory and as we know, it’s shared with JS.

What we write in JS should be accessible in C++ (WASM) code.

Writing the code using only wasmFiddle would be slightly hard. However we could use Emscripten, Emscripten is an ambitious project which can compile any piece of C/C++ code to WebAssembly and in the process also takes care of all glue code required to load WASM to the browser. It also provides a host of helper functions which allows one to pass data between JS and WASM.

Talking about the installation of emscriptes and using it, is outside the scope of this article. The documentation is pretty comprehensive. https://emscripten.org/docs/index.html

Passing Arrays from JavaScript

The capability of passing arrays practically gives us the capability of passing any data structure as arrays can be used to represent practically any data structure.

As you may know, arrays are continuous allocation of memory. We would be writing to wasm’s linear memory directly from JS.

We would require two things

  • A typed array buffer as C++ is a typed language.
  • The memory location, where this array would be written.

For the first we would be using JavaScipt’s typed array

const arrayToPass = [1,2,3];
const typedArray = new Int32Array(arrayToPass);
// C++ allocates 32bits for integers

For the latter we’d be using emscipten’s helper functions

//First compute the memory required in bytes const bytesN = arrayToPass.length * arrayToPass.BYTES_PER_ELEMENT/*Second allocating space in the memory buffer, using _malloc, a helper function provided by emscripten */const memPointer = Module._malloc(bytesN)
//Finally setting the data in HEAP memory
HEAP32.set(arrayToPass,memPointer/arrayToPass.BYTES_PER_ELEMENT);

The above snipet sets data (array) to wasm’s heap memory.

Now all that is required to be done ism call the C++ function with the pointer and length of the array.

sumUpArray(memPointer,arrayToPass.length);

C++ function to compute sum

function sumUpArray(int * arr, int length)
{
int sum = 0;
for(int i=0;i<length;i++)
sum+=arr[i];
return sum;
}

How fast is this thing? (MicroBenchmark)

For the purpose of comparing the speeds at which WASM and JS compute, I decided to run each of them against a common dataset.

To make things interesting, I chose an O(N³) based algorithm namely Floyd Warshall Algorithm. Fairly popular in graph theory, it’s used to compute shortest distances between each pair of vertices in a given graph.

Getting things ready

  • A random graph, which will be represented in adjacency matrix form.
const randomMatrix = (size) => ([...new Array(size)].map((_, row) => [...new Array(size)].map((_, col) => row === col ? 0 : (Math.floor(10 * Math.random(10 ** 1))))));

Where size would represent the order of this matrix, iterating over array and filling it with other random values between 1–10. While making sure the elements along diagonal are 0, which represents the distance between the same nodes.

  • Converting this matrix of matrices [[],[],[]] to a flat array.
const graphMatrix = randomMatrix(size);
const flattenedMatrix = new Int32Array(graphMatrix.flat());// C++ is //typed
const arrayToPtr = () => { // As explained above.
const bytesN = arrayToPass.length * arrayToPass.BYTES_PER_ELEMENTconst memPointer = Module._malloc(bytesN)
HEAP32.set(arrayToPass,memPointer/arrayToPass.BYTES_PER_ELEMENT);
}
floydW (arrayToPtr(flattenedMatrix),flattenedMatrix.size)// Call function
  • Once flattened matrix is obtained, perform algorithm on both JS and C++ and record findings.

C++

void floydW(int *flattenedMatrix, int order){int sum = 0;int n = sqrt(order);for (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (flattenedMatrix[i * n + k] + flattenedMatrix[n * k + j] < flattenedMatrix[i * n + j])flattenedMatrix[i * n + j] = flattenedMatrix[i * n + k] + flattenedMatrix[k * n + j];}

For sending the updated array back to JavaScript, I’ve used emscripten bindings, which are essentially a feature of emscipten to communicate between the 2 run times.

val getArray(){return val(typed_memory_view(size_t(order), flattenedMatrix));}EMSCRIPTEN_BINDINGS(){function("getArray", &getArray, allow_raw_pointers());}

Note for using emscipten bindings, compile the C++ code, like so.

em++ --bind -s WASM=1 wasm.cpp -s  EXPORTED_FUNCTIONS='["_floydW"]' -s ALLOW_MEMORY_GROWTH=1
// floydW is the exported function. And flag --bind to use bindings

Results

All timings in milliseconds(ms).

Conclusion

As may be seen using WebAssembly speeds up the process of computation by roughly 2 times or even more more, when the dataset is larger.

For more detail on the code, which was used. Check here: https://github.com/speedcuber911/wasmGraph

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade