RegExp syntax checking performance

rbuckton commented 2 weeks ago

This makes a few changes to the RegExp syntax checking algorithm for possible performance improvements. This also fixes a small typo in one of the RegExp diagnostic messages.

One of the changes is to ensure we perform proper bounds checks when pos might advance past end. To accomplish this, I added the charCodeChecked and charCodeUnchecked functions. charCodeChecked performs boundary tests which both improves reliability and avoids potential deoptimizations due to reading past the end of a string. charCodeUnchecked is simply a wrapper for text.charCodeAt and exists primarily to make it easier to readily identify unchecked vs checked reads from text. charCodeUnchecked should only be used when we've already performed a bounds check before reading a character, such as in a while (pos < end) loop. I've also done the same for code points with codePointChecked and codePointUnchecked. Each of these functions is small, so ideally will be inlined by an optimizing compiler like the one used by V8.

I've primarily focused on optimizing scanRegularExpressionWorker for now. If this seems effective, I will investigate adopting charCodeChecked in more places in the scanner in a later PR.

I've also made a few other small perf improvements:

We now delay allocations for capture group tracking until they are necessary.
scanRegularExpressionWorker has been moved out of reScanSlashToken and updated to use the existing text and end values from the outer scope.
A few frequently referenced variables from the RegExp scanner have been switched to var to avoid TDZ check overhead.

rbuckton commented 2 weeks ago

@typescript-bot perf test

typescript-bot commented 2 weeks ago

Starting jobs; this comment will be updated as builds start and complete.

Command	Status	Results
`perf test`	✅ Started	❌ Results

typescript-bot commented 2 weeks ago

@rbuckton, the perf run you requested failed. You can check the log here.

typescript-bot commented 2 weeks ago

@rbuckton The results of the perf run you requested are in!

Here they are:

tsc

Comparison Report - baseline..pr

