Repository navigation
Poor conditional type performance with large string literal union types #47481
Description
Activity
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
--generateTraceflag to zero in on the expressions that takes long time. And we concluded it to beExtract<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-bugWe found the following quote in emotion-js/emotion#2257
From Andrew Casey (@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.
With #53192 merged, I think that this one is effectively "done".
Reacted by Ahmad Izzuddin
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