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. Continue reading

Saying Farewell

After more than three years as full time qooxdoo developer I (Fabian) am going to leave 1&1 at the end of March. Looking back it is amazing how much qooxdoo has evolved.

  • When I came to 1&1, the qooxdoo core team consisted only of Alex, Andreas, Sebastian and me. Today the qooxdoo team has eight full time developers.
  • IE7 just came out and we were just starting to experiment with Safari. Today we have HTML5, CSS3, the mobile web and more.
  • In 2006 JavaScript was still regarded as a toy language. Today we have JavaScript everywhere. On the Phone, on the Desktop, on the Server and of course in the browser.
  • qooxdoo itself has come a pretty long way as well. We’ve added the OOP layer with version 0.7. In version 0.8 we reimplemented the widget and layout system from scratch. This all resolved into qooxdoo 1.0 which we released last December.
  • The perception and adoption of qooxdoo has changed as well. From the little known framework with a weird name, qooxdoo has grown up to be recognized as one of the top rich client JavaScript frameworks. Inside of 1&1 it has become the basis for most of the JavaScript development including the impressive gmx.com mail client.

The team is awesome, the community is extremely nice and qooxdoo is on a very good way – why on earth would someone leave this behind? One reason is that qooxdoo is leaving the rough waters of creative and sometimes chaotic development and entering the calm waters of a stable business approved toolkit. Deep in my heard I’m still a creator, who wants to build stuff. I’m not as good in maintaining things. That’s why it’s time for me to move on.

I’m really proud and thankful for being part of the team. I know qooxdoo can do without me – time will tell if I can do without qooxdoo.

Thank You

Mouse Capturing

Yesterday we have found solution for a really annoying problem. The problem was that we didn’t receive mouse events during drag operation in IE and Firefox if the cursor left the browser viewport. This was especially a problem for our scroll bars. Since qooxdoo 0.8 we render scroll bars using qooxdoo widgets. If the scrollbar was near the browser’s edge and the user dragged the scroll bar knob outside of the browser window, scrolling just stopped. Thanks to qooxdoo user Petr Kobalíček, who pointed out that other frameworks can handle this situation, this issue could finally be resolved.

You can see the difference in this screen cast:

A basic building block for drag operations in qooxdoo is a concept called mouse capturing. It was fist introduced by Microsoft with Internet Explorer 5 but unfortunately no other browser vendor has implemented it (MSDN). Mouse capturing allows web developers to tell the browser that all mouse events should be dispatched on the same DOM element. This is especially useful for drag operations or menus, when all mouse events should go to the dragged element even if the mouse cursor is not directly above the element.

This can be easily demonstrated by looking at a simplistic drag and drop implementation:

function draggable(element) {
    var dragging = null;
 
    addListener(element, "mousedown", function() {
        var e = window.event;
        dragging = {
            mouseX: e.clientX,
            mouseY: e.clientY,
            startX: parseInt(element.style.left),
            startY: parseInt(element.style.top)
        };
        element.setCapture();
    });
 
    addListener(element, "losecapture", function() {
        dragging = null;
    });
 
    addListener(element, "mousemove", function() {
        if (!dragging) return;
 
        var e = window.event;
        var top = dragging.startY + (e.clientY - dragging.mouseY);
        var left = dragging.startX + (e.clientX - dragging.mouseX);
 
        element.style.top = (Math.max(0, top)) + "px";
        element.style.left = (Math.max(0, left)) + "px";
    });
};
 
draggable(document.getElementById("drag"));

open demo (works only in IE). While dragging try moving the cursor out of the browser window.

In the mousedown handler the current mouse and element position is stored in a drag session and then mouse capturing is started. From this point on all mouse events will be dispatched on the dragged element even if the mouse cursor is not over the element. The mouse can even leave the viewport as long as the mouse button is pressed. Mouse capturing ends when the mouse button is released, an alert box is opened or the browser loses focus. Note that all listeners can be attached directly to the element.

To get the same behavior in non IE browsers is a little bit tricky because none do support mouse capturing. For this reason we cannot attach the mousemove listener to the dragged element. Instead we need to attach it to the document. Since mouse events bubble up the DOM tree the document will receive all move events. One problem with this approach is that while bubbling up an intermediate event listener might manually stop the bubbling by calling stopPropagation. In this case the event would never reach the document and the drag would be broken. To fix this we have to attach the listeners to the event capturing phase. This can be easily confused with mouse capturing but it has nothing to do with it. In the W3C DOM event model bubbling events have two phases. First in the capturing phase the event bubbles from the document down to the event target. Afterwards in the bubbling phase it bubbles back from the target to the document. The bubbling phase is much better known because IE doesn’t support the capturing phase at all. If the mousemove listener is added to the capturing phase of the document no other listener will be able to block it.

