Faster Loops and Faster Iterations in Node.js and V8
Wednesday, 29th August 2012, 13:16

So, my first version of Fastworks.js is faster than Connect, but how fast depends on what bits you use. At worst with a full stack I find a bit faster, but there is always room for improvement, so I spent today looking at possible ways to speed up loops.

Now, I'm always looking at interesting ways to use Javascript, and from my old C days I'm often interested in how a higher level language is compiled into a lower one. Now, V8 sits interestingly in a position of being both a high level interpreter and a compiler, so whilst some things you have to benchmark to find out if they are faster, others just simply are.

So after finding a pair of things that have been described as simply faster, I thought I'd try them out and see if they are and by how much. Then armed with that knowledge, implement them that way wherever possible.

For Loops with Arrays

Here is a standard for loop in Javascript, for iterating over an array object, it's pretty basic and surely there is no room for improvement?

    var animals = [ "dog", "cat", "mouse", "wolf", "chicken", "rabbit", "pidgeon" ];
    var totallen = 0;
    
    for (var u = 0; u < animals.length; u++)
    {
        totallen += animals[u].length;
    }

Benchmarking this for enough runs to get a big enough value we can measure, we get:

    Runs: 10000000 Total Time: 221ms, Avg Time: 0.0000221

Now, if we do something slightly different, and don't read animals.length every single time by assigning it to a variable, it runs fractionally faster.

    for (var u = 0, len = animals.length; u < len; u++)
    {
        totallen += animals[u].length;
    }

Gives us:

    Runs: 10000000 Total Time: 215ms, Avg Time: 0.0000215

That does however seem very insignificant though. Perhaps the increase would be more obvious with a larger loop?

    var values = [ ];
    for (var u = 0; u < 1000; u++)
        values.push(Math.random());
    var total = 0;
    
    for (var u = 0; u < values.length; u++)
    {
        total += values[u];
    }

We will run this somewhat less than the other, because it has more work to do. Here our run goes as follows:

    Runs: 1000000 Total Time: 3306ms, Avg Time: 0.003306

Whilst our faster version, which is:

    for (var u = 0, len = values.length; u < len; u++)
    {
        total += values[u];
    }

Gives us a much more pronounced speed increase:

    Runs: 1000000 Total Time: 2641ms, Avg Time: 0.002641

So for anything but very small arrays, you should get a good speed hike by saving the compiler a lookup on the length of the array, by storing it in a variable during the initialisation of the loop.

For... In vs Object.keys

So, you have your object and you want to iterate the properties of it. The standard, most obvious method is this one:

    var animals = { dog: 10, cat: 2, mouse: 3, pidgeon: 1, rabbit: 4 };
    var total = 0;

    for (key in animals)
    {
        total += animals[key];
    }

Is there a quicker way? Well our baseline for this is:

    Runs: 10000000 Total Time: 837ms, Avg Time: 0.0000837

So, let's rewrite JUST the For...In loop to use Object.keys, a method of the Object property which returns an array of enumerable properties for the provided object.

    for (var key = 0; key < Object.keys(animals).length; key++)
    {
        total += animals[Object.keys(animals)[key]];
    }

And to check the results:

    Runs: 10000000 Total Time: 47036ms, Avg Time: 0.0047036

Holy Moly! That's dreadful! Something must be wrong here, and indeed there is. We need to cache this array which the Object.keys() method returns, it is clearly not a good idea to return it every iteration of the loop, and there is no way V8 is optimising that bit for us.

    var keys = Object.keys(animals);
    
    for (var key = 0; key < keys.length; key++)
    {
        total += animals[keys[key]];
    }

The above change drops things down a lot, now giving us:

    Runs: 10000000 Total Time: 4737ms, Avg Time: 0.0004737

However, this is still a lot slower than the for...in loop. Perhaps we should add in our array optimisation we tested at the start of this post.

    for (var key = 0, len = keys.length; key < len; key++)
    {
        total += animals[keys[key]];
    }

Yet in this case, the time doesn't appear to change significantly.

    Runs: 10000000 Total Time: 4795ms, Avg Time: 0.0004795

One last thing that might be worth trying, though I wouldn't expect it to make any difference.

    for (var key = 0, len = keys.length; key < len; key++)
    {
        var thekey = keys[key];
        total += animals[thekey];
    }

And it doesn't really:

    Runs: 10000000 Total Time: 4635ms, Avg Time: 0.0004635

So there we go, one way to iterate faster arrays, and one way to make iterating object properties slower!

The former made sense to me, it seemed logical that V8 checks the length of an array every single loop, because it is possible that the array length could change inside that loop. A variable assignment would in theory be marginally quicker to check, especially as numbers are passed by value across functions and not by reference.

The second, I was unsure about. It looked like an interesting thing that was optimised in V8, where For...In loops weren't. I suspect that either there is a glaring error in my methodology, or the bright sparks at Google optimised them recently. Because Object.keys is really, really slow in comparison, nearly 5.5x slower in fact, so if there is code based on this method around on Node.js servers, it might be time to consider rewriting them.

All of this also highlights another important issue, V8 is a constantly moving goalpost, and the fastest way to code something now might not be that later on.