Run JavaScript Code One Magnitude Faster Using WebAssembly
JavaScript code taking 50 seconds is re-coded in Rust and converted to a WebAssembly injected back into JavaScript to run in 7 seconds.
I thought I would never relate JavaScript to Assembly. I thought, of course. Because in my mind, JavaScript is a scripting language, it does run pretty fast these days, but I haven’t used it for things more serious than web development. Recently while studying some path-finding problems, I ran into a situation where a piece of JavaScript code could run for 50 seconds to reach a solution. The construction of the problem is pretty heavy and algorithm-oriented, but I’ll share the basic structure of the code in the following lines:
const buildMaze = (data) => {
...
return { maze, startPos, numKeys }
}const findMazeKeys = (maze, srcPos, keysTaken) => {
...
return dests
}const findMazeSteps = (maze, startPos, numKeys) => {
const minMazeSteps = (srcPos, keysTaken) => {
...
return memo[memoKey]
}
let memo = {}, usage = 0, actual = 0
return minMazeSteps(startPos, [])
}function World(data) {
const { maze, startPos, numKeys } = buildMaze(data)
return findMazeSteps(maze, startPos, numKeys)
}
In the above code, I omitted all the details while highlighting the function names. One of the functions minMazeSteps is used recursively within a closure of another function. The running time is mostly spent on the function findMazeKeys which is a normal iteration-based function.
The low-level language used, Rust
For the lack of better words to describe my rationale, I first want to see if a lower-level language, such as C++ can do, in this case, I picked Rust since it got a lot of buzz lately. I have to admit that I don’t have much experience with it. And it really took me a while to translate this code. Put it this way, I rewrote it instead of porting it, since I really don’t know how to port JavaScript to Rust.
use std::collections::HashMap;#[derive(Debug,Hash,PartialEq,Eq,Copy,Clone)]
struct Pos(i8, i8);type CharMat = Vec<Vec<char>>;
type MemoHash = HashMap<String, usize>;struct Maze {
mat: CharMat,
origin: Pos,
keys_len: usize,
memo: MemoHash,
usage: usize,
actual: usize
}impl Maze {
fn new(strs: &str) -> Maze {
...
Maze {
mat,
origin,
keys_len,
memo: HashMap::new(),
usage: 0,
actual: 0
}
}
fn locate_keys(
&self, p: &Pos, keys: &Vec<char>
) -> Vec<(char, Pos, usize)> {
...
dest
}
fn min_steps(
&mut self, p: &Pos, keys: &Vec<char>
) -> usize {
...
steps
}
fn solve(&mut self) -> usize {
let o = self.origin.clone();
self.min_steps(&o, &vec![]);
}
}
The Rust version is relatively more structured in the sense it has well-defined types, such as Maze . All the functions are straightforward class-like methods implemented around the struct Maze . There’s no closure involved since I can’t get it successfully implemented the way how JavaScript uses it. In the end, I concluded that the closures in both languages are just different, so I gave up the port.
If you have followed this article thus far, I’ll tell you the first discovery. Shockingly the Rust version of code takes 5 seconds instead of 50 seconds for the JavaScript version, thus there’s about one magnitude of difference. The Rust version, to me, is a lot harder to write.
Speed up the high-level language, JavaScript
Though I’m shocked by the result, I’m also quite excited to see whether there’s any area that I can improve my JavaScript to be more performant. I’m actually quite excited because I thought I found a gold egg to help me improve my JavaScript skill.
There’s a couple of directions I went: a) Closure b) Recursion c) Vector allocation. Believe it or not, I rewrote the JavaScript version couple of times based on eliminating the closure, recursion as well as vector excessive allocation. There’s definitely more stuff I can try, but the more I tried the more I found the initial code that I wrote is in pretty good shape in terms of performance. I could improve it from 50 seconds to 40 seconds after the above optimization, but that’s about it. I can’t push it into 30 seconds category at all!
In short, the NodeJS engine is really fast. If the magnitude of the loop is less than 100,000 , your way of writing the code does not matter much. The engine optimization should cover you quite well. There’s definitely a noticeable difference when the scale of operation goes beyond 100,000 . I’m pretty happy about the speed although I intended to see if I can make it run faster. This also explains why I don’t see JavaScript that slow these days because it’s not that slow. Considering the speed I can use to formulate and code the algorithm, JavaScript is definitely not in the slow category. I’m convinced of that after this exercise.
Meet the gap between the 50s and 5s, WebAssembly
I’m a bit obsessed with my own Maze. To continue finding the gap, I went in a different direction other than justifying why the Rust version is fast. If assembly is faster, then I’ll go with assembly. So I picked some books and found there’s something called WebAssembly, which allows you to inject assembly code into JavaScript. And it turns out Rust supports a build target wasm32. I followed an online tutorial and copied the Rust version over. And then invoke the imported method in the JavaScript index.js file:
import * as wasm from "world-interpretation"
console.log(wasm.run())Wola, the JavaScript version now runs in 7 seconds. Though not 5 seconds as in the pure Rust case, it’s close. Moreover, the imported assembly function turns out to be as simple as the basic function, except that all the children functions are all named as something like wasm-function[2] (min_steps). In our case, this function is highly recursive as you can see in the performance tab and 1.6 seconds are spent. The most expensive function, wasm-function[48] (locate_keys) now takes 2.3 seconds, compared to 16 seconds in the original JavaScript version.
Summary
A JavaScript code that takes around 50 seconds is re-coded in Rust and converted to a WebAssembly injected back into JavaScript. The final version running in the browser takes 7 seconds, thus gaining one magnitude difference in this heavy exercise.
More content at plainenglish.io. Sign up for our free weekly newsletter. Get exclusive access to writing opportunities and advice in our community Discord.
