microsoft
Use a trie to quickly skip templates in union creation
For #59655
Right now, removeStringLiteralsMatchedByTemplateLiterals iterates over the entire combinatorial explosion of string literals and templates in a union to ensure that any string literal already captured by a template is removed.
In #59655, we have 1,733 template literals and 626,376 string literals, which means quite literally a billion string literal to template literal inferences, all of which "fail" and don't end up removing anything.
My alternative PR #59705 simply says "no, this is too much work, error" like we do in subtype reduction. However, for this particular case, there are actually algorithmic changes we could make to go faster.
The thing that's actually taking the most time in #59655 is the fast path (!!!) where we bail early if the string doesn't start/end with the first/last part of the template type. We're doing some billion startsWith/endsWith, where a significant number of those have common prefixes/suffixes such that we're scanning strings over and over and over.
There's a data structure which can help; the trie. We can put all of our template literals into one trie, then walk it for each string literal. This lets us check every template literal in one traversal, skipping impossible paths to greatly reduce which template literals we'll have to do a full inference on.
Since a trie is just a prefix tree, this PR introduces a data structure which is actually a prefix trie of suffix tries; when walking down the prefix trie looking for potential matches, each of those nodes also contains a suffix trie which is walked down as well. This prevents us from having bad perf when it's actually the suffixes that are long (and opens this to use in other contexts, see the end of this PR description).
For #59655, this nets:
Benchmark 1: node ~/work/TypeScript/built/local-old/tsc.js
Time (mean ± σ): 72.882 s ± 1.093 s [User: 77.298 s, System: 0.572 s]
Range (min … max): 72.052 s … 75.183 s 10 runs
Benchmark 2: node ~/work/TypeScript/built/local/tsc.js
Time (mean ± σ): 11.378 s ± 0.072 s [User: 15.875 s, System: 0.521 s]
Range (min … max): 11.291 s … 11.538 s 10 runs
Summary
'node ~/work/TypeScript/built/local/tsc.js' ran
6.41 ± 0.10 times faster than 'node ~/work/TypeScript/built/local-old/tsc.js'
This speeds up one of our slowest test cases:
Benchmark 1: node ./node_modules/mocha/bin/_mocha -g "templateLiteralTypes1" -t 40000 ./built/local-old/run.js
Time (mean ± σ): 4.947 s ± 0.050 s [User: 5.948 s, System: 0.410 s]
Range (min … max): 4.897 s … 5.074 s 10 runs
Benchmark 2: node ./node_modules/mocha/bin/_mocha -g "templateLiteralTypes1" -t 40000 ./built/local/run.js
Time (mean ± σ): 2.676 s ± 0.164 s [User: 3.719 s, System: 0.335 s]
Range (min … max): 2.580 s … 3.065 s 10 runs
Summary
'node ./node_modules/mocha/bin/_mocha -g "templateLiteralTypes1" -t 40000 ./built/local/run.js' ran
1.85 ± 0.11 times faster than 'node ./node_modules/mocha/bin/_mocha -g "templateLiteralTypes1" -t 40000 ./built/local-old/run.js'
TODO:
- [ ] Determine the cutoff point for when we should not bother to do this; building a trie is not free.
- [ ] Some sort of test like #59655 which takes a massively long time without this PR.
This two-way trie turns out to be exactly the data structure we'd need for #59058; our glob patterns are just a prefix and a suffix with a wildcard in the middle. The only difference is that while the template literal case needs to iterate through all possible matches, our file glob matching only needs to check if there's one match.
Though, paths/exports/etc are ordered, so it may still have to iterate all then sort by priority or something.
Starting jobs; this comment will be updated as builds start and complete.
| Command | Status | Results |
|---|---|---|
pack this |
✅ Started | ✅ Results |
test top400 |
✅ Started | ✅ Results |
user test this |
✅ Started | ✅ Results |
run dt |
✅ Started | ✅ Results |
perf test this faster |
✅ Started | ❌ Results |
Hey @jakebailey, I've packed this into an installable tgz. You can install it for testing by referencing it in your package.json like so:
{
"devDependencies": {
"typescript": "https://typescript.visualstudio.com/cf7ac146-d525-443c-b23c-0d58337efebc/_apis/build/builds/163443/artifacts?artifactName=tgz&fileId=414CCEA03231A30296955EFA7FE60C14F8AC648CA9CF1C873FC42723A7DA009D02&fileName=/typescript-5.7.0-insiders.20240826.tgz"
}
}
and then running npm install.
There is also a playground for this build and an npm module you can use via "typescript": "npm:@typescript-deploys/[email protected]".;
Hey @jakebailey, the results of running the DT tests are ready.
Everything looks the same!
@jakebailey Here are the results of running the user tests with tsc comparing main and refs/pull/59759/merge:
Everything looks good!
@jakebailey 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 | 30 | 30 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 62,153 | 62,153 | ~ | ~ | ~ | p=1.000 n=6 |
| Types | 50,242 | 50,242 | ~ | ~ | ~ | p=1.000 n=6 |
| Memory used | 192,506k (± 0.10%) | 192,480k (± 0.10%) | ~ | 192,365k | 192,848k | p=0.748 n=6 |
| Parse Time | 1.30s (± 0.93%) | 1.31s (± 0.96%) | ~ | 1.29s | 1.32s | p=0.101 n=6 |
| Bind Time | 0.71s | 0.71s | ~ | ~ | ~ | p=1.000 n=6 |
| Check Time | 9.57s (± 0.50%) | 9.60s (± 0.44%) | ~ | 9.55s | 9.65s | p=0.419 n=6 |
| Emit Time | 2.73s (± 0.55%) | 2.72s (± 0.65%) | ~ | 2.69s | 2.74s | p=0.216 n=6 |
| Total Time | 14.31s (± 0.36%) | 14.33s (± 0.28%) | ~ | 14.29s | 14.39s | p=0.574 n=6 |
| angular-1 - node (v18.15.0, x64) | ||||||
| Errors | 7 | 7 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 945,753 | 945,753 | ~ | ~ | ~ | p=1.000 n=6 |
| Types | 410,067 | 410,067 | ~ | ~ | ~ | p=1.000 n=6 |
| Memory used | 1,222,716k (± 0.00%) | 1,222,733k (± 0.00%) | ~ | 1,222,678k | 1,222,807k | p=0.810 n=6 |
| Parse Time | 6.64s (± 0.35%) | 6.61s (± 0.66%) | ~ | 6.56s | 6.68s | p=0.126 n=6 |
| Bind Time | 1.87s (± 0.44%) | 1.86s (± 0.22%) | ~ | 1.86s | 1.87s | p=0.248 n=6 |
| Check Time | 31.25s (± 0.30%) | 31.28s (± 0.26%) | ~ | 31.17s | 31.37s | p=0.468 n=6 |
| Emit Time | 14.97s (± 0.50%) | 14.95s (± 0.67%) | ~ | 14.78s | 15.08s | p=0.935 n=6 |
| Total Time | 54.74s (± 0.28%) | 54.70s (± 0.27%) | ~ | 54.56s | 54.90s | p=0.688 n=6 |
| mui-docs - node (v18.15.0, x64) | ||||||
| Errors | 0 | 0 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 2,532,459 | 2,532,459 | ~ | ~ | ~ | p=1.000 n=6 |
| Types | 996,223 | 996,223 | ~ | ~ | ~ | p=1.000 n=6 |
| Memory used | 2,460,244k (± 0.00%) | 2,460,229k (± 0.00%) | ~ | 2,460,166k | 2,460,319k | p=0.936 n=6 |
| Parse Time | 9.46s (± 0.38%) | 9.43s (± 0.21%) | ~ | 9.41s | 9.46s | p=0.227 n=6 |
| Bind Time | 2.24s (± 0.40%) | 2.23s (± 0.40%) | ~ | 2.22s | 2.24s | p=0.113 n=6 |
| Check Time | 75.18s (± 0.63%) | 75.08s (± 0.44%) | ~ | 74.79s | 75.67s | p=0.689 n=6 |
| Emit Time | 0.28s (± 1.86%) | 0.28s (± 2.26%) | ~ | 0.27s | 0.29s | p=0.386 n=6 |
| Total Time | 87.15s (± 0.53%) | 87.03s (± 0.36%) | ~ | 86.74s | 87.59s | p=0.575 n=6 |
| self-build-src - node (v18.15.0, x64) | ||||||
| Errors | 0 | 0 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 1,232,179 | 1,232,652 | +473 (+ 0.04%) | ~ | ~ | p=0.001 n=6 |
| Types | 264,629 | 264,756 | +127 (+ 0.05%) | ~ | ~ | p=0.001 n=6 |
| Memory used | 2,413,895k (± 6.02%) | 2,355,413k (± 0.01%) | ~ | 2,355,257k | 2,355,647k | p=0.066 n=6 |
| Parse Time | 5.01s (± 0.65%) | 5.04s (± 0.76%) | ~ | 4.97s | 5.08s | p=0.170 n=6 |
| Bind Time | 1.89s (± 0.79%) | 1.91s (± 0.47%) | ~ | 1.90s | 1.92s | p=0.060 n=6 |
| Check Time | 34.73s (± 0.68%) | 34.99s (± 0.19%) | +0.26s (+ 0.73%) | 34.91s | 35.08s | p=0.025 n=6 |
| Emit Time | 3.35s (± 0.92%) | 3.38s (± 0.67%) | ~ | 3.36s | 3.42s | p=0.054 n=6 |
| Total Time | 45.00s (± 0.62%) | 45.32s (± 0.20%) | +0.32s (+ 0.72%) | 45.20s | 45.43s | p=0.013 n=6 |
| self-build-src-public-api - node (v18.15.0, x64) | ||||||
| Errors | 0 | 0 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 1,232,179 | 1,232,652 | +473 (+ 0.04%) | ~ | ~ | p=0.001 n=6 |
| Types | 264,629 | 264,756 | +127 (+ 0.05%) | ~ | ~ | p=0.001 n=6 |
| Memory used | 2,428,783k (± 0.02%) | 2,428,873k (± 0.02%) | ~ | 2,428,043k | 2,429,361k | p=0.378 n=6 |
| Parse Time | 6.23s (± 0.92%) | 6.24s (± 0.62%) | ~ | 6.17s | 6.27s | p=0.520 n=6 |
| Bind Time | 2.03s (± 1.37%) | 2.23s (± 6.77%) | ~ | 2.03s | 2.36s | p=0.053 n=6 |
| Check Time | 41.79s (± 0.59%) | 41.50s (± 1.07%) | ~ | 40.99s | 42.15s | p=0.230 n=6 |
| Emit Time | 4.10s (± 3.23%) | 4.16s (± 3.57%) | ~ | 4.08s | 4.46s | p=0.230 n=6 |
| Total Time | 54.16s (± 0.43%) | 54.15s (± 0.52%) | ~ | 53.82s | 54.54s | p=0.936 n=6 |
| self-compiler - node (v18.15.0, x64) | ||||||
| Errors | 0 | 0 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 257,016 | 257,280 | +264 (+ 0.10%) | ~ | ~ | p=0.001 n=6 |
| Types | 105,789 | 105,916 | +127 (+ 0.12%) | ~ | ~ | p=0.001 n=6 |
| Memory used | 429,773k (± 0.02%) | 430,024k (± 0.01%) | +251k (+ 0.06%) | 429,941k | 430,115k | p=0.005 n=6 |
| Parse Time | 4.18s (± 0.62%) | 4.17s (± 0.33%) | ~ | 4.14s | 4.18s | p=0.744 n=6 |
| Bind Time | 1.60s (± 1.31%) | 1.59s (± 1.23%) | ~ | 1.57s | 1.62s | p=0.625 n=6 |
| Check Time | 22.44s (± 0.51%) | 22.61s (± 0.46%) | +0.17s (+ 0.77%) | 22.51s | 22.80s | p=0.025 n=6 |
| Emit Time | 2.04s (± 0.67%) | 2.03s (± 0.74%) | ~ | 2.02s | 2.05s | p=0.315 n=6 |
| Total Time | 30.26s (± 0.31%) | 30.41s (± 0.31%) | +0.15s (+ 0.49%) | 30.30s | 30.56s | p=0.037 n=6 |
| ts-pre-modules - node (v18.15.0, x64) | ||||||
| Errors | 68 | 68 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 225,018 | 225,018 | ~ | ~ | ~ | p=1.000 n=6 |
| Types | 94,249 | 94,249 | ~ | ~ | ~ | p=1.000 n=6 |
| Memory used | 370,215k (± 0.01%) | 370,251k (± 0.02%) | ~ | 370,160k | 370,303k | p=0.378 n=6 |
| Parse Time | 2.75s (± 0.55%) | 2.74s (± 0.82%) | ~ | 2.72s | 2.78s | p=0.465 n=6 |
| Bind Time | 1.58s (± 1.32%) | 1.58s (± 1.65%) | ~ | 1.55s | 1.62s | p=0.806 n=6 |
| Check Time | 15.74s (± 0.40%) | 15.76s (± 0.18%) | ~ | 15.73s | 15.80s | p=1.000 n=6 |
| Emit Time | 0.00s | 0.00s | ~ | ~ | ~ | p=1.000 n=6 |
| Total Time | 20.07s (± 0.33%) | 20.08s (± 0.27%) | ~ | 20.01s | 20.14s | p=0.810 n=6 |
| vscode - node (v18.15.0, x64) | ||||||
| Errors | 67 | 67 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 3,021,041 | 3,021,041 | ~ | ~ | ~ | p=1.000 n=6 |
| Types | 1,039,433 | 1,039,433 | ~ | ~ | ~ | p=1.000 n=6 |
| Memory used | 3,141,743k (± 0.00%) | 3,141,699k (± 0.00%) | ~ | 3,141,586k | 3,141,787k | p=0.378 n=6 |
| Parse Time | 14.07s (± 0.51%) | 14.05s (± 0.29%) | ~ | 14.00s | 14.10s | p=0.423 n=6 |
| Bind Time | 4.29s (± 0.40%) | 4.33s (± 2.29%) | ~ | 4.27s | 4.53s | p=0.935 n=6 |
| Check Time | 80.27s (± 0.30%) | 80.26s (± 0.19%) | ~ | 80.11s | 80.44s | p=0.936 n=6 |
| Emit Time | 20.49s (± 0.17%) | 20.59s (± 0.28%) | +0.11s (+ 0.52%) | 20.53s | 20.69s | p=0.006 n=6 |
| Total Time | 119.12s (± 0.17%) | 119.23s (± 0.18%) | ~ | 118.95s | 119.60s | p=0.295 n=6 |
| webpack - node (v18.15.0, x64) | ||||||
| Errors | 0 | 0 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 275,311 | 275,311 | ~ | ~ | ~ | p=1.000 n=6 |
| Types | 112,431 | 112,431 | ~ | ~ | ~ | p=1.000 n=6 |
| Memory used | 424,220k (± 0.01%) | 424,242k (± 0.02%) | ~ | 424,115k | 424,322k | p=0.378 n=6 |
| Parse Time | 3.96s (± 0.55%) | 3.96s (± 0.48%) | ~ | 3.94s | 3.99s | p=0.807 n=6 |
| Bind Time | 1.71s (± 1.21%) | 1.72s (± 0.70%) | ~ | 1.71s | 1.74s | p=0.288 n=6 |
| Check Time | 17.55s (± 0.41%) | 17.49s (± 0.43%) | ~ | 17.41s | 17.61s | p=0.172 n=6 |
| Emit Time | 0.00s | 0.00s | ~ | ~ | ~ | p=1.000 n=6 |
| Total Time | 23.22s (± 0.45%) | 23.17s (± 0.32%) | ~ | 23.10s | 23.26s | p=0.422 n=6 |
| xstate-main - node (v18.15.0, x64) | ||||||
| Errors | 0 | 0 | ~ | ~ | ~ | p=1.000 n=6 |
| Symbols | 535,759 | 535,759 | ~ | ~ | ~ | p=1.000 n=6 |
| Types | 177,028 | 177,028 | ~ | ~ | ~ | p=1.000 n=6 |
| Memory used | 480,464k (± 0.01%) | 480,478k (± 0.01%) | ~ | 480,444k | 480,546k | p=0.378 n=6 |
| Parse Time | 3.40s (± 0.24%) | 3.42s (± 0.61%) | ~ | 3.40s | 3.45s | p=0.498 n=6 |
| Bind Time | 1.25s (± 0.60%) | 1.25s (± 0.97%) | ~ | 1.24s | 1.27s | p=0.555 n=6 |
| Check Time | 18.16s (± 0.17%) | 18.20s (± 0.29%) | ~ | 18.15s | 18.29s | p=0.199 n=6 |
| Emit Time | 0.00s | 0.00s | ~ | ~ | ~ | p=1.000 n=6 |
| Total Time | 22.82s (± 0.14%) | 22.86s (± 0.27%) | ~ | 22.80s | 22.98s | p=0.148 n=6 |
- node (v18.15.0, x64)
- 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 | 6 |
| Baseline | baseline | 6 |
Developer Information:
@jakebailey Here are the results of running the top 400 repos with tsc comparing main and refs/pull/59759/merge:
Everything looks good!