Exponential increase in compile time and memory usage

[squidfunk]

This bug report is a follow-up to this tweet where I write about OOM crashes in 3.9.1-rc. @DanielRosenwasser asked me to report an issue, but I find it really hard to narrow it down.

I have a project with ~2k lines of code. It uses another internal package with ~18k lines of code. The problem is that the compiler doesn't terminate anymore. I then tried to compile a subset of the project (which is a recursive decent parser, BTW), which runs in under 6 seconds. If I add more and more files, it will get slower and slower to a point where it will run into OOM. The interesting thing is that there's no big bump in files, lines, types, instantiations or symbols:

Files:             1588      1597      1600
Lines:            65199     80674     81049
Nodes:           278678    349628    350339
Identifiers:      90620     91032     91288
Symbols:          64556    465900    478162
Types:             3027    109800    134328
Instantiations:   31435    115295    222586
Memory used:    125785K   295562K   952063K
I/O read:         0.19s     0.13s     0.90s
I/O write:        0.02s     0.05s     0.06s
Parse time:       3.78s     3.27s     4.77s
Bind time:        0.80s     0.78s     1.07s
Check time:       0.96s     5.37s    94.43s
Emit time:        0.25s     0.74s     0.77s
Total time:       5.79s    10.15s   101.04s

Yes, there are twice as many instantiations, which I assume results from the use of rather large discriminated unions (.e.g when restructuring them), but the increase in memory is almost three times as high. The CPU profile when compiling looks like this:

My current guess is that the exponential increase is somehow related to Instantiations ⨉ Instantiations, as most of the time is spent in someTypeRelatedToType.

I tried breaking it down to a reproducible case, but as the project with which I'm experiencing this issue is not Open Source, stripping everything down takes too much time. I understand that this is not an actionable error report, but maybe there's an obvious reason why this recent change in behavior may be causing this. If not, feel free to close it

TypeScript Version: 3.9.1-rc
Search Terms: crash, out of memory, oom

Code

Could not be provided

Expected behavior:

TypeScript compiles the code

Actual behavior:

TypeScript runs out of memory

UPDATE:

I managed to get all packages to build with 3.9.1 by removing mapped discriminated union types, i.e. functions with signatures like function<T extends FooKind>(kind: T): FooLike<T>, whereas FooLike<T> uses conditionals to select a specific type from a huge union with ~1k types. Build times now are:

package-c          3.8.3     3.9.1

Files:              1626      1628
Lines:             84005     84000
Nodes:            357333    357139
Identifiers:       93411     93314
Symbols:          488307    487405
Types:            128763    124300
Instantiations:        -    167777
Memory used:    1092025K   979008K
I/O read:          0.17s     0.33s
I/O write:         0.13s     0.22s
Parse time:        3.29s     5.44s
Bind time:         1.20s     1.64s
Check time:       60.46s    92.90s
Emit time:         2.41s     2.85s
Total time:       67.37s   102.82s

package-b          3.8.3     3.9.1

Files:              1588      1590
Lines:             64154     64149
Nodes:            276974    276780
Identifiers:       89681     89584
Symbols:           64608     64983
Types:              3484      3621
Instantiations:        -      9232
Memory used:     131259K   130999K
I/O read:          0.25s     0.22s
I/O write:         0.10s     0.08s
Parse time:        4.70s     4.62s
Bind time:         0.99s     1.14s
Check time:        0.99s     1.12s
Emit time:         1.16s     1.38s
Total time:        7.83s     8.26s

package-a          3.8.3     3.9.1

Files:              1577      1579
Lines:            115025    115020
Nodes:            329307    329113
Identifiers:       88729     88632
Symbols:          154484    151390
Types:             45980     45135
Instantiations:        -     36085
Memory used:     372082K   274693K
I/O read:          0.27s     1.54s
I/O write:         3.98s     3.98s
Parse time:        6.17s     7.64s
Bind time:         1.63s     1.77s
Check time:       21.55s     4.72s
Emit time:        13.94s    15.12s
Total time:       43.29s    29.25s

[amcasey]

@squidfunk That's really interesting. When you were ramping up the amount of code included, did you have the option of adding things back in different orders or are the dependencies pretty strict? I'd be interested to know whether something's growing quadratically (or worse) and any straw could be the one to break the camel's back or whether there was something interesting in that final delta.

