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:

• ar[10] = 10; // use the array as a small sparse array
• ar[50000000] = 10; // use the array as a huge sparse array
• 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:
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.