GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Tail recursive evaluation of conditional types by ahejlsberg · Pull Request #45711 · microsoft/TypeScript

Conversation

@ahejlsberg

@ahejlsberg Anders Hejlsberg (ahejlsberg) commented Sep 3, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

In #45025 we increased the type instantiation depth limit from 50 to 500. We've subsequently seen multiple examples of stack overflows occurring during compilation of programs containing non-terminating types, particularly when the compiler is used in browser hosted environments (where, apparently, in some cases the call stack limit is lower than in Node.js). It is clear that 500 is too high of a limit, so in this PR we lower the maximum to 100.

There are legitimate cases where evaluation of recursive conditional types needs more than 100 iterations to complete. For that reason, this PR implements tail recursive evaluation of conditional types. Specifically, when a conditional type ends in another (or, through recursion, another instantiation of the same) conditional type, the compiler now performs type resolution in a loop that consumes no extra call stack. We permit evaluation of such types to loop 1000 times before we consider the type non-terminating and issue an error.

The following conditional type is tail recursive:

type Trim<S extends string> =
    S extends ` ${infer T}` ? Trim<T> :
    S extends `${infer T} ` ? Trim<T> :
    S;

Previously, resolution of instantiations of this type would error for string literals containing more than 25 blanks. We now permit strings with up to 1000 blanks.

Conditional types that aren't tail recursive generally can be written in a tail recursive form by introducing an "accumulator". For example, this type, which extracts a union of the characters in a string, isn't tail recursive (because it recurs through a union type)

type GetChars<S> =
    S extends `${infer Char}${infer Rest}` ? Char | GetChars<Rest> : never;

but this rewritten form is

type GetChars<S> = GetCharsRec<S, never>;
type GetCharsRec<S, Acc> =
    S extends `${infer Char}${infer Rest}` ? GetCharsRec<Rest, Char | Acc> : Acc;

Some additional examples of tail recursive conditional types:

type Reverse<T> = any[] extends T ? T : ReverseRec<T, []>;
type ReverseRec<T, Acc extends unknown[]> =
    T extends [infer Head, ...infer Tail] ? ReverseRec<Tail, [Head, ...Acc]> : Acc;

