JavaScript Array-Looping Speed Test
It’s been said over and over again that the standard method of looping through array items in JavaScript (the for loop) is not very efficient. I wanted to check this for myself so I ran three implementations of array loop through the firebug profiler. While testing only in FireFox 4 is certainly not anything resembling scientific, I believe the drastic differences between execution times is quite telling, and can be considered definitive.
Update
After I wrote the examples here, I’ve done some more tests, and it seems that declaring the variables outside the loops (any loop) will speed it up a notch. It’s not a big deal, but it’s good to know. Also, you should do this anyway, to avoid some other unrelated headaches, preferably at the very top of the function in which the loop appears.
Looping through arrays
JavaScript arrays, like arrays in most computer languages are 0-indexed list of elements. Arrays in general, are very efficient and cheap data type. They can be looped efficiently, and quickly, and consume very little memory. But not in JavaScript. JavaScript arrays are implemented as special objects whose properties are numbers that represent the element indices. This makes JavaScript arrays look like oil tankers compared to Navy SEAL rubber boats that arrays are in other languages.
With this kind of handicap to begin with, we are in need of an efficient way of going through elements one by one.
Normal for-loop
The usual way people learn to loop through array elements is using a for loop.
a = [1,2,3,4,5,6,7,8,9]
for (var i = 0; i < a.length; i++) {
document.write(a[i]);
}
// Results in '123456789'
This is the slowest method. You should always avoid it. I’ve already mentioned that JavaScript arrays are oil tankers. Now imagine running through the tanker trying to number all the sailors on the thing. Sounds like a lot of footwork. Well, that’s what a.length is: a lot of footwork. If you evaluate the lot of footwork each iteration, you will end up with a humongous amount of footwork. And sore feet.
Length-caching for loop
A slightly better way to do the for loop (actually a lot better way) is to cache the length:
for (var i = 0, l = a.length; i < l; i++) {
document.write(a[i]);
}
In the above case, a.length is evaluated only once, so the loop should be much faster. It has also been argued that the i < l test is quite expensive when in a loop.
Reverse for loop
To get rid of this test, we can do the for loop like this:
for (var i = a.length, l = a.length; i; --i) {
document.write(a[l - i]);
}
The trick is to use the value of i itself as the test. Since a value of 0 is a falsy (treated like false), and since we are actually decrementing i instead of incrementing it as in previous examples, i will eventually become 0, and therefore, false, and the loop terminates there. The reason we have two variables initialized with the value of a.length is that we need the intact length of the array to extract items in order.
Do while loop
The above can be done in two more ways using do-while loop, and while loop.
var l = a.length,
i = a.length;
do {
document.write(a[l - i]);
} while(--i);
At first glance, the syntax seems simpler than with the last for loop, but it’s actually exactly the same thing, formulated a bit differently.
While loop
var l = a.length,
i = a.length + 1;
while(--i) {
document.write(a[l - i]);
}
Again, very similar, but with a catch. Entering the while loop, we decrement the i by one. So by the time we reach the last element of the array, we’ll be short by one element. That’s why we add one to the initial value of i. Otherwise, it does more or less the same thing.
The test
Before we begin, I encourage you to check out the JavaScript array loop speed test suite (ok, so it’s not exactly a suite, just 5 functions), and profile the code yourself with your favorite JavaScript debugger, and then come back here.
For those that are using Firebug, there’s a catch. The lower-left quadrant on Jsfiddle is actually an iframe. So if you profile the whole page, you will get a bunch of MooTools functions that are in charge of running the code. To see the actual code, you will right-click the result area, and select Inspect Element from the context menu. This will open firebug for that iframe, and you will be able to run the profiler on the code that is being executed.
Sorted by Own time column in Firebug (time it took to execute each function), I get that the tests are roughly ordered by speed ascending (test() is slowest, test4() fastest).
The while-loop method, and reverse-for-loop are by far the fastest, with do-while-loop close behind them. Length-caching-for-loop took a bit less than double the time of the first three runners. Finally, the normal for loop is an eye-popping 26 times slower than the fastest method.
UPDATE: After a few more rounds of tests, I’ve noticed that the three decrementing variants (reverse for loop, do-while loop, and while loop) change speed rankings. So my guess is that any one of those three is a good choice, and none is decidedly faster than the other. There seems to be a slight bias towards reverse for loop, but nothing conclusive.
Because it’s much easier to adapt your existing for loop code, I suggest you use the reverse for loop in your code. You can adapt your existing code with little effort like this:
for (var i=0, idx = a.length, l = a.length; idx; --idx) {
i = l - idx;
// Note that we don't use the i as the counter, but idx
// We calculate the correct index and assign it to i, and
// rest of your code can remain the same as before.
}
I hope you found this helpful. I did, for sure.
