Typescript: [Performance] repeated property spreading causes out of memory error

[niedzielski]

TypeScript Version: 3.7.0-beta

Search Terms: spread out of memory

When strictNullChecks is set, repeatedly spreading properties doesn't scale:

// Slow
const props: Record<string, string> = {
  ...config.a !== undefined && {a: config.a.toString()},
  ...config.b !== undefined && {b: config.b.toString()},
  ...config.c !== undefined && {c: config.c.toString()},
  // ...
}

// Fast
const props: Record<string, string> = {}
if (config.a !== undefined) props.a = config.a.toString()
if (config.b !== undefined) props.b = config.b.toString()
if (config.c !== undefined) props.c = config.c.toString()
// ...

In a real codebase, the issue will likely surface initially as slower and slower compilation times. Eventually, an out of memory error _appears_ to occur randomly since it can be triggered by simply repeating an existing pattern a few more times. The VS Code experience in these scenarios is also poor as the TypeScript server hangs.

Code

interface Props {
  readonly a?: string
  readonly b?: string
  readonly c?: string
  readonly d?: string
  readonly e?: string
  readonly f?: string
  readonly g?: string
  readonly h?: string
  readonly i?: string
  readonly j?: string
  readonly k?: string
  readonly l?: string
  readonly m?: string
  readonly n?: string
  readonly o?: string
  readonly p?: string
  readonly q?: string
  readonly r?: string
  readonly s?: string
  readonly t?: string
  readonly u?: string
  readonly v?: string
  readonly w?: string
  readonly x?: string
  readonly y?: string
  readonly z?: string
}

function parseWithSpread(config: Record<string, number>): Props {
  return {
    ...config.a !== undefined && {a: config.a.toString()},
    ...config.b !== undefined && {b: config.b.toString()},
    ...config.c !== undefined && {c: config.c.toString()},
    ...config.d !== undefined && {d: config.d.toString()},
    ...config.e !== undefined && {e: config.e.toString()},
    ...config.f !== undefined && {f: config.f.toString()},
    ...config.g !== undefined && {g: config.g.toString()},
    ...config.h !== undefined && {h: config.h.toString()},
    ...config.i !== undefined && {i: config.i.toString()},
    ...config.j !== undefined && {j: config.j.toString()},
    ...config.k !== undefined && {k: config.k.toString()},
    ...config.l !== undefined && {l: config.l.toString()},
    ...config.m !== undefined && {m: config.m.toString()},
    ...config.n !== undefined && {n: config.n.toString()},
    ...config.o !== undefined && {o: config.o.toString()},
    ...config.p !== undefined && {p: config.p.toString()},
    ...config.q !== undefined && {q: config.q.toString()},
    ...config.r !== undefined && {r: config.r.toString()},
    ...config.s !== undefined && {s: config.s.toString()},
    ...config.t !== undefined && {t: config.t.toString()},
    ...config.u !== undefined && {u: config.u.toString()},
    ...config.v !== undefined && {v: config.v.toString()},
    ...config.w !== undefined && {w: config.w.toString()},
    ...config.x !== undefined && {x: config.x.toString()},
    ...config.y !== undefined && {y: config.y.toString()},
    ...config.z !== undefined && {z: config.z.toString()}
  }
}

parseWithSpread({a: 1, b: 2, z: 26})

Expected behavior: Compilation performance is on par with conditional syntax.

Actual behavior: An out of memory error occurs.