function draggable(element) {
    var dragging = null;
 
    addListener(element, "mousedown", function(e) {
        var e = window.event || e;
        dragging = {
            mouseX: e.clientX,
            mouseY: e.clientY,
            startX: parseInt(element.style.left),
            startY: parseInt(element.style.top)
        };
        if (element.setCapture) element.setCapture();
    });
 
    addListener(element, "losecapture", function() {
        dragging = null;
    });
 
    addListener(document, "mouseup", function() {
        dragging = null;
    }, true);
 
    var dragTarget = element.setCapture ? element : document;
 
    addListener(dragTarget, "mousemove", function(e) {
        if (!dragging) return;
 
        var e = window.event || e;
        var top = dragging.startY + (e.clientY - dragging.mouseY);
        var left = dragging.startX + (e.clientX - dragging.mouseX);
 
        element.style.top = (Math.max(0, top)) + "px";
        element.style.left = (Math.max(0, left)) + "px";
    }, true);
};
 
draggable(document.getElementById("drag"));

open demo

If a mouse button is pressed and dragged out of the browser window, Firefox will continue to fire mouse events on the document. Opera, Safari and Chrome are a little more tolerant and fire the events on the document.documentElement as well. For this reason we must attach the listener to the document and not the document.documentElement or document.body.

Because if its usefulness we emulate the IE mouse capturing behavior in our cross browser event handling layer. The fix for IE was to call the native setCapture method. Since we used the emulated mouse capturing support for IE as well we’ve lost the side effect of receiving mouse events when the mouse left the browser window. In Firefox we just had to switch the event target from document.documentElement to document in our generic mouse event handler. With both fixes in place, mouse capturing and drag and drop operations now really work as expected on all supported browsers.

Global Error Handling

In object oriented programming it is common practice to throw exceptions for known error conditions. However, JavaScript lacks one essential feature to make consistent use of exceptions practical: There is no way have a fallback handler, which receives all exceptions that are not caught in the application code. The result is that uncaught exceptions show up in the browser and depending on the user’s preferences might even pop up an error dialog. Furthermore, in production systems it is often desirable to log all errors and send them back to the server to monitor the application.

Most browsers provide the window.onerror hook, which is supposed to act as a fallback error handler, but since it is not standardized, the implementations differ significantly.

window.onerror = function() {
  console.log(arguments);
  return true; // hide error from browser
}
throw new Error("Error");

onerror_firebug

Note that only the error message but not the exception object is available. The second and third parameters point to the URL, which raised the error and an error code. Both additional parameters are missing in Safari. Opera doesn’t support onerror at all.

Since we can’t rely on onerror, we decided to provide our own implementation of a fallback error handler. The basic idea is to wrap all JavaScript entry points with a try/catch block and call a predefined error handler on all exceptions. An entry point is a function, which is called directly by the browser. DOM event handlers or callbacks passed to window.setTimeout or window.setInterval are such entry points:

qx.event.GlobalError.setErrorHandler(function(ex) {
  console.log(ex);
});
 
window.setTimeout(qx.event.GlobalError.observeMethod(function() {
  throw new Error("Error");
}), 100);

globalerror_firebug

This time the error handler receives the real exception instance and not just the error message. qooxdoo already abstracts most of this low level event handling code so users won’t have to bother with wrapping their own methods (e.g. when using qx.Timer instead of a native window.setTimeout). For example all qooxdoo event handlers are already wrapped.

The implementation of observeMethod is a variation of a technique first documented by Nicholas Zakas:

observeMethod : function(method)
{
  if (qx.core.Setting.get("qx.globalErrorHandling") === "on")
  {
    var self = this;
    return function()
    {
      if (!self.__callback) {
        return method.apply(this, arguments);
      }
 
      try {
        return method.apply(this, arguments);
      } catch(ex) {
        self.__callback.call(self.__context, ex);
      }
    };
  }
  else
  {
    return method;
  }
}

The wrapped method is only enclosed by a try/catch block if an error handler is defined and the setting qx.globalErrorHandling is enabled. This is an important detail because the try/catch block can mess up the stacktrace and thus make the code harder to debug. In these cases the “normal” behavior can be restored by simply setting the error handler to null.

The global error handling is a replacement of the dysfunctional window.onerror and will be part of the next qooxdoo 0.8.3 release.