Production-ready WebAssembly support

[pdubroy]

#503 covers the initial investigation into WebAssembly. Due to funding limitations, that work was scoped to a 6-week effort. This issue is about the next phase: productionizing the current prototype.

Note

We are seeking $20k $12k US in funding to make this project possible. If you or your company could benefit from the portability and performance improvements of this work and could potentially help fund it, please get in touch with @pdubroy.

This project is now fully funded through the generous support of @Shopify! 🙏

Background

The goal of the MVP was:

The primary goal is to be able to produce a WebAssembly module (.wasm) from an existing Ohm grammar. The Wasm module would export a match function, which could be used just like the existing Grammar.match method.

At minimum, we also need an API (or ABI) for walking the parse tree.

This was successfully achieved, and the experiment showed that the Wasm version has significantly better performance on some real-world grammars (e.g. >10x on a 10k ES5 source file).

Goals

The next phase is to make the current prototype production-ready:

• Implement grammar features that are not supported in the MVP: parameterized rules, left recursion, missing primitive rules (caseInsensitive, lower, upper, UnicodeLtmo).
• Add implicit space skipping.
• Remove the input length limitation (support inputs >64k)
• (Maybe) support grammars with >256 rules.
• Implement error-handling.
• Implement a drop-in replacement for toAST() so at least some users could adopt the Wasm version without large-scale code changes.
• Make this available in a published NPM package (either a new major version of ohm-js, or in a separate package, etc. @ohmjs/wasm).
• Documentation.

Non-goals

Eventual goals, but not included in this phase:

• Incremental parsing.
• Fully replacing the functionality of pexprs-eval.js with the WebAssembly version, and rewriting the semantics code to work with CSTs in Wasm linear memory.

Estimate

• Parameterized rules: 1w
• Left recursion: 1w
• Missing primitive rules: 1w
• Space-skipping: 1.5w
• Input length: 1d
• Error-handling: 2w
• toAST: 1.5w
• Publish package: 1d
• Docs: 2d
• More testing/benchmarks: 1w

Total: 10w

Time-permitting:

• Work on reducing memory usage and/or parsing performance:
  • Dynamic memory allocation for memo table (HAMTs?)
  • More sophisticated memoization strategies
  • Compile-time optimization for parsing expressions

Reduced scope (~7w):

• Leave out implicit space-skipping and left recursion.
• Minimal documentation
• Focus testing & benchmarking on some existing real-world grammars (e.g. Shopify's liquid-html grammars).

[pdubroy]

I'm overdue for an update on this work!

I've made significant progress in the past couple months. The Wasm support is basically feature complete, and the remaining work is to remove some limitations, and to fix any bugs/incompatibilities that come up.

As Shopify is sponsoring this work, the main goal is now to get their liquid-html-grammar moved over to the Wasm implementation. Since this is a relatively complex real-world grammar, and one with millions of users, it makes sense to target this for the 1.0 release.

This does mean that the 1.0 release will still have some limitations, and not every existing Ohm grammar will be supported. For example, the full ES5 grammar is not currently supported, because of the very large number of rules (it requires >256 memo entries per input position).

Progress

• Parameterized rules: 1w
• Left recursion: 1w
• Missing primitive rules: 1w
• Space-skipping: 1.5w
• Input length: 1d
• Error-handling: 2w 1w remaining
  • Progress: I've implemented tracking of the failure position, which is the most difficult/risky part. I still need to implement constructions of the actual error message.
• toAST: 1.5w 1w remaining
  • Progress: I've implemented a modified version of toAST in the miniohm package. Next step is to create a fork of Shopify's LiquidHtml grammar and to get their stage-1-cst tests working with the new implementation.
• Publish package: 1d
• Docs: 2d
• More testing/benchmarks: 1w

Total: 10w 3w remaining

Performance

Many of the features in the list above had potential performance impact, and I'm happy to report we still see an roughly an order of magnitude speedup for real-world grammars.

The primary benchmark I'm using to estimate real-world performance is the scripts/parseLiquid.js, and summing the parse times for all the source files in Shopify's Dawn theme:

$ node scripts/parseLiquid.js '/Users/pdubroy/dev/third_party/Shopify/dawn/**/*.liquid'
skipping /Users/pdubroy/dev/third_party/Shopify/dawn/sections/main-product.liquid (too big)
JS total: 2032ms
Wasm avg: 238ms
Speedup:  8.54x

I also have a benchmark script that uses mitata, which can be run via make bench in packages/wasm. Since it runs each example many times, it may be more representative of the fully-tiered-up performance, but otoh it feels more artificial.

Here are the numbers from make bench (slightly edited for readability):

$ make bench
clk: ~3.16 GHz
cpu: Apple M1
runtime: node 24.5.0 (arm64-darwin)

• ES5: html5shiv
-------------------------------------------
   23.5x faster than JS

• ES5: underscore
-------------------------------------------
   36.68x faster than JS

• LiquidHTML: book-review.liquid
-------------------------------------------
   13.53x faster than JS

• LiquidHTML: featured-product.liquid
-------------------------------------------
   14.14x faster than JS

• LiquidHTML: footer.liquid
-------------------------------------------
   16.05x faster than JS

• JSON
-------------------------------------------
   4.91x faster than JS

Timeline

I'm on vacation for the rest of August and have somewhat limited availability in the first two week of September, so I'm aiming to complete this work by the end of September.

fyi @alexwarth @ajbouh @charlespwd

[pdubroy]

I just published v0.2.0 of the @ohm-js/wasm package (for compiling a grammar to a Wasm blog) and @ohm-js/miniohm-js (for using a Wasm grammar from JS).

As the API is changing, I'm going to wait a bit before updating the miniohm package for Go.

[pdubroy]

With the beta release of Ohm v18, the Wasm support is now production-ready (even if the API isn't 100% stable yet). So I'm going to close this issue, and will address the remaining things in more specific issues.

A snapshot of the most recent performance numbers —

es5bench-wasm

$ bin/es5bench-wasm
Compile: 68ms
......
JS match: 3516.2ms ± 353.3ms (n=3)
Wasm match: 98.2ms ± 33.5ms (n=3)
Speedup: 35.8x
Wasm memory: 174.0MB

parseLiquid

$ node scripts/parseLiquid.js '/Users/pdubroy/dev/third_party/Shopify/dawn/**/*.liquid'
......
JS parse: 2371ms ± 82ms (n=3)
Wasm parse: 44ms ± 1ms (n=3)
Parse speedup: 54.49x
Compile: 42ms
Compiled grammar size: 141.6 KB
Peak Wasm heap usage: 6.28 MB
Peak Wasm linear memory: 10.00 MB

Here are the results with --no-turbofan, to get a sense of the comparison outside the highest compilation tiers:

node --no-turbofan scripts/parseLiquid.js '/Users/pdubroy/dev/third_party/Shopify/dawn/**/*.liquid'
......
JS parse: 2679ms ± 10ms (n=3)
Wasm parse: 44ms ± 1ms (n=3)
Parse speedup: 61.00x
Compile: 43ms
Compiled grammar size: 141.9 KB
Peak Wasm heap usage: 6.28 MB
Peak Wasm linear memory: 10.00 MB