CODEWITHSUNDEEP
javascriptarraysappend
jfriend00
jfriend00

Reputation: 707826

How to append contents of one array onto another without intermediate copy of all the data?

Is there any clean and efficient way to add the contents of one array directly to another array without making an intermediate/temporary copy of all the data?

For example, you can use .push() to add the contents of one array directly onto another like this:

// imagine these are a both large arrays
let base = [1,2,3];
let data = [4,5,6]
base.push(...data);

But, that seemingly makes a copy of all the items in data as it makes them arguments to .push(). The same is true for .splice():

// imagine these are a both large arrays
let base = [1,2,3];
let data = [4,5,6]
base.splice(base.length, 0, ...data);

Both of these seem inefficient from a memory point of view (extra copy of all the data) and from an execution point of view (the data gets iterated twice).

Methods like .concat() don't add the contents of one array to another, but rather make a new array with the combined contents (which copies the contents of both arrays).

I've got some big arrays with lots of manipulations and I'm trying to ease the burden on the CPU/garbage collector by avoiding unnecessary intermediate copies of things and I find it curious that I haven't found such a built-in operation. So far, my best option for avoiding unnecessary copies has been this:

// imagine these are a both large arrays
let base = [1,2,3];
let data = [4,5,6];
for (let item of data) {
    base.push(item);
}

which seems like it's probably not as efficient in execution as it could be if it was one operation and obviously it's multiple lines of code when you'd like it to be one line.

Upvotes: 2

Views: 66

Answers (1)

jfriend00
jfriend00

Reputation: 707826

Per, Sebastian's helpful comments, the ideal case would be the fast-path optimization for code like this:

array.push(...data)

that V8 now deploys where it detects data as a known type of iterable and then takes optimized shortcuts to grow the target array once and then copy the data over without making the intermediate copy on the stack.

But, apparently the current V8 does not apply such an optimization to this specific case. When I tried this in node v14.3:

const targetCnt = 100_000;
const sourceCnt = 100_000_000;

// create initial arrays
let target = new Array(targetCnt);
let source = new Array(sourceCnt);

target.fill(1);
source.fill(2);

let b1 = new Bench().markBegin();
target.push(...source);
b1.markEnd();
console.log(`.push(...source): ${b1.formatNs()}`);

I got this error:

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

And, when I reduced the sourceCnt to 1_000_000, then I got this error:

RangeError: Maximum call stack size exceeded

So, I guess that optimization only applies to other circumstances mentioned in the article, not to this one.

So, it seems that until that fast path optimization is considered ubiquitous in all possible targets and you know exactly which situations it is applicable to in your code (I wonder if it would ever be codified in a spec?) and there's no danger of passing an unknown iterable in your code that wouldn't get such preferential treatment, perhaps the best option is to just make your own mini-version of the optimization as a function:

 function appendToArray(targetArray, sourceArray) {
     // grow the target
     let targetIndex = targetArray.length;
     let sourceLen = sourceArray.length;
     targetArray.length = targetIndex + sourceLen;
     // copy the data
     for (let sourceIndex = 0; sourceIndex < sourceLen; sourceIndex++, targetIndex++) {
         targetArray[targetIndex] = sourceArray[sourceIndex];
     }
     return targetArray;
 }

Upvotes: 1

Related Questions