Massive slowdown in compiling complicated union types

[Arnavion]

This is the same code as what originally prompted #2997

While it isn't crashing because of infinite loops any more, it has become very slow with 1.7. If I pause it in the debugger I see the following stack repeating many times.

inferFromTypes [tsc.js] Line 15334  JavaScript
inferFromTypes [tsc.js] Line 15314  JavaScript
inferFromTypes [tsc.js] Line 15301  JavaScript
inferFromProperties [tsc.js] Line 15350 JavaScript
inferFromTypes [tsc.js] Line 15334  JavaScript
inferFromTypes [tsc.js] Line 15314  JavaScript
inferFromTypes [tsc.js] Line 15301  JavaScript
inferFromIndexTypes [tsc.js] Line 15380 JavaScript
inferFromTypes [tsc.js] Line 15337  JavaScript
inferFromProperties [tsc.js] Line 15350 JavaScript

Reduced test case:

class Module {
    public members: { [name: string]: FFunction | Property };
}

class Namespace {
    public members: { [name: string]: Class | Enum };
}

class Class {
    public parent: Module | Namespace;

    public members: { [name: string]: Property | FFunction };
}

class Interface {
    public members: { [name: string]: Property | FFunction };
}

class FFunction {
    public parent: Module | Namespace | Class | Interface; // (1)
}

class Property {
    public parent: Module | Namespace | Class | Interface; // (2)
}

class Enum {
    public parent: Module | Namespace;

    public members: EnumMember[];
}

class EnumMember {
    public parent: Enum;
}

var members: (Property | FFunction)[];
members.map(member => "");

Compile with tsc foo.ts on node 4.2.2 x64 on Windows 7.

This takes ~18s on my machine. If I remove Module from the union type at (1), it drops to ~12s. Removing Module at (2) drops it to ~6s. And so on.

The original code is at https://github.com/Arnavion/libjass/blob/82f3706/build/typescript/ast.ts which has a much more complicated forest of types. It's been compiling for 5 minutes now, whereas it took ~2s with 1.6

[vladima]

@Arnavion can you give a try to typescript@next. Seems that this issue is already fixed in master. I can confirm that it takes 17.50 s on my machine to compile your sample using release-1.7, however on master it takes only 0.71 s

[Arnavion]

Yes, looks like it. The original code also takes ~2s with next, same as 1.6.

[Arnavion]

Can the fix be backported to 1.7 or do I skip it and wait for 1.8?

[mhegazy]

depends on the fix. @vladima do you know what is going on?

[vladima]

yes: #5738. If source and target types are unions or intersections then removing matching constituents from source and target sides significantly reduces amount of types that participate in type inference. I think it should be safe to backport this fix to 1.7

[Arnavion]

Yes, cherry-picking that PR onto 1.7 fixes the issue (and introduces #5861 but that's a minor annoyance in comparison).

[mhegazy]

@Arnavion is there a chance you can move to typescript@next directly?

[Arnavion]

If you're asking because you don't want to backport it, that's fine. I have no problem staying with 1.6 until 1.8 is released. :)

[mhegazy]

I am asking to figure out the logistics, porting it and publishing an npm is easy, but we will need to publish a VS 2012, VS 2015, and sublime text plugin updates and that all adds up.

[mhegazy]

Let's port #5738 and #5895 to release-1.7 branch.

[ahejlsberg]

I'm trying to understand why this got slower from 1.6 to 1.7? Vlad, did you look into that? I understand why the new union/intersection reduction in 1.8 makes it faster, but I'd like to know why it got slower in the first place.

[ahejlsberg]

Ok, I now understand why it got slower. When inferring types, if the source and target are both non-generic object types we don't descend into the types because it we know it won't produce inferences. However, in 1.7 all classes are generic because of the implied this type argument, so we end up doing a lot more work. I'm going to give some thought to a fix. The union/intersection reduction isn't really the answer, it just so happens to help in this example.

[vladima]

yes, this got slower in the 9438a4b

[ahejlsberg]

Ok, I have a fix. I will putting up a PR shortly.

[ahejlsberg]

I would recommend not back-porting the union/intersection type reduction, but instead back-porting the #5920 fix I just put up.

[mhegazy]

@Arnavion can you do us a big favor and give branch release-1.7 a quick test?

[Arnavion]

Everything seems fine. Thanks!

[mhegazy]

thanks @Arnavion!