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.

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

Properly cache types for shared control flow nodes #41665

Merged
merged 2 commits into from Nov 26, 2020
Merged

Properly cache types for shared control flow nodes #41665

merged 2 commits into from Nov 26, 2020

Conversation

ahejlsberg
Copy link
Member

Fixes #41124.

Simplified version of #41408. Thanks to @JoostK for diagnosing and proposing a fix.

@typescript-bot typescript-bot added the For Milestone Bug PRs that fix a bug with a specific milestone label Nov 24, 2020
@ahejlsberg
Copy link
Member Author

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

@typescript-bot
Copy link
Collaborator

typescript-bot commented Nov 24, 2020 •
edited

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

Update: The results are in!

@typescript-bot
Copy link
Collaborator

typescript-bot commented Nov 24, 2020 •
edited

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

@typescript-bot
Copy link
Collaborator

typescript-bot commented Nov 24, 2020 •
edited

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

@typescript-bot
Copy link
Collaborator

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

Here they are:

Comparison Report - master..41665

Metric master 41665 Delta Best Worst
Angular - node (v10.16.3, x64)
Memory used 344,473k (± 0.02%) 344,439k (± 0.03%) -34k (- 0.01%) 344,244k 344,684k
Parse Time 1.99s (± 0.70%) 1.99s (± 0.54%) -0.00s (- 0.15%) 1.96s 2.01s
Bind Time 0.84s (± 1.34%) 0.83s (± 0.48%) -0.01s (- 0.95%) 0.82s 0.84s
Check Time 4.98s (± 0.61%) 4.98s (± 0.43%) +0.00s (+ 0.00%) 4.93s 5.03s
Emit Time 5.37s (± 0.62%) 5.35s (± 0.61%) -0.02s (- 0.47%) 5.30s 5.44s
Total Time 13.19s (± 0.53%) 13.15s (± 0.32%) -0.04s (- 0.32%) 13.08s 13.24s
Monaco - node (v10.16.3, x64)
Memory used 354,771k (± 0.02%) 354,701k (± 0.02%) -70k (- 0.02%) 354,495k 354,942k
Parse Time 1.61s (± 0.77%) 1.61s (± 0.55%) +0.00s (+ 0.12%) 1.59s 1.63s
Bind Time 0.73s (± 0.50%) 0.73s (± 0.76%) +0.00s (+ 0.28%) 0.72s 0.74s
Check Time 5.15s (± 0.55%) 5.14s (± 0.44%) -0.01s (- 0.23%) 5.08s 5.19s
Emit Time 2.81s (± 0.85%) 2.82s (± 0.81%) +0.01s (+ 0.46%) 2.77s 2.89s
Total Time 10.29s (± 0.47%) 10.30s (± 0.41%) +0.01s (+ 0.11%) 10.24s 10.44s
TFS - node (v10.16.3, x64)
Memory used 307,848k (± 0.01%) 307,808k (± 0.02%) -40k (- 0.01%) 307,630k 307,863k
Parse Time 1.24s (± 0.45%) 1.24s (± 0.59%) -0.00s (- 0.00%) 1.22s 1.25s
Bind Time 0.68s (± 1.36%) 0.68s (± 1.11%) +0.00s (+ 0.29%) 0.66s 0.70s
Check Time 4.57s (± 0.46%) 4.60s (± 0.52%) +0.03s (+ 0.68%) 4.54s 4.66s
Emit Time 2.95s (± 0.71%) 2.96s (± 1.21%) +0.02s (+ 0.61%) 2.87s 3.04s
Total Time 9.45s (± 0.42%) 9.50s (± 0.41%) +0.05s (+ 0.52%) 9.40s 9.57s
material-ui - node (v10.16.3, x64)
Memory used 489,323k (± 0.02%) 489,357k (± 0.02%) +34k (+ 0.01%) 489,203k 489,505k
Parse Time 2.08s (± 0.69%) 2.07s (± 0.51%) -0.01s (- 0.53%) 2.04s 2.08s
Bind Time 0.65s (± 0.73%) 0.66s (± 0.76%) +0.00s (+ 0.31%) 0.65s 0.67s
Check Time 13.63s (± 0.81%) 13.65s (± 0.94%) +0.02s (+ 0.18%) 13.40s 13.86s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 16.36s (± 0.73%) 16.38s (± 0.80%) +0.01s (+ 0.09%) 16.15s 16.60s
Angular - node (v12.1.0, x64)
Memory used 322,277k (± 0.02%) 322,277k (± 0.02%) -0k (- 0.00%) 322,154k 322,469k
Parse Time 1.97s (± 0.56%) 1.96s (± 0.55%) -0.01s (- 0.61%) 1.94s 1.99s
Bind Time 0.81s (± 0.82%) 0.81s (± 0.99%) -0.00s (- 0.12%) 0.80s 0.83s
Check Time 4.88s (± 0.52%) 4.90s (± 0.50%) +0.01s (+ 0.25%) 4.84s 4.93s
Emit Time 5.46s (± 0.48%) 5.46s (± 0.35%) -0.00s (- 0.04%) 5.41s 5.51s
Total Time 13.13s (± 0.26%) 13.13s (± 0.26%) -0.00s (- 0.02%) 13.08s 13.22s
Monaco - node (v12.1.0, x64)
Memory used 336,797k (± 0.01%) 336,833k (± 0.02%) +36k (+ 0.01%) 336,699k 336,997k
Parse Time 1.59s (± 0.43%) 1.58s (± 0.30%) -0.00s (- 0.19%) 1.57s 1.59s
Bind Time 0.71s (± 0.99%) 0.71s (± 0.87%) 0.00s ( 0.00%) 0.70s 0.73s
Check Time 4.92s (± 0.70%) 4.93s (± 0.48%) +0.01s (+ 0.24%) 4.87s 4.98s
Emit Time 2.87s (± 0.56%) 2.87s (± 0.62%) +0.01s (+ 0.21%) 2.82s 2.90s
Total Time 10.08s (± 0.50%) 10.09s (± 0.29%) +0.01s (+ 0.12%) 10.04s 10.16s
TFS - node (v12.1.0, x64)
Memory used 292,071k (± 0.02%) 292,092k (± 0.03%) +21k (+ 0.01%) 291,948k 292,331k
Parse Time 1.25s (± 0.47%) 1.26s (± 0.47%) +0.00s (+ 0.16%) 1.24s 1.27s
Bind Time 0.65s (± 0.56%) 0.66s (± 0.94%) +0.00s (+ 0.76%) 0.64s 0.67s
Check Time 4.52s (± 0.40%) 4.53s (± 0.68%) +0.01s (+ 0.24%) 4.46s 4.60s
Emit Time 2.97s (± 0.65%) 2.98s (± 1.37%) +0.01s (+ 0.44%) 2.93s 3.10s
Total Time 9.39s (± 0.36%) 9.42s (± 0.42%) +0.03s (+ 0.33%) 9.29s 9.49s
material-ui - node (v12.1.0, x64)
Memory used 467,221k (± 0.06%) 466,998k (± 0.09%) -223k (- 0.05%) 466,146k 467,557k
Parse Time 2.08s (± 0.69%) 2.09s (± 0.36%) +0.01s (+ 0.38%) 2.07s 2.10s
Bind Time 0.65s (± 1.12%) 0.65s (± 0.58%) -0.00s (- 0.46%) 0.64s 0.65s
Check Time 12.18s (± 1.60%) 12.14s (± 0.97%) -0.04s (- 0.30%) 11.90s 12.43s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 14.90s (± 1.31%) 14.87s (± 0.77%) -0.03s (- 0.18%) 14.63s 15.14s
Angular - node (v8.9.0, x64)
Memory used 346,989k (± 0.02%) 347,007k (± 0.02%) +17k (+ 0.00%) 346,845k 347,121k
Parse Time 2.53s (± 0.45%) 2.51s (± 0.42%) -0.02s (- 0.83%) 2.49s 2.54s
Bind Time 0.87s (± 0.54%) 0.87s (± 0.71%) -0.00s (- 0.11%) 0.85s 0.88s
Check Time 5.60s (± 0.82%) 5.61s (± 0.50%) +0.01s (+ 0.18%) 5.55s 5.68s
Emit Time 6.36s (± 0.98%) 6.38s (± 1.18%) +0.02s (+ 0.31%) 6.10s 6.48s
Total Time 15.36s (± 0.69%) 15.37s (± 0.62%) +0.01s (+ 0.07%) 15.01s 15.47s
Monaco - node (v8.9.0, x64)
Memory used 358,535k (± 0.01%) 358,511k (± 0.01%) -23k (- 0.01%) 358,432k 358,569k
Parse Time 1.93s (± 0.25%) 1.94s (± 0.27%) +0.01s (+ 0.26%) 1.93s 1.95s
Bind Time 0.91s (± 0.77%) 0.91s (± 0.90%) +0.00s (+ 0.33%) 0.90s 0.93s
Check Time 5.68s (± 0.69%) 5.67s (± 0.38%) -0.02s (- 0.28%) 5.62s 5.73s
Emit Time 3.41s (± 1.14%) 3.43s (± 1.03%) +0.02s (+ 0.50%) 3.38s 3.56s
Total Time 11.94s (± 0.59%) 11.94s (± 0.39%) +0.01s (+ 0.06%) 11.87s 12.08s
TFS - node (v8.9.0, x64)
Memory used 310,392k (± 0.01%) 310,384k (± 0.02%) -7k (- 0.00%) 310,238k 310,457k
Parse Time 1.57s (± 0.45%) 1.57s (± 0.67%) +0.00s (+ 0.19%) 1.56s 1.60s
Bind Time 0.69s (± 0.75%) 0.68s (± 0.54%) -0.01s (- 0.87%) 0.68s 0.69s
Check Time 5.33s (± 0.63%) 5.33s (± 0.54%) -0.00s (- 0.00%) 5.27s 5.41s
Emit Time 2.95s (± 1.05%) 2.95s (± 0.72%) -0.00s (- 0.14%) 2.88s 2.98s
Total Time 10.55s (± 0.56%) 10.54s (± 0.25%) -0.00s (- 0.04%) 10.51s 10.64s
material-ui - node (v8.9.0, x64)
Memory used 496,391k (± 0.02%) 496,346k (± 0.01%) -45k (- 0.01%) 496,222k 496,447k
Parse Time 2.50s (± 0.42%) 2.49s (± 0.50%) -0.01s (- 0.24%) 2.46s 2.51s
Bind Time 0.82s (± 0.82%) 0.82s (± 1.00%) 0.00s ( 0.00%) 0.80s 0.83s
Check Time 18.05s (± 0.51%) 17.88s (± 0.78%) -0.17s (- 0.96%) 17.58s 18.11s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 21.37s (± 0.43%) 21.19s (± 0.67%) -0.18s (- 0.84%) 20.87s 21.42s
Angular - node (v8.9.0, x86)
Memory used 199,004k (± 0.03%) 198,970k (± 0.02%) -34k (- 0.02%) 198,897k 199,041k
Parse Time 2.44s (± 0.82%) 2.43s (± 0.54%) -0.01s (- 0.37%) 2.40s 2.46s
Bind Time 1.02s (± 0.98%) 1.02s (± 0.58%) +0.00s (+ 0.49%) 1.01s 1.04s
Check Time 5.07s (± 0.40%) 5.07s (± 0.59%) -0.00s (- 0.02%) 5.00s 5.13s
Emit Time 6.16s (± 1.28%) 6.16s (± 1.34%) -0.00s (- 0.02%) 6.03s 6.43s
Total Time 14.70s (± 0.42%) 14.69s (± 0.63%) -0.01s (- 0.05%) 14.51s 14.97s
Monaco - node (v8.9.0, x86)
Memory used 203,067k (± 0.02%) 203,089k (± 0.02%) +22k (+ 0.01%) 202,980k 203,228k
Parse Time 1.98s (± 0.55%) 1.99s (± 0.85%) +0.01s (+ 0.25%) 1.94s 2.01s
Bind Time 0.72s (± 0.51%) 0.72s (± 0.80%) +0.00s (+ 0.56%) 0.71s 0.73s
Check Time 5.80s (± 0.77%) 5.81s (± 0.65%) +0.01s (+ 0.12%) 5.72s 5.88s
Emit Time 2.74s (± 0.57%) 2.77s (± 0.72%) +0.03s (+ 0.99%) 2.74s 2.82s
Total Time 11.24s (± 0.42%) 11.29s (± 0.50%) +0.04s (+ 0.40%) 11.11s 11.37s
TFS - node (v8.9.0, x86)
Memory used 177,516k (± 0.02%) 177,525k (± 0.02%) +8k (+ 0.00%) 177,443k 177,608k
Parse Time 1.61s (± 0.66%) 1.62s (± 1.13%) +0.01s (+ 0.93%) 1.59s 1.66s
Bind Time 0.65s (± 0.99%) 0.65s (± 0.85%) +0.00s (+ 0.00%) 0.64s 0.67s
Check Time 4.84s (± 0.79%) 4.87s (± 0.57%) +0.03s (+ 0.56%) 4.78s 4.91s
Emit Time 2.82s (± 1.23%) 2.84s (± 1.42%) +0.02s (+ 0.71%) 2.74s 2.97s
Total Time 9.92s (± 0.57%) 9.98s (± 0.66%) +0.07s (+ 0.66%) 9.82s 10.19s
material-ui - node (v8.9.0, x86)
Memory used 279,467k (± 0.01%) 279,426k (± 0.02%) -41k (- 0.01%) 279,340k 279,515k
Parse Time 2.55s (± 0.57%) 2.56s (± 0.55%) +0.01s (+ 0.24%) 2.53s 2.59s
Bind Time 0.75s (± 6.26%) 0.74s (± 6.65%) -0.02s (- 2.13%) 0.69s 0.87s
Check Time 16.43s (± 0.82%) 16.47s (± 0.61%) +0.04s (+ 0.26%) 16.23s 16.63s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 19.73s (± 0.64%) 19.76s (± 0.48%) +0.03s (+ 0.16%) 19.50s 19.91s
System
Machine Namets-ci-ubuntu
Platformlinux 4.4.0-166-generic
Architecturex64
Available Memory16 GB
Available Memory1 GB
CPUs4 × Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
Hosts
  • node (v10.16.3, x64)
  • node (v12.1.0, x64)
  • node (v8.9.0, x64)
  • node (v8.9.0, x86)