Playground Link: https://www.typescriptlang.org/play/?noImplicitAny=false&strictFunctionTypes=false&strictPropertyInitialization=false&strictBindCallApply=false&noImplicitThis=false&noImplicitReturns=false&alwaysStrict=false&esModuleInterop=false&target=1&ssl=1&ssc=1&pln=110&pc=1#code/JYOwLgpgTgZghgYwgAgApQPYAcDOyDeAUMslBHACYYgA2AnsnAPwBcyOYUoA5saeVVoMARq3acefMpWr1kCMRy4heJaYLkVFElVIGyGEbctX8ZQ5DGOS1+i92u7b5uQAtHp9QeTAPelwwAVn7OGgwA1iFmYcg0UV4WALbxdnIgKQHIGBkxWDneAI75FlDFcjhlDGCVyACuNQBuNQDuNQAeNXQ1AF5+AL6EhAD0Q8gAchiQyGCucGDsEPNYmFjQYMAQOAA0yAD6EA0QINOuGDgo5-NgGHUgFBAwoBAUuzsYh1Bc98j38LU0YBwADphqMAOquI7IYS1YA0Cg8RhoFZ4DDCQIQBBgHZUZAgSYLeZwZDLbBrKo3Wp3B5PCi3GibPAzCCgn4POD-ebAPBU5pwcDPEEIGhwHB4ABiGBuRBICGoSlqWIwUAAFPhiQBeZAAcjg2p2wmQWu1wn18iNOoQZqBNtJuD6AEoCHxZfKMAygTQMNwVXADTsEDs7TgHXwBgNWQB5D5fFDE-l0w2-DkA7Z1c4nFDJzmWZXyHYJwnIbogkAQZrISUYFVYOBQc5g4AzADC1AR62ocBoODVcDYAEYDWwAEw7bojgBsjqdI2Q-eQw-N+HHOuHE+1AzLFarNbrDabrgAyssBL2B0OF2PJ9PkLP54uEAQV9q1xvBrOwcrwsDCDAqVjgGoEk9wgRsWzbJtAJALsezlEBHm4NgACVMWVCgAB4lB4HYQFqRJhGgAA+B02HQbA8BlaY6FWZAwS4MA4GEBl0IAFUIi18AAWgSOQAG0AGkfGOcIIDoDAYGQFiAF02BYgSpIGV0QA4EkUTYOim0Y5iyNwditXwRSfAklU4IQoFiQAQg1LUqV+WknWDcyLVM4BuHMoFrkPHQfVDEhgGMly3MNKybOpR4ywoByUSBQ0tUCmKPIwLyTBVXyjOQEzqDMx8QtuOyIqi8igUfOKstc4rEuSnhUr4fyMviulctsmkCtUoq6VK+DyooSrvJqvyArKtyUCasL7La3AgRQTqzIgXqUrSurMq6tyJNG-LnkKyaJJm8qYHm6rFsGlagW4ZB1pazaJuBM7drctzPL6o76qGoFXHO6y8suyLrre5zXtcA6VH69LlrM4APtCjafsciG7qBYAgZ82rjrMwJIa+8Krsc9H4cCJGQaW+Lwgx5qsZh6KSfh8ICeesHypoUmxtaxzGfhmhaZRl6TsSJnoa24FefhxJOYG7mzOOC7yYFoFjnhkBRdB+Kbil8bHJueGMEVonXqwPnvplvX4awbXUfKgp9el36LfhgpTfF8qoEttXoqd+GoHt+m3LwVWWeivB4eBR6Fq5r2POdv2ivmeGwE9+Lagj7HooT+Hajj16GkTimisz+GGnTk6K19pOioreHmgLsy2izmXq-htpK-Khhi+zyaGHhuhG7c7oa9+nv4ZLYPDr0MBaigY5g0ICMPy-PAYDzZlLGAet5hgcsJrWDY8BheYqE2EBtXmHAEC7FBmkhY4sKxMZ-hoZtIQQb8fBwVkji0wVkAAVRAOVEkSI51gqEzLYRIcBQCIjtJvTY8gOTnDwPyLItR5jiWQP-RIyo6Cv0+HmL0J8aD0CBMgAAkscReWARR0G4JgWyOwiEwOOKAkSPgriuGodwd6dtSCMDuNCUSbZphwBEqyYcAAGAA1AsOCFBUROzLB8eQGBEjkMWHNX8-4OwTxAmBI8J5KBe2QqhKAGEsIqBwnhAiUBiKkRRM6Wwo9x62JIMgG0xVXqWU+mTWkyAABk3iCB9gUSdOAtM+hbBdM4m08VgoeOZs8Hxfj8DCDYFEkJYSnERNcSdHKMTobxIIAgZJr0ECpNZOklxDUs55PwBQQpJ0epD2Bg6UJpSnHlNeiNHJ30qkQFqbNEps4ymRNemtTp5MqkwF6XtfpoxBmZLMmdFuVTEKBPmdM9JGT4rvUWb4ggrhJluUBg0nyzSBmtKGSdCG2yEnAH2QjNZsz4royuQQQItz8ZHNSicmZZy5nlRJs8-A4Rbk0w+U0sJpySBtJOozAFNBbkc1BV89ZUKzK8wBYkW5ItEXgu+ZC85EtKk7PwCAW5CtsUtLxb8tyKtRleKJRgW5WtyUQo2brQlCSsC3JNsy3FrKToWwBQUW5dseXIvxY7dlBAoC3I9qKh5r0fa0oilUnAtyg5JSeki+VJ15gArALc2Ocqfnx0lfgWoty05GspfFTOAKGi3PzlavlZki5KriUS5otyK5OpReVauAK2i3Ibj68Vblm5urpESugtzO7ku1WZHuAKVzxUHhqhahlwyECAA

