Performance regression from #48044

[epmatsw]

Bug Report

It seems like a fairly significant performance regression was introduced in this #48044, which was shipped in TS 4.7. In TS 4.6, it takes ~30 seconds to run yarn tsc in our repo, and the reported strict subtype cache size is 24_011. In TS 4.7, it takes 75+ seconds to run yarn tsc (~2.5x longer than previous), and the reported strict subtype cache size is 122_778 (~5x larger than previous).

I verified that it was that specific PR that regressed the performance by taking a locally-installed 4.6.4 and applying the changes from that PR directly.

Another symptom is that several types (mostly spreads of objects into others) are now reporting as "Expression produces a union type that is too complex to represent."

🔎 Search Terms

Expression produces a union type that is too complex to represent, strict subtype cache size

🕗 Version & Regression Information

• Regressed in fix(48034): Get a literal string of type intersection in a template literal type #48044
• This changed between versions 4.6.4 and 4.7.3

Version	Time	Strict Subtype Cache Size
4.6.4	33s	24011
4.7.3	75s	122778
4.9.4	77s	122869
5.0.0-dev.20230120	78s	122869

💻 Code

I haven't been able to narrow down a minimal reproduction of this issue, but if someone points me in the right direction I'm happy to work on it.

🙁 Actual behavior

Running yarn tsc --noEmit --extendedDiagnostics takes ~75 seconds in our repo, with a Strict subtype cache size of 122778.

🙂 Expected behavior

Running yarn tsc --noEmit --extendedDiagnostics takes ~30 seconds in our repo, with a Strict subtype cache size of 24011.

[DanielRosenwasser]

Would you be able to generate a trace and use our analyze-trace tool?

https://github.com/microsoft/typescript-analyze-trace

It should highlight specific hot spots that might occur as of TS 4.7. The usage instructions are a little better now. Let me know if you need any more info using it.

[jakebailey]

@epmatsw In lieu of a small repro, is your code public such that I can test it out?

The above tracing mechanism should get you some info about which types are problematic, but to work on this I do need something, so even the full thing would be helpful.

[epmatsw]

Not public, unfortunately. Sorry about the delay on the trace, I’ll try to get something going tomorrow.

[epmatsw]

