Skip to content

Use Set<T> for faster lookup of "maybe related" type pairs#43623

Closed
ahejlsberg wants to merge 1 commit intomainfrom
fix43437
Closed

Use Set<T> for faster lookup of "maybe related" type pairs#43623
ahejlsberg wants to merge 1 commit intomainfrom
fix43437

Conversation

@ahejlsberg
Copy link
Member

@ahejlsberg ahejlsberg commented Apr 9, 2021

Fixes #43437.

@typescript-bot typescript-bot added Author: Team For Uncommitted Bug PR for untriaged, rejected, closed or missing bug labels Apr 9, 2021
@ahejlsberg
Copy link
Member Author

ahejlsberg commented Apr 9, 2021

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

@typescript-bot
Copy link
Collaborator

typescript-bot commented Apr 9, 2021 •
edited
Loading

Heya @ahejlsberg, I've started to run the extended test suite on this PR at 4e7d25d. You can monitor the build here.

@typescript-bot
Copy link
Collaborator

typescript-bot commented Apr 9, 2021 •
edited
Loading

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

Update: The results are in!

@typescript-bot
Copy link
Collaborator

typescript-bot commented Apr 9, 2021 •
edited
Loading

Heya @ahejlsberg, I've started to run the parallelized community code test suite on this PR at 4e7d25d. You can monitor the build here.

@typescript-bot
Copy link
Collaborator

typescript-bot commented Apr 9, 2021 •
edited
Loading

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

@typescript-bot typescript-bot mentioned this pull request Apr 9, 2021
Open
@typescript-bot
Copy link
Collaborator

typescript-bot commented Apr 9, 2021

The user suite test run you requested has finished and failed. I've opened a PR with the baseline diff from master.

@typescript-bot
Copy link
Collaborator

typescript-bot commented Apr 9, 2021

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

Here they are:

Comparison Report - master..43623

