TS v2.3.1 runs out of memory compiling FP library

[gcanti]

TypeScript Version:: 2.3.1

Repo: https://github.com/gcanti/fp-ts

After upgrading typescript from 2.2.2 to 2.3.1 the compilation (npm run build) fails with the following error:

<--- Last few GCs --->

   25725 ms: Scavenge 1407.7 (1457.4) -> 1407.7 (1457.4) MB, 46.2 / 0 ms (+ 24.7 ms in 1 steps since last GC) [allocation failure] [incremental marking delaying mark-sweep].
   27079 ms: Mark-sweep 1407.7 (1457.4) -> 1406.4 (1456.4) MB, 1354.1 / 0 ms (+ 1071.3 ms in 617 steps since start of marking, biggest step 25.4 ms) [last resort gc].
   28376 ms: Mark-sweep 1406.4 (1456.4) -> 1405.9 (1457.4) MB, 1297.0 / 0 ms [last resort gc].


<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x1985f0ce3ac1 <JS Object>
    1: recursiveTypeRelatedTo(aka recursiveTypeRelatedTo) [/Users/giulio/.nvm/versions/node/v5.5.0/lib/node_modules/typescript/lib/tsc.js:~27814] [pc=0xf9f8ea8a65b] (this=0x1985f0c04189 <undefined>,source=0x173e2ea53611 <a Type with map 0x1089a6556cc9>,target=0x95cb168fbb1 <a Type with map 0x1089a6556b69>,reportErrors=0x1985f0c04299 <false>)
    2: isRelatedTo(aka isRelatedTo) [/Users/giulio/.n...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory
Abort trap: 6

Somehow seems related to the modules Tuple.ts and Apply.ts

In the module Tuple.ts if I comment the following lines

declare module './HKT' {
  // interface HKT<A> {
  //   Tuple: Tuple<any, A>
  // }
  interface HKT2<A, B> {
    Tuple: Tuple<A, B>
  }
}

the compilation doesn't crash.

Alternatively if I don't touch Tuples.ts but I comment out all the liftA* functions in Apply.ts the compilation doesn't crash.

Expected behavior:
Compilation success

Actual behavior:
Compilation fail

[gcanti]

Here's another repro which involves other modules.

Worth noting that with the following example the code completion feature in VSCode with TypeScript v2.2.2 hangs with CPU 100%

import * as array from 'fp-ts/lib/Array'
import * as validation from 'fp-ts/lib/Validation'

export function pouet(
  xs: number[],
  f: (x: number) => validation.Validation<string[], number>
): void {
  const x = array.traverse(validation. .getStaticApplicative(array))(f, xs) // Long hanging due to this space
}

In the Array.ts module, if I remove the currying in the definition of traverse, i.e from

export function traverse<F extends HKT2S>(applicative: StaticApplicative<F>): <L, A, B>(f: (a: A) => HKT2<L, B>[F], ta: Array<A>) => HKT2<L, Array<B>>[F]
export function traverse<F extends HKTS>(applicative: StaticApplicative<F>): <A, B>(f: (a: A) => HKT<B>[F], ta: Array<A>) => HKT<Array<B>>[F]
export function traverse<F extends HKTS>(applicative: StaticApplicative<F>): <A, B>(f: (a: A) => HKT<B>[F], ta: Array<A>) => HKT<Array<B>>[F] {
  return (f: any, ta: any) => {
    const snocA2 = liftA2(applicative, curriedSnoc)
    return reduce((fab, a) => snocA2(fab, f(a)), applicative.of(empty()), ta)
  }
}

to

export function traverse<F extends HKT2S, L, A, B>(applicative: StaticApplicative<F>, f: (a: A) => HKT2<L, B>[F], ta: Array<A>): HKT2<L, Array<B>>[F]
export function traverse<F extends HKTS, A, B>(applicative: StaticApplicative<F>, f: (a: A) => HKT<B>[F], ta: Array<A>): HKT<Array<B>>[F]
export function traverse<F extends HKTS, A, B>(applicative: StaticApplicative<F>, f: (a: A) => HKT<B>[F], ta: Array<A>): HKT<Array<B>>[F] {
  const snocA2 = liftA2(applicative, curriedSnoc)
  return reduce((fab, a) => snocA2(fab, f(a)), applicative.of(empty()), ta)
}

both the compilation crash and the VSCode hanging go away

[sledorze]

@sandersn One repo showing the last issue @gcanti reported (in case it could help) :
https://github.com/sledorze/vscode-hanging

[sandersn]

I can't repro this with typescript@next. Can you try typescript@next?

[gcanti]

With TypeScript 2.4.0-dev.20170502

• compilation succeeded
• Code helper still hangs with 100% CPU (snippet or repo above)

[sandersn]

I can't repro that exact behaviour in VS Code. For me, initial load time is very long and then if I type a dot after validation I get completions one time. Afterwards I just get Loading... indicating that the language service is not responsive. Does VSCode itself become unresponsive for you?

Are you using "typescript.tsdk" to point to typescript@next? Here's my settings.json

{
    "typescript.tsdk": "/media/nathansa/src2/ts/built/local",
    "typescript.tsserver.trace": "off",
    // ... other config stuff ...
}

Yours will be somewhat different since you want to point to typescript@next installed from npm instead of built locally from source.

[OliverJAsh]

I have a project that uses fp-ts and compilation still fails with this memory error on typescript@next:

❯ tsc --version
Version 2.4.0-dev.20170503

❯ yarn run compile
yarn run v0.22.0
$ rm -rf target && mkdir target && tsc && cp -r ./src/client ./target

<--- Last few GCs --->

   46574 ms: Mark-sweep 1367.1 (1435.0) -> 1367.1 (1435.0) MB, 1402.6 / 0.0 ms [allocation failure] [GC in old space requested].
   48162 ms: Mark-sweep 1367.1 (1435.0) -> 1367.1 (1435.0) MB, 1587.9 / 0.0 ms [allocation failure] [GC in old space requested].
   49752 ms: Mark-sweep 1367.1 (1435.0) -> 1371.7 (1419.0) MB, 1589.5 / 0.0 ms [last resort gc].
   51100 ms: Mark-sweep 1371.7 (1419.0) -> 1376.3 (1419.0) MB, 1347.6 / 0.0 ms [last resort gc].


<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x27062c3cfb51 <JS Object>
    1: inferFromTypes [/Users/OliverJAsh/Development/twitter-paper/node_modules/typescript/lib/tsc.js:~28893] [pc=0x286345341249] (this=0x27062c3e6f19 <JS Global Object>,source=0x3e76e59c9ba1 <a Type with map 0xb208b868ac1>,target=0x3df62ba20169 <a Type with map 0xb208b86b039>)
    2: inferFromProperties [/Users/OliverJAsh/Development/twitter-paper/node_modules/typescript/lib/tsc.js:~29042] [pc...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
 1: node::Abort() [/Users/OliverJAsh/.nvm/versions/node/v6.9.5/bin/node]
 2: node::FatalException(v8::Isolate*, v8::Local<v8::Value>, v8::Local<v8::Message>) [/Users/OliverJAsh/.nvm/versions/node/v6.9.5/bin/node]
 3: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/Users/OliverJAsh/.nvm/versions/node/v6.9.5/bin/node]
 4: v8::internal::Factory::NewRawOneByteString(int, v8::internal::PretenureFlag) [/Users/OliverJAsh/.nvm/versions/node/v6.9.5/bin/node]
 5: v8::internal::Factory::NumberToString(v8::internal::Handle<v8::internal::Object>, bool) [/Users/OliverJAsh/.nvm/versions/node/v6.9.5/bin/node]
 6: v8::internal::Runtime_NumberToStringSkipCache(int, v8::internal::Object**, v8::internal::Isolate*) [/Users/OliverJAsh/.nvm/versions/node/v6.9.5/bin/node]
 7: 0x2863447092a7
sh: line 1: 73747 Abort trap: 6           tsc
error Command failed with exit code 134.
info Visit https://yarnpkg.com/en/docs/cli/run for documentation about this command.

[gcanti]

For me, initial load time is very long and then if I type a dot after validation I get completions one time. Afterwards I just get Loading... indicating that the language service is not responsive

@sandersn 👍 That's the exact behaviour I'm experimenting

Does VSCode itself become unresponsive for you?

No, only the Code Helper is unresponsive (I must close and reopen vscode to regain the functionality)

Are you using "typescript.tsdk" to point to typescript@next?

Yes

[sandersn]

@OliverJAsh is your source available, or can you make a miniature repro?

@gcanti thanks for clarifying, I just misunderstood your terminology.

[sandersn]

@gcanti Interestingly, emacs with tide still has the long startup time but if you wait then it doesn't stop working afterward. So I suspect that VSCode is somehow still using some 2.3 code even though it is pointed to the latest code from master.

Edit: It's probably because emacs only does buffer-wide error checking when explicitly asked to. VSCode does it in the background when you're not typing. Maybe VSCode is getting overloaded because checking the entire file takes so long, and requests come in repeatedly?

[OliverJAsh]

@sandersn It took me ages to reduce the test case down to something I could share, but I want to help :-). This is as simple as I could get it whilst retaining the memory issue:

https://github.com/OliverJAsh/ts-2.4-memory-issue

Hope that helps!

[sandersn]

Thanks, ts-2.4-memory-issue repros for me too.

[OliverJAsh]

Any ideas what might be causing the issue, and if there is any workaround?

[sandersn]

From poking at it with the debugger, it looks like type inference starts comparing various failure Monads like Left | Right and Succcess | Failure and gets caught in structural comparison of their various methods.

Typescript in general has trouble whenever it has to do extensive structural comparison. We tried to help comparisons with lots of overloads with #15519. This was specifically aimed at Array in lib.d.ts, which recently grew a lot more overloads. I don't think that's the problem with fp-ts' types. It's probably that the library is structurally complex and recursive.

I'll try to further reduce ts-2.4-memory-issue to see whether there is any specific pattern at fault here.

[sledorze]

@sandersn do you have any recommandation as how to speed up that inference from a library author perspective? (in our context)

[sandersn]

No recommendations yet, but I discovered the reason that the per-class tags weren't helping, and why Anders' recent change to improve overloads didn't help enough (fp-ts doesn't have many overloads that I noticed, and it doesn't use Array much either). The compiler still gets stuck in a structural comparison of very complex types inside type inference.

Validation and Either include tags to make assignability fail fast, eg readonly _tag: 'Right'. But type inference doesn't fail fast — inferFromProperties iterates over each property of the target type trying to gather inferences from the same property in the source type. There's no way of failing quickly out of an inference. It just fails to find any inferences for _tag: 'Failure' → _tag: 'Right' and moves on to the next property.

