JavaScript loop performance - Why is to decrement the iterator toward 0 faster than incrementing

Question

In his book Even Faster Web Sites Steve Sounders writes that a simple way to improve the performance of a loop is to decrement the iterator toward 0 rather than incrementing toward the total length (actually the chapter was written by Nicholas C. Zakas). This change can result in savings of up to 50% off the original execution time, depending on the complexity of each iteration. For example:

var values = [1,2,3,4,5];
var length = values.length;

for (var i=length; i--;) {
   process(values[i]);
}

This is nearly identical for the for loop, the do-while loop, and the while loop.

I'm wondering, what's the reason for this? Why is to decrement the iterator so much faster? (I'm interested in the technical background of this and not in benchmarks proving this claim.)

---

EDIT: At first sight the loop syntax used here looks wrong. There is no length-1 or i>=0, so let's clarify (I was confused too).

Here is the general for loop syntax:

for ([initial-expression]; [condition]; [final-expression])
   statement

• initial-expression - var i=length

  This variable declaration is evaluated first.

• condition - i--

  This expression is evaluated before each loop iteration. It will decrement the variable before the first pass through the loop. If this expression evaluates to false the loop ends. In JavaScript is 0 == false so if i finally equals 0 it is interpreted as false and the loop ends.

• final-expression

  This expression is evaluated at the end of each loop iteration (before the next evaluation of condition). It's not needed here and is empty. All three expressions are optional in a for loop.

The for loop syntax is not part of the question, but because it's a little bit uncommon I think it's interesting to clarify it. And maybe one reason it's faster is, because it uses less expressions (the 0 == false "trick").

Answer 1

I've conducted a benchmark on C# and C++ (similar syntax). There, actually, the performance differs essentially in for loops, as compared to do while or while. In C++, performance is greater when incrementing. It may also depend on the compiler.

In Javascript, I reckon, it all depends on the browser (Javascript engine), but this behavior is to be expected. Javascript is optimized for working with DOM. So imagine you loop through a collection of DOM elements you get at each iteration, and you increment a counter, when you have to remove them. You remove the 0 element, then 1 element, but then you skip the one that takes 0's place. When looping backwards that problem disappears. I know that the example given isn't just the right one, but I did encounter situations where I had to delete items from an ever-changing object collection.

Because backward looping is more often inevitable than forward looping, I am guessing that the JS engine is optimized just for that.

Answer 2

I believe the reason is because you're comparing the loop end point against 0, which is faster then comparing again < length (or another JS variable).

It is because the ordinal operators <, <=, >, >= are polymorphic, so these operators require type checks on both left and right sides of the operator to determine what comparison behaviour should be used.

There's some very good benchmarks available here:

What's the Fastest Way to Code a Loop in JavaScript

Answer 3

I am not sure if it's faster but one reason i see is that when you iterate over an array of large elements using increment you tend to write:

for(var i = 0; i < array.length; i++) {
 ...
}

You are essentially accessing the length property of the array N (number of elements) times. Whereas when you decrement, you access it only once. That could be a reason.

But you can also write incrementing loop as follows:

for(var i = 0, len = array.length; i < len; i++) {
 ...
}

Answer 4

Have you timed it yourself? Mr. Sounders might be wrong with regards to modern interpreters. This is precisely the sort of optimization in which a good compiler writer can make a big difference.

Answer 5

It is easy to say that an iteration can have 50% less instructions. Let’s just compare these two:

for (var i=0; i<length; i++) {
}

for (var i=length; i--;) {
}

When you count each variable access and each operator as one instruction, the former for loop uses 5 instructions (read i, read length, evaluate i<length, test (i<length) == true, increment i) while the latter uses just 2 instructions (evaluate i == true, decrement i). That is a ratio of 5:2. So the latter saves even 60%.

Answer 6

I'm not sure about Javascript, and under modern compilers it probably doesn't matter, but in the "olden days" this code:

for (i = 0; i < n; i++){
  .. body..
}

would generate

move register, 0
L1:
compare register, n
jump-if-negative L2
-- body ..
increment register
jump L1
L2:

while the backward-counting code

for (i = n; --i>=0;){
  .. body ..
}

would generate

move register, n
L1:
decrement-and-jump-if-negative register, L2
.. body ..
jump L1
L2:

so inside the loop it's only doing two extra instructions instead of four.

Answer 7

What about using a reverse while loop then:

var values = [1,2,3,4,5]; 
var i = values.length; 

/* i is 1st evaluated and then decremented, when i is 1 the code inside the loop 
   is then processed for the last time with i = 0. */
while(i--)
{
   //1st time in here i is (length - 1) so it's ok!
   process(values[i]);
}

IMO this one at least is a more readble code than for(i=length; i--;)