Metric master 43623 Delta Best Worst
Angular - node (v10.16.3, x64)
Memory used 345,096k (± 0.02%) 344,991k (± 0.01%) -105k (- 0.03%) 344,903k 345,074k
Parse Time 1.93s (± 0.32%) 1.94s (± 0.60%) +0.00s (+ 0.21%) 1.92s 1.96s
Bind Time 0.83s (± 0.59%) 0.83s (± 0.60%) +0.00s (+ 0.12%) 0.83s 0.85s
Check Time 5.19s (± 0.34%) 5.21s (± 0.33%) +0.02s (+ 0.42%) 5.17s 5.25s
Emit Time 5.89s (± 0.24%) 5.93s (± 0.50%) +0.04s (+ 0.65%) 5.88s 6.02s
Total Time 13.84s (± 0.22%) 13.91s (± 0.36%) +0.07s (+ 0.48%) 13.84s 14.07s
Compiler-Unions - node (v10.16.3, x64)
Memory used 203,450k (± 0.02%) 203,326k (± 0.10%) -124k (- 0.06%) 202,488k 203,501k
Parse Time 0.79s (± 0.46%) 0.78s (± 0.83%) -0.00s (- 0.51%) 0.77s 0.80s
Bind Time 0.52s (± 1.35%) 0.52s (± 1.24%) +0.00s (+ 0.58%) 0.50s 0.53s
Check Time 7.48s (± 0.54%) 7.52s (± 0.47%) +0.04s (+ 0.48%) 7.42s 7.58s
Emit Time 2.58s (± 1.60%) 2.58s (± 0.62%) -0.00s (- 0.04%) 2.55s 2.63s
Total Time 11.36s (± 0.72%) 11.40s (± 0.27%) +0.03s (+ 0.29%) 11.34s 11.48s
Monaco - node (v10.16.3, x64)
Memory used 342,748k (± 0.01%) 342,770k (± 0.04%) +23k (+ 0.01%) 342,612k 343,182k
Parse Time 1.55s (± 0.65%) 1.55s (± 0.44%) -0.01s (- 0.51%) 1.54s 1.57s
Bind Time 0.74s (± 0.67%) 0.74s (± 0.70%) +0.00s (+ 0.41%) 0.73s 0.75s
Check Time 5.32s (± 0.54%) 5.32s (± 0.42%) -0.00s (- 0.09%) 5.28s 5.36s
Emit Time 3.11s (± 0.57%) 3.13s (± 0.61%) +0.01s (+ 0.39%) 3.08s 3.18s
Total Time 10.73s (± 0.45%) 10.72s (± 0.38%) -0.00s (- 0.02%) 10.64s 10.82s
TFS - node (v10.16.3, x64)
Memory used 304,372k (± 0.02%) 304,317k (± 0.01%) -55k (- 0.02%) 304,190k 304,401k
Parse Time 1.20s (± 0.41%) 1.20s (± 0.63%) +0.00s (+ 0.08%) 1.19s 1.22s
Bind Time 0.70s (± 0.84%) 0.71s (± 0.97%) +0.00s (+ 0.14%) 0.69s 0.72s
Check Time 4.76s (± 0.47%) 4.81s (± 0.63%) +0.05s (+ 0.99%) 4.75s 4.88s
Emit Time 3.24s (± 1.13%) 3.23s (± 0.90%) -0.01s (- 0.31%) 3.18s 3.30s
Total Time 9.91s (± 0.43%) 9.94s (± 0.39%) +0.04s (+ 0.36%) 9.87s 10.04s
material-ui - node (v10.16.3, x64)
Memory used 466,017k (± 0.01%) 466,094k (± 0.01%) +77k (+ 0.02%) 465,991k 466,292k
Parse Time 2.00s (± 0.45%) 2.01s (± 0.54%) +0.01s (+ 0.60%) 1.98s 2.04s
Bind Time 0.66s (± 1.28%) 0.65s (± 0.75%) -0.01s (- 0.76%) 0.64s 0.66s
Check Time 14.28s (± 0.29%) 14.34s (± 0.29%) +0.06s (+ 0.42%) 14.26s 14.45s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 16.93s (± 0.26%) 17.00s (± 0.24%) +0.07s (+ 0.41%) 16.92s 17.12s
Angular - node (v12.1.0, x64)
Memory used 322,772k (± 0.01%) 322,854k (± 0.02%) +82k (+ 0.03%) 322,727k 322,999k
Parse Time 1.93s (± 0.46%) 1.92s (± 0.81%) -0.01s (- 0.42%) 1.89s 1.95s
Bind Time 0.82s (± 0.73%) 0.82s (± 0.60%) 0.00s ( 0.00%) 0.81s 0.83s
Check Time 5.08s (± 0.20%) 5.11s (± 0.51%) +0.03s (+ 0.55%) 5.05s 5.18s
Emit Time 5.98s (± 0.66%) 5.99s (± 0.57%) +0.01s (+ 0.17%) 5.93s 6.08s
Total Time 13.80s (± 0.27%) 13.84s (± 0.33%) +0.04s (+ 0.26%) 13.73s 13.94s
Compiler-Unions - node (v12.1.0, x64)
Memory used 190,194k (± 0.15%) 190,474k (± 0.12%) +280k (+ 0.15%) 190,157k 190,904k
Parse Time 0.77s (± 0.67%) 0.77s (± 1.18%) -0.00s (- 0.26%) 0.75s 0.79s
Bind Time 0.53s (± 1.14%) 0.52s (± 0.57%) -0.00s (- 0.57%) 0.52s 0.53s
Check Time 6.99s (± 0.51%) 7.05s (± 0.55%) +0.07s (+ 0.97%) 6.95s 7.12s
Emit Time 2.53s (± 1.08%) 2.53s (± 0.96%) -0.00s (- 0.00%) 2.50s 2.59s
Total Time 10.82s (± 0.41%) 10.88s (± 0.25%) +0.06s (+ 0.58%) 10.82s 10.94s
Monaco - node (v12.1.0, x64)
Memory used 325,134k (± 0.01%) 325,167k (± 0.02%) +33k (+ 0.01%) 325,014k 325,279k
Parse Time 1.54s (± 0.61%) 1.53s (± 0.49%) -0.00s (- 0.20%) 1.52s 1.56s
Bind Time 0.72s (± 0.31%) 0.72s (± 0.72%) +0.00s (+ 0.28%) 0.71s 0.73s
Check Time 5.13s (± 0.21%) 5.16s (± 0.50%) +0.03s (+ 0.58%) 5.08s 5.22s
Emit Time 3.08s (± 0.27%) 3.09s (± 0.68%) +0.01s (+ 0.45%) 3.05s 3.16s
Total Time 10.46s (± 0.20%) 10.51s (± 0.27%) +0.04s (+ 0.42%) 10.44s 10.58s
TFS - node (v12.1.0, x64)
Memory used 288,812k (± 0.01%) 288,758k (± 0.02%) -53k (- 0.02%) 288,622k 288,889k
Parse Time 1.21s (± 0.61%) 1.21s (± 0.78%) -0.00s (- 0.25%) 1.19s 1.23s
Bind Time 0.69s (± 1.01%) 0.69s (± 0.94%) -0.00s (- 0.43%) 0.67s 0.70s
Check Time 4.69s (± 0.43%) 4.69s (± 0.36%) +0.01s (+ 0.11%) 4.64s 4.72s
Emit Time 3.16s (± 0.65%) 3.17s (± 0.56%) +0.01s (+ 0.25%) 3.13s 3.20s
Total Time 9.75s (± 0.24%) 9.75s (± 0.34%) +0.01s (+ 0.05%) 9.69s 9.81s
material-ui - node (v12.1.0, x64)
Memory used 444,189k (± 0.01%) 444,076k (± 0.06%) -114k (- 0.03%) 442,987k 444,378k
Parse Time 2.01s (± 0.38%) 2.02s (± 0.30%) +0.01s (+ 0.55%) 2.01s 2.04s
Bind Time 0.63s (± 0.78%) 0.64s (± 0.81%) +0.01s (+ 0.94%) 0.63s 0.65s
Check Time 12.91s (± 0.61%) 13.01s (± 0.58%) +0.10s (+ 0.80%) 12.80s 13.20s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 15.56s (± 0.51%) 15.68s (± 0.50%) +0.12s (+ 0.78%) 15.45s 15.87s
Angular - node (v14.15.1, x64)
Memory used 321,431k (± 0.01%) 321,439k (± 0.01%) +8k (+ 0.00%) 321,391k 321,501k
Parse Time 1.92s (± 0.55%) 1.93s (± 0.31%) +0.01s (+ 0.31%) 1.91s 1.94s
Bind Time 0.86s (± 0.46%) 0.86s (± 0.64%) +0.00s (+ 0.12%) 0.85s 0.88s
Check Time 5.13s (± 0.45%) 5.14s (± 0.42%) +0.01s (+ 0.21%) 5.08s 5.19s
Emit Time 6.32s (± 0.58%) 6.31s (± 0.35%) -0.01s (- 0.11%) 6.27s 6.37s
Total Time 14.23s (± 0.30%) 14.24s (± 0.25%) +0.01s (+ 0.07%) 14.19s 14.37s
Compiler-Unions - node (v14.15.1, x64)
Memory used 189,497k (± 0.01%) 189,431k (± 0.08%) -66k (- 0.03%) 188,792k 189,557k
Parse Time 0.81s (± 1.11%) 0.80s (± 0.77%) -0.00s (- 0.50%) 0.79s 0.82s
Bind Time 0.55s (± 0.54%) 0.56s (± 0.89%) +0.00s (+ 0.72%) 0.55s 0.57s
Check Time 7.09s (± 0.69%) 7.13s (± 0.34%) +0.03s (+ 0.48%) 7.08s 7.20s
Emit Time 2.54s (± 0.70%) 2.54s (± 0.71%) +0.00s (+ 0.12%) 2.52s 2.60s
Total Time 11.00s (± 0.45%) 11.03s (± 0.23%) +0.03s (+ 0.28%) 10.96s 11.08s
Monaco - node (v14.15.1, x64)
Memory used 324,133k (± 0.01%) 324,115k (± 0.01%) -18k (- 0.01%) 324,068k 324,166k
Parse Time 1.56s (± 0.39%) 1.56s (± 0.56%) +0.01s (+ 0.51%) 1.54s 1.58s
Bind Time 0.74s (± 0.40%) 0.75s (± 0.66%) +0.00s (+ 0.54%) 0.73s 0.75s
Check Time 5.11s (± 0.48%) 5.12s (± 0.57%) +0.01s (+ 0.25%) 5.07s 5.22s
Emit Time 3.18s (± 0.78%) 3.16s (± 0.35%) -0.01s (- 0.44%) 3.14s 3.19s
Total Time 10.59s (± 0.35%) 10.59s (± 0.37%) +0.01s (+ 0.06%) 10.52s 10.70s
TFS - node (v14.15.1, x64)
Memory used 287,746k (± 0.01%) 287,747k (± 0.01%) +1k (+ 0.00%) 287,678k 287,823k
Parse Time 1.26s (± 1.05%) 1.25s (± 0.80%) -0.01s (- 0.56%) 1.24s 1.28s
Bind Time 0.72s (± 0.80%) 0.72s (± 0.81%) -0.00s (- 0.42%) 0.71s 0.73s
Check Time 4.71s (± 0.43%) 4.72s (± 0.50%) +0.01s (+ 0.13%) 4.66s 4.78s
Emit Time 3.24s (± 0.55%) 3.24s (± 0.47%) +0.00s (+ 0.03%) 3.21s 3.27s
Total Time 9.93s (± 0.21%) 9.93s (± 0.35%) -0.01s (- 0.06%) 9.83s 10.03s
material-ui - node (v14.15.1, x64)
Memory used 442,316k (± 0.06%) 442,415k (± 0.01%) +99k (+ 0.02%) 442,360k 442,449k
Parse Time 2.09s (± 0.49%) 2.10s (± 0.32%) +0.01s (+ 0.38%) 2.08s 2.11s
Bind Time 0.69s (± 0.75%) 0.69s (± 0.80%) +0.00s (+ 0.44%) 0.68s 0.71s
Check Time 13.02s (± 0.57%) 13.08s (± 0.43%) +0.06s (+ 0.45%) 12.96s 13.23s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 15.80s (± 0.49%) 15.87s (± 0.36%) +0.07s (+ 0.43%) 15.75s 16.02s
System
Machine Namets-ci-ubuntu
Platformlinux 4.4.0-206-generic
Architecturex64
Available Memory16 GB
Available Memory9 GB
CPUs4 × Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
Hosts
  • node (v10.16.3, x64)
  • node (v12.1.0, x64)
  • node (v14.15.1, x64)