Scenarios
  • Angular - node (v10.16.3, x64)
  • Angular - node (v12.1.0, x64)
  • Angular - node (v8.9.0, x64)
  • Angular - node (v8.9.0, x86)
  • Monaco - node (v10.16.3, x64)
  • Monaco - node (v12.1.0, x64)
  • Monaco - node (v8.9.0, x64)
  • Monaco - node (v8.9.0, x86)
  • TFS - node (v10.16.3, x64)
  • TFS - node (v12.1.0, x64)
  • TFS - node (v8.9.0, x64)
  • TFS - node (v8.9.0, x86)
  • material-ui - node (v10.16.3, x64)
  • material-ui - node (v12.1.0, x64)
  • material-ui - node (v8.9.0, x64)
  • material-ui - node (v8.9.0, x86)
Benchmark Name Iterations
Current 41665 10
Baseline master 10

@typescript-bot typescript-bot mentioned this pull request Nov 24, 2020
Open
@typescript-bot
Copy link
Collaborator

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

@JoostK
Copy link
Contributor

JoostK commented Nov 24, 2020 •
edited

@ahejlsberg Thanks for taking a look at this, it's highly appreciated.

The changes in #41408 were deliberately caching up to two shared flow nodes, i.e. the one closest to and furthest from the root. In theory I think there can be arbitrarily many shared candidates that are visited in the getFlowTypeOfReference but keeping track of all these would not be worth it. I figured it couldn't hurt to cache at most two candidates as that doesn't require any allocations, whereas the simplification here caches up to one node (the one furthest from the root). I have seen the case where two nodes are cached being hit in the testsuite, but it may be that it's not widespread enough to warrant the extra branching and cache entries (I didn't gather statistics here).

