Exponential increase in compile time and memory usage #38339
Comments
|
@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 Also, which version of node are you running? |
|
Thanks for your quick response! I'm running Node 13.6.0. As you suggested, I tried increasing 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 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
: neverThis 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 | undefinedWhat I tried now: if I generate an interface with all values of 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 |
|
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: +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? |
|
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. |
|
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: 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 |
|
I managed to reproduce the exponential increase when branching using the Preact JSX typings: |
|
Wow, that's a lot of info! I'll do my best to respond in an orderly way. I'm interested in Edit: Figured it out - it takes the place of In your 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 Do you ever pass a second type argument to Your reduced repro is really fun. 😄 |
|
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. |
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.
But why? If the return type of
Do you mean
Actually, no! The second argument is just there to enable the actual narrowing. If I don't specify it and replace
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.
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 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.
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 Thanks for your time! |
|
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.
Users with no expectations and lots of details are my favorite!
That's not quite right - if
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.
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).
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 -
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. |
|
@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. |
That makes sense. I guess I've got to check my code base for further potential gains.
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 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 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 That's basically what I did.
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 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 |
|
Another question: I have another rather small internal project with zero external dependencies. It uses the Check time for 3.8.3 is at around 12s with |
RyanCavanaugh
added
the
Needs Investigation
I'm sorry you had to deal with that. I don't know whether it makes it better or worse, but that's more or less what we would have done ourselves, given a copy of your code. We'd really like to figure out a way to provide some profiling hints, but it's proved intractable so far. Having said that, if you can spare the time, I'd love to know whether running this private build on your pre-improvement code would have highlighted the problems you figured out the hard way.
When there's a clear fix for an error we try to put it in the error message and/or provide a code fix. Unfortunately, I don't think there's a general purpose solution to this problem (though, as you point out, there might be a general purpose mitigation), but it might be interesting to post a discussion of how to approach the problem on the blog or in the handbook. @DanielRosenwasser?
Error messages are one of the most important outputs of a compiler - if you think about it, most people can't type in error-free code on the first attempt, so nearly every successful compilation will be preceded by one or more failing compilations. As a result, producing clear, actionable diagnostics is really a top priority - especially for a compiler like tsc that leaves most input code untouched. So, yes, there's a balance we have to strike between running quickly and producing useful diagnostics (which tend to be expensive), but my personal feeling is that an unactionable diagnostic is basically a compiler bug.
You can use
|
|
Oh, it's only tangentially related, but I wanted to plug this really nice blog post from @andrewbranch about another And, obviously, if he feels like jumping in with an alternative solution for this particular coding pattern, that would be great too. 😉 |
Great article! Thanks for sharing.
I removed the
I think what we're looking at is the Instantiation² problem. From my knowledge of the TypeScript internals and the way the AST nodes are represented, I would've guessed that the compiler could detect the case when it's necessary to compare two unions and just do the math. For me, it's a union of
That's pretty handy. Indeed, a lot of default library files were picked up. However, only two files were added in 3.9.1: I'll see if I reduce the issue to another reproducible case. |
|
After testing the I understand that this is a downstream issue, but it may impact a lot of users. I'm not even using the dependency in the files that are compiled (but in other subpackages of the mono repo), but |
|
@squidfunk you can use the "types" field of tsconfig to limit it to only load specific |
I don't think that works for types that are included in a non-types npm package, but I could be mistaken. |
|
It does! 😁 |
|
@squidfunk +1 about the |
|
@aecorredor I'm not defining the |
|
@squidfunk unfortunately I already had |
|
@aecorredor Do you have an example project we can play with? |
|
@amcasey it's a close source project. But let me see if I can put together a reproducible repo and send it to you guys. I'm swamped right now but I'll do it as soon as I get a chance. By now I'm pretty sure it's related to ramda types. It happens wherever I'm editing files where |
|
Thanks @aecorredor! I agree with your assessment that it's probably ramda, but that library has so much surface area that it's hard for us to pinpoint problems without a repro. |
|
This is probably tangential to the problem at hand, but to clear up one point of possible confusion:
This is a very common misconception. When you set a import { compose } from 'ramda';
it('works', () => {
// ...
});Here, you’re explicitly referencing the ramda types, and implicitly referencing the jest types. Because you have an import from ramda, its entry in your As @squidfunk correctly pointed out, if you don’t specify |
|
@amcasey Anything you want me to do here? |
|
@ahejlsberg This is loosely tracking the fact that ramda seems to have perf issues. We're hoping to hear back from @aecorredor with a repro. I can self-assign until it's more actionable. |
|
@ahejlsberg @aecorredor sorry guys, I've been swamped. Since the issue for us is happening in a big monorepo, coming up with a reproducible one won't be as easy as I thought. Also, just to make this clear, it's not an issue with |
|
@amcasey so, disappointing news: I spent a while trying to come up with a big enough monorepo for the problem to show up, and I just couldn't replicate it. Ours is maybe just too custom/too big, and has too many variables/configs that may be playing a role in causing the issue. I honestly don't have much more time to spend on coming up with the correct reproducible repo. What we're sure of is that it happens everywhere |
|
@aecorredor Definitely disappointing, but I appreciate the effort. Thanks for following up! |
|
I'll be working during this year on more performant ways to write Another thing that I could do is to try to further optimize |
|
Woohoo! Does the update mentioned in #39398 work for you too, @squidfunk? |
|
So I've released another update for |
|
@millsp wow, updating |
|
@amcasey – yes, it does 🚀 Check times dropped from 8.10s to 1.55s, which means I can disable Before
After
|
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:
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>, whereasFooLike<T>uses conditionals to select a specific type from a huge union with ~1k types. Build times now are:The text was updated successfully, but these errors were encountered: