fast-es-module-lexer

What the lexer is for, and why it was slow

es-module-lexer finds the import and export statements in a JavaScript module without parsing the whole file. For each import it reports where the specifier is, where the statement starts and ends, and whether it is a static import, a dynamic import() or import.meta. For each export it reports the name and where it is. It also says whether the file uses module syntax at all. Its readme names es-module-shims as the tool it was written for. Anything that needs a module's dependencies before it can run or bundle the module calls it on every file it touches, so the cost grows with the size of the dependency graph.

The original is already WebAssembly, so the time goes elsewhere. Its C main loop looks at every character of the source in turn, and for most of them it does nothing except remember the last one that was not whitespace. Around that loop, the JavaScript glue copies the string into wasm memory one charCodeAt at a time, and afterwards reads each result field with a separate call into wasm. The note under the lanes above measures the copy step alone, using a copy of the original's loop, for whatever you are lexing.

How it skips almost every character

The Rust lexer keeps lexer.c's control flow, quirks included, so the answers match. What changed is how the main loop finds the next character worth looking at. The loop only needs to stop at ", ', `, (, ), {, } and /, and at an e followed by x, an i followed by m and a c followed by l, the first two letters of export, import and class. Every other character can only change the position of the last token, which the original tracks to decide, for instance, whether a / starts a regular expression or is a division.

The stop points are found 64 characters at a time. Each byte is split into its high and low four bits. Each half indexes a 16-entry table, the two values are ANDed, and the result is a set of class bits. WebAssembly has an instruction that does 16 such table lookups at once (i8x16.swizzle), so one pass classifies 16 characters and four passes fill a 64-bit mask with one bit per character. A second pair of tables classifies the following character, which is how ex, im and cl are told apart from a lone e, i or c. The loop then hops from set bit to set bit with a count-trailing-zeros instruction. A block with no stop point is left behind after one pass of the classifier.

Whitespace (tab through carriage return, and space) is classified in the same pass. When the loop stops, the last non-whitespace character before the stop is what the original would have in lastTokenPos, and it is recovered from the mask with a count-leading-zeros. Strings, template literals and comments are skipped by SIMD scans too: after an opening quote, the scanner looks 16 characters at a time for the closing quote, a backslash or a line break.

The panel below draws the classifier's flags over source code. The tables are copied from rust/src/lib.rs, and the same bytes are in the shipped wasm.

Getting the text in and the results out

The lexer reads one byte per UTF-16 unit. It only has to tell ASCII characters apart, plus U+00A0, which it treats as whitespace. Every other unit behaves like every other, so a unit above 0xff is squashed into a single byte. Positions in the results are still UTF-16 indices, as in the original, even after non-ASCII text.

How the string gets into memory depends on the engine. In Node, Buffer.latin1Write copies a string whose units are all at most 0xff, and ucs2Write copies the rest, both at memcpy speed. After a ucs2Write, a SIMD loop in the wasm narrows the UTF-16 units to bytes in place. In Chromium, a small second wasm module loops over the string with the JS-string builtins. V8 needs a while to optimize that loop, so for the first million characters it reads the string with intoCharCodeArray and only then switches to charCodeAt. Firefox and Safari have a fast TextEncoder.encodeInto and slow builtins, so they use encodeInto, and the wasm squashes the UTF-8 back to one byte per unit. On that path, strings of 128 units or fewer are copied by a JavaScript loop instead, because encodeInto has a fixed cost.

The results come back the other way as one array of integers. Each import is nine 32-bit words and each export is five, written one after another right after the source. The JavaScript reads them through a single Int32Array and builds the objects. The original makes a call into wasm for every field. An import specifier without a backslash is sliced out of the source, because evaluating a quoted literal with no escapes gives back its own text. One with a backslash still goes through eval, as in the original.

The wasm has no allocator. The source sits at the start of the heap, the records follow it, and memory is grown with memory.grow, by at least an eighth at a time because every grow detaches the JavaScript views of the memory.

Why Chromium gets less than Node

The recorded speedup is lower in Chromium than in Node: 3.5-4.9x against 5-7.7x on batches of real package files. The lexing is the same wasm in both. What differs is how the text gets in. Node copies it with memcpy, and Chromium runs a wasm loop that handles it one character at a time. That is the likely reason, but the recorded results do not separate the copy from the lexing, so treat it as an explanation and not a measurement. The same reasoning is behind the copy paths above: once the lexer is this fast, moving the text in is a large part of what is left.

When the original reads memory it should not

On malformed code, es-module-lexer can read memory outside its source: below it, where its bracket stack lives, past its end, where its records of the imports and exports found so far sit and then whatever earlier parses left behind, or through a null position. Its answer then depends on what it lexed before, and two calls with the same source can differ.

fast-es-module-lexer answers such inputs exactly as a fresh es-module-lexer instance does on its first parse. The Rust code works out what that instance's memory would hold at each address it reads, records included, and traps where that instance traps. Its answer does not depend on history. The panel gives each of two broken inputs to a new instance of each library, asks twice, then lexes an ordinary module and asks again.

What is different

Beyond the malformed-code case above, the package's readme lists these differences from es-module-lexer 1.7.0:

• Deep nesting. The original's stacks hold 1,024 open brackets and 512 open import( calls. Past that they overflow into its own copy of the source, and its answer goes wrong: 1,500 nested parentheses followed by import 'a' is a parse error at column 2900. The fast package answers correctly up to 16,384 open brackets and 4,096 open import( calls, and throws a parse error at the first one past that. The last row of the odd-inputs table shows this.
• Records that do not fit. A source that is mostly short exports, such as export{a,a,a,...} with around 20,000 names, makes a fresh original trap with memory access out of bounds, and the fast package traps too. An original whose memory grew in earlier parses answers instead. A trapped original traps on every later parse, and the fast package keeps working.
• Non-string arguments go through the original's own conversion, so null, undefined and similar throw the same errors. An object that has charCodeAt but no slice is answered as the string of its characters, where the original throws.
• Setup. init resolving after initSync() keeps the instance initSync made. The original replaces it with a second one, which shows up only as memory. The es-module-lexer/js subpath, the asm.js build, is not provided.
• Engine support. The wasm uses SIMD instructions and there is no fallback, so an engine without WebAssembly SIMD cannot load it. The package's browser tests run in Chromium, Firefox and WebKit.

On size, the fast package is larger. This is the browser bundle of { initSync, parse }, minified with esbuild:

Most of the bundle is the wasm: the SIMD scanners and the inlined fast paths that make it fast. The whole crate built for size, at opt-level = "z", is only 0.2 KB smaller after gzip and up to 13% slower. Dropping the Chromium copy module saves 0.5 KB and makes Chromium 37-135% slower. A wasm small enough to match the original's 6.5 KB bundle would mean giving up SIMD. The attempts are written down, along with the copy approaches that lost.

Startup is level with the original in Node. Importing takes 1.48 ms against 1.56 ms, and import, await init and a first parse takes 2.42 ms against 2.63 ms. With initSync() it is 2.33 ms against 2.24 ms. These are the package readme's numbers from fresh processes.