Another thing that might be interesting to try (though you may have already - your notes are really thorough) would be to (temporarily) use --max-old-space-size to increase the available memory and see if the whole thing compiles. From your description, it sounds like usage blows up so quickly that no amount of space would save it, but sometimes you see interesting things when then compilation runs to completion.

Also, which version of node are you running?

[squidfunk]

Thanks for your quick response! I'm running Node 13.6.0. As you suggested, I tried increasing --max-old-space-size to no avail (tried 1024 and 2048). However, I tried something different, but before I explain, maybe some more detail on my use case:

As I said, I'm building a fully-typed recursive descent parser for the CSS grammar. For example, this is the type of the AST node for the border property:

export interface BorderPropertyValue {
  type: ValueType.PROPERTY
  kind: "border"
  data: Array<LineWidthValue | LineStyleValue | ColorValue>
}

Currently, I have around 1.000 of those interfaces which I assemble into a huge union:

export type PropertyValue =
  ...
  | BorderPropertyValue
  | BorderBlockPropertyValue
  | BorderBlockColorPropertyValue
  ...

Now, as the parser is based on grammars (and the resulting automata), I'm doing this like:

 export type PropertyValueLike<
   T extends PropertyValue["kind"],
   U = PropertyValue
 > =
   U extends { kind: T }
     ? U
     : never

This allows me to write functions like:

declare function parsePropertyValue<T extends PropertyKind>(
  kind: T, data: string
): PropertyValueLike<T> | undefined

... which is super awesome, as the following call will give me the correct type:

const border = parsePropertyValue("border", "1px solid red")
// => BorderPropertyValue | undefined

What I tried now: if I generate an interface with all values of PropertyKind as members pointing to their respective values, the code compiles and check time goes down to 17s:

export interface PropertyValueMap {
  ...
  ["border"]: BorderPropertyValue
  ["border-block"]: BorderBlockPropertyValue
  ["border-block-color"]: BorderBlockColorPropertyValue
  ...
}

export interface PropertyLike<
  T extends PropertyKind
> = PropertyValueMap[T]

I don't know really how to proceed here, as I need mapped conditional types for derived types of PropertyValue, but I feel that the TypeScript compiler can't cope with this amount of complexity.

[squidfunk]

One more interesting thing – if I nest calls with those mapped types, instantiations and check time increase big a huge degree. This could be the cause of the exponential increase we're seeing:

Case 1:

export function parseX1<T extends PropertyKind>(): PropertyValueLike<T> {
  return {} as PropertyValueLike<T>
}

export function parseX2<T extends PropertyKind>(): PropertyValueLike<T> {
  return {} as PropertyValueLike<T>
}

export function parseX3<T extends PropertyKind>(): PropertyValueLike<T> {
  return {} as PropertyValueLike<T>
}

export function parseX4<T extends PropertyKind>(): PropertyValueLike<T> {
  return {} as PropertyValueLike<T>
}

Case 2:

export function parseX1<T extends PropertyKind>(): PropertyValueLike<T> {
  return parseX2()
}

export function parseX2<T extends PropertyKind>(): PropertyValueLike<T> {
  return parseX3()
}

export function parseX3<T extends PropertyKind>(): PropertyValueLike<T> {
  return parseX4()
}

export function parseX4<T extends PropertyKind>(): PropertyValueLike<T> {
  return {} as PropertyValueLike<T>
}

Result:

                  Case 1    Case 2

Files:              1629      1629
Lines:             85292     85292
Nodes:            363476    363464
Identifiers:       94611     94608
Symbols:          495374    495370
Types:            151530    154508
Instantiations:   289778    328368
Memory used:    1007317K  1117923K
I/O read:          0.15s     0.16s
I/O write:         0.15s     0.15s
Parse time:        3.74s     3.17s
Bind time:         0.90s     0.91s
Check time:       51.16s   100.72s
Emit time:         2.22s     3.02s
Total time:       58.02s   107.82s

+38.590 instantiations! Is there a way to tell the compiler not to evaluate all possible cases and keep it generic, i.e. evaluate lazily?

[squidfunk]

I'm sorry for flooding this topic, but I try to provide more insights as I gain them. I brought check times way down on certain code paths by introducing what I'd call happy paths, i.e. another level of indirection:

type Resolve<
  T extends PropertyKind,
  U = PropertyValue
> = U extends { kind: T }
  ? U
  : never

