CODEWITHSUNDEEP
javascriptoptimization
Mike Mameko
Mike Mameko

Reputation: 319

Loop optimization changing direction

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?

Upvotes: 1

Views: 110

Answers (2)

Bergi
Bergi

Reputation: 665486

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.

Upvotes: 0

Phildo
Phildo

Reputation: 1066

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.

Upvotes: 1

Related Questions