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:
- 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.
- 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 arrayar[50000000] = 10;// use the array as a huge sparse arrayar.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. Continue reading
There should be no reason that the UI of the whole browser freezes just because some badly written JavaScript code is running. With Chrome we see that at least Google can do better. My hope and my prediction is that we’ll see this in Firefox and Safari in the not so far future as well. I’m not so sure about the Internet Explorer though. Maybe in the year 2012 in IE9.