fast-acorn

Why there was room to improve a parser that is already good

acorn reads source in two steps. A tokenizer cuts the text into tokens, and a recursive descent parser decides what the tokens mean and builds the tree. It is small and carefully written, and this page is not about a bad algorithm. The gain is in the machinery underneath, which acorn keeps general on purpose.

The reason is plugins. Parser.extend() lets a plugin subclass the parser and override any method, so acorn's parse functions are methods on one class, looked up on this at every call. Its token types are objects with fields that plugins read. Every node comes out of one Node constructor and receives its fields as the parse functions assign them. That is what makes acorn-jsx and the other plugins possible, and it is also what a parser that only wants to be fast cannot assume.

fast-acorn splits the job. It has its own parser, written as plain functions over a state object, for everything acorn does: every ecmaVersion, every sourceType, every option, parseExpressionAt and tokenizer(). When you pass Parser.extend() a class it recognises, it uses that parser. Otherwise it runs acorn's own code.

What makes it faster

None of these changes what the parser decides. They change how the work is done. Each is in src/parser.mts with a comment explaining it. This page does not break the speedup down by technique; the recorded results at the bottom measure them all together.

Token types are integers

acorn describes each token type with an object that has fields such as beforeExpr, isLoop and binop. fast-acorn gives each type a small integer and keeps those facts in typed arrays indexed by it: one array of flag bits and one of operator precedences, both filled from acorn's own token type objects when the module loads. Asking whether a token starts an expression becomes an integer test against a table. The token type objects still exist, because onToken, tokenizer() and tokTypes hand them out.

Keywords without hashing

Every keyword has a unique combination of length, first letter and second letter. A table indexed by those three numbers says whether a word can be a keyword at all, and the remaining letters are then compared directly. The check for the names that strict mode restricts, such as eval, yield and interface, works the same way. Neither has to hash the string.

An ASCII fast path in the tokenizer

Characters below 128 are looked up in a 128-entry table, and a word made only of them is scanned in one tight loop. Non-ASCII characters and escapes drop to a slower path that follows acorn's readWord1 exactly. Places where acorn runs a regular expression, such as skipping whitespace and comments or finding a "use strict" directive, are written as scanners. Whether a line break came before a token is worked out once, while skipping whitespace, and stored as a flag.

One constructor for each node type

acorn makes every node with one constructor, new Node(parser, pos, loc), which sets type, start and end. The parse functions then add the rest as they go (node.left = ...) and finishNode sets the type name. fast-acorn has a constructor for each node type that creates every key at once, in the order acorn would have added them.

That order matters twice. The tree must have acorn's key order to be identical, and a constructor that always creates the same keys in the same order gives the engine one object shape per node type. The source compiles the constructors when the first parse runs, so that each has store sites of its own that only ever see one shape. Node types whose keys depend on ecmaVersion get one constructor per key order. The extra keys for loc, range and sourceFile are added by a small helper of each type's own.

Writing the nodes as object literals instead was tried and made node creation 4x slower. It is one of the dead ends the repository keeps on record.

Scopes and names

acorn keeps the names declared in a scope in arrays and searches them with indexOf. fast-acorn keeps short lists as arrays and switches to a Set once a list passes 16 names, so the big top-level scope of a bundle stays cheap to search. Whether a scope may await or use new.target depends only on its chain of parents, so it is worked out once when the scope is created instead of by walking the scope stack on every check.

Less garbage

With locations on, a node needs Position objects, and acorn shares them: one token's Position is used by every node that starts or ends there. fast-acorn keeps that sharing and creates a token's end position only when a node asks for it. (Doing the same for start positions is one of the recorded dead ends.) Lists in the tree are built as arrays of exactly the right size. The source explains why: an array grown with push keeps a 17-slot backing store, three times the memory of an exact one-element array, and trees are full of small lists that all live on. Other pieces are pooled or cached: the records used while parsing destructuring, and the results of validating regular expressions, keyed by version, pattern and flags.

Why the tree is identical

