perf: exponential slowdown due to type narrowing with enums / type unions

[JoostK]

TypeScript Version: 3.8.0-dev.20191119

Also reproduceable in earlier versions. A quick scan through older versions shows TS 2.0 has a check time of 0.2s, which regressed to 1.9s in TS 2.1.

Search Terms: performance, union types, enum, flow analysis, type narrowing

Code

export enum Choice {
  One,
  Two,
}

const choice: Choice = Choice.One;
const choiceOne = Choice.One;

if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}
if (choice === choiceOne) {}

Expected behavior:
Type checking of this single file completes in the order of milliseconds.

A real world example of this issue has been reported in the Angular repo for code generated by the template type checker: angular/angular#33532. Angular has a code generator that emits TypeScript code to typecheck Angular templates.

Actual behavior:

Each additional if-statement is causing the type checking phase to roughly double in time. The above sample takes ~2.9s in the "Check" phase, as reported in the diagnostics report:

Files:            2
Lines:         4381
Nodes:        13211
Identifiers:   5483
Symbols:       3528
Types:         1225
Memory used: 42102K
I/O read:     0.00s
I/O write:    0.00s
Parse time:   0.12s
Bind time:    0.04s
Check time:   2.87s
Emit time:    0.00s
Total time:   3.03s

Adding one additional if statement increases the Check time to ~6.5s:

Files:            2
Lines:         4382
Nodes:        13217
Identifiers:   5485
Symbols:       3528
Types:         1225
Memory used: 49768K
I/O read:     0.00s
I/O write:    0.00s
Parse time:   0.13s
Bind time:    0.05s
Check time:   6.43s
Emit time:    0.00s
Total time:   6.61s

These options do resolve the exponential slowdown:

• Changing the type of either choice or choiceOne to any
• inlining choiceOne into the if-statements

These options do not resolve the exponential slowdown:

• Reducing the enum to a single option
• Changing the type of choice into Choice.One
• Replacing the enum with a type union

Note that all these options do reduce the time, however adding additional if-statements still shows exponential slowdown.

Playground Link:

Terminal reproduction to get insight in timings:

npx typescript@3.8.0-dev.20191119 sample.ts --diagnostics --noEmit --lib es5 --strict false --typeRoots []

Source code for sample.ts is found above, under Code.

Related Issues: Not really