Optimize substitution types by ahejlsberg · Pull Request #50397 · microsoft/TypeScript · GitHub

This PR optimizes creation and instantiation of substitution types. Two main changes:

Substitution types previously stored the substitute type as an intersection between the base type and the constraint being added. These components are now stored separately (in baseType and constraint properties) and intersected when needed. The separation enables a more efficient check for whether an instantiated substitution type should be preserved or resolved to its base type: Peviously this check compared the base type to the full substitution intersection, it now just compares the base type to the constraint. This turned out to be the origin of the relation cache overflow in RangeError: Map maximum size exceeded with typescript@4.8.1-rc #50290.
Due to some erroneous logic in getTypeFromIndexedAccessTypeNode, previously we would stack two substitution types on top of each other for indexed access types. This created a lot of unnecessary work.

With these optimizations, the check time for the repro in #50290 drops from 11.2s to 5.2s, a greater than 50% reduction! I imagine other projects that contain complicated conditional types may see a similar benefit.

Fixes #50290.

ghost

TypeScript Bot (@typescript-bot) test this
TypeScript Bot (@typescript-bot) user test this inline
TypeScript Bot (@typescript-bot) run dt
TypeScript Bot (@typescript-bot) perf test faster

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've started to run the abridged perf test suite on this PR at a4a9ede. You can monitor the build here.

Update: The results are in!

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've started to run the parallelized Definitely Typed test suite on this PR at a4a9ede. You can monitor the build here.

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've started to run the extended test suite on this PR at a4a9ede. You can monitor the build here.

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've started to run the diff-based user code test suite on this PR at a4a9ede. You can monitor the build here.

Update: The results are in!

ghost

Anders Hejlsberg (@ahejlsberg) Here are the results of running the user test suite comparing main and refs/pull/50397/merge:

Something interesting changed - please have a look.

Details

puppeteer

scripts/tsconfig.json

[NEW] error TS2394: This overload signature is not compatible with its implementation signature.
- src/common/JSHandle.ts#L168

tsconfig.json

[NEW] error TS2394: This overload signature is not compatible with its implementation signature.
- src/common/JSHandle.ts#L168

ghost

Anders Hejlsberg (@ahejlsberg)
The results of the perf run you requested are in!

Here they are:

Comparison Report - main..50397