_Metric	_baseline	_pr	_Delta	_Best	_Worst	_p-value
_{Compiler-Unions - node (v18.15.0, x64)}
_Errors	₃₀	₃₀	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_62,154	_62,154	_~	_~	_~	_{p=1.000 n=6}
_Types	_50,273	_50,273	_~	_~	_~	_{p=1.000 n=6}
_{Memory used}	_{192,825k (± 0.74%)}	_{192,796k (± 0.75%)}	_~	_192,135k	_195,762k	_{p=0.521 n=6}
_{Parse Time}	_{2.02s (± 1.38%)}	_{1.95s (± 0.46%)}	_{🟩-0.07s (- 3.62%)}	_1.94s	_1.96s	_{p=0.005 n=6}
_{Bind Time}	_{1.07s (± 1.09%)}	_{1.07s (± 0.96%)}	_~	_1.06s	_1.08s	_{p=0.437 n=6}
_{Check Time}	_{14.04s (± 0.08%)}	_{14.08s (± 0.29%)}	_{+0.04s (+ 0.30%)}	_14.04s	_14.13s	_{p=0.040 n=6}
_{Emit Time}	_{3.87s (± 0.90%)}	_{3.88s (± 0.44%)}	_~	_3.86s	_3.90s	_{p=0.627 n=6}
_{Total Time}	_{21.00s (± 0.09%)}	_{20.98s (± 0.23%)}	_~	_20.91s	_21.04s	_{p=0.686 n=6}
_{angular-1 - node (v18.15.0, x64)}
_Errors	₅	₅	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_945,172	_945,172	_~	_~	_~	_{p=1.000 n=6}
_Types	_408,068	_408,068	_~	_~	_~	_{p=1.000 n=6}
_{Memory used}	_{1,222,036k (± 0.00%)}	_{1,222,022k (± 0.00%)}	_~	_1,221,973k	_1,222,117k	_{p=0.378 n=6}
_{Parse Time}	_{6.92s (± 0.50%)}	_{6.78s (± 0.50%)}	_{-0.15s (- 2.14%)}	_6.75s	_6.84s	_{p=0.005 n=6}
_{Bind Time}	_{1.87s (± 0.71%)}	_{1.87s (± 0.28%)}	_~	_1.87s	_1.88s	_{p=0.672 n=6}
_{Check Time}	_{31.41s (± 0.32%)}	_{31.36s (± 0.17%)}	_~	_31.27s	_31.42s	_{p=0.295 n=6}
_{Emit Time}	_{14.57s (± 0.82%)}	_{14.65s (± 0.75%)}	_~	_14.56s	_14.86s	_{p=0.809 n=6}
_{Total Time}	_{54.77s (± 0.42%)}	_{54.66s (± 0.33%)}	_~	_54.52s	_55.00s	_{p=0.297 n=6}
_{mui-docs - node (v18.15.0, x64)}
_Errors	₅	₅	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_1,954,635	_1,954,635	_~	_~	_~	_{p=1.000 n=6}
_Types	_676,418	_676,418	_~	_~	_~	_{p=1.000 n=6}
_{Memory used}	_{1,753,442k (± 0.00%)}	_{1,753,451k (± 0.00%)}	_~	_1,753,422k	_1,753,484k	_{p=0.630 n=6}
_{Parse Time}	_{6.89s (± 0.31%)}	_{6.73s (± 0.35%)}	_{-0.17s (- 2.42%)}	_6.70s	_6.76s	_{p=0.005 n=6}
_{Bind Time}	_{2.31s (± 0.18%)}	_{2.31s (± 0.33%)}	_~	_2.30s	_2.32s	_{p=1.000 n=6}
_{Check Time}	_{56.81s (± 0.11%)}	_{56.85s (± 0.45%)}	_~	_56.63s	_57.29s	_{p=0.470 n=6}
_{Emit Time}	_{0.14s (± 2.88%)}	_0.14s	_~	_~	_~	_{p=0.405 n=6}
_{Total Time}	_{66.16s (± 0.13%)}	_{66.03s (± 0.38%)}	_~	_65.82s	_66.43s	_{p=0.297 n=6}
_{self-build-src - node (v18.15.0, x64)}
_Errors	₀	₀	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_1,215,567	_1,215,606	_{+39 (+ 0.00%)}	_~	_~	_{p=0.001 n=6}
_Types	_257,612	_257,638	_{+26 (+ 0.01%)}	_~	_~	_{p=0.001 n=6}
_{Memory used}	_{2,323,147k (± 0.03%)}	_{2,323,519k (± 0.02%)}	_~	_2,323,071k	_2,324,130k	_{p=0.471 n=6}
_{Parse Time}	_{7.56s (± 0.61%)}	_{7.44s (± 1.06%)}	_{-0.12s (- 1.59%)}	_7.34s	_7.57s	_{p=0.016 n=6}
_{Bind Time}	_{2.75s (± 0.48%)}	_{2.75s (± 0.85%)}	_~	_2.73s	_2.78s	_{p=0.936 n=6}
_{Check Time}	_{49.78s (± 0.59%)}	_{49.66s (± 0.78%)}	_~	_49.29s	_50.38s	_{p=0.471 n=6}
_{Emit Time}	_{3.91s (± 1.63%)}	_{3.95s (± 3.43%)}	_~	_3.85s	_4.22s	_{p=0.810 n=6}
_{Total Time}	_{64.01s (± 0.48%)}	_{63.82s (± 0.61%)}	_~	_63.55s	_64.57s	_{p=0.173 n=6}
_{self-build-src-public-api - node (v18.15.0, x64)}
_Errors	₀	₀	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_1,215,567	_1,215,606	_{+39 (+ 0.00%)}	_~	_~	_{p=0.001 n=6}
_Types	_257,612	_257,638	_{+26 (+ 0.01%)}	_~	_~	_{p=0.001 n=6}
_{Memory used}	_{2,396,896k (± 0.01%)}	_{2,397,995k (± 0.02%)}	_{+1,099k (+ 0.05%)}	_2,397,126k	_2,398,511k	_{p=0.008 n=6}
_{Parse Time}	_{5.25s (± 1.17%)}	_{5.15s (± 0.75%)}	_{-0.09s (- 1.78%)}	_5.10s	_5.20s	_{p=0.016 n=6}
_{Bind Time}	_{1.70s (± 1.33%)}	_{1.69s (± 1.71%)}	_~	_1.64s	_1.73s	_{p=0.870 n=6}
_{Check Time}	_{34.43s (± 0.21%)}	_{34.41s (± 0.17%)}	_~	_34.34s	_34.47s	_{p=0.471 n=6}
_{Emit Time}	_{2.63s (± 0.83%)}	_{2.65s (± 1.54%)}	_~	_2.60s	_2.70s	_{p=0.575 n=6}
_{Total Time}	_{44.02s (± 0.23%)}	_{43.91s (± 0.22%)}	_~	_43.81s	_44.04s	_{p=0.199 n=6}
_{self-compiler - node (v18.15.0, x64)}
_Errors	₀	₀	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_256,196	_256,224	_{+28 (+ 0.01%)}	_~	_~	_{p=0.001 n=6}
_Types	_103,640	_103,656	_{+16 (+ 0.02%)}	_~	_~	_{p=0.001 n=6}
_{Memory used}	_{424,190k (± 0.01%)}	_{424,200k (± 0.01%)}	_~	_424,167k	_424,242k	_{p=0.471 n=6}
_{Parse Time}	_{3.49s (± 1.55%)}	_{3.33s (± 0.35%)}	_{🟩-0.16s (- 4.72%)}	_3.31s	_3.34s	_{p=0.005 n=6}
_{Bind Time}	_{1.30s (± 0.90%)}	_{1.30s (± 0.84%)}	_~	_1.29s	_1.32s	_{p=0.865 n=6}
_{Check Time}	_{18.21s (± 0.37%)}	_{18.18s (± 0.39%)}	_~	_18.09s	_18.27s	_{p=0.687 n=6}
_{Emit Time}	_{1.36s (± 1.28%)}	_{1.38s (± 0.89%)}	_~	_1.36s	_1.39s	_{p=0.241 n=6}
_{Total Time}	_{24.37s (± 0.31%)}	_{24.18s (± 0.32%)}	_{-0.18s (- 0.76%)}	_24.06s	_24.25s	_{p=0.005 n=6}
_{ts-pre-modules - node (v18.15.0, x64)}
_Errors	₃₅	₃₅	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_224,824	_224,824	_~	_~	_~	_{p=1.000 n=6}
_Types	_93,390	_93,390	_~	_~	_~	_{p=1.000 n=6}
_{Memory used}	_{369,410k (± 0.05%)}	_{369,296k (± 0.00%)}	_{-114k (- 0.03%)}	_369,279k	_369,315k	_{p=0.037 n=6}
_{Parse Time}	_{3.67s (± 0.38%)}	_{3.53s (± 1.05%)}	_{🟩-0.14s (- 3.91%)}	_3.49s	_3.59s	_{p=0.005 n=6}
_{Bind Time}	_{1.95s (± 1.41%)}	_{1.94s (± 0.78%)}	_~	_1.92s	_1.96s	_{p=0.413 n=6}
_{Check Time}	_{19.48s (± 0.41%)}	_{19.44s (± 0.24%)}	_~	_19.36s	_19.49s	_{p=0.195 n=6}
_{Emit Time}	_0.00s	_0.00s	_~	_~	_~	_{p=1.000 n=6}
_{Total Time}	_{25.10s (± 0.30%)}	_{24.90s (± 0.21%)}	_{-0.20s (- 0.80%)}	_24.83s	_24.97s	_{p=0.005 n=6}
_{vscode - node (v18.15.0, x64)}
_Errors	₄	₄	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_2,797,149	_2,797,149	_~	_~	_~	_{p=1.000 n=6}
_Types	_950,053	_950,053	_~	_~	_~	_{p=1.000 n=6}
_{Memory used}	_{2,925,215k (± 0.00%)}	_{2,925,305k (± 0.00%)}	_~	_2,925,155k	_2,925,515k	_{p=0.575 n=6}
_{Parse Time}	_{13.56s (± 0.28%)}	_{13.32s (± 0.30%)}	_{-0.24s (- 1.79%)}	_13.26s	_13.38s	_{p=0.005 n=6}
_{Bind Time}	_{4.12s (± 2.10%)}	_{4.09s (± 0.25%)}	_~	_4.07s	_4.10s	_{p=0.615 n=6}
_{Check Time}	_{73.08s (± 0.39%)}	_{73.11s (± 0.48%)}	_~	_72.52s	_73.49s	_{p=0.689 n=6}
_{Emit Time}	_{21.41s (± 9.45%)}	_{21.03s (± 8.39%)}	_~	_19.61s	_23.52s	_{p=0.810 n=6}
_{Total Time}	_{112.17s (± 1.88%)}	_{111.54s (± 1.59%)}	_~	_110.03s	_114.21s	_{p=0.575 n=6}
_{webpack - node (v18.15.0, x64)}
_Errors	₀	₀	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_265,853	_265,853	_~	_~	_~	_{p=1.000 n=6}
_Types	_108,438	_108,438	_~	_~	_~	_{p=1.000 n=6}
_{Memory used}	_{410,385k (± 0.02%)}	_{410,331k (± 0.01%)}	_~	_410,276k	_410,388k	_{p=0.109 n=6}
_{Parse Time}	_{3.95s (± 0.56%)}	_{3.84s (± 0.61%)}	_{-0.11s (- 2.74%)}	_3.80s	_3.87s	_{p=0.005 n=6}
_{Bind Time}	_{1.69s (± 0.79%)}	_{1.67s (± 0.63%)}	_{-0.02s (- 1.38%)}	_1.65s	_1.68s	_{p=0.017 n=6}
_{Check Time}	_{17.05s (± 0.41%)}	_{17.06s (± 0.30%)}	_~	_16.97s	_17.10s	_{p=0.936 n=6}
_{Emit Time}	_0.00s	_0.00s	_~	_~	_~	_{p=1.000 n=6}
_{Total Time}	_{22.69s (± 0.36%)}	_{22.57s (± 0.33%)}	_{-0.12s (- 0.54%)}	_22.43s	_22.64s	_{p=0.045 n=6}
_{xstate-main - node (v18.15.0, x64)}
_Errors	₀	₀	_~	_~	_~	_{p=1.000 n=6}
_Symbols	_523,981	_523,981	_~	_~	_~	_{p=1.000 n=6}
_Types	_178,708	_178,708	_~	_~	_~	_{p=1.000 n=6}
_{Memory used}	_{461,203k (± 0.01%)}	_{461,166k (± 0.01%)}	_~	_461,120k	_461,206k	_{p=0.298 n=6}
_{Parse Time}	_{2.69s (± 0.61%)}	_{2.61s (± 0.56%)}	_{-0.08s (- 2.92%)}	_2.59s	_2.63s	_{p=0.005 n=6}
_{Bind Time}	_{0.98s (± 0.64%)}	_{0.99s (± 0.82%)}	_{+0.01s (+ 1.36%)}	_0.98s	_1.00s	_{p=0.023 n=6}
_{Check Time}	_{15.47s (± 0.36%)}	_{15.31s (± 0.26%)}	_{-0.16s (- 1.02%)}	_15.26s	_15.36s	_{p=0.005 n=6}
_{Emit Time}	_0.00s	_0.00s	_~	_~	_~	_{p=1.000 n=6}
_{Total Time}	_{19.14s (± 0.24%)}	_{18.91s (± 0.19%)}	_{-0.23s (- 1.18%)}	_18.87s	_18.97s	_{p=0.005 n=6}

