Why is Array.splice () so slow?
I recently saw this test: 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 made me wonder why Array.splice () is so slow.
So I came here to ask you: Why is Array.splice () so slow?
source to share
There is a bug in this test: it .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 deletion is filtered to the end and can be removed by resizing the array. It follows from this that it .splice
works in linear time .
Conversely, this piece of code:
array[500000] = array[array.length-1];
array.pop();
collapses the last element with the one to be removed and shortens the 1 element array, an operation that can be performed in constant time . Technically, the above snippet doesn't even fulfill its declared purpose, since it changes the order of the elements in the array (!). For comparison:
> array.splice(500000,1)
> console.log(array[500000])
500001
from:
> array[500000] = array[array.length-1];
> array.pop();
> console.log(array[500000])
999999
source to share
Here are some measures from a real project (not a reference). I had a list of objects in an array and I needed to get a smaller subset. The list shown here had 17,000 items on the list, and we only needed 7.
My first approach was to iterate over the array and use splice
to remove unneeded ones. Firefox had serious problems with this approach, taking over 12 seconds to do what Chrome did in 0.09 seconds! The second approach was to repeat the iteration while doing the same. The third was to copy the desired objects into 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 browsers.
However, splice
doing it in reverse can be much faster if you need to.
source to share