[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?