Metric	main	50397	Delta	Best	Worst
Angular - node (v14.15.1, x64)
Memory used	337,333k (± 0.01%)	337,311k (± 0.01%)	-22k (- 0.01%)	337,261k	337,375k
Parse Time	2.05s (± 0.79%)	2.04s (± 0.59%)	-0.01s (- 0.39%)	2.02s	2.07s
Bind Time	0.79s (± 0.73%)	0.79s (± 0.51%)	-0.00s (- 0.13%)	0.78s	0.80s
Check Time	5.80s (± 0.44%)	5.81s (± 0.39%)	+0.01s (+ 0.10%)	5.76s	5.86s
Emit Time	6.20s (± 0.61%)	6.19s (± 0.74%)	-0.01s (- 0.15%)	6.11s	6.28s
Total Time	14.85s (± 0.34%)	14.84s (± 0.39%)	-0.01s (- 0.07%)	14.68s	14.95s
Compiler-Unions - node (v14.15.1, x64)
Memory used	192,155k (± 0.02%)	192,135k (± 0.01%)	-20k (- 0.01%)	192,086k	192,177k
Parse Time	0.85s (± 0.78%)	0.85s (± 0.52%)	+0.00s (+ 0.24%)	0.84s	0.86s
Bind Time	0.48s (± 0.92%)	0.49s (± 1.01%)	+0.00s (+ 0.83%)	0.48s	0.50s
Check Time	6.88s (± 0.63%)	6.90s (± 0.68%)	+0.02s (+ 0.28%)	6.81s	7.01s
Emit Time	2.40s (± 0.65%)	2.42s (± 0.68%)	+0.02s (+ 0.67%)	2.38s	2.46s
Total Time	10.61s (± 0.39%)	10.65s (± 0.44%)	+0.04s (+ 0.39%)	10.59s	10.77s
Monaco - node (v14.15.1, x64)
Memory used	326,020k (± 0.01%)	326,047k (± 0.01%)	+27k (+ 0.01%)	326,002k	326,099k
Parse Time	1.57s (± 0.67%)	1.57s (± 0.97%)	+0.01s (+ 0.38%)	1.54s	1.62s
Bind Time	0.72s (± 0.97%)	0.72s (± 0.86%)	+0.00s (+ 0.00%)	0.71s	0.73s
Check Time	5.69s (± 0.45%)	5.68s (± 0.56%)	-0.01s (- 0.11%)	5.63s	5.76s
Emit Time	3.34s (± 1.06%)	3.33s (± 0.66%)	-0.00s (- 0.15%)	3.29s	3.40s
Total Time	11.31s (± 0.54%)	11.31s (± 0.46%)	-0.01s (- 0.06%)	11.21s	11.44s
TFS - node (v14.15.1, x64)
Memory used	289,131k (± 0.01%)	289,126k (± 0.01%)	-5k (- 0.00%)	289,072k	289,176k
Parse Time	1.32s (± 1.49%)	1.32s (± 1.82%)	-0.00s (- 0.00%)	1.28s	1.37s
Bind Time	0.71s (± 4.22%)	0.73s (± 5.38%)	+0.01s (+ 1.97%)	0.67s	0.79s
Check Time	5.33s (± 0.49%)	5.34s (± 0.62%)	+0.02s (+ 0.30%)	5.27s	5.40s
Emit Time	3.47s (± 2.14%)	3.48s (± 2.04%)	+0.01s (+ 0.35%)	3.38s	3.62s
Total Time	10.83s (± 0.73%)	10.87s (± 0.66%)	+0.04s (+ 0.39%)	10.75s	11.07s
material-ui - node (v14.15.1, x64)
Memory used	450,523k (± 0.01%)	437,974k (± 0.00%)	-12,549k (- 2.79%)	437,942k	438,025k
Parse Time	1.86s (± 0.40%)	1.85s (± 0.70%)	-0.00s (- 0.16%)	1.83s	1.89s
Bind Time	0.58s (± 1.12%)	0.58s (± 0.90%)	+0.00s (+ 0.17%)	0.57s	0.59s
Check Time	13.18s (± 0.47%)	12.90s (± 0.62%)	-0.28s (- 2.14%)	12.76s	13.08s
Emit Time	0.00s (± 0.00%)	0.00s (± 0.00%)	0.00s ( NaN%)	0.00s	0.00s
Total Time	15.62s (± 0.39%)	15.33s (± 0.61%)	-0.28s (- 1.82%)	15.18s	15.54s
xstate - node (v14.15.1, x64)
Memory used	546,040k (± 0.01%)	545,888k (± 0.01%)	-153k (- 0.03%)	545,841k	545,947k
Parse Time	2.58s (± 0.45%)	2.60s (± 0.43%)	+0.02s (+ 0.77%)	2.59s	2.64s
Bind Time	0.98s (± 0.90%)	0.97s (± 0.84%)	-0.00s (- 0.41%)	0.96s	1.00s
Check Time	1.55s (± 0.54%)	1.56s (± 0.58%)	+0.01s (+ 0.65%)	1.54s	1.58s
Emit Time	0.07s (± 4.13%)	0.07s (± 3.14%)	-0.00s (- 1.39%)	0.07s	0.08s
Total Time	5.19s (± 0.41%)	5.22s (± 0.30%)	+0.03s (+ 0.56%)	5.18s	5.26s

System

Machine Name	ts-ci-ubuntu
Platform	linux 4.4.0-210-generic
Architecture	x64
Available Memory	16 GB
Available Memory	15 GB
CPUs	4 × Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz

Hosts

node (v14.15.1, x64)

Scenarios

Angular - node (v14.15.1, x64)
Compiler-Unions - node (v14.15.1, x64)
Monaco - node (v14.15.1, x64)
TFS - node (v14.15.1, x64)
material-ui - node (v14.15.1, x64)
xstate - node (v14.15.1, x64)

Benchmark	Name	Iterations
Current	50397	10
Baseline	main	10

Developer Information:

Download Benchmark

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've run the RWC suite on this PR - assuming you're on the TS core team, you can view the resulting diff here.

ghost

