Javascript array and object lookup speeds

I’m currently working on an an implementation of the LZW algorithm in Javascript and one of the things I need to decide to test out is whether using an Array is faster than using an Object for storage and retrieval of items which are indexed numerically. I decided to write a little Javascript test to see which was faster and find out how if the choice of browser made a difference to the relative results.

As you may already know Javascript arrays are pretty much the same as objects and with some subtle differences (see ECMA spec). Most notably, the length properly of an array really does give you the number of items in the array whereas in an object it simply returns the largest index + 1. So technically speaking it shouldn’t make a difference whether you use an array or an object to store your values.

I decided to test out this theory out across a number of browsers. My test would first involve populating an array or object with the first 65536 Unicode characters whereby each array or object index would hold the corresponding Unicode character. My test would then attempt to lookup a random index within the array or object and repeat this many times in order to generate comparable lookup times. I decided to compare the performance of 3 different storage mechanisms initialised as follows:

  • new Object() – an object.
  • new Array() – dynamically sized array.
  • new Array(65536) – statically sized array. Technically it’s size can still increase but perhaps different browsers optimise this differently?

I tried my best to write the test in such a way that it would prevent any “hotspot” optimisations from unfairly biasing any particular storage mechanism. Thus you will see in the code (below) that in each iteration of the test it changes the order in which it tests the storage mechanisms. It also passes the result of each lookup to a variable via a function call in order to get around any aggressive inline optimisations the interpreter/JIT may do (very likely if we were to simply assign the result of a lookup to local variable in the loop which didn’t get used anywhere else).

My test rig is has the following basic setup:

  • Intel(R) Core(TM)2 Duo CPU E7500 @ 2.93GHz
  • Just under 4 GB RAM
  • Ubuntu 10.10, kernel x86_64, 2.6.35-25-generic

100,000 lookups were performed on each storage mechanism in each iteration, with a total of 100 iterations done. The value shown below (in milliseconds) represent the average time taken to execute a single iteration of 100,000 lookups:

new Objectnew Array()new Array(65536)
Chrome 12.0.742.124888
Opera 11.10151515
Firefox 5.0442626

It’s no surprise that Chrome is the fastest. What is surprising though is that on Firefox the Object lookups take at least 1.5 times longer than Array lookups. Also to note is that when I ran the test in Firefox my browser momentarily froze as it was performing the calculations. There also doesn’t seem to be any significant performance difference between dynamically-sized and statically-sized arrays. Since all arrays are dynamic, the Javascript engines don’t rely on any initial size you specify.

In order to test Safari I decided to fire up VirtualBox running WinXP and test all the other browsers too. Here are the results:

new Objectnew Array()new Array(65536)
Chrome 12.0.742.122665
Opera 11.50151515
Firefox 5.0231212
Safari 5.0.5 (7533.21.1)79*22*36*

* Safari popped up a confirmation dialog during the test asking me if I wanted to keep running what seemed to be an responsive script, and I’m not sure how this may affected the results.

I could rewrite the code to be more asynchronous using setTimeout and whatnot but it’s telling to see that Safari’s Javascript engine was unable to cope with it. Safari and Firefox both seem to struggle with Object lookups more so than Array lookup. I don’t have a Windows Vista/7 rig right now so I can’t test out IE 9. However I hope to have results for that up soon. I ran the tests on my home machine which has the following specs:

  • Core 2 Duo E8400 @ 3.00 GHz
  • 2 GB RAM
  • Windows 7 Pro 64-bit

Here are the results:

new Objectnew Array()new Array(65536)
Chrome 12.0.742.122555
Opera 11.50141414
Firefox 5.0171212
Safari 5.1 (7534.50)461111
Internet Explorer 9.0.8112.16421 64-bit484242

So the much-vaunted IE 9 still doesn’t compare to other browsers when it comes to raw performance. Ok, ok, I accept that my test is FAR from conclusive on that matter! but I can only imagine older versions of IE to be much even worse.

So far it seems that Chrome gives the best performance and has the best underlying optimisation for property access. I’m putting this down to V8′s use of “hidden classes”. Opera also seems to have an architecture which allows for similar speeds across the types; it’s just slower than Chrome. For sequential numerical indexes Firefox and Safari do better with Arrays even though they’re still slower than Chrome for overall code execution speed. What’s most striking is the magnitude of the difference for Safari – clearly Objects and Arrays are handled very differently within the Nitro Javascript engine.

The full HTML page containing the Javascript test code follows:

<!DOCTYPE html>
<html>
<head>
    <title>Javascript array tests</title>
</head>
<body>
    <button>Test</button>
    <p id="results"></p>
    <script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jquery/1.6.2/jquery.min.js"></script>
    <script type="text/javascript">
        $("button").click(function(){

        // our storage mechanisms
        var inputs = {
            &quot;Object&quot; : new Object,
            &quot;Dynamic array&quot; : new Array(),
            &quot;Static array&quot; : new Array(65536)
        };

        // build array to hold timings as well as an array to hold the keys of 'input' so that
        var timeTakenMs = {};
        var inputKeys = [];
        for (var i in inputs) {
            timeTakenMs[i] = 0;
            inputKeys.push(i);
        }

        // fill up the storage arrays with initail data.
        for (var val=0; val&lt;65536; ++val) {
            for (var i in inputs) {
                inputs[i][val] = String.fromCharCode(val);
            }
        }

        // a dummy function call, to help prevent inline code optimisations in the inner test loop below
        var tmp = &quot;&quot;;
        var dummy = function(str) {
            tmp = str;
        }

        // how many lookups we will do in each iteration of the tests
        var MAX_LOOKUPS = 100000;
        // the number of iterations of the test to perform in order to get a decent average
        var MAX_ATTEMPTS = 100;

        /*
         The actual test.

         In each iteration of the test we reverse the direction in which we test the storage
          mechanisms. This is to try and prevent any &quot;hotspot&quot; optimisations the Javascript interpreter/JIT
          may try and do from unfairly benefiting the later-tested storage mechanisms.
         */
        var startKey=0, endKey=inputKeys.length-1, incKey = 1;
        for (var attempt=0; attempt&lt;MAX_ATTEMPTS; ++attempt) {
            for (var k=startKey; k!=(endKey+incKey); k+=incKey) {
                var list = inputs[inputKeys[k]];
                var startTimeMs = new Date().getTime();
                for (var val=0; val&lt;MAX_LOOKUPS; ++val) {
                    dummy(list[parseInt(Math.floor(Math.random()*65536))]);
                }
                timeTakenMs[inputKeys[k]] += new Date().getTime() - startTimeMs;
            }
            // reverse loop direction
            startKey ^= endKey; endKey = startKey ^ endKey; startKey ^= endKey;
            incKey = -incKey;
        }

        // show the results
        for (var i in timeTakenMs) {
            // work out average
            $(&quot;#results&quot;).append(&quot;&lt;div&gt;&quot; + i + &quot;: avge time taken for &quot; + MAX_LOOKUPS + &quot; lookups: &quot;
                    + Math.round(parseFloat(timeTakenMs[i]) / MAX_ATTEMPTS) + &quot; ms&lt;/div&gt;&quot;);
        }


    });
&lt;/script&gt;

</body> </html>