Loop optimization changing direction

Question

I have read about loop optimization (N.Zakas, Javascript Optimization). There, it was written that using inverse loop for arrays is more optimized than direct loop. It seems completely logical:

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

- checks condition
- increases variable i

for(i = length;i--;)

- checks condition + increases variable i (in one expression)
But, I've got unexpected result for Chrome.

var len = 100000000,
arr = new Array(len),
i = len - 1,
start = new Date(), 
end;

for(i = 0; i < len; i++){
    arr[i] = 1;
}

end = new Date();

console.log(end - start);

Direct loop return result near 4500ms, but inversed loop... 9500ms!

Why?

"is more optimized then direct loop." --- it makes very little sense. — zerkms, Sep 22 '16 at 21:24
N. Zakas was talking about unrolling loops and a technique called Duffs Device - https://en.wikipedia.org/wiki/Duff%27s_device. Use a `while` loop, not `for`. — colecmc, Sep 22 '16 at 21:28
"let say better in scope of performance" --- nope, it's not. — zerkms, Sep 22 '16 at 21:29
You misread Zakas. Based on http://jonraasch.com/blog/10-javascript-performance-boosting-tips-from-nicholas-zakas, his sample code uses a do while loop, NOT a for loop, in the more efficient version. — GendoIkari, Sep 22 '16 at 21:33
consider also that the cost of array access is going to dwarf the cost of a simple integer comparison. — Hamms, Sep 22 '16 at 21:34
"sorry, is this statement (about backwards loop) wrong?" --- it does not contain all the truth: iterating is not what actually is slow and what should be optimised, but the real work that you do in the loop body. In other words - it's like stating that red cars are faster than blue cars. — zerkms, Sep 22 '16 at 21:36
zerkms, thanks I understand but could you explain me why case with for(var i = 0; i < length; i++) faster then for(i = length;i--;)? — Mike Mameko, Sep 22 '16 at 21:46
Different code runs with different pace. Something sometimes is "slower" than something else. But there is nothing in the standard that guarantees that status quo keeps indefinitely: one engine can run it one way, the other - the other way. — zerkms, Sep 22 '16 at 21:47

score 1 · Answer 1 · answered Sep 22 '16 at 21:48

just because there's less code in for(i = length;i--;) doesn't mean less things are getting done; the i still needs to be incremented (or in this case, decremented), and a check still needs to take place (where before it was i < length, it's now i != 0).

I might expect the discrepancy in time to be due to the fact that for(i = 0; i < length; i++) is an incredibly common construct, and is thus very common to optimize (so modern compilers/interpreters have resources invested in explicitly optimizing those). But I'll admit this is speculation.

One case where iterating backwards would probably show a great increase in speed is when you're popping off the contents of an array:

for(i = 0; i < arr.length; i++) arr.splice(i,1); might be removing the first element from the array, and shifting all the other elements backwards to fill its spot under the hood.

whereas:

for(i = arr.length; i--; ) arr.splice(i,1); might need only decrement the length of the array under the hood (much cheaper!).

I'm not sure if this is the optimization you were going for, but the takaway isn't "backwards iteration is faster!" in the general sense.

score 0 · Answer 2 · edited May 23 '17 at 12:19

Yes, iterating an array backwards can be faster. But that's not what you are doing here. You are constructing an array in reverse, and that's quite weird (read: less likely optimised).

If you start assigning the highest indices first, I guess the array starts as a sparse array, which is much less efficient than a contiguous array. Either the assignment itself will be slower for that, or the conversion to a normal array once the engine realises what you are doing.
In contrast, if you start at 0, the engine can grow the array as necessary, and will use the efficient memory representation from the very beginning. Btw, I'd expect arr.fill(1) to be even faster.

Loop optimization changing direction

2 Answers2