Posts Tagged ‘fast loops’

I am currently playing around with a small sideline project that has led me into some interesting research regarding loops in JavaScript. As it turns out not all loops are made equal. On analyzing it, it is kind of obvious, but it is something I had never really thought about. It is important to also weigh up the benefit of the performance gain against maintainability. Typically we are talking a couple of milliseconds over several thousand iterations, but for high performance scenarios like canvas painting, every millisecond counts. Also, I will be focusing on the for loop, there are also some while loop variations to consider.

Anatomy of a For Loop

for ([initial-expression]; [condition]; [final-expression]) {
  // statement
}
  • initial-expression get evaluated on initialization of the loop, note this is an expression, and as such can have multiple comma delimited expressions in it.
  • condition is a Boolean condition that gets tested before entering each iteration of the loop
  • final-expression gets evaluated on completion of each iteration but before the next condition is evaluated.

For – In Loop

for (variable in object) {
  // statement
}

The for in loop, designed specifically for associative arrays, but being used quite a lot lately for its readability. Unfortunately it has pretty poor performance.

For Loop

for (i = 0; i < arr.length; i++) {
  // statement
}

The traditional for loop as used by most to iterate through an array. The one downside to this is that the length of the array is evaluated each iteration.

For Loop with Length Caching


var i, iLen;
for (i = 0, iLen = arr.length; i < iLen; i++) {
  // statement
}

This variation of the for loop will cache the length of the array. Syntax is slightly more complicated, but still pretty intuitive. The benefit of this is that the length of the array is not evaluated each iteration.

Decrementing for loop with no Operators


var i, iLen = arr.length;

for (var i=iLen; i--;) {
  // statement
}

This approach does three optimizations. Firstly it caches the length of the array. Secondly, it uses a decrementing counter to iterate through the array, for whatever reason, decrementing in JavaScript appears to be faster than incrementing. Thirdly, it uses the fact that an assignment statement (in this case the decrement) in JavaScript also evaluates to the value of the assignment, additionally, JavaScript evaluates 0, null, undefined and false as false under a boolean context. We therefore do not need to use the comparison operators of >=, <=, >, <, ==. This is faster because boolean operators are polymorphic and need to do type evaluation on the left and right side of the operator before an evaluation can take place. Since we do away with then altogether, we gain this performance.

As a knee jerk reaction we might question if we even enter the loop on the i == 0 case, however it is important to note we are post decrementing (i– instead of –i), which means the decrement takes place after the boolean evaluation. This takes care of the upper and lower edge cases.

Lastly, this method although fast, does not respect the ordering of the array since we are iterating from last to first.

There is an excellent breakdown with timings on Greg Reimer’s blog.

Advertisements