Notes on "Javascript as a compilation target"

Florian Loitsch’s gave a great JSConf talk describing how the Dart team at Google is compiling Dart to performant Javascript. Since I am currently working on compiling bytecode to Javascript for Doppio, I watched it with interest and took some notes. For those who prefer reading to watching videos, here is a summary of the talk.

Checking Function Arity

In Dart, calling a method with the wrong number of arguments is an error, but Javascript does not pick a fuss with this. A dynamic assertion on the number of arguments is expensive and unnecessary: the compiler can simply encode the arity of the function in its name. For example,

foo(num a, num b) { ... }

gets compiled to

foo$2: function(a, b) { ... }

Then if the library consumer tries to invoke foo with 3 arguments, it will compile to foo$3(1,2,3), and the Javascript runtime will throw an error.

Unfortunately, this strategy doesn’t quite work for closures, since the compiler cannot control the name of the identifier they are assigned to. Their solution was to compile closures to objects with a call$n method, where n is the number of parameters. Florian remarks that a closure is about the size of a JS object with six fields, so the additional overhead of an object is quite minimal.

Compiling Multiple Constructors

Dart allows multiple constructors per class. Since Javascript only allows for one per class, every call to new X() in Dart gets translated into a plain function call. The called function will call new X() in Javascript, and then run the constructor code on the returned object.

Operator Overloading

Dart allow for operator overloading. This means that a + b in Dart could correspond to an addition of JS primitives (if a and b are Numbers) or a method call like a.add$1(b) (if a and b are objects). The naive way to compile this would be to have .add$1() methods added to the prototypes of the JS primitives. However, this pollutes the global namespace, and it is slow, particularly in non-strict mode, because the JS engine has to box primitive this parameters into full objects. Thus a speedup is gained by making a call to a static function (Florian calls them “static interceptors”) that does the necessary instanceof checks:

$.add = function(x, y) {
    if (isNumber(x) && isNumber(y)) return x + y;
    if (isNumber(x)) throw $.ArgumentError(y);
    if (!isDartObject(x)) return x.add$1(y);
    throw noSuchMethodException(x, "+", y);
}

However, littering the code with all these method calls is still suboptimal, especially since operations on primitives are so common. Fortunately, local and global type inference means that we can usually detect if the operands are primitives, thereby eliminating the unnecessary checks. For the cases where type inference is insufficient, however, the Dart team has another trick: speculative optimization.

Speculative Optimization

The problem with static interceptors is that they usually do more instanceof checks than is actually necessary. For example, since the array dereference operator [] can be overloaded, summing an array with static interceptors requires the following checks:

$.sum = function(state, x) {
    var result = 0;
    for (var i = 0; $.ltB(i, $.get$length(x)); ++i) {
        var t1 = $.index(x, i);
        if (typeof t1 !== 'number') throw $.iae(t1);
        result += t1;
    }
    return result;
}

On every iteration of the loop, $.get$length(x) and $.index(x, i) check if x is an array. If so, they invoke x.length and x[i] respectively; otherwise they call the necessary method. However, only the first check is really needed. With that in mind, we could compile two copies of the function: an ‘optimistic’ one that runs optimally if its argument is a plain JS array, and another one that does all the necessary method dispatches. This gives us

$.sum = function(x) {
    if (!$.isJsArray(x)) return $.sum$bailout(1, x);
    var result = 0;
    for (var t1 = x.length, i = 0; i < t1; ++i) {
        if (i < 0 || i >= t1) throw $.ioore(i);
        var t2 = x[i];
        if (typeof t2 !== 'number') throw $.iae(2);
        result += t2;
    }
    return t2;
}

Where $.sum$bailout is essentially the earlier version of $.sum that we had. Interestingly, this seems very similar to what V8 itself does to optimize code: it looks for method calls in a section of code which always get passed arguments of the same type, inlines the functions that handle those specific types, and inserts a guard check that will cause a bailout if a different type comes along. I am curious as to how exactly these optimizations interact, since there seems to be an overlap in what they do.

The problem with speculative optimization, however, is that it increases the size of the generated code significantly. To mitigate this, the Dart team’s current heuristic is to only speculate on types that are used within loops, limiting the code increase to about 15%. They also employ profile-guided optimization1 to remove optimized methods that are rarely used or that always bail out. Finally, they use tree shaking to eliminate unreachable code paths.

With the abovementioned optimizations, compiled Dart code now runs at 75%+ of the speed of handwritten JS, which is pretty awesome.


  1. Correction: As of October 2012, this has not been implemented, but it’s on the roadmap. See comments.

Related Posts

Jez Ng 29 October 2012
blog comments powered by Disqus