Array method to append another array in-place

💡 Ideas
1

Note: this is a cross-post from https://discourse.wicg.io/t/js-array-method-to-append-another-array-in-place/3831

We have experience writing a high-performance game engine in JavaScript. One problem we've come across is the most performant way to append one array to the end of another in place. (arr1.concat(arr2) returns a new array; this is specifically for an in-place append that modifies arr1.)

The obvious solution is arr1.push(...arr2), but this has a nasty gotcha: the spread passes the array as arguments on the stack, which means if arr2 is long enough, you reach implementation-defined maximum argument length limits. Commonly this is around 65k, but varies from browser to browser. Worse, since the limits are fairly high, writing this type of code at first looks like it works, but then you find out it's broken later on as your arrays get longer and reach limit (worse still, a non-standard limit).

The next obvious solution is to use a loop to call push(), e.g.:

for (let i = 0, len = arr2.length; i < len; ++i)
    arr1.push(arr2[i]);

The problem with this is it's significantly slower, to the point we've found a helper method using exactly this approach was coming up high in performance profiles. It makes sense why: the optimizer probably can't tell how long arr1 will end up, so as it keeps pushing it will have to keep reallocating the backing store to increase the array capacity, and every time it does that it will have to copy the entire array.

Switching to arr1.push(...arr2) measurably increased performance - but then we have to impose an arbitrary hard-coded limit on how long arr2 is to use that fast-path, else fall back to the slow path push() loop - and then we end up switching to a slow path in the most performance intensive case (with long arrays).

This is all pretty awkward and still doesn't achieve maximum performance with long arrays. It could be solved by adding a new array method, e.g.:

// Appends all of arr2 to the end of arr1 in-place
arr1.append(arr2);

This method meets all of the following requirements:

  1. Modify an existing array, instead of returning a new array
  2. Resize the backing store once, since the final size is known
  3. Preserve the internal element kinds (providing the appended array has a compatible internal type)
  4. Append any size array, without arbitrary/non-standard limits

As far as I am aware, it is not possible to achieve all those requirements using any other JavaScript workaround.

1 Like
2

Your helper method should at least try to change independently the length and the individual values:

let len1 = arr1.length;
let len2 = arr2.length;
arr1.length = len1 + len2;
for (let i = 0; i < len2; i++) {
    arr1[len1 + i] = arr2[i];
}

—Claude

3

As far as I'm aware that breaks requirement 3 (preserving element kinds). Assigning the length to a higher value effectively inserts undefined elements, which in the case of V8 will deoptimise the array from SMI/double elements to generic elements. I'm not sure if it kicks it down to holey elements too, but if it does, that makes it even slower.

4

Are you imagining that a.append(b) would be significantly more performant than a.concat(b), particularly on the large arrays where spread-push is not an option?

5

I've kind of explored this space myself, just haven't had the time to go to propose it yet: https://github.com/isiahmeadows/es-stdlib-proposals/blob/57bebc0013805252c4d591571e3de9c872295f53/proposals/array/push-all.md

@ljharb I would. In fact, I've seen it in practice with loops like this out-performing a = a.concat(b) with even smaller collections, despite seeming like it should be doing more work (incrementing a.length and possibly re-allocating on each iteration):

for (const item of b) a.push(item)

It's been larger collections in my experience when performance seems to differ the least, because the cost of copying dwarves the cost of allocation. But even then, you get a GC spike from collecting a large array, so it's still often noticeable.

Edit: Rust's implementation does not far off of what I more or less propose for dynamically-sized vectors.

1 Like
6

pushAll looks like exactly what I was thinking of!

7

Would like to expand on this old topic, because I've ran into exactly the same issue.

.concat is always bad for appending like ary = ary.concat(chunk), especially when ary can grow much larger than chunk — in which case the obvious alternative is ary.push(...chunk), but then you cannot append arbitrarily long chunk. There is no method that'd give you both fast insertion of short arrays and the ability to append long arrays, you need to branch.

I'd like to propose insertion methods modeled after Array.from, not just for append.

replaceFrom(start, deleteCount, iterable[, mapFn, thisArg])
spliceFrom(start, deleteCount, iterable[, mapFn, thisArg])
insertFrom(start, iterable[, mapFn, thisArg])
pushFrom(iterable[, mapFn, thisArg])
unshiftFrom(iterable[, mapFn, thisArg])

replaceFrom would be like spliceFrom but without returning the original slice.

1 Like
8

I can't say I'm a fan of going that far. By that point, it'd be faster to extend length, invoke copyWithin as needed, and perform the insertion yourself.

1 Like
9

I'd point out that I already mentioned in an earlier post that extending length deoptimises the internal elements kinds, e.g. it could downgrade in internal floats array to a generic array, at least from what I understand of V8. So I think it's something you want to avoid if you want fast array operations. I'm happy to stand corrected if anyone can find a reference that says JS engines can handle this efficiently.

1 Like