TypeScript Bot (@typescript-bot) test this
TypeScript Bot (@typescript-bot) user test this inline
TypeScript Bot (@typescript-bot) run dt
TypeScript Bot (@typescript-bot) perf test faster

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've started to run the extended test suite on this PR at e73d268. You can monitor the build here.

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've started to run the diff-based user code test suite on this PR at e73d268. You can monitor the build here.

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've started to run the abridged perf test suite on this PR at e73d268. You can monitor the build here.

Update: The results are in!

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've started to run the parallelized Definitely Typed test suite on this PR at e73d268. You can monitor the build here.

ghost

Heya Anders Hejlsberg (@ahejlsberg), I've run the RWC suite on this PR - assuming you're on the TS core team, you can view the resulting diff here.

ghost

Anders Hejlsberg (@ahejlsberg)
The results of the perf run you requested are in!

Here they are:

Comparison Report - main..50397

Metric	main	50397	Delta	Best	Worst
Angular - node (v14.15.1, x64)
Memory used	337,196k (± 0.07%)	337,307k (± 0.01%)	+111k (+ 0.03%)	337,274k	337,357k
Parse Time	2.06s (± 0.51%)	2.06s (± 0.56%)	-0.00s (- 0.05%)	2.04s	2.09s
Bind Time	0.79s (± 0.78%)	0.79s (± 0.84%)	+0.00s (+ 0.25%)	0.78s	0.81s
Check Time	5.84s (± 0.90%)	5.77s (± 0.38%)	-0.07s (- 1.25%)	5.71s	5.82s
Emit Time	6.24s (± 0.88%)	6.17s (± 0.57%)	-0.06s (- 1.03%)	6.09s	6.25s
Total Time	14.94s (± 0.72%)	14.80s (± 0.33%)	-0.14s (- 0.93%)	14.68s	14.88s
Compiler-Unions - node (v14.15.1, x64)
Memory used	192,138k (± 0.02%)	192,143k (± 0.02%)	+6k (+ 0.00%)	192,059k	192,202k
Parse Time	0.85s (± 0.78%)	0.85s (± 0.56%)	-0.00s (- 0.35%)	0.84s	0.86s
Bind Time	0.49s (± 0.70%)	0.48s (± 1.03%)	-0.00s (- 0.41%)	0.48s	0.50s
Check Time	6.87s (± 0.74%)	6.87s (± 0.55%)	-0.00s (- 0.01%)	6.77s	6.94s
Emit Time	2.40s (± 0.41%)	2.41s (± 0.50%)	+0.01s (+ 0.33%)	2.38s	2.44s
Total Time	10.61s (± 0.46%)	10.61s (± 0.34%)	+0.00s (+ 0.03%)	10.52s	10.66s
Monaco - node (v14.15.1, x64)
Memory used	326,027k (± 0.01%)	326,032k (± 0.00%)	+4k (+ 0.00%)	326,001k	326,059k
Parse Time	1.57s (± 0.35%)	1.57s (± 0.53%)	-0.00s (- 0.13%)	1.55s	1.58s
Bind Time	0.72s (± 0.51%)	0.72s (± 0.62%)	+0.01s (+ 0.84%)	0.71s	0.73s
Check Time	5.71s (± 0.53%)	5.69s (± 0.39%)	-0.02s (- 0.32%)	5.64s	5.74s
Emit Time	3.34s (± 0.62%)	3.33s (± 0.64%)	-0.01s (- 0.21%)	3.29s	3.38s
Total Time	11.33s (± 0.42%)	11.31s (± 0.28%)	-0.02s (- 0.19%)	11.27s	11.38s
TFS - node (v14.15.1, x64)
Memory used	289,112k (± 0.01%)	289,126k (± 0.01%)	+13k (+ 0.00%)	289,064k	289,178k
Parse Time	1.34s (± 1.75%)	1.32s (± 1.42%)	-0.02s (- 1.19%)	1.29s	1.36s
Bind Time	0.71s (± 5.13%)	0.71s (± 4.27%)	-0.01s (- 0.84%)	0.67s	0.79s
Check Time	5.33s (± 0.56%)	5.34s (± 0.43%)	+0.00s (+ 0.07%)	5.30s	5.40s
Emit Time	3.57s (± 1.85%)	3.57s (± 1.67%)	+0.00s (+ 0.06%)	3.38s	3.67s
Total Time	10.96s (± 0.68%)	10.94s (± 0.77%)	-0.01s (- 0.13%)	10.69s	11.15s
material-ui - node (v14.15.1, x64)
Memory used	450,407k (± 0.06%)	437,927k (± 0.01%)	-12,480k (- 2.77%)	437,845k	437,993k
Parse Time	1.87s (± 0.86%)	1.86s (± 0.43%)	-0.01s (- 0.43%)	1.84s	1.87s
Bind Time	0.58s (± 0.38%)	0.57s (± 0.65%)	-0.01s (- 1.03%)	0.57s	0.58s
Check Time	13.27s (± 0.98%)	12.82s (± 0.53%)	🟩-0.45s (- 3.39%)	12.70s	13.00s
Emit Time	0.00s (± 0.00%)	0.00s (± 0.00%)	0.00s ( NaN%)	0.00s	0.00s
Total Time	15.71s (± 0.81%)	15.25s (± 0.44%)	-0.46s (- 2.94%)	15.14s	15.43s
xstate - node (v14.15.1, x64)
Memory used	546,054k (± 0.00%)	545,881k (± 0.01%)	-173k (- 0.03%)	545,772k	545,975k
Parse Time	2.61s (± 0.40%)	2.59s (± 0.44%)	-0.01s (- 0.58%)	2.57s	2.62s
Bind Time	0.98s (± 1.12%)	0.98s (± 1.03%)	+0.01s (+ 0.72%)	0.97s	1.01s
Check Time	1.56s (± 0.37%)	1.56s (± 0.51%)	-0.00s (- 0.32%)	1.54s	1.57s
Emit Time	0.07s (± 3.14%)	0.07s (± 3.14%)	0.00s ( 0.00%)	0.07s	0.08s
Total Time	5.23s (± 0.44%)	5.21s (± 0.38%)	-0.02s (- 0.40%)	5.17s	5.24s

System

Machine Name	ts-ci-ubuntu
Platform	linux 4.4.0-210-generic
Architecture	x64
Available Memory	16 GB
Available Memory	15 GB
CPUs	4 × Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz

Hosts

node (v14.15.1, x64)

Scenarios

Angular - node (v14.15.1, x64)
Compiler-Unions - node (v14.15.1, x64)
Monaco - node (v14.15.1, x64)
TFS - node (v14.15.1, x64)
material-ui - node (v14.15.1, x64)
xstate - node (v14.15.1, x64)

Benchmark	Name	Iterations
Current	50397	10
Baseline	main	10

Developer Information:

Download Benchmark

constraint === baseType

Is this just when someone writes

T extends T ? TrueType<T> : FalseType<T>

?

I presume so. The check was already there.

ghost

Would you be able to write a few tests that are known to trigger the new behavior? This gives a few good example cases to better understand the changes now and in the future too, and ensure we don't regress.

ghost

TypeScript Bot (@typescript-bot) user test this inline

Anders Hejlsberg added 2 commits August 21, 2022 18:24

Optimize substitution type infrastructure

c09b7dc

Accept new baselines

a4a9ede

TypeScript Bot (typescript-bot) assigned Anders Hejlsberg (ahejlsberg) Aug 22, 2022

TypeScript Bot (typescript-bot) added the Author: Team label Aug 22, 2022

TypeScript Bot (typescript-bot) assigned Wesley Wigham (weswigham) Aug 22, 2022

TypeScript Bot (typescript-bot) added the For Milestone Bug PRs that fix a bug with a specific milestone label Aug 22, 2022

Preserve instantiated substitution types for type variables

e73d268

Anders Hejlsberg (ahejlsberg) marked this pull request as ready for review August 22, 2022 18:55

Anders Hejlsberg (ahejlsberg) requested review from Andrew Casey (amcasey) and Wesley Wigham (weswigham) August 22, 2022 18:55

Daniel Rosenwasser (DanielRosenwasser) reviewed Aug 22, 2022

View reviewed changes

Daniel Rosenwasser (DanielRosenwasser) requested changes Aug 22, 2022

View reviewed changes

Daniel Rosenwasser (DanielRosenwasser) added Breaking Change Would introduce errors in existing code Domain: API Relates to the public API for TypeScript labels Aug 22, 2022

