Wednesday, June 8, 2011

javascript loop performance

javascript has several types of loops

1. for loop
Probably it is the most usual loop in javascript:
for (var i=0; i<items.length; i++) {

2. while loop
var i=0;
while(i < items.length) {

3. do while loop
this loop ensures the loop body gets executed at least once.
var i=0;
do {
} while (i < 10);

The above three loop types are quite common in other language as well. Here is another javascript specific loop:

4.for-in loop
for (var i in items) {
this loop enumerates the named properties of any object.


Only one loop is significantly slower than the others: for-in loop. It is slower due to the fact that each iteration results in a property lookup either on the instance or a prototype. Each time the loop is executed, the 'i' is filled with the name of another property that exists on the object 'items' until all properties have been returned. The returned properties are either on the object instance or inherited through the prototype chain. So, unless you have to iterate over object properties, for-in loop should not be used.

Except for-in loops, other loop types are so close in performance that it doesn't worth trying to determine which is faster. The choice should be based on your requirement instead of performance.

So if loop type doesn't matter in performance, what does? Two issues:
1. Tasks that must be done in loop, the obvious one is the body of the loop: handle(items[i])
2. Number of iterations, very obviously.

When it comes to issue 1, it is not as that simple as it looks. Let's check through loop type 1 in details.

for (var i=0; i<items.length; i++) {handle(items[i]);}

1. The loop first initiate a variable i=0. Fortunately, this task only has to be done once.
2. items.length is a property lookup that has to be done every time in the loop
3. i < items.length is a comparison that has to be done every time
4. (i < items.length) == true is another comparison every time
5. one increment operation i++ every time
6. array lookup every time: items[i]
7. handle(items[i]) every time.

Such a simple loop actually contains a lot of operations. The performance of this loop largely depends on handle(items[i]) function. But, reducing the total number of operations can still help in performance.

1. we don't want to do property lookup, items.length, every time, due to the fact that it is quite unlikely that the length could be changed during the loop. So, we can just do it once:

for (var i=0, length=items.length; i<length; i++){handle(items[i]);}

2. i < items.length, (i < items.length) == true are comparisons every time. We can try to reduce the comparisons by reversing the loop order. Usually, the order in which item is handled is irrelevant to the task. So, we can start the loop from the last item to the first item:

for (var i=items.length; i--;){handle(items[i]);}

In this way, we now simply compare 'i' against zero. Control conditions are compared against the value true, and any nonzero number is treated as true automatically, while zero is equivalent of false. So two comparisons(Is i less than the total items.length? Is that equals to true?) has been reduced to one comparison(Is the value true)

Finally, function based iteration, forEach. It is introduced in 4th editon of ECMA-262. 
items.forEach(function(value, index, itemsArray){handle(value);});

You may already see some implemetations in popular js libraries. One example is Prototype's items.each().

Comparing function based iteration with basic loop types in performance is not that fair, at least that is what i think. Because in some situations function based iteration is very handy and convenient. But if we have to compare, then, as you may already expect, function based iteration is quite slower than basic loop types, due to the overhead that an extra method has to be called every time.

No comments: