Saturday, March 31, 2007

The attack of the forEach loops?

Many library writers are (finally) tuning into library performance and speed optimization. DOM query libraries are getting pretty good, but I still find that most libraries have made the very grave mistake of making a forEach-like structure available.

Sure, Firefox has a fast native implementation, but for the great majority of browsers out there, implementing forEach in javascript is a huge performance hit. And not only that, today I found out that even the plain old for loop used by many of these implementations is slow as well.

Here's my benchmark code and results:

Code

var bm=function(action,load) {
 for (var i=0;i<load;i++) action+=action+action;
 var t0=now();
 eval(action);
 var tf=now();
 return tf-t0;
};
var div=document.getElementById("output");//this is my output div, just add one to the page.
var a="var a=[0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9],b=function() {return this;};"
var load=6;
var test = function() {
 var resultsets="";
 for (var i=0;i<15;i++) {
  var results=[];
  results.push(bm(a+"for (var i=0,l=a.length;i<l;i++) b();",load));//for
  results.push(bm(a+"var i=a.length;while (--i!==0) b();",load));//while backwards
  results.push(bm(a+"var i=-1,l=a.length-1;while (++i!==l) b();",load));//while forward
  resultsets+=results+"<br>";
 }
 div.innerHTML=resultsets;
};

Results

note: I'm just posting the results from my final algorithms, tested in Opera.

forwhile backwardswhile forward
1567878
787279
936394
787878
787878
786378
936378
947878
787878
797878
787878
946279
936394
787878
787878
132610781204

The last column shows the sum of all times. The forward while loop performed 9.2% better than the for loop, and the backwards while loop performed 18.7% better.

Breakdown

Things that I noticed while testing and trying different looping algorithms:

  • The number of declared variables matter. If possible, use only one.
  • Using array.length in the exit condition instead of assigning it to a variable first (i.e. var length = array.length) slows things down a lot.
  • The operator in the exit condition matters. The === and !== operators are faster than <, > and variations.
  • Math operators for the incrementation don't seem to affect the speed of the loop. --i takes the same time as ++i.

Final thoughts

One last phenomenon that I think is worth mentioning on this whole forEach talk: many developers have the tendency of "latching" onto familiar practices. What this means is that updating existing functionality gets done using a structured programming approach. So, it's not uncommon to see things like this:

//the old version
array.forEach(doSomething);
//becomes
array.forEach(function(i) {doSomething(i,someNewParam)});

Notice the double function call? In browsers without native support for Array.forEach, this also needs to internally call a Function.call() for every iteration. Definitely not cheap. Use it in the core of a nifty popular library for maximum damage amplification.

Bottom line: the forEach pattern is redundant and expensive. And now, with the talks of centralizing javascript distribution, (like Yahoo is doing with YUI) the code footprint argument is becoming obsolete too.

Note to self: my getElementsByClassName function needs to be updated now =P

3 comments:

  1. Hello,


    this ist a nice Explication.
    You self my Day...

    Thx..

    ReplyDelete
  2. I came via Blogsearch to this Article! Thank you for the Informations :)

    Great work!

    ReplyDelete
  3. It would be nice to see you replicate this test across all possible browsers without using the evil eval...

    ReplyDelete