5

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?

Stack Tracer
  • 968
  • 7
  • 26
  • 2
    Compare their algorithms: [`splice`](http://www.ecma-international.org/ecma-262/5.1/#sec-15.4.4.12), and [`pop`](http://www.ecma-international.org/ecma-262/5.1/#sec-15.4.4.6). – Sampson Jun 09 '15 at 23:15
  • " than a for loop iterating through the elements" --- you don't have any loops in your jsperf example tests – zerkms Jun 09 '15 at 23:15
  • If you are going to compare the speed of different algorithms, you should start by having them all do the same thing. The linked code doesn't do that, each snippet has a different result. – RobG Jun 09 '15 at 23:52
  • pop() just shortens the array from the end,;most of the array is unchanged, whereas that splice() pulls from the front, demanding the whole array be re-indexed. – dandavis Jun 10 '15 at 00:57

3 Answers3

6

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
Stefano Sanfilippo
  • 32,265
  • 7
  • 79
  • 80
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.

Kim Ryan
  • 515
  • 1
  • 3
  • 11
  • 1
    `splice` does not return nor copies the whole array, check the docs. – Stefano Sanfilippo Jun 09 '15 at 23:26
  • Yes, that's right, only neeeds 1 copy and not 499999 as I said. But according to this, it still returns an array https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/splice . If that has only one element, memory overhead should be similar than for a pop operation, but still slightly more work than returning a variable. – Kim Ryan Jun 09 '15 at 23:32
  • @StefanoSanfilippo—according to [*the language specification*](http://ecma-international.org/ecma-262/5.1/#sec-15.4.4.12), step 2 in the *splice* algorithm is: "*Let A be a new array…*". It creates a new array and copies the removed elements to it, then returns that new array. – RobG Jun 09 '15 at 23:45
1

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.

Glen Little
  • 6,951
  • 4
  • 46
  • 68
  • The objects in the array were quite simple, with 3 strings and 1 number. – Glen Little Jun 21 '16 at 20:29
  • What was your faster way to copy a subset, do you remember? I'm using slice to remove x elements from the start of the array, but this is a bit of a bottleneck in an intensive workflow. – Tiago Apr 09 '18 at 16:56
  • @Tiago I think I ended up not altering the original array, just copying what I needed to a new array, then abandoning/deleting the original. – Glen Little Apr 10 '18 at 15:35