Nathan Shively-Sanders (sandersn) mentioned this pull request Aug 29, 2022

three: Fix ConstructorUnion's distributivity DefinitelyTyped/DefinitelyTyped#62011

Merged

Anders Hejlsberg (ahejlsberg) mentioned this pull request Dec 3, 2022

TypeScript 4.9 does not build Playwright anymore #51619

Closed

github-actions Bot mentioned this pull request Dec 18, 2022

Rename property in ts 4.9 satisfies section microsoft/TypeScript-Website-Localizations#194

Merged

Jake Bailey (jakebailey) mentioned this pull request Jan 20, 2023

Can no longer write deep predicates in conditional types #52271

Closed

Tobias S. (Tobias-Scholz) mentioned this pull request Feb 2, 2023

any | T from conditional type does not reduce to any #52568

Closed

Mateusz Burzyński (Andarist) mentioned this pull request Mar 2, 2023

Add an extra test case for deferred conditional types #53067

Merged

Jake Bailey (jakebailey) mentioned this pull request Mar 2, 2023

Ensure distributive constraints of restrictive instantiations of type parameters don't exist #47091

Closed

Richard Wise (Woodz) mentioned this pull request Jun 14, 2024

Inverted union type narrowing was broken in 4.9 #58861

Open

Microsoft (microsoft) locked as resolved and limited conversation to collaborators Oct 22, 2025

-                      function getSubstitutionType(baseType: Type, substitute: Type) {
-                          if (substitute.flags & TypeFlags.AnyOrUnknown || substitute === baseType) {
+                      function getSubstitutionType(baseType: Type, constraint: Type) {
+                          if (constraint.flags & TypeFlags.AnyOrUnknown || constraint === baseType ||

Optimize substitution types by ahejlsberg · Pull Request #50397 · microsoft/TypeScript · GitHub

Uh oh!

Optimize substitution types - #50397

Optimize substitution types#50397Anders Hejlsberg (ahejlsberg) merged 6 commits intomainmicrosoft/TypeScript:mainfrom fix50290microsoft/TypeScript:fix50290Copy head branch name to clipboard

Conversation

Anders Hejlsberg (ahejlsberg) commented Aug 22, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Aug 22, 2022

Uh oh!

ghost commented Aug 22, 2022 • edited by typescript-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Aug 22, 2022 • edited by typescript-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Aug 22, 2022 • edited by typescript-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Aug 22, 2022 • edited by typescript-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Aug 22, 2022

puppeteer

scripts/tsconfig.json

tsconfig.json

Uh oh!

ghost commented Aug 22, 2022

Uh oh!

ghost commented Aug 22, 2022

Uh oh!

ghost commented Aug 22, 2022

Uh oh!

ghost commented Aug 22, 2022 • edited by typescript-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Aug 22, 2022 • edited by typescript-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Aug 22, 2022 • edited by typescript-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Aug 22, 2022 • edited by typescript-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Aug 22, 2022

Uh oh!

ghost commented Aug 22, 2022

Uh oh!

ghost Aug 22, 2022 • edited by DanielRosenwasser Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ghost Aug 22, 2022

Choose a reason for hiding this comment

Uh oh!

ghost left a comment

Choose a reason for hiding this comment

Uh oh!

ghost commented Aug 22, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

Optimize substitution types#50397
Anders Hejlsberg (ahejlsberg) merged 6 commits into
mainfrom
fix50290

Anders Hejlsberg (ahejlsberg) commented Aug 22, 2022 •
edited
Loading

ghost commented Aug 22, 2022 •
edited by typescript-bot
Loading

ghost commented Aug 22, 2022 •
edited by typescript-bot
Loading

ghost commented Aug 22, 2022 •
edited by typescript-bot
Loading

ghost commented Aug 22, 2022 •
edited by typescript-bot
Loading

ghost commented Aug 22, 2022 •
edited by typescript-bot
Loading

ghost commented Aug 22, 2022 •
edited by typescript-bot
Loading

ghost commented Aug 22, 2022 •
edited by typescript-bot
Loading

ghost commented Aug 22, 2022 •
edited by typescript-bot
Loading

ghost Aug 22, 2022 •
edited by DanielRosenwasser
Loading