Speed Alley: The fastest way to copy an array

Speed Alley is a section of NOOBjs where we explore performance implications for various code decisions. Let’s go experiment!

A Little Background

Depending on how far along you are in your noobhood, you may realize that arrays in JavaScript are really just objects. One implication of arrays being objects is that the variable that you’re using to access the array is really just pointing to the array, not storing the actual array itself.

Let’s look at a JavaScript primitive type first, like numbers, to see the difference. Since numbers are not stored by reference, we can do something like this:

var a, b;
a = b = 5;

a = a + 5;

console.log(a); // logs 10
console.log(b); // logs 5

Now, let’s try that with an array:

var a, b;
a = b = [1, 2, 3, 4, 5];

a[0] = 10;

console.log(a[0]); // logs 10
console.log(b[0]); // ???

If you put this into your console, you’d see that b[0] logs 10 as well! Why? Because they’re both referencing the same array. If you wish to read a little more about object references, check out my article on playing with objects.

“Copying” an array like this is called a shallow copy because you’re just copying the reference. However, what if we wanted two distinct arrays that were independent from each other? In that case, we’d want to do a deep copy of the array where we copy each individual element. I don’t want to go into the ins and outs copying, but rather focus on performance. More power! Here’s a nice little article on deep copies versus shallow copies if you’re still not with us.

Comparing Methods by Performance

In order to make a deep (and more useful) copy of an array (underscore refers to this as a shallow-copied clone), we’re going to need to go through each element and copy it. Before we get carried away here, let’s write our performance test:

var ourArray = [], 
	i, start, end;

for(i = 0; i < 1000; i++) {
	ourArray[i] = i;
}

start = new Date();

for(i = 0; i < 1000000; i++) {
	// clone the array here
}

end = new Date();
console.log('TIME: ' + (end - start));

Essentially, we’re creating an array of 1,000 integers, getting the start time in milliseconds, running our clone function a million times, getting the end time, and logging the results. Nothing fancy there. My machine is a late 2011 MacBook Pro with a 2.2 GHz Intel Core i7 processor, and all times will be based off that machine using Node v0.10.26. Results will vary depending on machine and interpreter.

JavaScript has a number of built-in methods we can use that will make it really easy for us to clone this array: slice, concat, and map.

slice returns a simple copy of a portion of an array. The first argument is the starting element, and the second argument is an optional ending element. If we want to copy the entire array, we start at zero and leave the last argument blank:

ourArray.slice(0);

Let’s stick slice in our speed test to check the performance. On my machine, the performance was 536-543 milliseconds. Not too impressive.

concat combines any arrays passed in as arguments into a new array. If we were to concat the array we wanted to clone with an empty array, it should do the trick:

ourArray.concat([]);

Now, when I tested the performance of using concat in this way, I found it to be 541-550 milliseconds. A little slower yet.

The last built-in method we’ll try is map, for fun. map goes through each element in an array, performs an action on it, and returns the result into a new array. We send in the action via a callback, and if we return the element, it just gets added to the array and it’s like a clone:

ourArray.map(function(element) {
	return element;
});

When I tested the speed of map, I found that it performed the operation in over 40,000 milliseconds! Okay, let’s never do that again.

Let’s try one more.

The most obvious method would be to use a for loop to go through each element and copy the contents into a new array. Let’s write a function to do that:

function clone(base) {
	var newArray = [];
    for(var i; i < base.length; i++) {
	    newArray[i] = base[i];
	}
	return newArray;
};

If we stick clone(ourArray) into our speed test, we can see the performance. On my machine, the performance was 14-15 milliseconds! That’s a little better…

Conclusions

The conclusions here are obvious:

1. NEVER use map to clone an array (not to mention it’d be a little silly anyway).
2. In a pinch and when performance isn’t an issue, slice is the easiest way to clone an array.
3. The most performant, straightforward, way to clone an array is via a for loop.

If you’ve read a fair amount about JavaScript, this conclusion would not have been surprising, as for loops are one of the fastest ways to get things done in JavaScript, and using map to perform a callback each time is not surprisingly slow either.

Caveats

We only tested speed on copying an array of integers. It’s possible that copying different types would yield different results, though performance will likely fall in the same hierarchy.

More importantly, if we’re cloning an array of arrays, we’re creating a new outer array, but the elements are still going to be referencing the same arrays. For example:

var arr = [[1,2,3], [4,5,6]];
var arr2 = arr.slice(0);

arr[0][0] = 5;
console.log(arr2[0][0]); // logs 5!

Well, that might be an issue. However, a simple fix to that would be to call clone recursively if an element is an array:

function clone(base) {
    var newArray = [];
    for(var i = 0; i < base.length; i++) {
        if(base[i] instanceof Array) {
        	newArray[i] = clone(base[i]);
    } else {
	        newArray[i] = base[i];
        }
}
	return newArray;
};

Now, if we change either array in any way, they are no longer linked in any way. That being said, if the arrays have objects in them, they will still reference the same object. Addressing that issue is beyond the scope of this article since there are many nuances to what exactly you want to clone in the objects, though you should be aware of that, and we’re already sidetracked from performance!

Speaking of performance, with this enhanced clone function using the same test, our performance blew up to about ~15,000 milliseconds!

Final conclusion: For best performance, write a function tailored to the kind of array you’re planning on cloning!

---

Check out the original post and more resources on Matt’s blog, Noob.js.