facebook / facebook/hermes

hermes-parser: babel:true conversion is O(n^2) in sibling count — 88s on a file that parses in 0.1s

Open
#2,158 0 comments 1 reaction 0 assignees View on GitHub
Dominant language
JavaScript
Stars
11.3k
Forks
859
Avg merge
1h 30m
Merged PRs (30d)
3

Description

### Summary

`hermes-parser`'s `parse(src, {babel: true})` takes **88 seconds** on a 502 KB minified JavaScript file. The parse itself takes **0.1 seconds**. All of the time is in the JavaScript code that converts the Hermes AST into a Babel AST.

The cause is that each node replacement copies the whole array of sibling nodes. With one large array in the file, the conversion becomes quadratic.

### Measurements

`hermes-parser@0.36.1`, Node 26.5.0, macOS arm64, on `@lottiefiles/dotlottie-react@0.13.5` (`dist/browser/index.js`, 502 KB):

| call | time |
|---|---|
| `parse(src, {babel: false})` | **0.1s** |
| `parse(src, {babel: true})` | **88.3s** |

CPU profile of the slow call:

| time | share | function |
|---|---|---|
| 36.1s | 41% | `enter` (`transform/SimpleTransform.js:50`) |
| 26.2s | 30% | `getParentKey` (`transform/astNodeMutationHelpers.js:29`) |
| 17.3s | 20% | `replaceInArray` (`transform/astArrayMutationHelpers.js:59`) |
| 4.0s | 5% | garbage collector |

That file has one `ArrayExpression` with **128,834 elements**, out of 153,581 AST nodes in total.

### Minimal repro

```js
import * as hermes from 'hermes-parser';

for (const n of [2000, 4000, 8000, 16000, 32000]) {
const src = `var a=[${Array.from({length: n}, (_, i) => i).join(',')}];`;
const t = Date.now();
hermes.parse(src, {babel: true, sourceType: 'script'});
console.log(n, Date.now() - t + 'ms');
}
```

```
2000 46ms
4000 100ms
8000 381ms
16000 1350ms
32000 5593ms
```

Time goes up 4x each time the element count doubles, which is quadratic. Extending the curve to 128,834 elements gives roughly 88s, matching the real file.

With `babel: false` the same inputs are fast, so this is only the conversion step.

Long lines and non-ASCII characters are not involved — we checked both. A file with 40,000 statements on a single line converts in 321ms, and the slow file is pure ASCII.

### Cause

`replaceInArray` (`transform/astArrayMutationHelpers.js:59`) rebuilds the entire array for every replacement:

```js
function replaceInArray(array, index, elements) {
assertArrayBounds(array, index);
return array.slice(0, index).concat(elements).concat(array.slice(index + 1));
}
```

And `getParentKey` (`transform/astNodeMutationHelpers.js:29`) scans the parent's visitor keys to find where the target node sits, rather than using an index already known during traversal.

The Babel conversion replaces literal nodes (for example `NumericLiteral`), so in an array of N literals both functions run N times, each costing O(N).

### Suggested fix

Two independent changes, either of which should remove most of the cost:

1. In `replaceInArray`, when a single node replaces a single node, assign in place (`array[index] = elements[0]`) instead of building two slices and two concats.
2. Pass the array index down from the traversal in `SimpleTransform`, so `getParentKey` does not have to search the parent for the node it just visited.

### Who this affects

Anyone calling `hermes-parser` with `babel: true` on files containing large arrays or object literals — which is common in prebuilt or minified bundles. There is no warning, and the cost is invisible in build output. We only found it by bisecting a slow bundler build, where this one file set a floor of 94 seconds on every cold build.

### Environment

`hermes-parser@0.36.1`, Node 26.5.0, macOS arm64, 12-core M-series.

Contributor guide

Open the contributing guide

Research direction

Start with transform/astArrayMutationHelpers.js at replaceInArray and transform/astNodeMutationHelpers.js at getParentKey, then trace their callers in transform/SimpleTransform.js. Run the minimal reproduction with babel:true and compare conversion time as array size doubles. Done means large arrays no longer show quadratic scaling while Babel AST conversion remains correct.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
performance
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
76/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.