Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

fix: optimize Range parsing and formatting #726

Merged
merged 3 commits into from
Jul 16, 2024
Merged

fix: optimize Range parsing and formatting #726

merged 3 commits into from
Jul 16, 2024

Conversation

jviide
Copy link
Contributor

@jviide jviide commented Jul 7, 2024 •
edited
Loading

This pull request optimizes the Range class in the following ways:

  1. Produce fewer intermediate objects when reducing a range's space characters to single spaces. This seems to improve bench-subset scores by up to 5%, and bench-satisfies scores to a lesser degree.
  2. Optimize Range formatting with explicit for loops instead, avoiding an intermediate array creation. This seems to improve bench-satisfies and bench-subset scores by up to 20%.
  3. Calculate Range's .range string (used by .format() and .toString()) lazily. This seems to improve bench-satisfies and bench-subset scores by up to 9%.

The external interface for the class stays the same, except for the new internal .formatted property used to cache its lazily calculated string. Range#range property is now also read-only.

There is a new test lazy formatting to ensure full test coverage.

The benchmarks bench-satisfies and bench-subset benefit from these changes, sometimes by up to 40%. Other benchmark results seem to stay the same. Here are the affected benchmarks before:

$ node benchmarks/bench-satisfies.js
satisfies(1.0.6, 1.0.3||^2.0.0) x 695,094 ops/sec ±0.68% (97 runs sampled)
satisfies(1.0.6, 2.2.2||~3.0.0) x 764,115 ops/sec ±0.40% (99 runs sampled)
satisfies(1.0.6, 2.3.0||<4.0.0) x 805,593 ops/sec ±0.62% (97 runs sampled)
satisfies(1.0.6, 1.0.3||^2.0.0, {"includePrelease":true}) x 695,045 ops/sec ±0.73% (95 runs sampled)
satisfies(1.0.6, 2.2.2||~3.0.0, {"includePrelease":true}) x 750,433 ops/sec ±0.66% (99 runs sampled)
satisfies(1.0.6, 2.3.0||<4.0.0, {"includePrelease":true}) x 787,903 ops/sec ±0.39% (99 runs sampled)
satisfies(1.0.6, 1.0.3||^2.0.0, {"includePrelease":true,"loose":true}) x 652,166 ops/sec ±0.34% (99 runs sampled)
satisfies(1.0.6, 2.2.2||~3.0.0, {"includePrelease":true,"loose":true}) x 696,377 ops/sec ±0.36% (96 runs sampled)
satisfies(1.0.6, 2.3.0||<4.0.0, {"includePrelease":true,"loose":true}) x 721,729 ops/sec ±0.35% (98 runs sampled)
satisfies(1.0.6, 1.0.3||^2.0.0, {"includePrelease":true,"loose":true,"rtl":true}) x 585,692 ops/sec ±0.75% (95 runs sampled)
satisfies(1.0.6, 2.2.2||~3.0.0, {"includePrelease":true,"loose":true,"rtl":true}) x 631,653 ops/sec ±0.33% (96 runs sampled)
satisfies(1.0.6, 2.3.0||<4.0.0, {"includePrelease":true,"loose":true,"rtl":true}) x 650,110 ops/sec ±0.64% (95 runs sampled)

$ node benchmarks/bench-subset.js
subset(1.2.3, *) x 633,342 ops/sec ±0.61% (95 runs sampled)
subset(^1.2.3, *) x 743,036 ops/sec ±0.47% (97 runs sampled)
subset(^1.2.3-pre.0, *) x 680,087 ops/sec ±0.76% (98 runs sampled)
subset(^1.2.3-pre.0, *) x 680,948 ops/sec ±0.46% (96 runs sampled)
subset(1 || 2 || 3, *) x 330,669 ops/sec ±0.53% (98 runs sampled)

And after:

$ node benchmarks/bench-satisfies.js
satisfies(1.0.6, 1.0.3||^2.0.0) x 896,936 ops/sec ±0.53% (94 runs sampled)
satisfies(1.0.6, 2.2.2||~3.0.0) x 998,214 ops/sec ±0.40% (95 runs sampled)
satisfies(1.0.6, 2.3.0||<4.0.0) x 1,000,593 ops/sec ±0.43% (97 runs sampled)
satisfies(1.0.6, 1.0.3||^2.0.0, {"includePrelease":true}) x 890,369 ops/sec ±0.41% (100 runs sampled)
satisfies(1.0.6, 2.2.2||~3.0.0, {"includePrelease":true}) x 977,239 ops/sec ±0.48% (97 runs sampled)
satisfies(1.0.6, 2.3.0||<4.0.0, {"includePrelease":true}) x 983,682 ops/sec ±0.95% (96 runs sampled)
satisfies(1.0.6, 1.0.3||^2.0.0, {"includePrelease":true,"loose":true}) x 805,330 ops/sec ±0.84% (98 runs sampled)
satisfies(1.0.6, 2.2.2||~3.0.0, {"includePrelease":true,"loose":true}) x 894,117 ops/sec ±0.43% (99 runs sampled)
satisfies(1.0.6, 2.3.0||<4.0.0, {"includePrelease":true,"loose":true}) x 911,742 ops/sec ±0.42% (96 runs sampled)
satisfies(1.0.6, 1.0.3||^2.0.0, {"includePrelease":true,"loose":true,"rtl":true}) x 741,254 ops/sec ±0.35% (97 runs sampled)
satisfies(1.0.6, 2.2.2||~3.0.0, {"includePrelease":true,"loose":true,"rtl":true}) x 807,380 ops/sec ±0.42% (99 runs sampled)
satisfies(1.0.6, 2.3.0||<4.0.0, {"includePrelease":true,"loose":true,"rtl":true}) x 820,390 ops/sec ±0.37% (99 runs sampled)

$ node benchmarks/bench-subset.js
subset(1.2.3, *) x 905,030 ops/sec ±0.63% (96 runs sampled)
subset(^1.2.3, *) x 1,026,457 ops/sec ±0.63% (95 runs sampled)
subset(^1.2.3-pre.0, *) x 923,789 ops/sec ±0.41% (97 runs sampled)
subset(^1.2.3-pre.0, *) x 923,136 ops/sec ±0.44% (96 runs sampled)
subset(1 || 2 || 3, *) x 432,037 ops/sec ±0.67% (96 runs sampled)

@jviide jviide requested a review from a team as a code owner July 7, 2024 03:02
kurtextrem
kurtextrem reviewed Jul 9, 2024
View reviewed changes
classes/range.js Outdated Show resolved Hide resolved
kurtextrem
kurtextrem reviewed Jul 9, 2024
View reviewed changes
classes/range.js Outdated Show resolved Hide resolved
@jviide jviide changed the title refactor: optimize Range and SemVer parsing and formatting fix: optimize Range and SemVer parsing and formatting Jul 10, 2024
@jviide
Copy link
Contributor Author

jviide commented Jul 10, 2024

The "refactor:" pull request name prefix was not allowed so I picked "fix:", and changed the commit messages to use the same prefix as well.

@wraithgar
Copy link
Member

We generally squash-merge external PRs unless there's a compelling reason to keep each commit. linting will pass if either the PR title or every commit has a valid conventional prefix.

Don't worry about keeping the commit messages "valid" as we go through this PR, as we'll be using the PR title if and when this lands.

wraithgar
wraithgar reviewed Jul 12, 2024
View reviewed changes
classes/semver.js Outdated Show resolved Hide resolved
wraithgar
wraithgar reviewed Jul 12, 2024
View reviewed changes
functions/inc.js Outdated Show resolved Hide resolved
wraithgar
wraithgar reviewed Jul 12, 2024
View reviewed changes
test/classes/range.js Outdated Show resolved Hide resolved
@wraithgar
Copy link
Member

Thanks for the help in reviewing this @kurtextrem. Yes, that comment was referring to s* which is a classic ReDOS vector. Historically we've used the .split approach to fix that, because it's rarely in a hot path where performance matters as much as it does here. Good to know that String.replace is faster.

@jviide jviide changed the title fix: optimize Range and SemVer parsing and formatting fix: optimize Range parsing and formatting Jul 13, 2024
@jviide
fix(range): optimize space character normalization
f4083bd 
Produce fewer intermediate objects when a range's space characters are reduced to single spaces.

