Skip to content

fix: replace regex used to split ranges#434

Merged
lukekarrys merged 1 commit intomainfrom
lk/polynomial-regex
Mar 25, 2022
Merged

fix: replace regex used to split ranges#434
lukekarrys merged 1 commit intomainfrom
lk/polynomial-regex

Conversation

@lukekarrys
Copy link
Contributor

@lukekarrys lukekarrys commented Feb 26, 2022

Found in #433, the regex used to split ranges on || was padded by \s*
on either side causing a decrease in performance when used on range
strings with a lot of spaces. Since the result of the split is
immediately trimmed, we can just split on the string instead.

@lukekarrys
fix: replace regex used to split ranges
499a161 
Found in #433, the regex used to split ranges on `||` was padded by `\s*`
on either side causing a decrease in performance when used on range
strings with a lot of spaces. Since the result of the split is
immediately trimmed, we can just split on the string instead.
@lukekarrys
Copy link
Contributor Author

lukekarrys commented Feb 26, 2022 •
edited
Loading

I ran some benchmarks locally using the following script which passes different arguments to range.split for ranges with differing amounts of whitespace. The difference between /\|\|/ and '||' seemed trivial, so I went with '||'.

const Range = require('./classes/range')
const a = process.argv.slice(2)
const s = ' '.repeat(Number(a[0]))
const r = `${s}1.1.1${s}`
const v = `${r}||${r}`.repeat(Number(a[1]))
const split = ({
  poly: /\s*\|\|\s*/,
  regex: /\|\|/,
  string:  '||',
})[a[2]]
new Range(v, {}, split)

5 spaces x 10 versions

❯ hyperfine -w 3 -L r poly,regex,string -L s 5 -L v 10 'node regex.js {s} {v} {r}'
Benchmark 1: node regex.js 5 10 poly
  Time (mean ± σ):      55.1 ms ±   2.0 ms    [User: 42.0 ms, System: 13.1 ms]
  Range (min … max):    51.5 ms …  61.8 ms    48 runs
 
Benchmark 2: node regex.js 5 10 regex
  Time (mean ± σ):      54.3 ms ±   1.9 ms    [User: 41.6 ms, System: 12.4 ms]
  Range (min … max):    50.6 ms …  58.1 ms    47 runs
 
Benchmark 3: node regex.js 5 10 string
  Time (mean ± σ):      54.6 ms ±   2.1 ms    [User: 41.9 ms, System: 12.5 ms]
  Range (min … max):    50.5 ms …  61.9 ms    50 runs
 
Summary
  'node regex.js 5 10 regex' ran
    1.01 ± 0.05 times faster than 'node regex.js 5 10 string'
    1.01 ± 0.05 times faster than 'node regex.js 5 10 poly'

100 spaces x 100 versions

❯ hyperfine -w 3 -L r poly,regex,string -L s 100 -L v 100 'node regex.js {s} {v} {r}'
Benchmark 1: node regex.js 100 100 poly
  Time (mean ± σ):      57.4 ms ±   1.5 ms    [User: 44.5 ms, System: 12.5 ms]
  Range (min … max):    54.0 ms …  59.8 ms    46 runs
 
Benchmark 2: node regex.js 100 100 regex
  Time (mean ± σ):      54.7 ms ±   2.2 ms    [User: 41.8 ms, System: 12.6 ms]
  Range (min … max):    51.3 ms …  64.3 ms    47 runs
 
Benchmark 3: node regex.js 100 100 string
  Time (mean ± σ):      54.4 ms ±   2.0 ms    [User: 41.7 ms, System: 12.5 ms]
  Range (min … max):    50.9 ms …  62.8 ms    49 runs
 
Summary
  'node regex.js 100 100 string' ran
    1.01 ± 0.06 times faster than 'node regex.js 100 100 regex'
    1.05 ± 0.05 times faster than 'node regex.js 100 100 poly'

1000 spaces x 1000 versions

❯ hyperfine -w 3 -L r poly,regex,string -L s 1e3 -L v 1e3 'node regex.js {s} {v} {r}'
Benchmark 1: node regex.js 1e3 1e3 poly
  Time (mean ± σ):      2.179 s ±  0.011 s    [User: 2.152 s, System: 0.018 s]
  Range (min … max):    2.166 s …  2.202 s    10 runs
 
