CODEWITHSUNDEEP
javascriptarraysoptimizationtraversal
Doug
Doug

Reputation: 3312

Array traversal magnitudes faster after removing the first element

After reading the recent smashing magazine article on optimisation, I ran some tests to see what would be the most effective way of "deleting" an element from the middle of one of my arrays.

After running my own tests regarding splicing a value out from the middle of the array vs deleting it/setting it to null, I came across the rather unexpected result that splicing the value out from the array made the array an order of magnitude faster to traverse.

More investigation led me to this.

For some reason, .shift()'ing the first record from the array made it 300 times faster to traverse (the biggest performance being seen in v8, but it seems to be valid for all the browsers I've tried it in).

I doubt I'll abuse this as I don't think the actual traversal is a bottleneck, but does anyone know why this behaviour occurs?

Edit: Incorrect use of jsPerf was the underlying issue here, see my answer below.

Upvotes: 5

Views: 350

Answers (3)

GameAlchemist
GameAlchemist

Reputation: 19294

The performance test is filled with countless errors.
Most important one is to take a sample length of 1000. With today's processor, traversing a 1000 items array is done instantly, and you measure more the time taken by the first array method you call (shift, slice, ...) than the actual array traversal.
So you have to
1) use a much longer array,
2) do the slice/shift/... BEFORE the loops since that's not what you want to measure.

You will then see that there's no magic, and that the array traversal takes the same time for all arrays.

i started in http://jsperf.com/spliced-vs-non-spliced/4, for normal/sliced(0,0) and shift() cases. differences in performance are inferior to measure error.

Upvotes: 1

Doug
Doug

Reputation: 3312

Okay, it turns out this is actually a misunderstanding on my part of how jsPerf works.

The setup section of the script is something that's run at the beginning of each set of loops rather than running it everytime it tries the script.

As shown here the numbers actually turn out as you'd expect.

Upvotes: 0

Joshua
Joshua

Reputation: 3603

So I tried removing the for-loops from each of the functions, comparing the core array functions to the for-loop itself.

http://jsperf.com/spliced-vs-non-spliced/3

The benchmarks are scaling orders of magnitude due to these simple differences in the inner-workings of each function. By simplifying to the bare minimum parts, we are able to isolate the real differences. I doubt based on this that the for-loop is actually traversing any faster or slower - it just appears that way because of the other functions in the test.

Despite the misinterpretation, it is still VERY helpful to shed light on how the Array functions work and how JavaScript developers should be applying them.

Upvotes: 0

Related Questions