JavaScript Array Performance Oddities (Characteristics)

Update: We’ve added Opera 10.50 tests and rerun all tests on a MacBook Pro. Further links to the code and the running tests have been added.

When working with a programming language we often make assumptions about the performance of certain language constructs. However, as good engineers we know that whenever we make performance assumptions without measurement we drown a kitten.

When working with JavaScript arrays two independent assumptions are prevalent:

  1. They behave like C/Java arrays. Iteration over the contents and accessing data by index is fast – deleting entries and extending the size is expensive.
  2. They behave like JavaScript objects. Iteration over the contents and accessing data by index is slow – deleting entries and extending the size is fast.

It turns out that depending on the context both assumptions can be true or wrong. More on this later.

JS Arrays

Arrays are one of JavaScript’s core data structures. However, arrays in JavaScript are a totally different beast than arrays in most other languages. In JavaScript arrays are a special case of objects. In fact they inherit from Object.prototype, which also explains why typeof([]) == "object". The keys of the object are positive integers and in addition the length property is always updated to contain the largest index + 1. This supports the second assumption (array == object).

Our Use Case

In our use case we wanted to improve our custom event layer. We store the list of event listeners in an array like this.

listeners.push({
  id: id,
  callback: callback,
  context: self
});

Working with the array is quite efficient but removing items by id is a linear operation. Since arrays are just special cases of objects we thought that rewriting the code to use objects should speed up deletions but maintains all other performance characteristics:

listeners[id] = {
  callback: callback,
  context: self
}

The somewhat unexpected result was that while deletions became faster the overall performance became much worse.

Array vs. Object

So while Arrays and Objects are conceptual almost the same, most JavaScript engines treat them very differently.

var ar = [];
for (var i = 0; i < 500000; i++) {
  ar[i] = i;
};
 
var map = {};
for (var i = 0; i < 500000; i++) {
  map[i] = i;
};

These two loops are almost identical but the first one can be up to 200 times faster (Firefox 3.6) than the second one.

So we know that arrays are treated differently by the JavaScript engines but under which circumstances do the optimizations kick in? To test this we kept the first loop but added the following statements before the loop:

  1. ar[10] = 10; // use the array as a small sparse array
  2. ar[50000000] = 10; // use the array as a huge sparse array
  3. ar.monkey = 10; // treat the array as an object

In addition we tested the same code but initializing the array backwards (counting down from 500,000),  the first time without any modifications and the second time initializing the array with new Array(500000) instead of []. The constructor parameter to Array is supposed to give the JavaScript engine a hint about the expected array size. Here is the outcome of the test runs across various browsers:

Array initialization

The tests code is available on Github. Click here to run the tests locally.

Analysis

The first observation is that there are huge differences between the browsers. The second observation is that depending on the context arrays are either extremely fast or as slow as objects.

  • WebbKit: In WebKit there is a huge difference between objects and arrays. Further it is the only one which can optimize the huge sparse array case. WebKit on the other hand doesn’t like the reverse case at all. To me this looks like a bug in the implementation.
  • Chrome 5 (V8): The V8 JavaScript engine of Chrome does an amazing job. With the exception of the huge sparse array case, all tests took almost the same time. From a performance point of view there is almost no difference between objects and arrays.
  • FireFox: We have tested two FireFox versions. Firefox 3.0 with the old SpiderMonkey engine and FireFox 3.6 with the tracing JIT TraceMonkey. The characteristics of both are very similar with FireFox 3.6 being a lot faster. If the array is used purely as array, Firefox 3.6 is the absolute winner. In all other cases performance degrades to the much slower object case.
  • Opera: Since Opera 10.50 has a completely new JavaScript engine we’ve tested both Opera 10.50 beta and the current stable version 10.10. Both versions show a very different performance characteristic, which shows how much the JavaScript engine has changed. In Opera 10.10 there is almost no difference between objects and arrays. This indicates that Opera does not have any special optimizations for arrays. The overall performance is pretty decent. Opera 10.50 is a huge improvement. The performance is similar to V8 and the common tasks are even faster than on V8. Like V8 it has a peak in the huge sparse array test.
  • Internet Explorer 8: Internet Explorer does a pretty good job in optimizing most of the array cases. However, the overall performance is rather poor (We didn’t test it on the same machine so the numbers cannot be compared directly). Unlike most other JavaScript engines, IE does respect the constructor argument of new Array(count) and is able to optimize the reverse initialization case.

