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

Error on excessive relation complexity #55851

Merged
merged 6 commits into from
Sep 26, 2023
Merged

Error on excessive relation complexity #55851

merged 6 commits into from
Sep 26, 2023

Conversation

ahejlsberg
Copy link
Member

@ahejlsberg ahejlsberg commented Sep 25, 2023 •
edited
Loading

With this PR we now error when computing a relation is excessively complex. Specifically, when computing a relation results in adding more relation cache entries than 1/8th of the current capacity of that relation, we issue an error. Relation caches use JavaScript maps, which in Node.js are limited to 2^24 (~16M) entries.

An example of a relation computation that is excessively complex is the following:

type Digits = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';
type T1 = `${Digits}${Digits}${Digits}${Digits}` | undefined;
type T2 = { a: string } | { b: number };

function f1(x: T1 | null, y: T1 & T2) {
    x = y;  // Excessive complexity error
}

Above, T1 is a union with 10,001 members, and T2 normalizes to a union with 20,002 members.

This PR further implements an optimization outlined here. For example, the following example doesn't cause an excessive complexity error because we now have a fast path when relating a union resulting from normalizing an intersection of large unions to one of those same unions.

function f2(x: T1, y: T1 & T2) {
    x = y;  // Ok
}

Fixes #55630.

@typescript-bot typescript-bot added Author: Team For Milestone Bug PRs that fix a bug with a specific milestone labels Sep 25, 2023
@ahejlsberg
Merge branch 'main' into fix55630
89f5d10 
# Conflicts:
#	src/compiler/diagnosticMessages.json
@ahejlsberg
Copy link
Member Author

@typescript-bot test top100
@typescript-bot user test this
@typescript-bot run dt
@typescript-bot perf test this faster

@typescript-bot
Copy link
Collaborator

typescript-bot commented Sep 25, 2023 •
edited
Loading

Heya @ahejlsberg, I've started to run the tsc-only perf test suite on this PR at 89f5d10. You can monitor the build here.

Update: The results are in!

@typescript-bot
Copy link
Collaborator

typescript-bot commented Sep 25, 2023 •
edited
Loading

Heya @ahejlsberg, I've started to run the diff-based top-repos suite on this PR at 89f5d10. You can monitor the build here.

Update: The results are in!

@typescript-bot
Copy link
Collaborator

typescript-bot commented Sep 25, 2023 •
edited
Loading

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

Update: The results are in!

@typescript-bot
Copy link
Collaborator

typescript-bot commented Sep 25, 2023 •
edited
Loading

Heya @ahejlsberg, I've started to run the parallelized Definitely Typed test suite on this PR at 89f5d10. You can monitor the build here.

Update: The results are in!

@typescript-bot
Copy link
Collaborator

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

Here they are:

Compiler