Scenarios
  • Angular - node (v10.16.3, x64)
  • Angular - node (v12.1.0, x64)
  • Angular - node (v14.15.1, x64)
  • Compiler-Unions - node (v10.16.3, x64)
  • Compiler-Unions - node (v12.1.0, x64)
  • Compiler-Unions - node (v14.15.1, x64)
  • Monaco - node (v10.16.3, x64)
  • Monaco - node (v12.1.0, x64)
  • Monaco - node (v14.15.1, x64)
  • TFS - node (v10.16.3, x64)
  • TFS - node (v12.1.0, x64)
  • TFS - node (v14.15.1, x64)
  • material-ui - node (v10.16.3, x64)
  • material-ui - node (v12.1.0, x64)
  • material-ui - node (v14.15.1, x64)
Benchmark Name Iterations
Current 43623 10
Baseline master 10

Developer Information:

Download Benchmark

sheetalkamat
sheetalkamat reviewed Apr 9, 2021
View reviewed changes
src/compiler/checker.ts
let relatedInfo: [DiagnosticRelatedInformation, ...DiagnosticRelatedInformation[]] | undefined;
let maybeKeys: string[];
let maybeKeyList: string[];
let maybeKeySet: Set<string>;
Copy link
Member

@sheetalkamat sheetalkamat Apr 9, 2021