tldr; I think the simplification is fine, just wanted to share the reasoning behind the changes in #41408.

@ahejlsberg
Copy link
Member Author

ahejlsberg commented Nov 24, 2020 •
edited

@JoostK With the simplification we'll cache in the last shared node visited, which is the one closest to the "top" of the control flow graph. That should get us the most sharing possible. It may take a few extra loop iterations to hit the cache, but those iterations are cheap--the costly stuff all happens in the recursive calls. Either way, the key insight here is that we sometimes didn't cache at all, and I appreciate you discovering that.

It's interesting to see that the fix has little or no effect on our performance suites. I guess the pattern that leads to the exponential slowdown is rare. But then again, if it was more common we'd probably have run into it already.

@ahejlsberg ahejlsberg mentioned this pull request Nov 24, 2020
Closed
@JoostK
Copy link
Contributor

JoostK commented Nov 24, 2020

@ahejlsberg Thanks for the additional explanation. I would kindly request if this could be backported to 4.1, as the 4.2 release is still 3 months out.

@RyanCavanaugh
Copy link
Member

This looks like a pretty safe backport. @DanielRosenwasser @ahejlsberg thoughts?

@ahejlsberg
Copy link
Member Author

@RyanCavanaugh Yes, this is a very safe fix and I agree we should backport.

@ahejlsberg ahejlsberg merged commit ec1490f into master Nov 26, 2020
@ahejlsberg ahejlsberg deleted the fix41124 branch November 26, 2020 00:51
@JoostK JoostK mentioned this pull request Nov 26, 2020
Closed
JoostK pushed a commit to JoostK/TypeScript that referenced this pull request Dec 9, 2020
@ahejlsberg @JoostK
Properly cache types for shared control flow nodes (microsoft#41665)
0ebfeb4 
* Properly cache shared flow node types

* Add test
@JoostK JoostK mentioned this pull request Dec 9, 2020
Merged
DanielRosenwasser pushed a commit that referenced this pull request Dec 10, 2020
@JoostK @ahejlsberg
Properly cache types for shared control flow nodes (#41665) (#41906)
3c73625 
* Properly cache shared flow node types

* Add test

Co-authored-by: Anders Hejlsberg <andersh@microsoft.com>
@dependabot dependabot bot mentioned this pull request Mar 14, 2021
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@weswigham weswigham weswigham approved these changes

@nitish-awasthi nitish-awasthi nitish-awasthi approved these changes

@sandersn sandersn Awaiting requested review from sandersn

Assignees

@weswigham weswigham

@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.

perf: exponential slowdown in flow analysis
6 participants
@ahejlsberg @typescript-bot @JoostK @RyanCavanaugh @weswigham @nitish-awasthi