Comparison Report - baseline..pr
Metric baseline pr Delta Best Worst p-value
Angular - node (v18.15.0, x64)
Memory used 294,958k (± 0.01%) 294,960k (± 0.01%) ~ 294,938k 294,997k p=1.000 n=6
Parse Time 2.62s (± 0.31%) 2.63s (± 0.47%) ~ 2.61s 2.64s p=0.730 n=6
Bind Time 0.84s (± 1.17%) 0.84s (± 0.97%) ~ 0.83s 0.85s p=0.394 n=6
Check Time 8.05s (± 0.46%) 8.06s (± 0.34%) ~ 8.03s 8.10s p=0.629 n=6
Emit Time 7.05s (± 0.30%) 7.03s (± 0.16%) ~ 7.01s 7.04s p=0.061 n=6
Total Time 18.56s (± 0.22%) 18.55s (± 0.16%) ~ 18.50s 18.58s p=1.000 n=6
Compiler-Unions - node (v18.15.0, x64)
Memory used 192,115k (± 1.24%) 193,628k (± 1.64%) ~ 190,726k 196,592k p=0.423 n=6
Parse Time 1.34s (± 0.77%) 1.34s (± 1.05%) ~ 1.32s 1.36s p=0.738 n=6
Bind Time 0.73s (± 0.00%) 0.73s (± 0.00%) ~ 0.73s 0.73s p=1.000 n=6
Check Time 9.11s (± 0.54%) 9.17s (± 0.46%) ~ 9.12s 9.24s p=0.078 n=6
Emit Time 2.64s (± 0.44%) 2.63s (± 0.83%) ~ 2.60s 2.66s p=0.192 n=6
Total Time 13.81s (± 0.45%) 13.87s (± 0.30%) ~ 13.79s 13.91s p=0.092 n=6
Monaco - node (v18.15.0, x64)
Memory used 347,217k (± 0.00%) 347,209k (± 0.01%) ~ 347,183k 347,239k p=0.575 n=6
Parse Time 2.46s (± 0.43%) 2.44s (± 0.34%) ~ 2.44s 2.46s p=0.109 n=6
Bind Time 0.94s (± 0.43%) 0.94s (± 0.00%) ~ 0.94s 0.94s p=0.405 n=6
Check Time 6.88s (± 0.41%) 6.88s (± 0.58%) ~ 6.84s 6.94s p=1.000 n=6
Emit Time 4.02s (± 0.41%) 4.02s (± 0.34%) ~ 4.01s 4.05s p=0.505 n=6
Total Time 14.28s (± 0.28%) 14.29s (± 0.19%) ~ 14.26s 14.33s p=0.808 n=6
TFS - node (v18.15.0, x64)
Memory used 302,484k (± 0.00%) 302,554k (± 0.01%) +71k (+ 0.02%) 302,498k 302,598k p=0.008 n=6
Parse Time 2.01s (± 0.41%) 2.00s (± 0.63%) -0.01s (- 0.74%) 1.98s 2.01s p=0.038 n=6
Bind Time 1.00s (± 1.17%) 1.00s (± 0.83%) ~ 0.99s 1.01s p=0.555 n=6
Check Time 6.25s (± 0.28%) 6.25s (± 0.48%) ~ 6.22s 6.30s p=0.870 n=6
Emit Time 3.54s (± 1.34%) 3.53s (± 0.83%) ~ 3.50s 3.57s p=1.000 n=6
Total Time 12.81s (± 0.38%) 12.80s (± 0.32%) ~ 12.74s 12.86s p=0.630 n=6
material-ui - node (v18.15.0, x64)
Memory used 470,448k (± 0.00%) 470,426k (± 0.01%) ~ 470,382k 470,463k p=0.128 n=6
Parse Time 2.57s (± 0.58%) 2.56s (± 0.64%) ~ 2.55s 2.59s p=0.314 n=6
Bind Time 1.00s (± 0.75%) 0.99s (± 1.04%) ~ 0.98s 1.01s p=0.155 n=6
Check Time 16.56s (± 0.59%) 16.57s (± 0.33%) ~ 16.51s 16.67s p=0.872 n=6
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) ~ 0.00s 0.00s p=1.000 n=6
Total Time 20.13s (± 0.56%) 20.13s (± 0.24%) ~ 20.08s 20.21s p=0.748 n=6
xstate - node (v18.15.0, x64)
Memory used 512,548k (± 0.01%) 512,514k (± 0.02%) ~ 512,399k 512,749k p=0.298 n=6
Parse Time 3.27s (± 0.17%) 3.27s (± 0.23%) ~ 3.26s 3.28s p=0.476 n=6
Bind Time 1.55s (± 0.33%) 1.55s (± 0.53%) ~ 1.54s 1.56s p=0.929 n=6
Check Time 2.83s (± 0.69%) 2.85s (± 1.15%) ~ 2.80s 2.90s p=0.226 n=6
Emit Time 0.08s (± 4.99%) 0.08s (± 0.00%) ~ 0.08s 0.08s p=0.405 n=6
Total Time 7.71s (± 0.25%) 7.74s (± 0.43%) ~ 7.69s 7.79s p=0.196 n=6
System info unknown
Hosts
  • node (v18.15.0, x64)
Scenarios
  • Angular - node (v18.15.0, x64)
  • Compiler-Unions - node (v18.15.0, x64)
  • Monaco - node (v18.15.0, x64)
  • TFS - node (v18.15.0, x64)
  • material-ui - node (v18.15.0, x64)
  • xstate - node (v18.15.0, x64)
Benchmark Name Iterations
Current pr 6
Baseline baseline 6

Developer Information:

Download Benchmarks

@typescript-bot
Copy link
Collaborator

@ahejlsberg Here are the results of running the user test suite comparing main and refs/pull/55851/merge:

There were infrastructure failures potentially unrelated to your change:

  • 1 instance of "Unknown failure"
  • 2 instances of "Package install failed"

Otherwise...

Everything looks good!

@typescript-bot
Copy link
Collaborator

@ahejlsberg Here are the results of running the top-repos suite comparing main and refs/pull/55851/merge:

Everything looks good!

@typescript-bot
Copy link
Collaborator

Hey @ahejlsberg, the results of running the DT tests are ready.
Everything looks the same!
You can check the log here.

@gabritto
Copy link
Member

On PR #50329, @weswigham had proposed a more general form of the optimization found on this PR. What's the reasoning behind picking this simpler form of the optimization instead?

@ahejlsberg
Copy link
Member Author

What's the reasoning behind picking this simpler form of the optimization instead?

I hadn't seen #50329, but certainly the optimization in this PR removes far more work when the fast path is available. There's no reason the two couldn't co-exist.

@ahejlsberg
Copy link
Member Author

@typescript-bot test top100
@typescript-bot user test this
@typescript-bot run dt
@typescript-bot perf test this faster

@typescript-bot
Copy link
Collaborator

typescript-bot commented Sep 26, 2023 •
edited
Loading

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

@typescript-bot
Copy link
Collaborator

typescript-bot commented Sep 26, 2023 •
edited
Loading

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

@typescript-bot
Copy link
Collaborator

typescript-bot commented Sep 26, 2023 •
edited
Loading

Heya @ahejlsberg, I've started to run the tsc-only perf test suite on this PR at be68f32. You can monitor the build here.

Update: The results are in!

@typescript-bot
Copy link
Collaborator

typescript-bot commented Sep 26, 2023 •
edited
Loading

Heya @ahejlsberg, I've started to run the diff-based top-repos suite on this PR at be68f32. You can monitor the build here.

Update: The results are in!

@typescript-bot
Copy link
Collaborator

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

Here they are:

Compiler