Related Issues:

Trace:

Local execution of `time tsc --strictNullChecks` (v3.7.0-beta) with the
uncommented code:

<--- Last few GCs --->
at[10896:0x2b128d0]   127908 ms: Mark-sweep 2043.7 (2057.8) -> 2040.9 (2058.1) MB, 752.5 / 0.0 ms  (+ 227.7 ms in 67 steps since start of marking, biggest step 17.0 ms, walltime since start of marking 997 ms) (average mu = 0.092, current mu = 0.017) allocat[10896:0x2b128d0]   129003 ms: Mark-sweep 2043.7 (2058.1) -> 2041.6 (2057.6) MB, 917.0 / 0.0 ms  (+ 167.1 ms in 43 steps since start of marking, biggest step 10.2 ms, walltime since start of marking 1095 ms) (average mu = 0.048, current mu = 0.011) alloca

<--- JS stacktrace --->

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

    0: ExitFrame [pc: 0x136cf99]
Security context: 0x1078847808a1 <JSObject>
    1: createObjectType(aka createObjectType) [0x35be1a4076d9] [/home/stephen/dev/nature-elsewhere/node_modules/typescript/lib/tsc.js:~29235] [pc=0xeb30e605cfb](this=0x005fc70404a9 <undefined>,16,0x14f39511c269 <Symbol map = 0x234283fb2161>)
    2: getSpreadType(aka getSpreadType) [0x174d4996a8d9] [/home/stephen/dev/nature-elsewhere/node_modules/typescript/lib/ts...

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory

Writing Node.js report to file: report.20191019.123833.10896.0.001.json
Node.js report completed
 1: 0x9d2fd0 node::Abort() [node]
 2: 0x9d4166 node::OnFatalError(char const*, char const*) [node]
 3: 0xb3281e v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [node]
 4: 0xb32b99 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [node]
 5: 0xcddeb5  [node]
 6: 0xcde546 v8::internal::Heap::RecomputeLimits(v8::internal::GarbageCollector) [node]
 7: 0xcea3da v8::internal::Heap::PerformGarbageCollection(v8::internal::GarbageCollector, v8::GCCallbackFlags) [node]
 8: 0xceb2e5 v8::internal::Heap::CollectGarbage(v8::internal::AllocationSpace, v8::internal::GarbageCollectionReason, v8::GCCallbackFlags) [node]
 9: 0xcedcf8 v8::internal::Heap::AllocateRawWithRetryOrFail(int, v8::internal::AllocationType, v8::internal::AllocationAlignment) [node]
10: 0xcb4627 v8::internal::Factory::NewFillerObject(int, bool, v8::internal::AllocationType) [node]
11: 0xfea55b v8::internal::Runtime_AllocateInYoungGeneration(int, unsigned long*, v8::internal::Isolate*) [node]
12: 0x136cf99  [node]
Aborted (core dumped)

real    2m10.683s
user    2m50.317s
sys 0m1.371s

[cjc343]

Sample react app: https://github.com/cjc343/spread-operator-overflow

Overflows with 21 for me

[RyanCavanaugh]

I'm not confident there's going to be a straightforward fix available for this...

[weswigham]

Oh boy. I know what's going on and you're not going to like it. So, let's break it down. Start with this:

function parseWithSpread(config: Record<string, number>) {
    return {
        ...config.a !== undefined && { a: config.a.toString() },
    }
}

over in the playground, that'll have a return type of {}, but in reality before subtype reduction (done during return type fetching) it has a type of {} | { a: string }. Alright, let's add another field:

function parseWithSpread(config: Record<string, number>) {
    return {
        ...config.a !== undefined && { a: config.a.toString() },
        ...config.b !== undefined && { b: config.b.toString() },
    }
}

OK, so the first spread is a union of {} | { a: string }, the second spread is then {} | { b: string }, which we then combine with the first spread - this means for each element of the first union, we combine with each element of the second spread. So we end up with {} | { b: string } | { a: string } | { a: string; b: string }. Alright, neat. Now let's add a 3rd:

function parseWithSpread(config: Record<string, number>) {
    return {
        ...config.a !== undefined && { a: config.a.toString() },
        ...config.b !== undefined && { b: config.b.toString() },
        ...config.c !== undefined && { c: config.c.toString() },
    }
}

so let's spread in {} | { c: string }.... we get {} | { b: string } | { a: string } | { a: string; b: string } | {c: string} | { b: string; c: string; } | { a: string; c: string; } | { a: string; b: string; c: string }. Ah, hopefully by this point, the pattern is apparent - since a union representation is in use, each spread doubles the number of union elements under consideration. 2^25 is something like 33 million, so, naturally, we OOM at that point. The "fast" method is fast because it's less precise - at no point is a union of alternatives ever under consideration, really.

[niedzielski]

Thank you each for your considerations.

Given the conclusion that the spreads are modeled as:

type Spread =
  | {}
  | { a: string }
  | { b: string }
  | { c: string }
  | { a: string, b: string }
  | { b: string, c: string }
  | { a: string, c: string }
  | { a: string, b: string, c: string };
  // | ...

Is there a more general (and hopefully performant) representation that could be used instead? I think this is saying "it is either present or missing but not undefined" so maybe #13195?

[mieszko4]

I still have an issue with this on 3.8.0-beta so fix in #34853 did not solve the problem for me.

Consider the following file test.js

const filters = {
  f01: true,
};
const extendedFilter = {
  ...(filters.f01 ? { b01: 1 } : { a01: 2 }),
  ...(filters.f02 ? { b02: 1 } : { a02: 2 }),
  ...(filters.f03 ? { b03: 1 } : { a03: 2 }),
  ...(filters.f04 ? { b04: 1 } : { a04: 2 }),
  ...(filters.f05 ? { b05: 1 } : { a05: 2 }),
  ...(filters.f06 ? { b06: 1 } : { a06: 2 }),
  ...(filters.f07 ? { b07: 1 } : { a07: 2 }),
  ...(filters.f08 ? { b08: 1 } : { a08: 2 }),
  ...(filters.f09 ? { b09: 1 } : { a09: 2 }),
  ...(filters.f10 ? { b10: 1 } : { a10: 2 }),
  ...(filters.f11 ? { b11: 1 } : { a11: 2 }),
  ...(filters.f12 ? { b12: 1 } : { a12: 2 }),
  ...(filters.f12 ? { b12: 1 } : { a12: 2 }),
  ...(filters.f13 ? { b13: 1 } : { a13: 2 }),
  ...(filters.f14 ? { b14: 1 } : { a14: 2 }),
  ...(filters.f15 ? { b15: 1 } : { a15: 2 }),
  ...(filters.f16 ? { b16: 1 } : { a16: 2 }),
  ...(filters.f17 ? { b17: 1 } : { a17: 2 }),
  ...(filters.f18 ? { b18: 1 } : { a18: 2 }),
  ...(filters.f19 ? { b19: 1 } : { a19: 2 }),
  ...(filters.f20 ? { b20: 1 } : { a20: 2 }),
};

I get out of memory error when running ts test.js --allowJs

Any suggestion how I could overcome this problem?

[weswigham]

We _very narrowly_ optimized the repeaded spread of undefined | {p1: T} case; a repeated spread of {p1: T} | {h1: U} creates a exponential expansion in the number of types required to compute the expression. In effect, each line you've written there doubles the number of possible output types, and 2^20 is not a small number, by any means.

[AnyhowStep]

2^20 is tiny compared to Tree(3), though

Runs away

[mieszko4]

@weswigham thank you for the explanation.

I've noticed that for the example I gave if I replace ... with Object.assign typescript works well.
So maybe that could be a hint how the case with ... could be fixed in the core.

[jorisw]

I still encounter the memory leak with TypeScript 3.9.6 when using the spread operator to compose ThemeUI styles:

  const selectStyles: SxStyleProp = {
    ...defaultSelectStyles,
    ...filledOrEmptySelectStyles,
    ...(showSmallLabel ? withSmallLabelSelectStyles : {}),
    ...(focused || hovered ? focusedOrHoveredSelectStyles : {}),
    ...(readOnly || disabled ? disabledStyles : {}),
    ...(hovered ? hoveredStyles : {}),
    ...(focused ? focusedStyles : {}),
    ...(hasErrors ? errorStyles : {}),
    ...(hasWarnings ? warningStyles : {}),
  }

Each of the objects being spread above are also typed as SxStyleProps.

[dotansimha]

@weswigham I just encountered this with TS 4.0.2. Has a file with ~50 spreads (🤦 ).

If it's done this way:

// something = any
// somethingElse = any
return {
  ...(something && { foo: 'foo' }),
  ...(somethingElse && { bar: 'bar' }),
}

If I set something or somethingElse to it's real value (boolean) it fails with an invalid memory allocation in V8 (running with 12GB of RAM...).

Also, if I change this to:

// something = any
// somethingElse = any
return {
  ...(something ? { foo: 'foo' } : {}),
  ...(somethingElse ? { bar: 'bar' } : {}),
}

It fails :(

I guess the only solution here is to use Object.assign instead of spreads?