Monday, July 28th, 2008
What’s the Fastest Way to Code a Loop in JavaScript?
Category: Browsers
, JavaScript, Performance
Gregory Reimer, frontend engineer for sun.com, has written a barrage of tests to answer the question What's the Fastest Way to Code a Loop in JavaScript? specifically for large data sets:
I built a loop benchmarking test suite for different ways of coding loops in JavaScript. There are a few of these out there already, but I didn't find any that acknowledged the difference between native arrays and HTML collections. Since the underlying implementations are different (HTML collections for example lack the pop() and slice() methods, etc), benchmarks that don't test against both are probably missing important information.
My suspicions were confirmed. Accessing the length property is more expensive on HTML collections than on arrays, depending on the browser. In those cases, caching it made a huge difference. However, HTML collections are live, so a cached value may fail if the underlying DOM is modified during looping. On the other hand, HTML collections will never be sparse, so the best way to loop an HTML collection might just be to ignore the length property altogether and combine the test with the item lookup, since you have to do that anyway:
JAVASCRIPT:
If you take a look at the results you will see that in general, reverse while loops are the fastest way to iterate a basic collection, e.g.:
-
-
var i = arr.length; while (i--) {}
-
Take a peak at the test suite.
micro optimisations are soooooo 2004
The clearest, most obvious code is almost always the best optimized, as it doesn’t leave as much room to introduce and hide bugs and bottlenecks.
I heart reverse while loop :P
I always thought the fastest was the Duff.
http://home.earthlink.net/~kendrasg/info/js_opt/jsOptMain.html
But it’s a total nightmare to implement.
I never really understood why the reverse while didn’t catch on more. It’s easy to use, doesn’t really need any more code and it much faster than a regular for loop.
@SchizoDuckie: It is *not* micro optimization when you consider how long IE takes to loop through arrays and collections.
I use reverse loops a couple places where it’s critical. Otherwise, I don’t bother.
@SchizoDuckie: 2004 techniques are completely valid when you need to support a browser from 2001.
Whats also interesting in certain situations is that looping through a linked list is faster than looping through an array.
Eg something like
while (node.next) {
.. process node.item …
node = node.next
}
Also, you can make sure that you always use the same kind of loop over arrays by providing functional style mapping functions eg:
Arrays = {
// implement array loop using downwards while
loop: function(ary, lambda) {
var l = ary.length;
var i, n;
if (l > 0) {
i = l;
do {
n = l - i;
lambda(ary[n], n);
i -= 1;
} while (i);
}
}
}
eg:
Arrays.loop([1,2,3], function(i) { console.log(i) });
This way you can keep the loop code seperate so it can be improved or modified. You lose the ability to break out of a loop half way through but this can be achieved with return values or exceptions.
http://www.devpro.it/examples/loopsbench/
I made a benchmark of my own, one of them is about loops.
I wrote a couple of adapted versions of Duff’s device, some based on existing code.
Here you can see the benchmarker: http://benchmarker.flesler.com/
The test is called ‘loops’.
Cheers
I’ve always loved Duff’s Device. It works great and it has a great name.
ok… mili sec savings can be good.. BUT nobody actually tested memory usage… What technique requires the less memory from the system..
Now that would be usefull, because applications grow bigger and the memory get more stuffed..
I partially agree with SchizoDuckie; in my experience it takes a loooong time of optimizing the actual architecture and code before this sort of optimization is worth the effort. Thankfully, the author agrees:
Hmm… I gained a lot, using optimal algorithms for my two most extensive JS applications…
http://www.mdk-photo.com/Vector3_2 (went from 20ball to 50 at the same fps)
http://www.mdk-photo.com/Editor (doing the impossible every day i code on it…)
I’ve read : http://www.devwebpro.com/devwebpro-39-20030514OptimizingJavaScriptforExecutionSpeed.html
and every application since, executes faster now !
Reverse loop is as good as a For(Assignment) imo.
for best readability and performance I’ve been going with:
for (var i=0, len=arr.length; i<len; i++) { }
If I need to loop through 1000 item array, 100 times (which is rare if never) I’ll start using reverse whiles. :)
OK thanks