Benchmark 2: node regex.js 1e3 1e3 regex
  Time (mean ± σ):      68.4 ms ±   2.1 ms    [User: 53.6 ms, System: 14.2 ms]
  Range (min … max):    66.6 ms …  80.1 ms    40 runs
 
  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet PC without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.
 
Benchmark 3: node regex.js 1e3 1e3 string
  Time (mean ± σ):      68.5 ms ±   2.2 ms    [User: 53.5 ms, System: 14.3 ms]
  Range (min … max):    65.9 ms …  80.3 ms    40 runs
 
  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet PC without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.
 
Summary
  'node regex.js 1e3 1e3 regex' ran
    1.00 ± 0.04 times faster than 'node regex.js 1e3 1e3 string'
   31.85 ± 1.00 times faster than 'node regex.js 1e3 1e3 poly'

lukekarrys added a commit that referenced this pull request Feb 26, 2022
@lukekarrys
chore: use @npmcli/template-oss
e628d22 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores. It specifically pins to the latest version of the library
in order to allow for the following manual changes:

- Files outside of `lib/` to avoid breaking public API
- Keeping engines (and testing) on `>=10`
- Installs `npm@7` in CI to work with node 10

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
@lukekarrys lukekarrys mentioned this pull request Feb 26, 2022
Merged
lukekarrys added a commit that referenced this pull request Mar 23, 2022
@lukekarrys
chore: use @npmcli/template-oss
f75a170 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores. It specifically pins to the latest version of the library
in order to allow for the following manual changes:

- Files outside of `lib/` to avoid breaking public API
- Keeping engines (and testing) on `>=10`
- Installs `npm@7` in CI to work with node 10

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
chore: use @npmcli/template-oss
8a3aa0e 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores. It specifically pins to the latest version of the library
in order to allow for the following manual changes:

- Files outside of `lib/` to avoid breaking public API
- Keeping engines (and testing) on `>=10`
- Installs `npm@7` in CI to work with node 10

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
nlf
nlf approved these changes Mar 25, 2022
View reviewed changes
Copy link
Contributor

@nlf nlf left a comment

Choose a reason for hiding this comment

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

this is very clearly correct 👍

@lukekarrys lukekarrys merged commit 9ab7b71 into main Mar 25, 2022
@lukekarrys lukekarrys deleted the lk/polynomial-regex branch March 25, 2022 18:29
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
chore: use @npmcli/template-oss
23dbd47 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores.

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
chore: use @npmcli/template-oss
8ed4b9d 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores.

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
fix: replace regex used to split ranges (#434)
60cbd60 
Found in #433, the regex used to split ranges on `||` was padded by `\s*`
on either side causing a decrease in performance when used on range
strings with a lot of spaces. Since the result of the split is
immediately trimmed, we can just split on the string instead.
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
fix: replace regex used to split ranges (#434)
fd59bca 
Found in #433, the regex used to split ranges on `||` was padded by `\s*`
on either side causing a decrease in performance when used on range
strings with a lot of spaces. Since the result of the split is
immediately trimmed, we can just split on the string instead.
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
chore: use @npmcli/template-oss
7ce491b 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores.

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
chore: use @npmcli/template-oss
e920066 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores.

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
chore: use @npmcli/template-oss
8b4da5f 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores.

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
chore: use @npmcli/template-oss
b9515aa 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores.

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
chore: use @npmcli/template-oss
3c88c5e 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores.

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
lukekarrys added a commit that referenced this pull request Mar 25, 2022
@lukekarrys
chore: use @npmcli/template-oss (#433)
4907647 
This adds `@npmcli/template-oss` to manage GitHub Actions, linting, and
other chores.

This surfaced a few bugs which I opted to fix in separate issues:

- #432
- #434
@github-actions github-actions bot mentioned this pull request Mar 25, 2022
Merged
@ireinhart ireinhart mentioned this pull request Apr 7, 2022
Closed
1 task
@snyk-bot snyk-bot mentioned this pull request May 16, 2023
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

1 more reviewer

@nlf nlf nlf approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@lukekarrys @nlf