I'm not fluent enough with the architecture of type parameter inference to see any avenues for optimisation yet. I'll consult with @ahejlsberg in the next few days to find out if there's something we can do.

[sandersn]

Here is one workaround: Always provide type parameters. This avoids type inference, but is tremendously inconvenient. So I don't think it's actually feasible.

[sandersn]

Reducing the inference-too-deep cap to 3 nested occurrences of the same type makes compilation complete in 3.3 seconds. Reducing it to 4 makes compilation complete in 10 seconds.

[sledorze]

@sandersn how can one configure that inference-too-deep cap ?
Also how could one find out what part of the code make the compiler crazy?
Thanks in advance, I have some hard times with that..

[sandersn]

@sledorze the inference-too-deep cap isn't configurable right now. Setting it too low will start to create bogus inferences of {}. Maybe we should revisit the value, but I don't think it should be configurable. The only time you need it, you're avoiding an architectural problem of the compiler.

Node crashes don't give much of the stack, as you can see. I debugged using the following:

$ node --inspect --debug_brk ~/ts/built/local/tsc.js

Then I opened Chrome to the provided URL and let the compiler run for a while. Each time I did this there were many recursive calls in inference on the stack, so I guessed that inference was causing the out-of-memory crash. (You can substitute any copy of tsc.js that you have, you don't need to build a copy yourself.)

[sandersn]

Update from talking to @ahejlsberg. The inference-too-deep cap should maybe be removed entirely — it was a mistake from when we believed that inference should behave similarly to assignability checking.

@ahejlsberg is working on a fix that just quits when inference sees an instantiation of a type that it has seen before. That should fix this bug.

I'll also add fp-ts to our real-world code test suite after the bug is fixed so that we can catch compiler bugs in this library and similar FP/monad libraries.

[sandersn]

fp-ts is now part of our RWC corpus so we should notice any performance regressions in the future.

[OliverJAsh]

This fixed the issue for https://github.com/OliverJAsh/ts-2.4-memory-issue, but I ran into another scenario where the memory issue pops up again. I've created a small test case in https://github.com/OliverJAsh/ts-2.4-memory-issue/tree/2.4.0-dev.20170519.

[OliverJAsh]

@sandersn Do you have any idea what is causing the above?

[sledorze]

@sandersn note that the problem happens with fp-ts when there's a type error in the program, not compiling an actually well typed program (this is from my observations).

Also considering this problem, the worst case is not when one changes some code and have the compiler getting lost in inference, the real issue is when one upgrade a library and it breaks the compiler without any clue where the type error is and how to fix it.

[sledorze]

@sandersn it should be reopened IMHO

[sandersn]

@sledorze I opened a new bug based on @OliverJAsh's repro: #16029. If you have another repro please link to it there.

I'm keeping this bug closed just to make bookkeeping simpler. And it's unlikely that the compiler is getting stuck in inference again (or at least, for the same reason).

[bryanerayner]

I'm not sure whether or not the pain point I had today was caused by this issue, but I also was running into the problem of Node running out of space on the heap.

I reverted to 2.3.2, and was able to successfully compile. If you guys can nail down this bug, it would be greatly appreciated!

[sandersn]

@bryanerayner there are, unfortunately, many reasons for typescript to run out of memory while compiling fp-ts. The root cause of this issue is definitely fixed: type inference no longer recursively examines types that it has already seen. But (for example) assignability checking still does recursively examine types. It's likely that the issue you're hitting is different. Can you open a new issue and give some detail about your code there?