export type PropertyValueLike<
  T extends PropertyKind
> = PropertyKind extends T
  ? PropertyValue
  : Resolve<T>

Now, if the type is not specified, the union type is just returned. This brings the number of instantiations from my previous comment way down.

[squidfunk]

I continued iterating section by section and have brought check time down to 7 seconds for the complete project! However, there's still a very odd case:

Case 1:

export function parseDeclarationHack(
  data: Tokenizer | string
): Declaration | undefined {
  let declaration: Declaration | undefined
  return declaration
}

Case 2:

export function parseDeclarationHack(
  data: Tokenizer | string
): Declaration | undefined {
  let declaration: Declaration | undefined
  return typeof data === "string" 
    ? declaration
    : declaration
}

Result:

Files:             1629     1629
Lines:            84064    84064
Nodes:           357331   357327
Identifiers:      93383    93383
Symbols:         488675   488675
Types:           131501   131501
Instantiations:  218010   218010
Memory used:    337297K  685474K
I/O read:         0.19s    0.14s
I/O write:        0.13s    0.16s
Parse time:       3.92s    3.58s
Bind time:        0.97s    1.32s
Check time:       6.96s   29.04s
Emit time:        2.02s    1.99s
Total time:      13.88s   35.93s

Of course that condition is non-sensical, but I reduced it to that case and I don't understand why a simple conditional, which returns the exact same value increases check time from 7s to 30s. Also, note that the number of types and instantiations is the same.

Adding as any to any of the branches brings it down to 7s again. What the heck. So, I don't know how to move forward on this topic. It's super, super strange. If one of you wants to pair with me, I'm happy to assist via vidchat. As I said, I'm afraid I cannot share the code 😞

[squidfunk]

I managed to reproduce the exponential increase when branching using the Preact JSX typings:
https://github.com/squidfunk/typescript-issue-38339-repro

[amcasey]

Wow, that's a lot of info! I'll do my best to respond in an orderly way.

I'm interested in PropertyValueMap and PropertyLike, but I'm blanking on where they fit into your original code. What am I missing?

Edit: Figured it out - it takes the place of PropertyValueLike. Yes, doing it as a lookup should be much faster than iterating over the whole union.

In your ParseX example, my (unconfirmed) guess is that you're actually seeing more laziness than you want - if the generics didn't prevent things from being evaluated eagerly, they wouldn't explode when they eventually are. Also, I realize your example is intentionally contrived, but there's no way to infer a type argument that only appears in the return type and I suspect that's making things worse than they would be in normal practice.

Edit: My mistake - the return type is inferred from the contextual type (forgot which language I was in 😉), probably very expensively.

Edit 2: If you specify the type arguments explicitly, does the second version of ParseX get faster?

Do you ever pass a second type argument to Resolve or is it always the default? Also, I'm not sure how we could generalize that fix. The compiler could probably recognize the case where the type argument is exactly the constraint type, but the conclusion (in this case, that you can just use PropertyValue) seems to depend on outside knowledge.

Your reduced repro is really fun. 😄

[amcasey]

Just to manage expectations, my current read on the problem is that TS doesn't provide a way to efficiently express the behavior you want and changes to the expressiveness of a programming language take time. In the meantime, you may need to trade off between correctness and perf (or find clever workarounds, as you seem to have done).

We're still looking at it and there may just be a bug that we can fix, but I wanted to warn you that there might not be a satisfactory answer in the short-term.

[squidfunk]

Just to manage expectations, my current read on the problem is that TS doesn't provide a way to efficiently express the behavior you want and changes to the expressiveness of a programming language take time. In the meantime, you may need to trade-off between correctness and perf (or find clever workarounds, as you seem to have done).

I understand completely. I don't have any expectations. I was asked to open an issue for my observations, so I did. I also wanted to provide my insights as I debugged the situation. I'm using TypeScript for 2,5 years now, and it's the first time I run into these kinds of problems with the compiler.

Edit: My mistake - the return type is inferred from the contextual type (forgot which language I was in 😉), probably very expensively.

But why? If the return type of parseX2 is exactly the same as in parseX1, which calls parseX2, and the type parameters have the same constraints, why isn't it just "handed down"? Why is it instantiated?

Edit 2: If you specify the type arguments explicitly, does the second version of ParseX get faster?

Do you mean parseX2<T>() etc.? Actually, yes! It does seem to bring down the number of instantiations. Note the big drop in compilation time due to the two sections in the code which I found and where I fled to any, so 3.9.1 has big improvements overall:

                 3.8.3   3.9.1-rc
                   All     Case 1     Case 2      + <T>
                                  
Files:            1627       1629       1629       1629
Lines:           84094      84090      84090      84090
Nodes:          357108     356928     356916     356922
Identifiers:     93508      93414      93411      93414
Symbols:        488382     492630     491639     489657
Types:          145922     147336     145354     135456
Instantiations:      -     285166     282223     234763
Memory used:   616019K    348405K    340213K    332866K
I/O read:        0.15s      0.15s      0.26s      0.17s
I/O write:       0.14s      0.15s      0.14s      0.16s
Parse time:      3.28s      3.46s      5.87s      4.00s
Bind time:       0.96s      1.05s      1.26s      1.09s
Check time:     24.39s      6.82s      8.11s      6.40s
Emit time:       1.90s      1.99s      1.99s      2.01s
Total time:     30.52s     13.31s     17.24s     13.50s

Do you ever pass a second type argument to Resolve or is it always the default? Also, I'm not sure how we could generalize that fix. The compiler could probably recognize the case where the type argument is exactly the constraint type, but the conclusion (in this case, that you can just use PropertyValue) seems to depend on outside knowledge.

Actually, no! The second argument is just there to enable the actual narrowing. If I don't specify it and replace U with PropertyValue, it will always get inferred to PropertyValue. It has the nice property of defaulting to PropertyValue – the union type – when the type cannot be narrowed. However, this is now handled by the happy paths when the type parameters are not constrained.

Your reduced repro is really fun. 😄

The repro code is complete garbage, but it clearly shows the problem with branching which is very surprising to me, and might also be to others.

Just to manage expectations, my current read on the problem is that TS doesn't provide a way to efficiently express the behavior you want and changes to the expressiveness of a programming language take time. In the meantime, you may need to trade-off between correctness and perf (or find clever workarounds, as you seem to have done).

That's exactly what I do, but I wasn't aware of the necessity before. No hard feelings, though. If it's not possible to solve, it's fine. The improvements I'm seeing in 3.9.1 after fixing those weird places where I had to use any as an escape hatch within a function, (so no big deal) are very, very few. In fact, only two. However, it took quite some time to pin those situations down.

I'm using generics a lot. I love them. For my undertaking, I've developed an internal standard library with algorithms for trees, automata, graphs etc., and they're all generic. This is also why I'm seeing this problem because I need to preserve typing when I call those generic functions.

We're still looking at it and there may just be a bug that we can fix, but I wanted to warn you that there might not be a satisfactory answer in the short-term.

It would be amazing if the compiler could tell you where there're hot spots in the code, so where it spends the check times. In my case it was the expansion and contraction of large unions. This would be a big, big improvement. My experience digging into this topic showed me that the tooling isn't quite there yet. I understand that this might not have been necessary for the past, but as more and more projects adopt generics, they may run into the same problems. Especially when they upgrade to 3.9.1 and see the same behavior I was seeing. Think of packages like ramda or rxjs which have extraordinary typings and are all generic as they are utility libraries. So compiler hot spots - that'd be awesome!

Thanks for your time!

[amcasey]

Disclaimer: I'm not intimately familiar with these parts of the TypeScript compiler, so you're getting my intuition based on other systems I've worked on.

I understand completely. I don't have any expectations.

Users with no expectations and lots of details are my favorite!

If the return type of parseX2 is exactly the same as in parseX1, which calls parseX2, and the type parameters have the same constraints, why isn't it just "handed down"?

That's not quite right - if parseX1<SomeType> calls parseX2<SomeType>, then they have the same return type. If parseX1<SomeType> calls parseX2 with no type argument, then it's only type inference (expensive) that tells us they're the same. That's why specifying the type argument helps so much.

The repro code is complete garbage

Fun in the sense that it's a compact representation of the problem. I used to work with someone who called repros like this "jewels", because of how compact and elegant they are.

However, it took quite some time to pin those situations down.

I'd love to hear more about how you pinned down the places you needed escape hatches. We're hoping to build a tool that will help users self-service in cases like this (i.e. where a general fix is unlikely in the short-term).

I'm using generics a lot

Generics cause the compiler to check types more lazily, because a lot depends on how they are instantiated. I don't know if you've ever used Haskell, but laziness is great until it's not. At some point, keeping track of deferred work gets more expensive than just doing the work, but the compiler doesn't know that, so you need an out - ! in Haskell. I'm not aware of a comparable escape hatch in TS, but @DanielRosenwasser may have some ideas.

It would be amazing if the compiler could tell you where there're hot spots in the code, so where it spends the check times.

I've been looking for something like that (e.g. #37785), but caching and laziness make it surprisingly difficult to tie costs back to particular statements or libraries. That's why I'm really keen to hear more about how you found your hot spots.

[amcasey]

@ahejlsberg This is the bug we were just talking about. @squidfunk might be able to tell you more about the intent of the code that was reduced to make that repro.

[squidfunk]

That's not quite right - if parseX1 calls parseX2, then they have the same return type. If parseX1 calls parseX2 with no type argument, then it's only type inference (expensive) that tells us they're the same. That's why specifying the type argument helps so much.

That makes sense. I guess I've got to check my code base for further potential gains.

Fun in the sense that it's a compact representation of the problem. I used to work with someone who called repros like this "jewels", because of how compact and elegant they are.

With garbage I meant it is non-sensical, but yes, it manages to reproduce the problem. I've struggled before to achieve that but the Preact JSX typings seem to be sufficiently complex.

I'd love to hear more about how you pinned down the places you needed escape hatches. We're hoping to build a tool that will help users self-service in cases like this (i.e. where a general fix is unlikely in the short-term).

I pretty much documented the process in this thread. When I got the OOM errors and my project refused to compile, I checked how I can debug tsc, skimmed the docs and saw the diagnostics and CPU profile generation flags (awesome that they exist, btw). The profiles showed me that it seemed to be related to type checking unions, and I knew that I had enormous unions, because code completion time got worse over time and the time was spent in isRelatedToType. I've used the compiler API before to build a code generator (love it), so I knew some of the internals. Then I tried to add some console.log statements in tsc.js, but that didn't lead to any new insights.

As my project is recursive and there are some inevitable cycles due to the fact that I'm parsing a context-free grammar, I started by only compiling a very small subset of the files and commenting out functions by best-guessing what could be potential bottlenecks in checking and replacing them with (...args: any[]) => any stubs. When there was a drop in compilation time, I knew I'm on the right track, so I reverted the functions and started commenting out stuff from the body of those functions. This is also how I found the ternary problem of #38399. That took many hours.

That's basically what I did.

Generics cause the compiler to check types more lazily, because a lot depends on how they are instantiated. I don't know if you've ever used Haskell, but laziness is great until it's not. At some point, keeping track of deferred work gets more expensive than just doing the work, but the compiler doesn't know that, so you need an out - ! in Haskell. I'm not aware of a comparable escape hatch in TS, but @DanielRosenwasser may have some ideas.

Never used it, but quite curious. However, deferring and not doing the work turning out being quite expensive in the end is quite intuitive. Every student knows that 😅

I've been looking for something like that (e.g. #37785), but caching and laziness make it surprisingly difficult to tie costs back to particular statements or libraries. That's why I'm really keen to hear more about how you found your hot spots.

I've seen the compiler telling me "Union is too complex to represent" or something like that, and that is a very frustrating error, because it doesn't tell you how to solve it. In the end, using as any here (I feel dirty) solves it. However, I understand that diagnostics is a probably orthogonal problem to building a compiler with great performance.

[squidfunk]

Another question: I have another rather small internal project with zero external dependencies. It uses the "es2017" and "esnext" definitions (defined in tsconfig.json). The only definition that it uses from those definitions is the Readonly mapped type. Yet, toggling skipLibCheck has a massive impact on compile time:

skipLibCheck      false    true

Files:              101     101
Lines:            34296   34296
Nodes:           157185  157185
Identifiers:      56737   56737
Symbols:          85308   40276
Types:            58262    1454
Instantiations:  436338    3544
Memory used:    123382K  76193K
I/O read:         0.03s   0.02s
I/O write:        0.02s   0.03s
Parse time:       1.21s   1.19s
Bind time:        0.63s   0.63s
Check time:      22.95s   0.26s
Emit time:        0.43s   0.44s
Total time:      25.23s   2.51s

Check time for 3.8.3 is at around 12s with skipLibCheck set to true.