This appears to have about 5% performance benefit for bench-subset, and smaller but detectable impact on bench-satisfies.
@jviide
fix(range): optimize range formatting
a9f61b8 
This speeds bench-subset and bench-satisfies by up to 20%.
@jviide
fix(range): compute formatted value lazily
3f5ec0b 
This speeds bench-subset and bench-satisfies by up to 9%.

The external interface of the Range class is kept as-is except that the .range property is not writable anymore.

format test
@wraithgar wraithgar merged commit 73a3d79 into npm:main Jul 16, 2024
@github-actions github-actions bot mentioned this pull request Jul 16, 2024
Merged
@jviide jviide deleted the opt branch July 16, 2024 15:51
hashtagchris pushed a commit that referenced this pull request Jul 16, 2024
@github-actions
chore: release 7.6.3 (#720)
0a12d6c 
🤖 I have created a release *beep* *boop*
---


## [7.6.3](v7.6.2...v7.6.3)
(2024-07-16)

### Bug Fixes

*
[`73a3d79`](73a3d79)
[#726](#726) optimize Range
parsing and formatting (#726) (@jviide)

### Documentation

*
[`2975ece`](2975ece)
[#719](#719) fix extra backtick
typo (#719) (@stdavis)

---
This PR was generated with [Release
Please](https://github.com/googleapis/release-please). See
[documentation](https://github.com/googleapis/release-please#release-please).

Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>
@wojtekmaj wojtekmaj mentioned this pull request Jul 16, 2024
Merged
aduh95 pushed a commit to nodejs/corepack that referenced this pull request Jul 20, 2024
@wojtekmaj
chore(deps): bump semver from 7.6.2 to 7.6.3 (#534)
93a49c8 
This bugfix version of semver includes significant performance improvements that I guess we would like to see in corepack.

See: npm/node-semver#726
@Annie602942 Annie602942 mentioned this pull request Aug 6, 2024
Open
This was referenced Aug 7, 2024
Merged
Merged
@Mhmonicox Mhmonicox mentioned this pull request Aug 7, 2024
Open
@devcurt696 devcurt696 mentioned this pull request Aug 7, 2024
Open
@Exkaleburx Exkaleburx mentioned this pull request Aug 7, 2024
Open
@mcsaur mcsaur mentioned this pull request Aug 7, 2024
Open
This was referenced Sep 17, 2024
Open
Open
Open
Open
@maelis1234 maelis1234 mentioned this pull request Sep 19, 2024
Open
@organich organich mentioned this pull request Sep 22, 2024
Open
This was referenced Sep 22, 2024
Open
Open
Open
@WontonSam WontonSam mentioned this pull request Sep 23, 2024
Open
@m-heyda m-heyda mentioned this pull request Sep 24, 2024
Open
@organich organich mentioned this pull request Sep 24, 2024
Open
@marklacasse marklacasse mentioned this pull request Sep 26, 2024
Open
@phoebeyusnyk phoebeyusnyk mentioned this pull request Sep 29, 2024
Open
This was referenced Sep 30, 2024
Merged
Merged
@tahmid198 tahmid198 mentioned this pull request Sep 30, 2024
Open
@AeonArriving AeonArriving mentioned this pull request Sep 30, 2024
Open
@chambridge chambridge mentioned this pull request Oct 2, 2024
Merged
@InfiniteLove2020 InfiniteLove2020 mentioned this pull request Oct 3, 2024
Open
This was referenced Oct 4, 2024
Open
Open
@CASABECI CASABECI mentioned this pull request Oct 6, 2024
Open
@ms-bot ms-bot mentioned this pull request Oct 7, 2024
Draft
@abdulrahman305 abdulrahman305 mentioned this pull request Oct 22, 2024
Merged
@nerds-github nerds-github mentioned this pull request Oct 24, 2024
Open
@lkeff lkeff mentioned this pull request Oct 26, 2024
Open
@snykyzach snykyzach mentioned this pull request Oct 27, 2024
Open
@suculent suculent mentioned this pull request Oct 30, 2024
Open
@HaLaGu1L HaLaGu1L mentioned this pull request Nov 1, 2024
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@marvinhagemeister marvinhagemeister marvinhagemeister left review comments

@kurtextrem kurtextrem kurtextrem left review comments

@wraithgar wraithgar wraithgar approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
4 participants
@jviide @wraithgar @kurtextrem @marvinhagemeister