Why is Array.splice() so slow?

Question

I recently saw this benchmark: http://jsperf.com/remove-element-splice-vs-move-and-pop

I noticed that Array.splice() is several orders of magnitude slower than a for loop iterating through the elements. This lead me to wonder why Array.splice() is so slow.

Therefore, I came here to ask you: Why is Array.splice() so slow?

Answer 1

There is a fallacy in that benchmark: .splice preserves the order of the elements in the array, and therefore needs to move half of the elements until the hole created by the removal is sifted up to the end and can be removed by resizing the array. It follows that .splice works in linear time.

Conversely, this piece of code:

array[500000] = array[array.length-1];
array.pop();

swaps the last element with the one to be removed, and shortens the array of 1 element, an operation that can be done in constant time. Technically, the snippet above does not even accomplish the declared goal, since it changes the order of elements in the array (!). Compare:

> array.splice(500000,1)
> console.log(array[500000])
500001

with:

> array[500000] = array[array.length-1];
> array.pop();
> console.log(array[500000])
999999

Answer 2

splice will return your entire array, less the deleted item. So for the 1 element in the benchmark example, you have to copy the other 499999 elements to a new array. But pop just has to shorten the array by one element.

Answer 3

Here are some measures from a real project (not a benchmark). I had a list of objects in an array and had to end up with a smaller subset. In the case shown here, the list happened to have 17,000 items and we happened to need just 7.

My first approach was to iterate through the array and use splice to remove those not needed. Firefox had major problems with that approach, taking over 12 seconds to do what Chrome did in 0.09 seconds! The second approach was to iterate in reverse, doing the same. The third was to copy the wanted objects to a new array.

              Splice Forward   Splice Reverse   Copy to Array   (time in milliseconds)
Chrome 51             91              64             47
IE 11.0.31           309             144             31
Firefox 47        12,544              61             21

In the end, copying was much faster for all the browsers.

However, if you do need to splice, doing it in reverse may be much faster.