System info unknown

Hosts

node (v18.15.0, x64)

Scenarios

Compiler-Unions - node (v18.15.0, x64)
angular-1 - node (v18.15.0, x64)
mui-docs - node (v18.15.0, x64)
self-build-src - node (v18.15.0, x64)
self-build-src-public-api - node (v18.15.0, x64)
self-compiler - node (v18.15.0, x64)
ts-pre-modules - node (v18.15.0, x64)
vscode - node (v18.15.0, x64)
webpack - node (v18.15.0, x64)
xstate-main - node (v18.15.0, x64)

_Benchmark	_Name	_Iterations
_Current	_pr	₆
_Baseline	_baseline	₆

tsserver

Comparison Report - baseline..pr

_Metric	_baseline	_pr	_Delta	_Best	_Worst	_p-value
_{Compiler-UnionsTSServer - node (v18.15.0, x64)}
_{Req 1 - updateOpen}	_{3,504ms (± 0.33%)}	_{3,421ms (± 0.43%)}	_{-83ms (- 2.36%)}	_3,399ms	_3,436ms	_{p=0.005 n=6}
_{Req 2 - geterr}	_{7,555ms (± 0.59%)}	_{7,546ms (± 0.55%)}	_~	_7,478ms	_7,603ms	_{p=0.575 n=6}
_{Req 3 - references}	_{439ms (± 1.96%)}	_{428ms (± 1.03%)}	_{-12ms (- 2.62%)}	_423ms	_436ms	_{p=0.016 n=6}
_{Req 4 - navto}	_{336ms (± 0.36%)}	_{337ms (± 0.75%)}	_~	_334ms	_341ms	_{p=0.803 n=6}
_{Req 5 - completionInfo count}	_1,357	_1,357	_~	_~	_~	_{p=1.000 n=6}
_{Req 5 - completionInfo}	_{112ms (± 1.04%)}	_{116ms (± 8.29%)}	_~	_111ms	_135ms	_{p=0.867 n=6}
_{CompilerTSServer - node (v18.15.0, x64)}
_{Req 1 - updateOpen}	_{3,701ms (± 1.21%)}	_{3,581ms (± 0.38%)}	_{🟩-120ms (- 3.25%)}	_3,556ms	_3,593ms	_{p=0.005 n=6}
_{Req 2 - geterr}	_{5,702ms (± 0.16%)}	_{5,685ms (± 0.40%)}	_~	_5,652ms	_5,715ms	_{p=0.128 n=6}
_{Req 3 - references}	_{445ms (± 0.46%)}	_{443ms (± 0.46%)}	_~	_441ms	_447ms	_{p=0.145 n=6}
_{Req 4 - navto}	_{341ms (± 1.35%)}	_{340ms (± 1.31%)}	_~	_333ms	_346ms	_{p=1.000 n=6}
_{Req 5 - completionInfo count}	_1,519	_1,519	_~	_~	_~	_{p=1.000 n=6}
_{Req 5 - completionInfo}	_{111ms (± 6.02%)}	_{109ms (± 0.90%)}	_~	_107ms	_110ms	_{p=0.929 n=6}
_{xstate-main-1-tsserver - node (v18.15.0, x64)}
_{Req 1 - updateOpen}	_{6,228ms (± 0.67%)}	_{7,346ms (± 8.35%)}	_~	_6,095ms	_7,632ms	_{p=0.066 n=6}
_{Req 2 - geterr}	_{1,633ms (± 8.49%)}	_{1,627ms (± 8.59%)}	_~	_1,342ms	_1,695ms	_{p=0.810 n=6}
_{Req 3 - references}	_{127ms (± 3.66%)}	_{123ms (± 9.38%)}	_~	_100ms	_133ms	_{p=0.934 n=6}
_{Req 4 - navto}	_{588ms (± 2.73%)}	_{584ms (± 2.54%)}	_~	_573ms	_609ms	_{p=0.871 n=6}
_{Req 5 - completionInfo count}	_3,413	_3,413	_~	_~	_~	_{p=1.000 n=6}
_{Req 5 - completionInfo}	_{1,273ms (± 1.81%)}	_{1,261ms (± 1.97%)}	_~	_1,228ms	_1,304ms	_{p=0.423 n=6}

