Unexpected slowness initializing large array with discriminated union constituents

[RyanCavanaugh]

Bug Report

🔎 Search Terms

union array initialization performance

🕗 Version & Regression Information

• This is the behavior in every version I tried since 3.3. No meaningful perf changes were observed depending on TS version

⏯ Playground Link

Too large; here's a spreadsheet

https://docs.google.com/spreadsheets/d/1mk6oEwD8YrycBeSNDX4gaM9rxVULgNB_ljAGrQkned8/edit?usp=sharing

💻 Code

Instead of 3 constituents, the actual repro has 500 (this is approximately the number found in the real repro) for each example.

Setup:

type Action =
 | Action1
 | Action2
 | Action3;

type Action1 = { type: 1, payload: number };
type Action2 = { type: 2, payload: number };
type Action3 = { type: 3, payload: number };

🙁 Actual behavior

Checking with --skipLibCheck --strict --extendedDiagnostics, we see some undesirable perf variances here.

The "const" version checks in 0.6s:

const p1: Action = { type: 1, payload: 42 };
const p2: Action = { type: 2, payload: 42 };
const p3: Action = { type: 3, payload: 42 };

The "basic array" version checks in 1.0s:

const test: Action[] = [
    { type: 1, payload: 42 },
    { type: 2, payload: 42 },
    { type: 3, payload: 42 }
];

The "poisoned array" version (which is closest to the customer repro) checks in 1.3s:

declare const a: Action;
const test: Action[] = [
    a,
    { type: 1, payload: 42 },
    { type: 2, payload: 42 },
    { type: 3, payload: 42 }
];

The "array with extra target" version checks in 1.6s:

const test: Array<Action | string> = [
    { type: 1, payload: 42 },
    { type: 2, payload: 42 },
    { type: 3, payload: 42 }
];

The "unannotated array" version checks in 0.07s (obviously not a target, but shows that these perf numbers aren't cause by "other work):

const test = [
    { type: 1, payload: 42 },
    { type: 2, payload: 42 },
    { type: 3, payload: 42 }
];

🙂 Expected behavior

All of the array cases should be checked approximately as fast as the const version, not >2x slower.

Other notes:

• Using a string discriminant in place of number doesn't change anything
• The original repro is even larger
• Timing numbers are on my i7-10700K (i.e. a very fast computer by 2021 standards)

[ahejlsberg]

Several costly operations are at play in various forms in the examples.

const p1: Action = { type: 1, payload: 42 };
const p2: Action = { type: 2, payload: 42 };
const p3: Action = { type: 3, payload: 42 };
...

The first expensive operation here is assignability checking between each object literal type and the Action union. Because the object literals have unique type identities, we end up linearly searching for a match in the union--which gets expensive when the matching candidate is towards the end.

Second issue is contextual type discrimination. Every time we ask for a contextual type on the object literal side, we end up filtering the Action union down to a single applicable constituent using the discriminateTypeByDiscriminableItems function. That is an expensive linear operation and we perform no caching of the results.

const test: Action[] = [
    { type: 1, payload: 42 },
    { type: 2, payload: 42 },
    { type: 3, payload: 42 },
    ...
];

Here we add a third expensive operation, subtype reduction. Every object literal type ends up being structurally related to every other object literal type--without actually reducing anything.

declare const a: Action;
const test: Action[] = [
    a,
    { type: 1, payload: 42 },
    { type: 2, payload: 42 },
    { type: 3, payload: 42 },
    ...
];

Adding an extra target causes the source and target union types to have different numbers of constituents, so we defeat an optimization we have where we first relate constituents at the same index in both unions when they're the same size.

const test = [
    { type: 1, payload: 42 },
    { type: 2, payload: 42 },
    { type: 3, payload: 42 },
    ...
];

The unannotated example is the happy path where none of the expensive operations occur: There's no contextual type for the object literals, so no expensive contextual type discrimination; all elements end up having the same type, { type: number, payload: number } because there is no contextual type to cause literal types to be used; and because all elements have the same type, no subtype reduction occurs.

The good news with all of this is there are numerous places we could optimize:

• Unless we're performing type inference, there's no point in doing subtype reduction when a contextual type is present--the contextual type is an indication that the target has a known type to which we'll be relating, and relations don't really care if unions have been subtype reduced. This common situation is very easy to detect, so quick win here.
• In relation checking, when the target type is a large union with constituents that have discriminants, we can build a map of constituents based on their discriminants and do a lookup to find a best first candidate to check. There's some complexity involved in "mixed" unions with ambiguous or missing discriminants, but it should be workable.
• The expensive contextual type discrimination can hopefully use the same map as relation checking. Again, mixed unions add complexity, but luckily the existing linear logic only kicks in when it can identify a single unambiguous candidate in the contextual type--which harmonizes well with a lookup.

I'll start working these ideas.