[Babel 8] perf: Improve traverse performance #16965

liuxingbaoyu · 2024-11-15T19:25:02Z

Q	A
Fixed Issues?	`Fixes #1, Fixes #2`
Patch: Bug Fix?
Major: Breaking Change?
Minor: New Feature?
Tests Added + Pass?	Yes
Documentation PR Link
Any Dependency Changes?
License	MIT

This PR is a bit weird because I can't fully explain the benchmark results. Discussions are welcome!

Overall time reduction of 10%-20, with one benchmark regression (~15%) that can be fixed by merging #16964.
Also reduced reliance on the global cache and almost no global cache in Babel 8.

There are two changes in this PR

Organize traversal related logic into one file
Store cache in parentPath
Each of them alone gives little or no improvement, but together the performance improvement is much larger.

Even weirder is that there is a benchmark mjs-cjs/ts-checker that drops by more than 15%, and it has the same drop when only the second change is made, while js-node6/typescript-5.6.2 (larger file) and mjs-cjs/ts-parser (similar benchmark) do not have the same situation.

I recently found that when I merged #16964, the situation of 1+1>2 appeared again, and the above issue disappeared.
This is confusing to me, because in my assumption the performance regression comes from recreating part of the NodePath (since there is no global cache anymore, when a node is moved to its parent, all related NodePath need to be recreated), and that PR just avoids multiple traversals and shouldn't fix it. (Traversals are faster, so the impact of the changes in #16964 in this PR should be less than 3%)

Note: This PR may be risky to merge in Babel 7, but since it doesn't require any changes to our plugins, it might be worth a try.

with #16964

PS F:\babel\benchmark> node --expose-gc .\all\real-case-ts-mjs.mjs
all/real-case-ts-mjs.mjs babel-parser-express.ts @ current: 51.15 ops/sec ±1.61% 256 runs (20ms)
all/real-case-ts-mjs.mjs babel-parser-express.ts @ baseline: 40.84 ops/sec ±2.95% 205 runs (24ms)
all/real-case-ts-mjs.mjs ts-parser.ts @ current: 9.41 ops/sec ±2.02% 48 runs (106ms)
all/real-case-ts-mjs.mjs ts-parser.ts @ baseline: 6.82 ops/sec ±2.78% 35 runs (147ms)
PS F:\babel\benchmark> node --expose-gc .\all\real-case-mjs-cjs.mjs
all/real-case-mjs-cjs.mjs ts-checker.mjs @ current: 1.25 ops/sec ±1.91% 10 runs (801ms)
all/real-case-mjs-cjs.mjs ts-checker.mjs @ baseline: 1.09 ops/sec ±3.99% 10 runs (922ms)
all/real-case-mjs-cjs.mjs ts-parser.mjs @ current: 10.07 ops/sec ±2.11% 51 runs (99ms)
all/real-case-mjs-cjs.mjs ts-parser.mjs @ baseline: 8.96 ops/sec ±3.3% 45 runs (112ms)
PS F:\babel\benchmark> node --expose-gc .\all\real-case-js-node6.mjs
all/real-case-js-node6.mjs jquery-3.6.js @ current: 10.35 ops/sec ±2.04% 52 runs (97ms)
all/real-case-js-node6.mjs jquery-3.6.js @ baseline: 9.21 ops/sec ±2.6% 47 runs (109ms)
all/real-case-js-node6.mjs typescript-5.6.2.js @ current: 0.34 ops/sec ±1.14% 10 runs (2970ms)
all/real-case-js-node6.mjs typescript-5.6.2.js @ baseline: 0.28 ops/sec ±4.03% 10 runs (3602ms)
PS F:\babel\benchmark> node --expose-gc .\babel-traverse\real-case.mjs
babel-traverse/real-case.mjs babel-parser-express.ts @ current: 95.92 ops/sec ±1.33% 480 runs (10ms)
babel-traverse/real-case.mjs babel-parser-express.ts @ baseline: 85.51 ops/sec ±0.76% 428 runs (12ms)
babel-traverse/real-case.mjs jquery-3.6.js @ current: 28.58 ops/sec ±1.58% 143 runs (35ms)
babel-traverse/real-case.mjs jquery-3.6.js @ baseline: 22.53 ops/sec ±1.23% 113 runs (44ms)
babel-traverse/real-case.mjs ts-checker.mjs @ current: 4.05 ops/sec ±2.13% 21 runs (247ms)
babel-traverse/real-case.mjs ts-checker.mjs @ baseline: 3.05 ops/sec ±2.34% 16 runs (328ms)
babel-traverse/real-case.mjs ts-parser.mjs @ current: 26.39 ops/sec ±1.64% 132 runs (38ms)
babel-traverse/real-case.mjs ts-parser.mjs @ baseline: 20.6 ops/sec ±1.79% 103 runs (49ms)
babel-traverse/real-case.mjs ts-parser.ts @ current: 21.94 ops/sec ±1.88% 110 runs (46ms)
babel-traverse/real-case.mjs ts-parser.ts @ baseline: 16.91 ops/sec ±1.37% 85 runs (59ms)
babel-traverse/real-case.mjs typescript-5.6.2.js @ current: 0.99 ops/sec ±3.47% 10 runs (1012ms)
babel-traverse/real-case.mjs typescript-5.6.2.js @ baseline: 0.73 ops/sec ±2.19% 10 runs (1369ms)