Dang, thought I had a reproduction but apparently not. Probably not gonna get something until Monday now :(

[epmatsw]

Okay, so I'm not sure this is minimal, but I think it's on the right track:

type R = `${number}a` & {
    _thing: true;
};

type _S = "1" | "2" | "3" | "4" | "5";
type S = `${_S}${_S}`;

// Produces "Expression produces a union type that is too complex to represent"
// type S = `${_S}${_S}${_S}`;


type T = R | S;
type X = `${T} ${T}`;

export type Props = Partial<{
    x: X;
}>;

const a1: Props = {};
const a2: Props = {};

const b = { ...a1, ...a2 };

export { b };

In 4.6.4, that has a Strict subtype cache size of 0. In 4.7.4, that has a Strict subtype cache size of 34476.

[epmatsw]

Hmmm. I guess because X boils down to string in 4.6.4. So I'm not sure how useful that even actually is other than "actually checking this gigantic type rather than not checking it is expensive" :/

[jakebailey]

That might be enough, actually. By modifiying it a bit to try and make it worse (but not enough to make it go to string), I can get the test to take a good 5-6 seconds on my machine, wheras in v4.6, it takes under a second.

type R = `${number}a` & {
    _thing: true;
};

type _S = "1" | "2" | "3" | "4" | "5" | "6";

type S = `${_S}${_S}${_S}`;


type T = R | S;
type X = `${T} ${T}`;

export type Props = Partial<{
    x: X;
}>;

const a1: Props = {};
const a2: Props = {};

const b = { ...a1, ...a2 };

export { b };

[jakebailey]

After staring at this for a while, I'm at a loss for a way to speed this up; we're now actually traversing the intersections whereas before, we weren't. This example in particular turns into a combinatorial explosion after #48044, which I didn't really see coming at the time.

I'm not sure what the path forward is at the moment, besides reverting that PR (or doing nothing), but I'll keep trying.

[jakebailey]

@epmatsw Would you mind testing the package on my PR for this issue here? #52836 (comment)

I believe it fixes the performance problem (in that it avoids massive intersections), but, it does make these sorts of constructs stricter (more correct in some situations) and the above sample in particular will still give an error that complains about it being too big.

EDIT: updated the link to the latest version

[epmatsw]

Unfortunately not a huge improvement:

TS 4.6.4

Strict subtype cache size:    24040
Total time:                  34.40s

TS Version 5.0.0-insiders.20230218 (https://typescript.visualstudio.com/cf7ac146-d525-443c-b23c-0d58337efebc/_apis/build/builds/146938/artifacts?artifactName=tgz&fileId=E6600AFB90EEF24611686B292C01E0D427A0C8AA2B90E3E4B7E85880B3CF614102&fileName=/typescript-5.0.0-insiders.20230218.tgz):

Strict subtype cache size:   122673
Total time:                  65.03s

[jakebailey]

Just to confirm, it's ~13s faster than a previous 5.0 build, correct?

[jakebailey]

But, good to know that it's not a complete fix; I'll need to retry with the test case and check the subtype cache metric, as you had said it was previously zero, so that's next to look at.

[epmatsw]

Unfortunately I think that's my bad (I had a fairly significant hardware upgrade since the first set of measurements).

Testing on the 20230120 build from before, I get ~64s now, so no significant difference from the 20230218 build.

[jakebailey]

Hm, that's unfortunate; it means that the test case I've been using is not representative of your actual code.

Have you been able to use the analyze-trace tool to try and pinpoint the exact expression that is problematic?

Also, we are able sign NDAs (or reuse existing ones) in order to look at private code, if that's palatable. @DanielRosenwasser knows that process better than me, I think.

[epmatsw]

Sorry for the radio silence for a bit, sick kid from daycare unfortunately. I'm hoping I'll get some time to tinker on this more this week.

[epmatsw]

Well, the only thing I could really glean from the trace is that it's only places where we spread 2 object of the type together. So in the example from #52345 (comment), where Props is the expensive type, the flagged code looks like:

const Component2 = ({ p }: { p?: Props }) => {};

const Component = ({ p }: { p?: Props }) => {
	const p2: Props = {};
	return <Component2 p={{ ...p, ...p2 }} />;
}

Always 2+ spreads of the Props type.

Also confirmed that 5.0.1rc, 5.1.0-dev.20230303, and the packed build from the PR all have roughly identical performance :(

[jakebailey]

I've merged #52836, which you said unfortunately didn't help; the PR was updated a little bit since you tested so I'll be interested whether or not tonight's nightly build will improve things even a little.

[jakebailey]

@epmatsw Another one for you to try, when you get a chance: #53406

The package should show up in a few minutes.

[jakebailey]

The rest of the time after #53406 is spent checking subtypes in the union created by property spreading:

I think I have another optimization here which should fix this.

[epmatsw]

Okay, I finally got back to this (so sorry for the delay!).

I got a really minimal reproduction of the slowdown: https://github.com/epmatsw/tsdemo

There's two workspaces, one with ts4.6 and one with ts5.2. There's two tsconfigs, one that includes a "slow" file and one that includes a "fast" file. The only difference between the slow and fast files is that one has an extra as any:

That as any doesn't make any difference in TS4.6, but in TS5.2 it results in a ~13x speedup (bringing the number back to TS4.6 levels):

[epmatsw]

Fwiw, I also found a single any that when added to our codebase reduced our tsc time from ~70s to ~50s. Presumably there's another one or two instances of this slowdown that accounts for the remaining 20s of regression that I may eventually be able to track down, but it (potentially naively) seems like there may be some optimization that could be made here.

[jakebailey]

I just got a chance to look at this; this case doesn't look anything like your previous example; it doesn't involve intersections / template literals and can't be caused by the same thing.

The code is fast in both 4.6 and 4.7 (the original issue started happening in 4.7), but gets 10x slower in 4.8, then 2x slower still in 5.0.

It might be worth filing this case separately as it'll involve different stuff. I'll have to bisect it, but it's definitely not the original issue here, which was more "we actually start handling intersections within template expressions instead of converting them to string straight away", compared to this example, which is more like a combinatoric explosion from attempting to narrow a union of 10,000 strings against itself.

[jakebailey]

#55926 technically resolves this case; a PR build will be available soon. Though I'm not totally sure how I feel about this particular condition just because it only works when you attempt to narrow something to itself, which feels rare and is only causing a perf hole here because you're narrowing a huge union to itself. If you ever change one of them, this optimization fails again.

[jakebailey]

So barring the stuff in #55948, is there anything left here that isn't fast? I've gone through the code bits in this thread and they have all improved, and I can't really recall what's left here. It'd be nice of course to actually be able to test the real world example... I am of course happy to test it and if privacy is a concern I'm pretty sure we do NDAs.

[epmatsw]

I think it's safe to call this one fixed! The remaining regression since 4.6 is fully accounted for by the issue we're tracking in the other thread.