Performance depends on declaration order

[amcasey]

These lines compile successfully in any order (assuming the import stays first, of course). Unexpectedly, the compilation time varies substantially based on the order.

import * as CSS from 'csstype';
declare const width: string | number; declare const y: CSSObject; const x: CSSObject = { width, ...y };
type CSSProperties = CSS.PropertiesFallback<number | string>;
type CSSPropertiesWithMultiValues = { [K in keyof CSSProperties]: CSSProperties[K] | Array<Exclude<CSSProperties[K], undefined>> };
interface ArrayCSSInterpolation extends Array<CSSInterpolation> {}
type InterpolationPrimitive = null | undefined | boolean | number | string | CSSObject;
type CSSInterpolation = InterpolationPrimitive | ArrayCSSInterpolation;
interface CSSOthersObject { [propertiesName: string]: CSSInterpolation }
interface CSSObject extends CSSPropertiesWithMultiValues, CSSOthersObject {}

On my box, compilation time varies between 2 and 3 seconds, depending on the order - quite a range. It appears to depend primarily on whether const x: CSSObject = { width, ...y }; or interface CSSObject extends CSSPropertiesWithMultiValues, CSSOthersObject {} comes first (slower with the const first).

This difference dates back to at least TS 3.6.

Discovered while investigating #43422 and reduced from the same codebase (i.e. emotion).

[amcasey]

For the sake of explicitness:

Fast

import * as CSS from 'csstype';

type CSSProperties = CSS.PropertiesFallback<number | string>;
type CSSPropertiesWithMultiValues = { [K in keyof CSSProperties]: CSSProperties[K] | Array<Exclude<CSSProperties[K], undefined>> };
interface ArrayCSSInterpolation extends Array<CSSInterpolation> {}
type InterpolationPrimitive = null | undefined | boolean | number | string | CSSObject;
type CSSInterpolation = InterpolationPrimitive | ArrayCSSInterpolation;
interface CSSOthersObject { [propertiesName: string]: CSSInterpolation }

declare const width: string | number; 
declare const y: CSSObject; 

interface CSSObject extends CSSPropertiesWithMultiValues, CSSOthersObject {}
const x: CSSObject = { width, ...y };

Slow

import * as CSS from 'csstype';

type CSSProperties = CSS.PropertiesFallback<number | string>;
type CSSPropertiesWithMultiValues = { [K in keyof CSSProperties]: CSSProperties[K] | Array<Exclude<CSSProperties[K], undefined>> };
interface ArrayCSSInterpolation extends Array<CSSInterpolation> {}
type InterpolationPrimitive = null | undefined | boolean | number | string | CSSObject;
type CSSInterpolation = InterpolationPrimitive | ArrayCSSInterpolation;
interface CSSOthersObject { [propertiesName: string]: CSSInterpolation }

declare const width: string | number; 
declare const y: CSSObject; 

const x: CSSObject = { width, ...y };
interface CSSObject extends CSSPropertiesWithMultiValues, CSSOthersObject {}

[amcasey]

Breaking it down even further, it's still fast if you declare const temp = { width, ...y } as const; before CSSObject and assign it afterward. So it's specific to comparing that (large) object type to CSSObject before CSSObject is declared.

[amcasey]

An interesting consequence of this order-dependence is that, if you move the types into a .d.ts file, building with --skipLibCheck is slower than building with just --skipDefaultLibCheck because it is effectively the same as checking the const declaration before the interface declaration (as in the slow case above).

[amcasey]

If you declare CSSObject as an intersection instead, it's slow in both orders. This suggests that there's an interface-specific optimization that may or may not happen, depending on the order.

[amcasey]

@RyanCavanaugh suggested allocating type IDs in descending order to see if this was a fluke of type allocation order. In local testing, the fast order remains fast and the slow order remains slow, even with the type IDs reversed.

[amcasey]

Mostly for my own amusement, I made a graph representation of the should-precede relation. A -- N% --> B should be read as "A should precede B, otherwise compilation time will increase by N%". Note that the effect of reversing multiple edges is not cumulative.

Methodology: Time compilation of each permutation of the lines. Compare the average time of the permutations with A preceding B to the average time of the permutations with B preceding A. One run per permutation seemed sufficient, since we're taking averages of 8!/2 =~ 20K runs.

Disclaimer: This is mostly for fun, so I didn't double check it very carefully. However, the arrow from the top node to the bottom node matches the description of this bug.

[ahejlsberg]

I figured out what's happening here. As we discussed, it is caused by the way we cache temporary results on a "maybe related" list during evaluation of nested relationships (those "maybe related" results aren't recorded in the main cache until we reach depth zero and know that our assumptions were correct). The "maybe related" list is scanned linearly and in this particular example it grows very large--we accumulate 17,500 temporary results during evaluation of 80,000 nested relationships and eventually the linear scan time completely dominates.

When the declarations in the repro example are reversed, a number of the interesting relationships are evaluated as part of checking the interface declaration and therefore cached in the main relationship cache. Thus, when it comes time to evaluate a relationship involving the interface, we already have most of the results cached and they never end up on the "maybe related" list.

I've verified we can be fix the issue by adding a map of "maybe related" results, but I'm going to think on it a little bit before putting up a PR.

[ahejlsberg]

Was fixed by #43624. Closing.