System info unknown

Hosts

node (v18.15.0, x64)

Scenarios

CompilerTSServer - node (v18.15.0, x64)
Compiler-UnionsTSServer - node (v18.15.0, x64)
xstate-main-1-tsserver - node (v18.15.0, x64)

_Benchmark	_Name	_Iterations
_Current	_pr	₆
_Baseline	_baseline	₆

startup

Comparison Report - baseline..pr

_Metric	_baseline	_pr	_Delta	_Best	_Worst	_p-value
_{tsc-startup - node (v18.15.0, x64)}
_{Execution time}	_{227.45ms (± 0.18%)}	_{227.31ms (± 0.17%)}	_{-0.14ms (- 0.06%)}	_225.53ms	_231.35ms	_{p=0.001 n=600}
_{tsserver-startup - node (v18.15.0, x64)}
_{Execution time}	_{359.11ms (± 0.27%)}	_{359.09ms (± 0.28%)}	_~	_350.85ms	_367.65ms	_{p=0.655 n=600}
_{tsserverlibrary-startup - node (v18.15.0, x64)}
_{Execution time}	_{287.26ms (± 0.28%)}	_{287.27ms (± 0.32%)}	_~	_280.38ms	_306.23ms	_{p=0.291 n=600}
_{typescript-startup - node (v18.15.0, x64)}
_{Execution time}	_{286.91ms (± 0.30%)}	_{286.91ms (± 0.28%)}	_~	_280.02ms	_293.59ms	_{p=0.230 n=600}

