Poor conditional type performance with large string literal union types

[phulin]

Bug Report

The TypeScript compiler has poor performance when compiling conditional types involving large string literal unions. In particular, performance appears to be multilinear in the size of the unions involved. The example below takes 19 seconds to compile on my (recent) laptop, with two 10,000 string literal union types. A 5,000 x 5,000 example takes 4.5 seconds, a 10,000 x 5,000 example 9 seconds, and a 15,000 x 10,000 example 27 seconds, suggesting the asymptotic performance I indicated.

I discovered this issue while attempting to implement strong typing on requests to a key-value store in a project. The values in the store have different types that are static, but the store is large enough that using types like the example below leads to what is, for me, unacceptably slow compile times (which are then reflected in slow VS Code Intellisense updates).

I imagine this may be a fundamental algorithmic limitation, but I don't know enough about TS's inner workings to know.

This may be related to #29350.

Thanks to all TS contributors - hope this report helps.

🔎 Search Terms

union conditional type poor performance slow multilinear quadratic

🕗 Version & Regression Information

Observed on multiple versions, including today's next. I have not seen a version with good performance in this case.

⏯ Playground Link

Unfortunately, playground screeches to a halt with the full 10,000 x 10,000 test case. Here is a 1,000 x 1,000 example instead:

Playground link with relevant code

Test case repository

💻 Code

export type NumericProperty = "n1" | "n2" | /* snip */ "n10000";
export type StringProperty = "s1" | "s2" | /* snip */ "s10000";
export type KnownProperty =
  | NumericProperty
  | StringProperty

type PropertyValue<
  Property,
> = Property extends NumericProperty
  ? number
  : Property extends StringProperty
  ? string : null;

export function useProperty<Property extends KnownProperty>(
  default_: PropertyValue<Property>,
): PropertyValue<Property> {
  return default_;
}

[tinganho]

I work on a project where we use a lot of translation strings. We have provided a union type of all translation keys. Some times we have variables that just works on a sub category of the union strings and we use Extract<T, U> to extract them. We have noticed that the project just explodes in compile time. From 36s to over 4 minutes. TS Server is also very sluggish.

We have used --generateTrace flag to zero in on the expressions that takes long time. And we concluded it to be Extract<T, U> that is the culprit.

I created a repo of the perf bug we experienced. If you want to evaluate.
https://github.com/tinganho/extract-bug

We found the following quote in emotion-js/emotion#2257
From @amcasey:

Why don't we topologically sort them? I wasn't there but I would guess it was either too hard in the general case or didn't seem like it would make a difference (this is a pathological case).

Maybe our case is very specific. But, I think it would make sense to sort them based on a certain threshold? At least, I think it's quite general that the more union constituents you have the more lookups people tends to do.

[jakebailey]

With #53192 merged, I think that this one is effectively "done".