Javascript for..in vs for loop performance

Question

I was clustering around 40000 points using kmean algorithm. In the first version of the program I wrote the euclidean distance function like this

var euclideanDistance = function( p1, p2 ) { // p1.length === p2.length == 3
    var sum = 0;
    for( var i in p1 ){
        sum += Math.pow( p1[i] - p2[i], 2 );
    }
    return Math.sqrt( sum );
};

The overall program was quite slow taking on average 7sec to execute. After some profiling I rewrote the above function like this

var euclideanDistance = function( p1, p2 ) { // p1.length === p2.length == 3
    var sum = 0;
    for( var i = 0; i < p1.length; i++ ) {
        sum += Math.pow( p1[i] - p2[i], 2 );
    }
    return Math.sqrt( sum );
};

Now the programs on average take around 400ms. That's a huge time difference just because of the way I wrote the for loop. I normally don't use for..in loop for arrays but for some reason I used it while writing this function.

Can someone explain why there is this huge difference in performance between these 2 styles?

Answer 1

Look at what's happening differently in each iteration:

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

1. Check if i < p1.length
2. Increment i by one

Very simple and fast.

Now look at what's happening in each iteration for this:

for( var i in p1 )

Repeat

1. Let P be the name of the next property of obj whose [[Enumerable]] attribute is true. If there is no such property, return (normal, V, empty).

It has to find next property in the object that is enumerable. With your array you know that this can be achieved by a simple integer increment, where as the algorithm to find next enumerable is most likely not that simple because it has to work on arbitrary object and its prototype chain keys.

Answer 2

As a side note, if you cache the length of p1:

var plen = p1.length;
for( var i = 0; i < plen; i++ )

you will get a slight speed increase.

...And if you memoize the function, it will cache results, so if the user tries the same numbers you will see a massive speed increase.

var eDistance = memoize(euclideanDistance);  

function memoize( fn ) {  
    return function () {  
        var args = Array.prototype.slice.call(arguments),  
            hash = "",  
            i = args.length;  
        currentArg = null;  
        while (i--) {  
            currentArg = args[i];  
            hash += (currentArg === Object(currentArg)) ?  
            JSON.stringify(currentArg) : currentArg;  
            fn.memoize || (fn.memoize = {});  
        }  
        return (hash in fn.memoize) ? fn.memoize[hash] :  
        fn.memoize[hash] = fn.apply(this, args);  
    };  
}

eDistance([1,2,3],[1,2,3]);
eDistance([1,2,3],[1,2,3]); //Returns cached value

credit: http://addyosmani.com/blog/faster-javascript-memoization/