WebAssembly (Wasm, in short) is an assembly-like instruction format for a stack-based virtual machine. It is designed to be encoded in an efficient binary format that can be executed at near-native speed on any platform that can host the virtual machine. In particular, this is supported on all modern browsers (Chrome, Edge, Firefox and Safari).
This becomes significant when performing computation-heavy tasks, such as graphics rendering or data processing. To showcase how Wasm fares against JS, we will implement in both languages one such task: the LZ77 compression algorithm, chosen as it is quite straightforward to explain and visualise.
Lempel-Ziv (1977) algorithm
LZ77 is a lossless data compression algorithm, often referred to as a “sliding window”. It transforms an input into a sequence of tuples, according to the occurrence of repeated symbols, where each tuple has the form: (offset, length, trailing). Starting from the beginning of the input, we look for the rightmost longest occurrence of the lookahead (the unprocessed section of the input) in the window (the processed part), record where the match occurred (i.e. offset and length), and the trailing symbol (the first unmatched one) – this delimits the new lookahead/window, and the same step is repeated until all the input has been encoded.
As an example, consider “ababcxabcd”. We use the vertical bar to delimit at each step where lookahead and window are; we also underline the match and highlight the trailing symbol in bold. The algorithm goes as follows:
| ababcxabcd (0, 0, a)
a | babcxabcd (0, 0, b)
ab | abcxabcd (2, 2, c)
ababc | xabcd (0, 0, x)
ababcx | abcd (4, 3, d)
where the offset in each tuple denotes where the match begins in the window, and the length how many symbols are repeated (e.g. in the last step the match is “abc”, of length 3, located 4 symbols to the left of the delimiter).
Rust to Wasm
Rust is a low-level, statically-typed programming language, with its main focus on safety and performance. It is quite new but already making a name for itself, being voted most-loved language on Stack Overflow for four years in a row. And compiling to Wasm is almost trivial! The crate (Rust for external package/module) wasm-pack handles generating all the boilerplate needed to import the Wasm binary into JS (to execute it in a web page), together with the compilation itself.
The Rust implementation of LZ77 is quite straightforward, taking roughly 50 lines in total
We then only need to instruct wasm-pack on what functions/objects to export to the binary format
Running wasm-pack build –target web generates the Wasm binary and JS boilerplate in the pkg folder.
Run in the browser
All we need to do is to import the init method from the JS file generated by wasm-pack, which handles loading the Wasm binary into the browser’s virtual machine. Now all the functions declared in Wasm are accessible, and we can invoke them as any other JS method.
We do exactly this in the main script of the test app
where we run the Wasm and then the JS implementation of LZ77 against a given input and record the execution time of each. The JS version of LZ77
is identical to the Rust one, so that the execution should be similar from the algorithmic point of view, and all optimisations be down to static and JIT compilations.
Is Wasm really faster?
JS files are really just text documents. To understand and execute them, the browser needs to parse their syntax and compile it to the hosting machine’s native instruction set: this is done by the JIT compiler, which also applies one (or more) optimisation steps based on how often particular code blocks appear.
Wasm promises to drastically reduce the impact of these steps because:
- Its binary format is already precompiled, and can be fed directly to the JIT for the optimisation step;
- No garbage collection happens on the Wasm virtual machine.
Performance is not everything, though. Another use case of Wasm is to port applications written for different platforms in different languages to the browser. For instance, C++ can be compiled into Wasm, and a few desktop applications have been made into web apps with this approach – notably, Autocad and Figma (amongst others), but also games like Doom 3 (https://wasm.continuation-labs.com/d3demo/).