The parse functions are acorn's, one for one: the same checks in the same order, the same rules for deciding whether a / starts a regular expression, the same errors raised at the same points. What differs is how each step is carried out, not what it concludes. The repository checks this against acorn: 93,841 parses over 14,670 real files from installed npm packages, plus 8,849 errors, all identical; 309,982 checks over every ecmaVersion and option; and 274,791 generated errors, each one identical to acorn's and each one produced by the fast parser.

Plugins, subclasses and the fallback

Parser.extend() is where a drop-in can go wrong, because a plugin may change any part of parsing. fast-acorn looks at the class it is given and takes one of three paths.

• acorn-jsx. The class runs on a native JSX mode. It is recognised if it is the genuine acorn-jsx 5.3.2 plugin, judged by its source text, its structure and some probe calls (which also reveal its options), or if it was made by @r1ck404/fast-acorn-jsx. That package is registered by identity, so it also works in minified bundles, where the genuine plugin's source text no longer matches. This is why the migration has two lines.
• Subclasses that only override parseFunctionBody. A parser that skips function bodies to list a file's top-level declarations quickly is the usual example. Nodepod's topLevelParser is one, and the tests use it. The method's source must pass a whitelist check: plain control flow over locals, reads of a fixed set of parser properties, and calls only to a short list of parser methods such as next, startNode, finishNode and eat. So it cannot have effects outside the parse. The method then runs for real, against a facade that shows the fast parser's state through acorn's API. This works after minification too.
• Anything else. Other plugins, subclasses with methods of their own, new Parser(...) and a patched Parser.prototype run acorn's own parser code, sharing the same tokTypes, Node and Position objects as the rest of the package. In Node it loads on first use. In browsers and bundles, import it once with import "@r1ck404/fast-acorn/full". Without that, such a parse throws an Error that says so.

The panel below runs six calls through both libraries in this tab, at least one for each path. This page bundles only the main entry, not /full, so the last row shows what an unrecognised plugin does without it.

Where the speedup shrinks

Anything that makes the parser allocate more shrinks the ratio. On the 1.2 MB three.module input in the results below, plain parsing is 2.8x faster and parsing with locations is 2.3x, because every node then carries a SourceLocation and two Position objects, which the tree has to contain. The repository's notes put the cost of locations down to collecting that garbage. The largest input in the results, typescript.js at 9 MB, shows the lowest speedup for plain parsing, 2.5x.

Plugins the fast parser does not recognise run acorn's own code on top of the faster tokenizer. The package README puts that at about 1.5x, after a one-time load of about 5 ms in Node. Import time is unchanged: importing acorn takes 5.4 ms in Node and importing fast-acorn takes 5.1 ms, and importing plus the first parse takes 9.4 ms and 9.5 ms.

What is different, and what is bigger

fast-acorn ships as one minified module. Minified it is a little smaller than acorn, but it compresses worse, because the fast machinery compresses less well than acorn's code. Sizes from the repository's size script, which bundles with esbuild:

On its own, fast-acorn is about 20% larger than acorn when gzipped (41.3 against 34.5 KB) and about 26% larger with brotli (36.3 against 28.9 KB). With acorn-jsx it is smaller, but for a reason that has little to do with the parser: acorn-jsx loads acorn with require, and an app that imports acorn as a module then bundles both of acorn's builds, the ES module and the CommonJS one. fast-acorn has a single entry. The size gap is recorded with the other things tried for acorn, such as shipping several files or an unminified bundle.

The behaviour differences are few, and each is pinned by a test.

• Unrecognised plugins, subclasses with methods of their own, new Parser(...) and a patched Parser.prototype need import "@r1ck404/fast-acorn/full" outside Node, as above.
• Parser.prototype has no methods of its own. It inherits acorn's from a prototype that receives them on first use.
• The token types' behaviour is built in. Replacing tokTypes.x.updateContext or a token context's override only affects parses that run acorn's own code.
• tokenizer() returns an object with acorn's token API and state, and it is an instanceof Parser, but it is not a whole parser: no scope stack, labels or parse methods.
• Nesting too deep for the stack throws acorn's "Not enough stack space to parse input" in both, at a different depth.
• Error stack traces show this package's functions.