Monday, July 28th, 2008

What’s the Fastest Way to Code a Loop in JavaScript?

Category: Browsers, JavaScript, Performance

<p>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
< view plain text >
  1. // looping a dom html collection
  2. for (var i=0, node; node = hColl[i++];) {
  3.     // do something with node
  4. }

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.:

javascript
< view plain text >
  1. var i = arr.length; while (i--) {}

Take a peak at the test suite.

Related Content:

  • Scaling Your Java EE Applications
    In this article, Wang Yu takes real world cases as examples to explain ways on how to scale Java applications based on his experiences on the...

Posted by Dion Almaer at 10:15 am
17 Comments

++++-
4.1 rating from 31 votes

17 Comments »

Comments feed TrackBack URI

micro optimisations are soooooo 2004

Comment by SchizoDuckie — July 28, 2008

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.

Comment by eyelidlessness — July 28, 2008

I heart reverse while loop :P

Comment by jdalton — July 28, 2008

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.

Comment by jpsykes — July 28, 2008

@SchizoDuckie: It is *not* micro optimization when you consider how long IE takes to loop through arrays and collections.

Comment by MrMuskrat — July 28, 2008

I use reverse loops a couple places where it’s critical. Otherwise, I don’t bother.

Comment by Nosredna — July 28, 2008

@SchizoDuckie: 2004 techniques are completely valid when you need to support a browser from 2001.

Comment by MattCoz — July 28, 2008

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.

Comment by LindsaySmith — July 28, 2008

http://www.devpro.it/examples/loopsbench/

Comment by PaulIrish — July 28, 2008

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

Comment by Flesler — July 28, 2008

I’ve always loved Duff’s Device. It works great and it has a great name.

Comment by Nosredna — July 28, 2008

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..

Comment by V1 — July 29, 2008

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:

1) The best kind of speed optimization is more efficient algorithm design. Before you go nuts trying to squeeze every last ounce of speed out of every statement, take a serious look at the design of your algorithms first. Why? See next point.
2) Speed optimization is usually the last step and the last resort while programming. Code that has been altered explicitly for speed concerns is almost always difficult to read, maintain and overhaul. If you plan on sharing your code with others, this is something you should think about seriously.
3) For most uses of JavaScript, speed optimization is just not necessary. If you are feeling the urge to speed up your code just for the sake of it, don’t. It’s not worth it. If, however, speed is critical to your project, and you can’t seem to get the necessary speed from your design, then your code is a good candidate for speed optimization.

Comment by Menno — July 29, 2008

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.

Comment by Montago — July 29, 2008

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. :)

Comment by waynep — July 30, 2008

OK thanks

Comment by Remedies — November 19, 2008

I think I just discovered the fastest JavaScript loop – in my benchmarks over 500% improvement cross-browser. Read all about it at:

http://milan.adamovsky.com/2011/12/fastest-loop-in-javascript.html

The loop construct looks like this:

var counter = 10;

redo:
while (counter–)
{
… your code …

continue redo;
}

I haven’t tried all the various loop constructs (e.g. for, do, etc) to see which one is the absolute winner – as the main goal was to prove that the use of a label increases the performance dramatically.

Comment by Milan1980 — December 15, 2011

Leave a comment

You must be logged in to post a comment.