Choose a reason for hiding this comment

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

Suggestion. You can just just Map<string, number> where number is index mayBeList index and then you dont need array.

Copy link
Member

@amcasey amcasey Apr 12, 2021 •
edited
Loading

Choose a reason for hiding this comment

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

I don't think that's true because of the way the set has to be "popped" down to maybeStart.

Edit: I guess you could traverse the whole thing, dropping keys with values above maybeStart?

Copy link
Member Author

@ahejlsberg ahejlsberg Apr 12, 2021

Choose a reason for hiding this comment

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

Yeah, we'd have to traverse the whole thing every time--which we really don't want to do.

amcasey
amcasey reviewed Apr 12, 2021
View reviewed changes
@andrewbranch
Copy link
Member

andrewbranch commented Apr 12, 2021

@typescript-bot pack this

@typescript-bot
Copy link
Collaborator

typescript-bot commented Apr 12, 2021 •
edited
Loading

Heya @andrewbranch, I've started to run the tarball bundle task on this PR at 4e7d25d. You can monitor the build here.

@typescript-bot
Copy link
Collaborator

typescript-bot commented Apr 12, 2021 •
edited
Loading

Hey @andrewbranch, 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/100762/artifacts?artifactName=tgz&fileId=E993E55929F3E4F83879920F4E7108AB2F5C50C7A87F447DF37A3B8FBDCC3EA702&fileName=/typescript-4.3.0-insiders.20210412.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/pr-build@4.3.0-pr-43623-9".;

