Willian Martins

@wmsbill

WebAssembly, the journey

Hello all, I’m writing a series of posts to show my journey on trying to learn WebAssembly. I hope to bring more articles on this field soon.

In 2015 on BrazilJs conf I watched the closing keynote of BrendanEich, the creator of Javascript, speaking about the born, raise and evolution of JS. Who knows him, knows that one of his most famous quotes is “Always bet on JS”, but at the end of his talk he told something that got stuck in my mind:

Always bet on Js & WASM

That was my first contact with this name, but what is WebAssembly? What is the problem that this technology tries to solve? In that Moment I started my journey to answer all of these questions.

Our PoC

For a better understanding of this technology, I joined with my friend and developer Elia Maino to develop an algorithm that could allow us to compare the performance of WASM over Vanilla JS.

To prove our concept, we choose the John Conway’s game of life as our problem for this PoC. It is a zero-player game that has some simple rules.

  • The world is a Matrix which each cell can have two states: ALIVE or DEAD.
  • The only external input is the initial state
  • The interaction of the current cell with his horizontal, vertical and diagonal adjacent cells determines the state of a specific cell.
  • A live cell with less than two live neighbors dies.
  • A live cell with two or three live neighbors stays alive for the next generation.
  • A live cell with more than three live neighbors dies.
  • A dead cell with exactly three live neighbors becomes alive.

So the plan here was to create a big matrix, fill it with random values (0 or 1), send this initial state and render the result, then calculate the next state and render it again, repeating this last step several times.

We planned to implement this solution in three strategies: Vanilla JS, WebAssembly, and Web workers. The time complexity of our algorithm on all approaches was O(n*m) where n is the width of our world and m the height of it. Since the render is the same piece of code for all approaches, we won’t consider it in our results measurements.

Vanilla JS

The underlying architecture for this approach consists in create the new game, to generate and to send the first state (0 and 1 filled matrix) to it. The game component stores this state and returns a function next which returns the next state when called. In this case, we call the getNextState() function from our environment.js file that is the Vanilla JS implementation.

...
const next = game(
document.getElementById('game'),
COLUMNS,
LINES,
createGameMatrix(LINES, COLUMNS), // generates the initial state
strategy(
STRATEGY,
COLUMNS,
LINES,
initialConfig
) // Defines which strategy to use to calculate the next state
);
...
function loop() {
next().then(() => {
requestAnimationFrame(loop);
});
};
loop();

Inside the environment.js component, we keep splitting the problem into small specialized functions. It will help to trigger browser JIT compiler optimization more easily. We will discuss these optimizations in the next article. These functions calculate the current state of the neighbors above, aside and below, covering all the border’s corner cases.

The average speed of this state calculation varied from 9 to 4ms for a matrix of 800x450.

You may wonder the reason for so many variations on those calculations for the next state, or why so many functions? To answer these questions, we need to show you how JS JIT compilers work and how this makes JS be so fast today. But this is a subject for the next article.

Links

More by Willian Martins

Topics of interest

More Related Stories