Performance regression in `__spreadArray`

[FlorianDr]

Bug Report

🔎 Search Terms

__spreadArray performance benchmarking

🕗 Version & Regression Information

• This changed between versions 4.1 and 4.2

⏯ Playground Link

CodeSandbox with benchmarks
Playground link with configuration example

💻 Code

__spreadArray(__spreadArray([], arr1), arr2)
// vs.
__spreadArrays(arr1, arr2)

🙁 Actual behavior

Starting from 4.2, occurences of __spreadArrays are replaced with multiple calls to __spreadArray. The change fixes side effects in the polyfill (#32959).

Function	Browser	Arrays	Elements per Array	Runs	Mean time in ms	Slowdown
__spreadArrays	Chromium 90	1	(numbers) 1000000	100	2.32
__spreadArray	Chromium 90	1	(numbers) 1000000	100	10.29	4.43
__spreadArrays	Chromium 90	2	(numbers) 1000000	100	4.35
__spreadArray	Chromium 90	2	(numbers) 1000000	100	25.4	5.83
__spreadArrays	Chromium 90	2	(objects) 1000000	100	4.82
__spreadArray	Chromium 90	2	(objects) 1000000	100	68.1	14.10

🙂 Expected behavior

No or moderate performance impact.

[rbuckton]

We changed from __spreadArrays to multiple calls to __spreadArray to match the ES2015 runtime semantics because the runtime behavior of __spreadArrays incorrectly captured side effects too early, as per the linked PR.

I compared what we do to what BabelJS does. Babel has the same error we used to have for this case:

const k = [1, 2];
const o = [3, ...k, k[0]++];
console.log(o.join(", "));
// out
var k = [1, 2];
var o = [3].concat(k, [k[0]++]);
console.log(o.join(", ")); // prints: 3, 2, 2, 1; should print: 3, 1, 2, 1

This is because Babel statically looks up k and sees it's an array, emitting the "faster" code that doesn't correctly preserve side-effects. If you're able to convince Babel that k isn't statically an array, then it emits a _toConsumableArray helper:

const k = (() => [1, 2])();
const o = [3, ...k, k[0]++];
console.log(o.join(", "));
// out
...
var k = function () {
  return [1, 2];
}();
var o = [3].concat(_toConsumableArray(k), [k[0]++]);
console.log(o.join(", "));

I ran this through your benchmark, and while its still slower than the old __spreadArrays helper, it is faster than __spreadArray.

What's expensive in __spreadArray is that we're rebuilding the array each time from the beginning. We can improve this by using concat and ensuring that to is always an array during emit, and that any from that is a spread is always a packed array:

var __spreadArray2 = function(to, from, pack /*optional*/) {
  if (pack) for (var i = 0, l = from.length, ar = Array(l); i < l; i++) ar[i] = from[i];
  return to.concat(pack ? ar : from);
};
var k = [1, 2];
var o = __spreadArray2(__spreadArray2([3], k, 1), [k[0]++]);
console.log(o.join(", "); // prints: 3, 1, 2, 1

It's important that we coerce from into a packed array, since that does matter to spread:

Unfortunately, this is something that we unintentionally regressed with __spreadArray, as the following results in incorrect output:

const k = [1, , 2];
const o = [3, , 4, ...k, , k[0]++];
console.log(1 in o); // expected: false; actual: false (ok)
console.log(4 in o); // expected: true; actual: true (ok)
console.log(6 in o); // expected: false, actual: true (wrong)
console.log(o.join(", ")); // [3, , 4, 1, , 2, , 1]

We always guarantee that the first argument to the innermost __spreadArray is always an array literal containing the leading non-spread arguments. This means it should generally be safe to call .concat on the first argument since it's always an array.

The new version of __spreadArray2 above is backwards compatible with __spreadArray (though with the same incorrect packing behavior for non-spread holes), has the correct packing behavior if we update our emit to pass a truthy value for the 3rd argument, and outperforms the current __spreadArray (with or without the 3rd argument) and is on par with Babel's toConsumableArray:

While still slower than the older __spreadArrays helper, I'm not sure we can fully recover that performance without sacrificing correctness with runtime semantics.

As a result, I propose the following changes:

1. Replace __spreadArray with the arguments and body of the __spreadArray2 variant.
2. Update EmitHelpers.createSpreadArrayHelper to take an extra pack argument to emit a truthy value (i.e., 1 for brevity or true for clarity).

Alternatively, we can deprecate __spreadArray and introduce a new __pack helper:

var __pack = function (from) {
  for (var i = 0, l = from.length, ar = Array(l); i < l; i++) ar[i] = from[i];
  return ar;
};

We could then use __pack along with concat directly:

const k = [1, 2];
const o = [3, ...k, k[0]++];
console.log(o.join(", "));
// out
var k = [1, 2];
var o = [3].concat(__pack(k), [k[0]++]);
console.log(o.join(", ")); // 3, 1, 2, 1

const k = [1, , 2];
const o = [3, , ...k, , k[0]++];
console.log(o.join(", "));
// out
var k = [1, , 2];
var o = [3, ,].concat(__pack(k), [, k[0]++]);
console.log(1 in o); // expected: false; actual: false (ok)
console.log(4 in o); // expected: true; actual: true (ok)
console.log(6 in o); // expected: false, actual: false (ok)
console.log(o.join(", ")); // 3, , 1, , 2, , 1

This approach has slightly better performance than __spreadArray2, but has the downside of shipping yet another helper that replaces __spreadArrays, meaning we would need to ship all 3 variants to maintain backwards compatibility in perpetuity (or at least until we no longer support TS versions that emit those helpers).

[FlorianDr]

Thank you so much @rbuckton and team for working on this issue. Looking forward to bumping the version :)