System info unknown

Hosts

node (v18.15.0, x64)

Scenarios

tsc-startup - node (v18.15.0, x64)
tsserver-startup - node (v18.15.0, x64)
tsserverlibrary-startup - node (v18.15.0, x64)
typescript-startup - node (v18.15.0, x64)

_Benchmark	_Name	_Iterations
_Current	_pr	₆
_Baseline	_baseline	₆

Developer Information:

Download Benchmarks

rbuckton commented 2 weeks ago

@typescript-bot run dt @typescript-bot test top400 @typescript-bot test tsserver top100 @typescript-bot user test this @typescript-bot user test tsserver

typescript-bot commented 2 weeks ago

Starting jobs; this comment will be updated as builds start and complete.

Command	Status	Results
`run dt`	✅ Started	✅ Results
`test top400`	✅ Started	✅ Results
`test tsserver top100`	✅ Started
`user test this`	✅ Started	✅ Results
`user test tsserver`	✅ Started	✅ Results

typescript-bot commented 2 weeks ago

@rbuckton Here are the results of running the user tests comparing main and refs/pull/58339/merge:

Everything looks good!

typescript-bot commented 2 weeks ago

Hey @rbuckton, the results of running the DT tests are ready.

Everything looks the same!

You can check the log here.

typescript-bot commented 2 weeks ago

@rbuckton Here are the results of running the user tests comparing main and refs/pull/58339/merge:

Everything looks good!

typescript-bot commented 2 weeks ago

@rbuckton Here are the results of running the top 400 repos comparing main and refs/pull/58339/merge:

Everything looks good!

jakebailey commented 2 weeks ago

The perf seels really good. Is that all from avoiding out of bounds?

rbuckton commented 2 weeks ago

The perf seels really good. Is that all from avoiding out of bounds?

Yeah, if charCodeAt is called for an out of bounds index it returns NaN, which isn't an SMI. IIRC, accessing a string out of bounds also results in sub optional compilation as it requires a recompile to introduce additional checks in the compiled code.

DanielRosenwasser commented 2 weeks ago

Might be worth mentioning in the PR description that you also var-ified the regular expression parser (https://github.com/microsoft/TypeScript/issues/52924).

DanielRosenwasser commented 2 weeks ago

Also other specific optimizations - like hoisting out helper functions and lazily initializing state for captures.

rbuckton commented 2 weeks ago

I've been working on expanding this throughout scanner.ts and writing up a lint rule to ensure enforcement, so I'll probably need another review shortly.

rbuckton commented 2 weeks ago

I've been working on expanding this throughout scanner.ts and writing up a lint rule to ensure enforcement, so I'll probably need another review shortly.

Since I have some additional testing to do, I think I'll put those changes up as a separate PR following this one.

microsoft / TypeScript

RegExp syntax checking performance #58339

tsc

tsserver

startup