Skip to content

Use set in parser scope#13408

Merged
JLHwung merged 3 commits intobabel:mainfrom
JLHwung:use-set-in-parser-scope
Jun 1, 2021
Merged

Use set in parser scope#13408
JLHwung merged 3 commits intobabel:mainfrom
JLHwung:use-set-in-parser-scope

Conversation

@JLHwung
Copy link
Copy Markdown
Contributor

@JLHwung JLHwung commented Jun 1, 2021 •
edited by gitpod-io bot
Loading

Q                       A
Fixed Issues? Parsing let/const declarations costs O(n^2) time
License MIT

This PR is similar to #13406: We use Set for checking duplicate bindings in parser scope.

Benchmark result (baseline is 7.14.4, current is this PR)

Length-1 let declarations 
$ node --predictable ./many-let-declarations/1-length-binding.mjs

baseline 256 length-1 let bindings: 1772 ops/sec ±21.58% (0.564ms)
baseline 512 length-1 let bindings: 733 ops/sec ±0.68% (1.365ms)
baseline 1024 length-1 let bindings: 232 ops/sec ±0.78% (4.312ms)
baseline 2048 length-1 let bindings: 66.35 ops/sec ±1.49% (15ms)

current 256 length-1 let bindings: 2592 ops/sec ±26.52% (0.386ms)
current 512 length-1 let bindings: 1497 ops/sec ±1.32% (0.668ms)
current 1024 length-1 let bindings: 728 ops/sec ±0.85% (1.374ms)
current 2048 length-1 let bindings: 323 ops/sec ±1.32% (3.093ms)

@JLHwung JLHwung added pkg: parser PR: Performance 🏃‍♀️ A type of pull request used for our changelog categories labels Jun 1, 2021
@babel-bot
Copy link
Copy Markdown
Collaborator

babel-bot commented Jun 1, 2021

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

@codesandbox-ci
Copy link
Copy Markdown

codesandbox-ci bot commented Jun 1, 2021

This pull request is automatically built and testable in CodeSandbox.

To see build info of the built libraries, click here or the icon next to each commit SHA.

Latest deployment of this branch, based on commit 82abbaa:

Sandbox Source
babel-repl-custom-plugin Configuration
babel-plugin-multi-config Configuration

nicolo-ribaudo
nicolo-ribaudo approved these changes Jun 1, 2021
View reviewed changes
Copy link
Copy Markdown
Member

@nicolo-ribaudo nicolo-ribaudo left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for going through all these complexity issues.

@JLHwung JLHwung merged commit b281fe3 into babel:main Jun 1, 2021
@JLHwung JLHwung deleted the use-set-in-parser-scope branch June 1, 2021 14:35
@motiz88
Copy link
Copy Markdown
Contributor

motiz88 commented Jun 1, 2021 •
edited
Loading

Just in case this isn't already on your radar @JLHwung, I recently noticed something similar in @babel/traverse's scope tracking - e.g. referencePaths should be a Set in

babel/packages/babel-traverse/src/scope/binding.ts

Lines 94 to 101 in b281fe3

reference(path: NodePath) {
if (this.referencePaths.indexOf(path) !== -1) {
return;
}
this.referenced = true;
this.references++;
this.referencePaths.push(path);
}

(Of course, there it's technically an API change so may not be straightforward to just change, but maybe we can add a secondary set to speed up checking for duplicates while still maintaining the array for compatibility.)

@JLHwung
Copy link
Copy Markdown
Contributor Author

JLHwung commented Jun 1, 2021

@motiz88 Thanks. That's a good catch!

A secondary set may introduce consistent issues due to multiple truth. We could provide referencePaths as an accessor for referencePathSet and migrate built-in plugins first.

This was referenced Jun 10, 2021
Closed
Closed
Closed
@github-actions github-actions bot added the outdated A closed issue/PR that is archived due to age. Recommended to make a new issue label Sep 1, 2021
@github-actions github-actions bot locked as resolved and limited conversation to collaborators Sep 1, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

@existentialism existentialism existentialism approved these changes

@nicolo-ribaudo nicolo-ribaudo nicolo-ribaudo approved these changes

@fedeci fedeci fedeci approved these changes

Assignees

No one assigned

Labels

outdated A closed issue/PR that is archived due to age. Recommended to make a new issue pkg: parser PR: Performance 🏃‍♀️ A type of pull request used for our changelog categories

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

6 participants

@JLHwung @babel-bot @motiz88 @existentialism @nicolo-ribaudo @fedeci