without #16964

PS F:\babel\benchmark> node --expose-gc .\all\real-case-ts-mjs.mjs    
all/real-case-ts-mjs.mjs babel-parser-express.ts @ current: 51.02 ops/sec ±1.75% 256 runs (20ms)
all/real-case-ts-mjs.mjs babel-parser-express.ts @ baseline: 40.44 ops/sec ±3.88% 203 runs (25ms)
all/real-case-ts-mjs.mjs ts-parser.ts @ current: 7.45 ops/sec ±1.81% 38 runs (134ms)
all/real-case-ts-mjs.mjs ts-parser.ts @ baseline: 6.85 ops/sec ±3.06% 35 runs (146ms)
PS F:\babel\benchmark> node --expose-gc .\all\real-case-mjs-cjs.mjs
all/real-case-mjs-cjs.mjs ts-checker.mjs @ current: 0.93 ops/sec ±2.63% 10 runs (1072ms)
all/real-case-mjs-cjs.mjs ts-checker.mjs @ baseline: 1.13 ops/sec ±3.04% 10 runs (884ms)
all/real-case-mjs-cjs.mjs ts-parser.mjs @ current: 10.44 ops/sec ±1.89% 53 runs (96ms)
all/real-case-mjs-cjs.mjs ts-parser.mjs @ baseline: 9.14 ops/sec ±3.65% 47 runs (109ms)
PS F:\babel\benchmark> node --expose-gc .\all\real-case-js-node6.mjs  
all/real-case-js-node6.mjs jquery-3.6.js @ current: 10.19 ops/sec ±1.83% 51 runs (98ms)
all/real-case-js-node6.mjs jquery-3.6.js @ baseline: 9.08 ops/sec ±2.76% 46 runs (110ms)
all/real-case-js-node6.mjs typescript-5.6.2.js @ current: 0.33 ops/sec ±1.52% 10 runs (3007ms)
all/real-case-js-node6.mjs typescript-5.6.2.js @ baseline: 0.27 ops/sec ±3.89% 10 runs (3687ms)
PS F:\babel\benchmark> node --expose-gc .\babel-traverse\real-case.mjs
babel-traverse/real-case.mjs babel-parser-express.ts @ current: 97.12 ops/sec ±1.24% 486 runs (10ms)
babel-traverse/real-case.mjs babel-parser-express.ts @ baseline: 84.19 ops/sec ±0.74% 421 runs (12ms)
babel-traverse/real-case.mjs jquery-3.6.js @ current: 28.25 ops/sec ±1.42% 142 runs (35ms)
babel-traverse/real-case.mjs jquery-3.6.js @ baseline: 22.43 ops/sec ±1.37% 113 runs (45ms)
babel-traverse/real-case.mjs ts-checker.mjs @ current: 4.05 ops/sec ±1.74% 21 runs (247ms)
babel-traverse/real-case.mjs ts-checker.mjs @ baseline: 3.07 ops/sec ±2.26% 16 runs (325ms)
babel-traverse/real-case.mjs ts-parser.mjs @ current: 26.19 ops/sec ±1.52% 132 runs (38ms)
babel-traverse/real-case.mjs ts-parser.mjs @ baseline: 20.55 ops/sec ±1.29% 103 runs (49ms)
babel-traverse/real-case.mjs ts-parser.ts @ current: 21.85 ops/sec ±1.67% 110 runs (46ms)
babel-traverse/real-case.mjs ts-parser.ts @ baseline: 16.54 ops/sec ±1.35% 83 runs (60ms)
babel-traverse/real-case.mjs typescript-5.6.2.js @ current: 0.99 ops/sec ±3.61% 10 runs (1014ms)
babel-traverse/real-case.mjs typescript-5.6.2.js @ baseline: 0.71 ops/sec ±3.9% 10 runs (1404ms)

babel-bot · 2024-11-15T19:27:01Z

Build successful! You can test your changes in the REPL here: https://babeljs.io/repl/build/58733

liuxingbaoyu · 2024-11-15T19:42:19Z

The CI failure is related, which is a bit bad.

liuxingbaoyu · 2024-11-18T17:14:11Z

packages/babel-traverse/test/modification.js

+              "b",
+              "b",
+            ],
+          ]


Technically Jest's CI failure is not a bug.
The new behavior seems to make more sense than the old one.
Previously we didn't traverse the emptyStatement due to

babel/packages/babel-traverse/src/context.ts

Lines 34 to 56 in a6aa8a9

shouldVisit(node: t.Node): boolean {

const opts = this.opts as Visitor;

if (opts.enter || opts.exit) return true;

// check if we have a visitor for this node

if (opts[node.type]) return true;

// check if we're going to traverse into this node

const keys: Array<string> | undefined = VISITOR_KEYS[node.type];

if (!keys?.length) return false;

// we need to traverse into this node so ensure that it has children to traverse into!

for (const key of keys) {

if (

// @ts-expect-error key is from visitor keys

node[key]

) {

return true;

}

}

return false;

}

babel/packages/babel-traverse/src/context.ts

Lines 92 to 99 in a6aa8a9

for (let key = 0; key < container.length; key++) {

const node = container[key];

if (node && this.shouldVisit(node)) {

queue.push(this.create(parent, container, key, listKey));

}

}

return this.visitQueue(queue);

, so it had no contexts and the queue was not added correctly.

Old snapshots

expect(logs).toMatchInlineSnapshot(` Array [ Array [ "a", ], Array [ "a", "b", "b", "b", "b", ], ] `);

Of course we should avoid this change in non-major releases anyway, because it will affect Jest users.

JLHwung · 2024-11-20T02:09:28Z

packages/babel-traverse/test/modification.js

@@ -335,16 +335,65 @@ describe("modification", function () {
        );
      });