Comparison Report - baseline..pr
Metric baseline pr Delta Best Worst p-value
Angular - node (v18.15.0, x64)
Memory used 294,994k (± 0.01%) 294,988k (± 0.01%) ~ 294,945k 295,050k p=0.873 n=6
Parse Time 2.64s (± 0.73%) 2.63s (± 0.65%) ~ 2.60s 2.65s p=0.216 n=6
Bind Time 0.84s (± 0.97%) 0.84s (± 1.17%) ~ 0.83s 0.85s p=0.394 n=6
Check Time 8.06s (± 0.21%) 8.06s (± 0.35%) ~ 8.02s 8.09s p=0.935 n=6
Emit Time 7.04s (± 0.15%) 7.04s (± 0.25%) ~ 7.02s 7.07s p=1.000 n=6
Total Time 18.58s (± 0.13%) 18.57s (± 0.24%) ~ 18.52s 18.65s p=0.517 n=6
Compiler-Unions - node (v18.15.0, x64)
Memory used 190,707k (± 0.01%) 192,093k (± 1.25%) ~ 190,656k 196,506k p=1.000 n=6
Parse Time 1.35s (± 0.56%) 1.35s (± 0.47%) ~ 1.34s 1.36s p=0.718 n=6
Bind Time 0.73s (± 0.56%) 0.73s (± 0.00%) ~ 0.73s 0.73s p=0.405 n=6
Check Time 9.15s (± 0.63%) 9.16s (± 0.31%) ~ 9.12s 9.20s p=0.468 n=6
Emit Time 2.63s (± 0.50%) 2.64s (± 0.59%) ~ 2.62s 2.66s p=0.452 n=6
Total Time 13.86s (± 0.32%) 13.88s (± 0.22%) ~ 13.84s 13.93s p=0.370 n=6
Monaco - node (v18.15.0, x64)
Memory used 347,227k (± 0.01%) 347,240k (± 0.00%) ~ 347,213k 347,257k p=0.378 n=6
Parse Time 2.46s (± 0.56%) 2.45s (± 0.26%) ~ 2.44s 2.46s p=0.362 n=6
Bind Time 0.94s (± 0.43%) 0.94s (± 0.88%) ~ 0.94s 0.96s p=0.527 n=6
Check Time 6.87s (± 0.28%) 6.88s (± 0.20%) ~ 6.86s 6.90s p=0.167 n=6
Emit Time 4.03s (± 0.43%) 4.03s (± 0.29%) ~ 4.02s 4.05s p=1.000 n=6
Total Time 14.29s (± 0.27%) 14.31s (± 0.17%) ~ 14.27s 14.34s p=0.332 n=6
TFS - node (v18.15.0, x64)
Memory used 302,503k (± 0.01%) 302,550k (± 0.01%) ~ 302,491k 302,613k p=0.065 n=6
Parse Time 2.01s (± 0.86%) 1.99s (± 0.49%) ~ 1.98s 2.01s p=0.072 n=6
Bind Time 1.01s (± 0.97%) 1.01s (± 1.20%) ~ 0.99s 1.02s p=0.865 n=6
Check Time 6.24s (± 0.19%) 6.26s (± 0.55%) ~ 6.20s 6.30s p=0.256 n=6
Emit Time 3.52s (± 0.53%) 3.52s (± 0.45%) ~ 3.50s 3.55s p=0.490 n=6
Total Time 12.77s (± 0.23%) 12.78s (± 0.23%) ~ 12.73s 12.81s p=0.413 n=6
material-ui - node (v18.15.0, x64)
Memory used 470,468k (± 0.00%) 470,493k (± 0.01%) ~ 470,456k 470,519k p=0.173 n=6
Parse Time 2.56s (± 0.48%) 2.57s (± 0.59%) ~ 2.55s 2.59s p=1.000 n=6
Bind Time 0.99s (± 1.18%) 1.00s (± 0.84%) ~ 0.98s 1.00s p=0.555 n=6
Check Time 16.62s (± 0.43%) 16.60s (± 0.33%) ~ 16.51s 16.66s p=0.627 n=6
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) ~ 0.00s 0.00s p=1.000 n=6
Total Time 20.18s (± 0.35%) 20.17s (± 0.32%) ~ 20.07s 20.24s p=0.747 n=6
xstate - node (v18.15.0, x64)
Memory used 512,559k (± 0.02%) 512,535k (± 0.01%) ~ 512,435k 512,635k p=0.748 n=6
Parse Time 3.27s (± 0.45%) 3.27s (± 0.32%) ~ 3.25s 3.28s p=1.000 n=6
Bind Time 1.55s (± 0.33%) 1.55s (± 0.53%) ~ 1.54s 1.56s p=0.140 n=6
Check Time 2.83s (± 0.62%) 2.84s (± 1.16%) ~ 2.80s 2.89s p=0.466 n=6
Emit Time 0.08s (± 5.21%) 0.08s (± 0.00%) ~ 0.08s 0.08s p=0.405 n=6
Total Time 7.71s (± 0.37%) 7.73s (± 0.47%) ~ 7.68s 7.78s p=0.467 n=6
System info unknown
Hosts
  • node (v18.15.0, x64)
Scenarios
  • Angular - node (v18.15.0, x64)
  • Compiler-Unions - node (v18.15.0, x64)
  • Monaco - node (v18.15.0, x64)
  • TFS - node (v18.15.0, x64)
  • material-ui - node (v18.15.0, x64)
  • xstate - node (v18.15.0, x64)
Benchmark Name Iterations
Current pr 6
Baseline baseline 6

Developer Information:

Download Benchmarks

@DanielRosenwasser DanielRosenwasser merged commit c052bc7 into main Sep 26, 2023
@DanielRosenwasser DanielRosenwasser deleted the fix55630 branch September 26, 2023 22:58
@typescript-bot
Copy link
Collaborator

@ahejlsberg Here are the results of running the top-repos suite comparing main and refs/pull/55851/merge:

Everything looks good!

@ahejlsberg ahejlsberg mentioned this pull request Sep 28, 2023
Open
@Andarist Andarist mentioned this pull request Nov 30, 2023
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@sandersn sandersn sandersn approved these changes

@gabritto gabritto gabritto approved these changes

@RyanCavanaugh RyanCavanaugh Awaiting requested review from RyanCavanaugh

Assignees

@ahejlsberg ahejlsberg

Labels
Author: Team For Milestone Bug PRs that fix a bug with a specific milestone
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Compiler crash with RangeError: Map maximum size exceeded
5 participants
@ahejlsberg @typescript-bot @gabritto @sandersn @DanielRosenwasser