Conclusion

Normal array uses are almost always faster than objects, up to two orders of magnitude in some browser.

  • If in doubt, prefer arrays over objects.
  • Never treat arrays as objects.
  • Never initialize arrays backwards.
  • Sparse arrays behave (performance-wise) like objects.
  • Unusual array usage has a cost.

So far we only tested array initialization. There are many other aspects, which deserve attention but for us this already gave an interesting insight into the way browsers treat our code. Things are not as even as we’d like to think.

Test Setup

IE tests were performed on 3 GHz Pentium D with 2GB RAM with Windows XP. All other tests were run on a MacBook Pro 2.53 GHZ Intel Core 2 Duo with 4 GB of RAM.

10 thoughts on “JavaScript Array Performance Oddities (Characteristics)

  1. Would be interesting to see the same tests in Opera 10.50 since it boast a new JS engine.

  2. Thanks for confirming what I already suspected.

    I’d also like to see the .push version in between these stats. Since push is technically a function call, but might be optimized somehow by the interpreter, I’m curious what the difference is between arr.push(x); and arr[arr.length] = x;

  3. Maybe we’ll do a follow up article, which tests actions like push and iteration as well. In the mean time you can check out the code and easily add the push test yourself.

  4. It looks like the creation of huge sparse array is part of the timing. I feel it’s unfair. The timing should be exactly done on the for loop itself.

  5. [...] the first time without any modifications and the second time initializing the array with new Array(500000) instead of []

    Humm, this doesn’t feel right. AFAIK, the difference between the two approaches for creating arrays is more than just that. Using the “native array” constructor, [], just creates an array, while the class constructor, new Array(), creates an Array class. While the first would be faster for just initializing an array structure (without the class overhead), the latter would be faster for invoking methods on the array variable (as a “native array” will need to be cast to an Array class prior to invoking methods). I recall reading something about that in either the ECMAScript Language Specification or in John Resig’s blog. :-)
    So, in sum and without running any formal tests to support my claims, I’d say that:

    var simpleArray = []; is the fastest approach for simple array creation/manipulation, and should be used together with simpleArray[simpleArray.length] = newArrayItem; (which involves no cast to an object representation)
    var arrayInstance = new Array(); is more appropriate for later invocation of methods such as arrayInstance.push(newArrayItem);
    As usual, the best depends on the intended purpose, else one of the approaches would probably have been marked deprecated already :-)

    @Ain Tohvri
    The above also explains why your test is probably biased and its results should be seen in a different perspective. ;-)

    To me this looks like a bug in the [WebKit] implementation

    I’d seriously recommend creating a thread in the developers mailing list and/or reporting it to the team (in order to clarify as a non-bug or to help the team understanding the issue). ;-)

    Firefox 3.0 with the old SpiderMonkey engine and FireFox 3.6 with the tracing JIT TraceMonkey

    Comparing these two Firefox versions, given the difference in performance between both, is almost unfair. ;-)
    Instead, I’d suggest toggling the value of javascript.options.jit.content through the about:config configuration panel (more details). :-)

    Few nits follow:

    depending on the context both assumptions can be true or wrong

    I’d suggest either using right/wrong or true/false. ;-)

    WebbKit

    Typo (“WebbKit” –> “WebKit”)

    FireFox

    Case issue (“FireFox” –> “Firefox”); More than one occurrence

  6. Pingback: Javascript arrays vs objects | s-anand.net