amcasey
amcasey approved these changes Apr 12, 2021
View reviewed changes
Copy link
Member

@amcasey amcasey left a comment •
edited
Loading

Choose a reason for hiding this comment

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

Cuts the check-time of Vanilla by 60-70% with Exclude<CSSProperties[K], undefined> (proposed correctness fix) or by 5-10% with Extract<CSSProperties[K], string> (behavior when the bug was originally filed).

In round numbers: 70s -> 22s with Exclude; 25s -> 22s with Extract (i.e. the proposed Emotion correctness fix no longer causes a huge perf regression in Vanilla).

@amcasey amcasey mentioned this pull request Apr 12, 2021
Merged
@ahejlsberg
Copy link
Member Author

ahejlsberg commented Apr 13, 2021

In many way I like the fix in #43624 better than adding the Set<T> logic to the "maybe related" tracking. But #43624 only fixes the issue for non-augmenting interface types. If the ArrayCSSInterpolation type in the repro were to add any members, the problem would be right back. So maybe with need both PRs.

@amcasey amcasey mentioned this pull request Apr 15, 2021
Open
@sandersn
Copy link
Member

sandersn commented Apr 29, 2021

@ahejlsberg should we take this for 4.3? Or do you want to wait to see whether #43624 performs well enough in the real world?

@ahejlsberg
Copy link
Member Author

ahejlsberg commented Apr 29, 2021

We know that #43624 fixes the known issues in the wild, so I'm tempted to just go with that and keep this one on file.

@DanielRosenwasser
Copy link
Member

DanielRosenwasser commented Apr 29, 2021

It seems like this fix is more general though - what sort of case would this handle that #43624 doesn't right now?

weswigham
weswigham approved these changes Mar 4, 2022
View reviewed changes
Copy link
Member

@weswigham weswigham left a comment

Choose a reason for hiding this comment

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

Reminder ping that this is probably still a performance gain that we could merge at some point.

@sandersn
Copy link
Member

sandersn commented Jun 1, 2022

To help with PR housekeeping, I'm going to close this PR since it's pretty old. We can re-open it if the performance gain is desirable enough.

@sandersn sandersn closed this Jun 1, 2022
@DanielRosenwasser DanielRosenwasser deleted the fix43437 branch June 1, 2022 23:10
@microsoft microsoft locked as resolved and limited conversation to collaborators Oct 21, 2025
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

@sheetalkamat sheetalkamat sheetalkamat approved these changes

@weswigham weswigham weswigham approved these changes

@DanielRosenwasser DanielRosenwasser Awaiting requested review from DanielRosenwasser

+2 more reviewers

@amcasey amcasey amcasey approved these changes

@raghavthind2005 raghavthind2005 raghavthind2005 approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

@ahejlsberg ahejlsberg

Labels

Author: Team For Uncommitted Bug PR for untriaged, rejected, closed or missing bug

Projects

PR Backlog
Archived in project

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Performance depends on declaration order

9 participants

@ahejlsberg @typescript-bot @andrewbranch @sandersn @DanielRosenwasser @weswigham @sheetalkamat @amcasey @raghavthind2005