-      it("the exported expression", function () {


Q: Why is the test "the exported expression" removed? The new test seems drastically different than the previous test.

Oh, it looks like it was removed accidentally. Thanks for noticing it!

liuxingbaoyu · 2025-02-17T00:17:53Z

To avoid possible regressions, I moved it to Babel 8.

liuxingbaoyu force-pushed the perf-traverse2 branch from 0a1208d to e9bb192 Compare November 18, 2024 17:07

liuxingbaoyu commented Nov 18, 2024

View reviewed changes

JLHwung reviewed Nov 20, 2024

View reviewed changes

liuxingbaoyu force-pushed the perf-traverse2 branch from e9bb192 to bd24696 Compare November 20, 2024 06:55

liuxingbaoyu mentioned this pull request Dec 4, 2024

fix: Regression of new traverse with transform-modules-amd #17001

Closed

liuxingbaoyu force-pushed the perf-traverse2 branch from bd24696 to 2c580d6 Compare December 6, 2024 06:53

liuxingbaoyu mentioned this pull request Dec 9, 2024

Improve babel-plugin-jest-hoist logic jestjs/jest#15415

Merged

liuxingbaoyu force-pushed the perf-traverse2 branch from 2c580d6 to c2c16cf Compare December 12, 2024 19:12

liuxingbaoyu added 3 commits February 17, 2025 01:00

perf

bb7e0a7

add test

47cb39b

babel 8

77bc11b

liuxingbaoyu force-pushed the perf-traverse2 branch from c2c16cf to 77bc11b Compare February 16, 2025 17:12

liuxingbaoyu changed the title ~~perf: Improve traverse performance~~ [Babel 8] perf: Improve traverse performance Feb 16, 2025

liuxingbaoyu added pkg: traverse PR: Performance (next major) 🏃‍♀️ A type of pull request used for our changelog categories for next major release labels Feb 17, 2025

nicolo-ribaudo approved these changes Apr 12, 2025

View reviewed changes

JLHwung approved these changes Apr 22, 2025

View reviewed changes

JLHwung merged commit 8e23272 into babel:main Apr 22, 2025
55 checks passed

github-actions bot added the outdated A closed issue/PR that is archived due to age. Recommended to make a new issue label Jul 23, 2025

github-actions bot locked as resolved and limited conversation to collaborators Jul 23, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

[Babel 8] perf: Improve traverse performance #16965

[Babel 8] perf: Improve traverse performance #16965

Uh oh!

liuxingbaoyu commented Nov 15, 2024 •

edited

Loading

Uh oh!

babel-bot commented Nov 15, 2024 •

edited

Loading

Uh oh!

liuxingbaoyu commented Nov 15, 2024

Uh oh!

liuxingbaoyu Nov 18, 2024

Uh oh!

JLHwung Nov 20, 2024

Uh oh!

liuxingbaoyu Nov 20, 2024

Uh oh!

liuxingbaoyu commented Feb 17, 2025

Uh oh!

Uh oh!

Uh oh!

	shouldVisit(node: t.Node): boolean {
	const opts = this.opts as Visitor;
	if (opts.enter \|\| opts.exit) return true;

	// check if we have a visitor for this node
	if (opts[node.type]) return true;

	// check if we're going to traverse into this node
	const keys: Array<string> \| undefined = VISITOR_KEYS[node.type];
	if (!keys?.length) return false;

	// we need to traverse into this node so ensure that it has children to traverse into!
	for (const key of keys) {
	if (
	// @ts-expect-error key is from visitor keys
	node[key]
	) {
	return true;
	}
	}

	return false;
	}

	for (let key = 0; key < container.length; key++) {
	const node = container[key];
	if (node && this.shouldVisit(node)) {
	queue.push(this.create(parent, container, key, listKey));
	}
	}

	return this.visitQueue(queue);

Uh oh!

[Babel 8] perf: Improve traverse performance #16965

[Babel 8] perf: Improve traverse performance #16965

Uh oh!

Conversation

liuxingbaoyu commented Nov 15, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

babel-bot commented Nov 15, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

liuxingbaoyu commented Nov 15, 2024

Uh oh!

liuxingbaoyu Nov 18, 2024

Choose a reason for hiding this comment

Uh oh!

JLHwung Nov 20, 2024

Choose a reason for hiding this comment

Uh oh!

liuxingbaoyu Nov 20, 2024

Choose a reason for hiding this comment

Uh oh!

liuxingbaoyu commented Feb 17, 2025

Uh oh!

Uh oh!

Uh oh!

liuxingbaoyu commented Nov 15, 2024 •

edited

Loading

babel-bot commented Nov 15, 2024 •

edited

Loading