About Me

Curriculum Vitae

A brief list of my current skill set

Bloggybits

Object Oriented Programming for Javascript Dummies - Part 1
Tuesday, 30th October 2012, 16:01

Not using OOP? Are you mad?

Strange Windows Errors and a Bowser in My Event Log
Wednesday, 24th October 2012, 11:10

It's like my own DailyWTF round-up!

Why Do People Come Here?
Monday, 15th October 2012, 15:47

They come to look at porn!

Idiot thinks Raspberry Pi Unsuitable for Education
Tuesday, 2nd October 2012, 15:24

Dumbest thing I've read since...

Upgrading to PostgreSQL 9.2 on CentOS 5
Tuesday, 25th September 2012, 14:52

It's easy as PI!

Fare Ye Well Work Email You Have Served Me Well
Monday, 17th September 2012, 14:36

Cause of death too much spam

Forest Racer - A HTML5 Game in Under 13K
Tuesday, 11th September 2012, 20:46

Including all assets, but only when zipped

Entering a 13k HTML5 Game Competition
Tuesday, 4th September 2012, 16:31

I'm so tempted to have a go at this

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

Is Object.keys faster than For...In?

And the Fastworks.js framework is Born!
Wednesday, 22nd August 2012, 16:23

Well I'm excited, even if you aren't

Libxmljs Update on CentOS 3.8 throws an SELinux Wobbley Fit
Monday, 20th August 2012, 15:40

The right way to fix this sort of issue

TV Land Doesn't Understand Technology
Friday, 17th August 2012, 17:09

Or maybe it does and thinks we don't?

Yet More Benchmarking - Function Chains vs Object Chains
Wednesday, 15th August 2012, 13:34

Working towards a faster Node.js framework

More Benchmarking in Node.js and V8
Tuesday, 14th August 2012, 12:19

Working out the fastest way to route

MinnaHTML.js Benchmarking for Speed in Node.js
Monday, 13th August 2012, 17:55

Don't believe it, test it

Projects and Sillyness

MAME Cabinet Diary

How I built my own arcade cabinet

Loading Screen Simulator

I don't miss the ZX Spectrum, I still use it!

The Little Guy Chat Room

It's a Pitfall inspired chat room

GPMad MP3

A fully featured MP3 player what I wrote

GP Space Invaders

My first little emulator

GP32 Development Page

Some info and links about this cute little handheld

Disney Nasties

Uncensored images, you must be 18 to view them

Minna's World

The cuttest fluffy puppy in the world

Diary of a Hamster

Learn about how hamsters think, first hand

Utilities

Time Calculator

A simple little online utility for working out how many hours to bill a client

A Few Links

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.

Comments

posted by Joern on Friday, 13th June 2014, 11:34

Hey, I know that this post is quite old but have you seen the incredible performance boost at http://jsperf.com/object-keys-iteration/46

posted by DKL on Tuesday, 17th March 2015, 10:41

Many thanks for figuring this out! Very helpful.

Add Your Own Comment