type T1 = Reverse<[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;

type TupleOf<T, N extends number> = number extends N ? T[] : TupleOfRec<T, N, []>;
type TupleOfRec<T, N extends number, Acc extends unknown[]> =
    Acc["length"] extends N ? Acc : TupleOfRec<T, N, [T, ...Acc]>;

type T2 = TupleOf<any, 200>;

The examples above previously would error in "Type instantiation is excessively deep and possibly infinite", but now succeed.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
schickling, awerlogus, IllusionMH, vasilii-kovalev, tjjfvi, andrewbranch, fuafa, etienne-dldc, MattiasBuelens, acutmore, and 74 more reacted with thumbs up emoji wongmjane, tjjfvi, acutmore, sledorze, tonivj5, sumitparakh, dsebastien, ExE-Boss, sinclairzx81, AriaMinaei, and 22 more reacted with hooray emoji acutmore, sledorze, tonivj5, tajakobsen, sumitparakh, treybrisbane, sinclairzx81, gvergnaud, ssalbdivad, JadenSimon, and 18 more reacted with heart emoji AviVahl, ExE-Boss, sinclairzx81, gvergnaud, markusjohnsson, iiojib, JadenSimon, cherryblossom000, schneiderfelipe, millsp, and 10 more reacted with rocket emoji mbifulco, tjjfvi, dauntlxss, tonivj5, itsMapleLeaf, mpawelski, NickSchmitt, cindmichelle, JohannesSchwegler, and avinoamsn reacted with eyes emoji
All reactions
  • 👍 84 reactions
  • 🎉 32 reactions
  • ❤️ 28 reactions
  • 🚀 20 reactions
  • 👀 10 reactions
Anders Hejlsberg (ahejlsberg) added 2 commits September 2, 2021 10:10
@ahejlsberg
Implement tail-recursion for conditional types and lower general inst…
1610e19 
…antiation depth limit to 100
@ahejlsberg
Add tests
093f76a
@typescript-bot TypeScript Bot (typescript-bot) assigned Anders Hejlsberg (ahejlsberg) Sep 3, 2021
@typescript-bot TypeScript Bot (typescript-bot) added Author: Team For Uncommitted Bug PR for untriaged, rejected, closed or missing bug labels Sep 3, 2021
@ahejlsberg
Anders Hejlsberg (ahejlsberg) requested review from Daniel Rosenwasser (DanielRosenwasser), Andrew Branch (andrewbranch) and Wesley Wigham (weswigham) September 3, 2021 15:39
@ahejlsberg Anders Hejlsberg (ahejlsberg) added this to the TypeScript 4.5.0 milestone Sep 3, 2021
@ahejlsberg

Anders Hejlsberg (ahejlsberg) commented Sep 3, 2021

Copy link
Copy Markdown
Member Author

TypeScript Bot (@typescript-bot) test this
TypeScript Bot (@typescript-bot) user test this
TypeScript Bot (@typescript-bot) run dt
TypeScript Bot (@typescript-bot) perf test this
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@typescript-bot

TypeScript Bot (typescript-bot) commented Sep 3, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@typescript-bot

TypeScript Bot (typescript-bot) commented Sep 3, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@typescript-bot

TypeScript Bot (typescript-bot) commented Sep 3, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

Heya Anders Hejlsberg (@ahejlsberg), I've started to run the parallelized community code test suite on this PR at 093f76a. You can monitor the build here.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@typescript-bot

TypeScript Bot (typescript-bot) commented Sep 3, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

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

Update: The results are in!
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
weswigham
Wesley Wigham (weswigham) approved these changes Sep 3, 2021
View reviewed changes

@weswigham Wesley Wigham (weswigham) left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

It'd be nice if we could kinda automatically do the "extract to an accumulator" thing you suggest in the OP, so people didn't need to write their conditionals with such structure in mind; but this seems good.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
ExE-Boss, yaroslavvoloshchuk-codaio, LeoniePhiline, and strblr reacted with thumbs up emoji
All reactions
  • 👍 4 reactions
@typescript-bot TypeScript Bot (typescript-bot) mentioned this pull request Sep 3, 2021
🤖 User test baselines have changed for tailRecursiveConditionals typescript-bot/TypeScript#204
Open
@typescript-bot

TypeScript Bot (typescript-bot) commented Sep 3, 2021

Copy link
Copy Markdown
Contributor

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@typescript-bot

TypeScript Bot (typescript-bot) commented Sep 3, 2021

Copy link
Copy Markdown
Contributor

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

Here they are:

Comparison Report - main..45711

Metric main 45711 Delta Best Worst
Angular - node (v10.16.3, x64)
Memory used 351,611k (± 0.03%) 351,552k (± 0.02%) -59k (- 0.02%) 351,375k 351,666k
Parse Time 1.91s (± 0.30%) 1.90s (± 0.49%) -0.00s (- 0.26%) 1.88s 1.92s
Bind Time 0.85s (± 0.40%) 0.85s (± 0.70%) +0.00s (+ 0.23%) 0.84s 0.87s
Check Time 5.39s (± 0.41%) 5.40s (± 0.32%) +0.01s (+ 0.15%) 5.36s 5.43s
Emit Time 5.83s (± 0.42%) 5.84s (± 0.45%) +0.01s (+ 0.17%) 5.79s 5.91s
Total Time 13.97s (± 0.25%) 13.99s (± 0.27%) +0.02s (+ 0.11%) 13.93s 14.10s
Compiler-Unions - node (v10.16.3, x64)
Memory used 203,474k (± 0.03%) 203,450k (± 0.03%) -24k (- 0.01%) 203,353k 203,620k
Parse Time 0.78s (± 0.85%) 0.78s (± 0.87%) +0.00s (+ 0.51%) 0.77s 0.80s
Bind Time 0.52s (± 1.13%) 0.52s (± 1.28%) -0.00s (- 0.19%) 0.51s 0.54s
Check Time 7.82s (± 0.42%) 7.80s (± 0.42%) -0.02s (- 0.26%) 7.75s 7.91s
Emit Time 2.44s (± 0.51%) 2.43s (± 1.06%) -0.01s (- 0.25%) 2.40s 2.53s
Total Time 11.56s (± 0.42%) 11.54s (± 0.39%) -0.02s (- 0.15%) 11.47s 11.65s
Monaco - node (v10.16.3, x64)
Memory used 340,659k (± 0.02%) 340,634k (± 0.02%) -25k (- 0.01%) 340,472k 340,811k
Parse Time 1.45s (± 0.69%) 1.45s (± 0.67%) +0.00s (+ 0.07%) 1.43s 1.47s
Bind Time 0.75s (± 0.87%) 0.75s (± 0.40%) 0.00s ( 0.00%) 0.74s 0.75s
Check Time 5.44s (± 0.37%) 5.40s (± 0.45%) -0.04s (- 0.68%) 5.36s 5.48s
Emit Time 3.17s (± 0.78%) 3.15s (± 0.58%) -0.02s (- 0.63%) 3.11s 3.18s
Total Time 10.80s (± 0.32%) 10.75s (± 0.34%) -0.05s (- 0.50%) 10.67s 10.82s
TFS - node (v10.16.3, x64)
Memory used 304,028k (± 0.01%) 304,024k (± 0.03%) -4k (- 0.00%) 303,780k 304,176k
Parse Time 1.18s (± 0.52%) 1.19s (± 0.57%) +0.01s (+ 0.59%) 1.18s 1.21s
Bind Time 0.72s (± 0.95%) 0.71s (± 1.06%) -0.00s (- 0.14%) 0.70s 0.73s
Check Time 4.92s (± 0.56%) 4.94s (± 0.62%) +0.03s (+ 0.53%) 4.86s 4.99s
Emit Time 3.31s (± 1.05%) 3.37s (± 1.96%) +0.06s (+ 1.72%) 3.25s 3.52s
Total Time 10.12s (± 0.45%) 10.21s (± 0.71%) +0.09s (+ 0.86%) 10.08s 10.40s
material-ui - node (v10.16.3, x64)
Memory used 469,942k (± 0.01%) 469,793k (± 0.01%) -149k (- 0.03%) 469,715k 469,940k
Parse Time 1.73s (± 0.40%) 1.73s (± 0.43%) +0.01s (+ 0.46%) 1.72s 1.75s
Bind Time 0.66s (± 0.55%) 0.67s (± 0.51%) +0.01s (+ 1.36%) 0.67s 0.68s
Check Time 14.15s (± 0.27%) 14.35s (± 0.65%) +0.20s (+ 1.43%) 14.16s 14.60s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 16.54s (± 0.24%) 16.76s (± 0.58%) +0.22s (+ 1.31%) 16.56s 17.01s
Angular - node (v12.1.0, x64)
Memory used 329,584k (± 0.03%) 329,534k (± 0.02%) -49k (- 0.01%) 329,365k 329,668k
Parse Time 1.88s (± 0.62%) 1.88s (± 0.48%) -0.00s (- 0.21%) 1.85s 1.89s
Bind Time 0.83s (± 0.44%) 0.84s (± 0.80%) +0.00s (+ 0.24%) 0.82s 0.85s
Check Time 5.22s (± 0.52%) 5.22s (± 0.39%) +0.01s (+ 0.10%) 5.19s 5.28s
Emit Time 6.05s (± 0.49%) 6.13s (± 1.46%) +0.08s (+ 1.32%) 6.04s 6.47s
Total Time 13.98s (± 0.31%) 14.07s (± 0.71%) +0.08s (+ 0.59%) 13.94s 14.41s
Compiler-Unions - node (v12.1.0, x64)
Memory used 191,013k (± 0.02%) 190,985k (± 0.03%) -28k (- 0.01%) 190,894k 191,166k
Parse Time 0.78s (± 0.83%) 0.78s (± 0.88%) -0.01s (- 0.77%) 0.76s 0.79s
Bind Time 0.52s (± 1.13%) 0.53s (± 1.09%) +0.01s (+ 1.15%) 0.52s 0.54s
Check Time 7.37s (± 0.58%) 7.39s (± 0.72%) +0.02s (+ 0.22%) 7.31s 7.50s
Emit Time 2.47s (± 1.18%) 2.45s (± 0.78%) -0.02s (- 0.61%) 2.42s 2.51s
Total Time 11.15s (± 0.49%) 11.15s (± 0.57%) 0.00s ( 0.00%) 11.04s 11.28s
Monaco - node (v12.1.0, x64)
Memory used 323,734k (± 0.01%) 323,779k (± 0.02%) +45k (+ 0.01%) 323,576k 323,859k
Parse Time 1.43s (± 0.51%) 1.43s (± 0.85%) +0.00s (+ 0.21%) 1.41s 1.46s
Bind Time 0.72s (± 0.47%) 0.73s (± 0.92%) +0.00s (+ 0.55%) 0.71s 0.74s
Check Time 5.26s (± 0.43%) 5.28s (± 0.37%) +0.03s (+ 0.49%) 5.23s 5.31s
Emit Time 3.19s (± 0.67%) 3.19s (± 0.78%) -0.00s (- 0.06%) 3.15s 3.25s
Total Time 10.60s (± 0.35%) 10.63s (± 0.30%) +0.03s (+ 0.30%) 10.54s 10.69s
TFS - node (v12.1.0, x64)
Memory used 288,714k (± 0.02%) 288,785k (± 0.02%) +71k (+ 0.02%) 288,664k 288,910k
Parse Time 1.20s (± 0.77%) 1.21s (± 0.93%) +0.01s (+ 0.75%) 1.19s 1.24s
Bind Time 0.70s (± 0.71%) 0.70s (± 0.97%) +0.01s (+ 1.29%) 0.69s 0.72s
Check Time 4.83s (± 0.41%) 4.87s (± 0.53%) +0.04s (+ 0.81%) 4.82s 4.92s
Emit Time 3.37s (± 0.55%) 3.40s (± 0.83%) +0.03s (+ 0.77%) 3.34s 3.48s
Total Time 10.10s (± 0.32%) 10.18s (± 0.55%) +0.08s (+ 0.82%) 10.05s 10.34s
material-ui - node (v12.1.0, x64)
Memory used 448,462k (± 0.07%) 448,419k (± 0.05%) -43k (- 0.01%) 447,608k 448,684k
Parse Time 1.72s (± 0.47%) 1.73s (± 0.50%) +0.00s (+ 0.29%) 1.71s 1.75s
Bind Time 0.65s (± 0.86%) 0.65s (± 0.91%) +0.01s (+ 0.93%) 0.64s 0.67s
Check Time 12.78s (± 0.53%) 12.97s (± 0.89%) +0.19s (+ 1.50%) 12.76s 13.24s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 15.15s (± 0.46%) 15.36s (± 0.78%) +0.20s (+ 1.34%) 15.16s 15.63s
Angular - node (v14.15.1, x64)
Memory used 328,115k (± 0.01%) 328,111k (± 0.01%) -4k (- 0.00%) 328,022k 328,206k
Parse Time 1.91s (± 0.70%) 1.90s (± 0.52%) -0.01s (- 0.37%) 1.88s 1.92s
Bind Time 0.88s (± 1.13%) 0.88s (± 0.41%) +0.00s (+ 0.45%) 0.88s 0.89s
Check Time 5.29s (± 0.46%) 5.28s (± 0.47%) -0.01s (- 0.13%) 5.21s 5.33s
Emit Time 6.22s (± 0.87%) 6.22s (± 0.78%) -0.01s (- 0.10%) 6.12s 6.30s
Total Time 14.30s (± 0.55%) 14.29s (± 0.49%) -0.02s (- 0.11%) 14.11s 14.39s
Compiler-Unions - node (v14.15.1, x64)
Memory used 192,165k (± 0.48%) 192,487k (± 0.38%) +321k (+ 0.17%) 189,506k 192,910k
Parse Time 0.81s (± 0.76%) 0.81s (± 0.58%) +0.00s (+ 0.12%) 0.80s 0.82s
Bind Time 0.55s (± 1.08%) 0.56s (± 0.53%) +0.00s (+ 0.54%) 0.55s 0.56s
Check Time 7.50s (± 0.50%) 7.54s (± 0.71%) +0.04s (+ 0.52%) 7.42s 7.65s
Emit Time 2.45s (± 0.58%) 2.46s (± 0.56%) +0.01s (+ 0.45%) 2.43s 2.49s
Total Time 11.31s (± 0.44%) 11.37s (± 0.50%) +0.06s (+ 0.51%) 11.26s 11.52s
Monaco - node (v14.15.1, x64)
Memory used 322,544k (± 0.00%) 322,548k (± 0.01%) +4k (+ 0.00%) 322,489k 322,578k
Parse Time 1.49s (± 0.98%) 1.49s (± 0.61%) +0.00s (+ 0.27%) 1.47s 1.51s
Bind Time 0.75s (± 0.40%) 0.76s (± 0.66%) +0.00s (+ 0.40%) 0.75s 0.77s
Check Time 5.21s (± 0.61%) 5.24s (± 0.27%) +0.03s (+ 0.58%) 5.22s 5.28s
Emit Time 3.22s (± 0.63%) 3.22s (± 0.65%) 0.00s ( 0.00%) 3.16s 3.26s
Total Time 10.67s (± 0.46%) 10.71s (± 0.27%) +0.04s (+ 0.34%) 10.61s 10.75s
TFS - node (v14.15.1, x64)
Memory used 287,699k (± 0.01%) 287,695k (± 0.00%) -5k (- 0.00%) 287,669k 287,707k
Parse Time 1.26s (± 1.13%) 1.25s (± 2.11%) -0.01s (- 0.48%) 1.21s 1.34s
Bind Time 0.72s (± 0.80%) 0.76s (± 4.49%) +0.04s (+ 5.28%) 0.71s 0.83s
Check Time 4.86s (± 0.54%) 4.87s (± 0.68%) +0.01s (+ 0.14%) 4.79s 4.92s
Emit Time 3.46s (± 1.01%) 3.46s (± 0.88%) -0.00s (- 0.14%) 3.40s 3.53s
Total Time 10.30s (± 0.40%) 10.34s (± 0.60%) +0.03s (+ 0.33%) 10.20s 10.44s
material-ui - node (v14.15.1, x64)
Memory used 447,023k (± 0.00%) 446,915k (± 0.01%) -108k (- 0.02%) 446,870k 446,976k
Parse Time 1.76s (± 0.47%) 1.77s (± 0.62%) +0.02s (+ 0.97%) 1.75s 1.80s
Bind Time 0.68s (± 0.87%) 0.69s (± 0.94%) +0.01s (+ 1.02%) 0.68s 0.71s
Check Time 12.90s (± 0.53%) 13.19s (± 0.49%) +0.29s (+ 2.27%) 13.00s 13.34s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 15.34s (± 0.50%) 15.66s (± 0.42%) +0.32s (+ 2.09%) 15.47s 15.78s
System
Machine Namets-ci-ubuntu
Platformlinux 4.4.0-210-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 45711 10
Baseline main 10

Developer Information:

Download Benchmark
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@DanielRosenwasser

Daniel Rosenwasser (DanielRosenwasser) commented Sep 3, 2021

Copy link
Copy Markdown
Member

I can't tell how much of this in the noise, but the check time on material-ui does seem like it's taken a hit across all versions.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@DanielRosenwasser Daniel Rosenwasser (DanielRosenwasser) mentioned this pull request Sep 3, 2021
Design Meeting Notes, 9/3/2021 #45718
Closed
@nandorojo Fernando Rojo (nandorojo) mentioned this pull request Sep 4, 2021
Support dotted path notation millsp/ts-toolbelt#154
Closed
@ahejlsberg
Skip caching for tail recursive temporary conditional types
a4224d6
@ahejlsberg

Anders Hejlsberg (ahejlsberg) commented Sep 4, 2021

Copy link
Copy Markdown
Member Author

TypeScript Bot (@typescript-bot) perf test this
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@typescript-bot

TypeScript Bot (typescript-bot) commented Sep 4, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

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

Update: The results are in!
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@typescript-bot

TypeScript Bot (typescript-bot) commented Sep 4, 2021

Copy link
Copy Markdown
Contributor

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

Here they are:

Comparison Report - main..45711

Metric main 45711 Delta Best Worst
Angular - node (v10.16.3, x64)
Memory used 351,498k (± 0.02%) 351,568k (± 0.02%) +70k (+ 0.02%) 351,360k 351,643k
Parse Time 1.90s (± 0.34%) 1.91s (± 0.68%) +0.01s (+ 0.63%) 1.89s 1.94s
Bind Time 0.85s (± 0.76%) 0.86s (± 0.69%) +0.01s (+ 0.94%) 0.85s 0.87s
Check Time 5.40s (± 0.45%) 5.41s (± 0.37%) +0.01s (+ 0.24%) 5.36s 5.47s
Emit Time 5.83s (± 0.29%) 5.86s (± 0.64%) +0.03s (+ 0.55%) 5.77s 5.95s
Total Time 13.97s (± 0.26%) 14.04s (± 0.38%) +0.07s (+ 0.48%) 13.88s 14.14s
Compiler-Unions - node (v10.16.3, x64)
Memory used 203,519k (± 0.04%) 203,445k (± 0.03%) -74k (- 0.04%) 203,329k 203,611k
Parse Time 0.78s (± 0.85%) 0.79s (± 0.89%) +0.01s (+ 1.15%) 0.77s 0.80s
Bind Time 0.52s (± 1.43%) 0.52s (± 1.66%) -0.00s (- 0.19%) 0.51s 0.54s
Check Time 7.84s (± 0.50%) 7.89s (± 0.64%) +0.05s (+ 0.66%) 7.76s 7.99s
Emit Time 2.44s (± 0.70%) 2.46s (± 0.74%) +0.02s (+ 0.61%) 2.42s 2.49s
Total Time 11.58s (± 0.37%) 11.65s (± 0.54%) +0.07s (+ 0.60%) 11.51s 11.77s
Monaco - node (v10.16.3, x64)
Memory used 340,627k (± 0.03%) 340,619k (± 0.02%) -9k (- 0.00%) 340,464k 340,827k
Parse Time 1.45s (± 0.90%) 1.46s (± 0.46%) +0.01s (+ 0.76%) 1.44s 1.47s
Bind Time 0.75s (± 1.07%) 0.75s (± 0.60%) 0.00s ( 0.00%) 0.74s 0.76s
Check Time 5.44s (± 0.60%) 5.41s (± 0.72%) -0.03s (- 0.50%) 5.31s 5.49s
Emit Time 3.16s (± 0.86%) 3.16s (± 1.04%) +0.01s (+ 0.25%) 3.11s 3.26s
Total Time 10.79s (± 0.44%) 10.78s (± 0.29%) -0.01s (- 0.05%) 10.71s 10.86s
TFS - node (v10.16.3, x64)
Memory used 303,979k (± 0.03%) 304,033k (± 0.02%) +55k (+ 0.02%) 303,923k 304,196k
Parse Time 1.18s (± 0.59%) 1.18s (± 0.31%) +0.00s (+ 0.25%) 1.18s 1.19s
Bind Time 0.71s (± 0.52%) 0.71s (± 0.69%) -0.00s (- 0.14%) 0.71s 0.73s
Check Time 4.92s (± 0.65%) 4.93s (± 0.43%) +0.01s (+ 0.20%) 4.89s 4.97s
Emit Time 3.32s (± 1.36%) 3.32s (± 1.45%) +0.00s (+ 0.06%) 3.22s 3.43s
Total Time 10.13s (± 0.60%) 10.15s (± 0.56%) +0.01s (+ 0.13%) 10.00s 10.28s
material-ui - node (v10.16.3, x64)
Memory used 469,920k (± 0.02%) 469,714k (± 0.01%) -207k (- 0.04%) 469,641k 469,788k
Parse Time 1.73s (± 0.70%) 1.74s (± 0.61%) +0.01s (+ 0.35%) 1.72s 1.76s
Bind Time 0.66s (± 0.45%) 0.67s (± 0.67%) +0.01s (+ 0.91%) 0.66s 0.68s
Check Time 14.19s (± 0.63%) 14.44s (± 0.92%) +0.25s (+ 1.76%) 14.17s 14.71s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 16.59s (± 0.55%) 16.85s (± 0.85%) +0.26s (+ 1.56%) 16.57s 17.15s
Angular - node (v12.1.0, x64)
Memory used 329,562k (± 0.02%) 329,438k (± 0.08%) -124k (- 0.04%) 328,468k 329,679k
Parse Time 1.89s (± 0.82%) 1.89s (± 0.77%) +0.00s (+ 0.05%) 1.86s 1.92s
Bind Time 0.84s (± 0.95%) 0.84s (± 0.79%) +0.00s (+ 0.12%) 0.83s 0.86s
Check Time 5.25s (± 0.64%) 5.28s (± 0.93%) +0.03s (+ 0.50%) 5.14s 5.34s
Emit Time 6.08s (± 0.55%) 6.11s (± 0.53%) +0.03s (+ 0.54%) 6.02s 6.17s
Total Time 14.06s (± 0.43%) 14.12s (± 0.57%) +0.06s (+ 0.43%) 13.92s 14.24s
Compiler-Unions - node (v12.1.0, x64)
Memory used 190,701k (± 0.32%) 190,839k (± 0.13%) +137k (+ 0.07%) 190,261k 191,234k
Parse Time 0.78s (± 0.77%) 0.78s (± 0.85%) +0.00s (+ 0.52%) 0.77s 0.80s
Bind Time 0.54s (± 0.92%) 0.53s (± 0.84%) -0.00s (- 0.75%) 0.53s 0.55s
Check Time 7.41s (± 0.69%) 7.42s (± 0.79%) +0.01s (+ 0.18%) 7.26s 7.54s
Emit Time 2.46s (± 1.08%) 2.47s (± 0.92%) +0.01s (+ 0.61%) 2.43s 2.53s
Total Time 11.17s (± 0.46%) 11.20s (± 0.59%) +0.03s (+ 0.26%) 11.02s 11.35s
Monaco - node (v12.1.0, x64)
Memory used 323,777k (± 0.02%) 323,810k (± 0.02%) +33k (+ 0.01%) 323,637k 323,961k
Parse Time 1.43s (± 0.61%) 1.44s (± 0.77%) +0.01s (+ 0.63%) 1.42s 1.46s
Bind Time 0.73s (± 0.50%) 0.73s (± 0.41%) +0.01s (+ 0.83%) 0.73s 0.74s
Check Time 5.30s (± 0.34%) 5.32s (± 0.75%) +0.02s (+ 0.38%) 5.23s 5.43s
Emit Time 3.19s (± 0.71%) 3.19s (± 0.63%) -0.01s (- 0.22%) 3.15s 3.24s
Total Time 10.65s (± 0.16%) 10.68s (± 0.60%) +0.02s (+ 0.23%) 10.52s 10.83s
TFS - node (v12.1.0, x64)
Memory used 288,768k (± 0.02%) 288,762k (± 0.02%) -6k (- 0.00%) 288,621k 288,915k
Parse Time 1.21s (± 0.72%) 1.22s (± 0.83%) +0.01s (+ 0.66%) 1.20s 1.24s
Bind Time 0.71s (± 1.36%) 0.70s (± 1.18%) -0.00s (- 0.56%) 0.69s 0.72s
Check Time 4.87s (± 0.49%) 4.87s (± 0.29%) +0.01s (+ 0.12%) 4.85s 4.90s
Emit Time 3.39s (± 1.13%) 3.38s (± 0.61%) -0.01s (- 0.32%) 3.32s 3.42s
Total Time 10.17s (± 0.63%) 10.17s (± 0.25%) +0.00s (+ 0.04%) 10.10s 10.23s
material-ui - node (v12.1.0, x64)
Memory used 448,584k (± 0.02%) 448,412k (± 0.06%) -172k (- 0.04%) 447,378k 448,617k
Parse Time 1.72s (± 0.62%) 1.73s (± 0.64%) +0.01s (+ 0.64%) 1.70s 1.75s
Bind Time 0.65s (± 0.90%) 0.65s (± 1.02%) +0.01s (+ 0.93%) 0.63s 0.66s
Check Time 12.85s (± 0.43%) 13.00s (± 0.75%) +0.15s (+ 1.14%) 12.79s 13.19s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 15.22s (± 0.32%) 15.38s (± 0.66%) +0.16s (+ 1.08%) 15.15s 15.59s
Angular - node (v14.15.1, x64)
Memory used 328,088k (± 0.01%) 328,103k (± 0.01%) +15k (+ 0.00%) 328,050k 328,149k
Parse Time 1.90s (± 0.73%) 1.91s (± 0.64%) +0.01s (+ 0.63%) 1.89s 1.94s
Bind Time 0.88s (± 0.51%) 0.88s (± 0.93%) +0.00s (+ 0.11%) 0.87s 0.91s
Check Time 5.30s (± 0.76%) 5.32s (± 0.67%) +0.02s (+ 0.32%) 5.24s 5.43s
Emit Time 6.22s (± 0.72%) 6.18s (± 0.70%) -0.04s (- 0.71%) 6.11s 6.31s
Total Time 14.30s (± 0.51%) 14.29s (± 0.54%) -0.01s (- 0.09%) 14.18s 14.55s
Compiler-Unions - node (v14.15.1, x64)
Memory used 191,742k (± 0.55%) 192,190k (± 0.49%) +448k (+ 0.23%) 189,614k 192,907k
Parse Time 0.81s (± 0.92%) 0.81s (± 0.45%) -0.00s (- 0.12%) 0.80s 0.81s
Bind Time 0.56s (± 0.85%) 0.56s (± 0.99%) +0.01s (+ 0.90%) 0.55s 0.58s
Check Time 7.55s (± 0.61%) 7.55s (± 0.52%) -0.00s (- 0.03%) 7.49s 7.68s
Emit Time 2.48s (± 1.01%) 2.46s (± 0.82%) -0.02s (- 0.73%) 2.41s 2.49s
Total Time 11.39s (± 0.32%) 11.37s (± 0.48%) -0.02s (- 0.16%) 11.27s 11.54s
Monaco - node (v14.15.1, x64)
Memory used 322,540k (± 0.00%) 322,541k (± 0.00%) +1k (+ 0.00%) 322,511k 322,563k
Parse Time 1.48s (± 0.68%) 1.49s (± 0.67%) +0.00s (+ 0.20%) 1.47s 1.51s
Bind Time 0.76s (± 0.66%) 0.76s (± 0.99%) +0.00s (+ 0.26%) 0.75s 0.78s
Check Time 5.23s (± 0.43%) 5.23s (± 0.51%) +0.01s (+ 0.13%) 5.19s 5.29s
Emit Time 3.21s (± 0.69%) 3.24s (± 1.03%) +0.02s (+ 0.72%) 3.18s 3.31s
Total Time 10.68s (± 0.34%) 10.72s (± 0.42%) +0.03s (+ 0.32%) 10.63s 10.82s
TFS - node (v14.15.1, x64)
Memory used 287,700k (± 0.01%) 287,713k (± 0.01%) +13k (+ 0.00%) 287,663k 287,761k
Parse Time 1.26s (± 2.81%) 1.26s (± 2.13%) +0.00s (+ 0.24%) 1.21s 1.33s
Bind Time 0.73s (± 1.27%) 0.73s (± 1.11%) +0.00s (+ 0.27%) 0.72s 0.75s
Check Time 4.87s (± 0.35%) 4.91s (± 0.46%) +0.04s (+ 0.76%) 4.84s 4.97s
Emit Time 3.47s (± 0.77%) 3.49s (± 0.84%) +0.02s (+ 0.72%) 3.43s 3.57s
Total Time 10.32s (± 0.42%) 10.38s (± 0.43%) +0.07s (+ 0.65%) 10.27s 10.46s
material-ui - node (v14.15.1, x64)
Memory used 447,030k (± 0.01%) 446,950k (± 0.00%) -80k (- 0.02%) 446,922k 446,990k
Parse Time 1.76s (± 0.48%) 1.77s (± 0.33%) +0.01s (+ 0.63%) 1.76s 1.78s
Bind Time 0.69s (± 0.58%) 0.69s (± 0.49%) +0.00s (+ 0.29%) 0.69s 0.70s
Check Time 13.02s (± 0.60%) 13.13s (± 0.71%) +0.12s (+ 0.88%) 12.87s 13.26s
Emit Time 0.00s (± 0.00%) 0.00s (± 0.00%) 0.00s ( NaN%) 0.00s 0.00s
Total Time 15.47s (± 0.50%) 15.59s (± 0.59%) +0.13s (+ 0.83%) 15.33s 15.72s
System
Machine Namets-ci-ubuntu
Platformlinux 4.4.0-210-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 45711 10
Baseline main 10

Developer Information:

Download Benchmark
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@ahejlsberg

Anders Hejlsberg (ahejlsberg) commented Sep 8, 2021

Copy link
Copy Markdown
Member Author

Changed the tail recursion logic to bypass caching since it is effectively just computing temporary results. There's still a slight slowdown in material-ui (<1%), but generally I think not caching in the tail recursion loop is the best approach.
andrewbranch reacted with thumbs up emoji Seauning reacted with laugh emoji
All reactions
  • 👍 1 reaction
  • 😄 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@ahejlsberg
Anders Hejlsberg (ahejlsberg) merged commit b9eeb74 into main Sep 8, 2021
@ahejlsberg
Anders Hejlsberg (ahejlsberg) deleted the tailRecursiveConditionals branch September 8, 2021 22:42
@renovate renovate Bot mentioned this pull request Sep 23, 2021
fix(deps): update dependency ts-pattern to v3.3.3 natelindev/vlepo#118
Merged
1 task
@mgreenw

Max Greenwald (mgreenw) commented Sep 24, 2021 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown

Anders Hejlsberg (@ahejlsberg) Thanks for this work! Using 4.4.3, I just hit the instantiationDepth === 50 limit (literally just 50, nothing above that) on a project I am working on.

Because it is possible / even likely to hit this depth limit of 50 with tuple types and template literal types in 4.4, I'm wondering if it would be possible to backport the instantiationDepth === 100 limit to a new patch release of 4.4 without including this tail recursive evaluation strategy This would mitigate the issue until 4.5 is released with this new (awesome) work. Let me know if you think this would be possible / a good idea. Thanks!
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@nandorojo Fernando Rojo (nandorojo) mentioned this pull request Sep 27, 2021
Custom theme-based TypeScript Intellisense nandorojo/dripsy#6
Closed
@renovate renovate Bot mentioned this pull request Oct 1, 2021
Update dependency ts-pattern to v3.3.3 taneba/fullstack-graphql-app#98
Merged
1 task
@somebody1234 somebody1234 mentioned this pull request Oct 3, 2021
2257 - MinusOne type-challenges/type-challenges#2563
Open
This was referenced Oct 3, 2021
flag to customize type instantiation depth limit #46180
Closed
rewrite recursive conditional types to be tail-recursive millsp/ts-toolbelt#255
Open
rewrite recursive conditional types to be tail-recursive millsp/ts-toolbelt#256
Draft
@getTobiasNielsen Tobias Nielsen (getTobiasNielsen) mentioned this pull request Oct 6, 2021
[Bug]: Regression: TS2589: Type instantiation is excessively deep and possibly infinite react-hook-form/react-hook-form#6679
Closed
1 task done
@timkendall Tim Kendall (timkendall) mentioned this pull request Nov 5, 2021
TypeScript 4.5 Recursive type tail recursion timkendall/tql#86
Closed
@samchon Jeongho Nam (samchon) mentioned this pull request Nov 25, 2021
Critical change from the [email protected] samchon/safe-typeorm#46
Closed
@renovate renovate Bot mentioned this pull request Dec 11, 2021
chore(deps): update dependency ts-pattern to v3 strong-roots-capital/od#87
Merged
1 task
@crazyones110 crazyones110 mentioned this pull request Dec 21, 2021
Feature request: Ability to parse a stringified number on type-level #47141
Closed
5 tasks done
@renovate renovate Bot mentioned this pull request Apr 2, 2022
chore(deps): update dependency ts-pattern to v4 strong-roots-capital/percentage-change#42
Merged
1 task
@swimmie0 Swimmie (swimmie0) mentioned this pull request May 17, 2022
531 - String to Union swimmie0/type-challenges#1
Open
@zhaoyao91 Yao Zhao (zhaoyao91) mentioned this pull request Nov 18, 2022
2257 - MinusOne with 2 versions and explanatations type-challenges/type-challenges#19437
Open
@MajorLift Jongsun (MajorLift) mentioned this pull request Jan 6, 2023
test: 00651-hard-length-of-string-2 input of length 999 type-challenges/type-challenges#21603
Merged
@Dragon-Hatcher Dragon-Hatcher mentioned this pull request Jun 24, 2023
Increase type instantiation depth limit #45025
Merged
@deathemperor deathemperor (deathemperor) mentioned this pull request Jan 30, 2024
Increase tail-recursive conditional types from 50 to 1000 for variables 0no-co/gql.tada#46
Closed
@ENvironmentSet Jaewon Seo (ENvironmentSet) mentioned this pull request Feb 10, 2024
Tail recursion optimization limit 999 may be manipulated #49459
Open
@buqiyuan bqy_fe (buqiyuan) mentioned this pull request Feb 14, 2024
Type instantiation is excessively deep and possibly infinite nestjs/nest#13210
Closed
2 of 15 tasks
@microsoft 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

@weswigham Wesley Wigham (weswigham) weswigham approved these changes
@andrewbranch Andrew Branch (andrewbranch) Awaiting requested review from andrewbranch
@DanielRosenwasser Daniel Rosenwasser (DanielRosenwasser) Awaiting requested review from DanielRosenwasser

Uh oh!

There was an error while loading. Please reload this page.

Assignees

@ahejlsberg Anders Hejlsberg (ahejlsberg)

Labels

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

Projects

None yet

Milestone

TypeScript 4.5.0

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

5 participants

@ahejlsberg @typescript-bot @DanielRosenwasser @mgreenw @weswigham
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.