Thursday, March 28, 2013

Why dart2js produces faster JavaScript code from Dart

The dart2js compiler, which converts Dart to JavaScript, now produces smaller and faster code thanks to its global type inferencer. By analyzing the entire program, the compiler can eliminate bailouts and redundant checks, resulting in code that runs faster on modern JavaScript engines.

As evidenced by the graph below, the performance of the code generated by dart2js (the purple line) now slightly outperforms the original hand-written benchmark code (the gold line). The Dart VM, which natively runs Dart code, is the top line. High is better in this benchmark (Dart code, JavaScript code).

Taken on 2012/03/28. From dartlang.org/performance

Type inferencing helps performance

Nicolas Geoffray, engineer on dart2js, has been working on the beginnings of the global type inferencer. In a recent interview (video) he showed examples of the original Dart code, the previously generated JavaScript code, and the new more optimized JavaScript code.





Code gets smaller, faster

For reference, here is a snippet of raw Dart code from the original benchmark:


 void addConstraintsConsumingTo(Variable v, List<Constraint> coll) {  
  Constraint determining = v.determinedBy;  
   for (int i = 0; i < v.constraints.length; i++) {  
    Constraint c = v.constraints[i];  
    if (c != determining && c.isSatisfied()) {  
     coll.add(c);  
    }  
   }  
 }  

Previously, the dart2js compiler would output this JavaScript code (for why, see Preserving Semantics below):


 addConstraintsConsumingTo$2: function(v, coll) {  
   var determining, i, t1, c;  
   determining = v.get$determinedBy();  
   i = 0;  
   while (true) {  
    t1 = $.get$length$as(v.get$constraints());  
    if (typeof t1 !== "number")  
         return bailout(1, v, coll, i, determining, t1);  
    if (!(i < t1))  
     break;  
    t1 = v.get$constraints();  
    if (t1.constructor !== Array)  
     return bailout(2, v, coll, i, determining, t1);  
    if (i >= t1.length)  
     throw $.ioore(i);  
    c = t1[i];  
    if (!$.$eq(c, determining) && c.isSatisfied$0() === true)  
     coll.push(c);  
    ++i; 


Since revision 20130 of dart2js, the JavaScript output now looks like this:

  addConstraintsConsumingTo$2: function(v, coll) {  
   var determining, t1, i, c;  
   determining = v.determinedBy;  
   for (t1 = v.constraints, i = 0; i < t1.length; ++i) {  
    c = t1[i];  
    if ((c == null ? determining != null : c !== determining)  
      && c.isSatisfied$0()) {  
     coll.push(c);  
    }  
   }   

The second version is obviously smaller, and runs faster in part because:

  • bailout code is removed
    • ex: no more return bailout(1...
  • type checks are removed
    • ex: no more typeof t1 !== "number"
  • the while loop is replaced by a for loop
  • function calls are replaced by field access
    • ex: v.get$determinedBy() is now v.determinedBy


Preserving null semantics

Remember that Dart is not just a different syntax for JavaScript, but is itself a new language and libraries with their own semantics. These semantics need to be preserved when compiled to JavaScript, which helps to explain why the original JavaScript code was so verbose. However, the global type inferencing can now help to reduce the verbosity, without changing the semantics of the operations.

Treatment of nulls is a good example of differing behavior between Dart and JavaScript. Consider this code snippet:


 var x = null;  
 var y = 1;  
   
 var results = x + y;  
   
  // Dart throws NoSuchMethodError because the null object  
  // doesn't define the + operator.  
  // However, JavaScript sets results to 1.


Many developers appreciate being told when they try to use a null variable, and thus like the NoSuchMethodError. The dart2js compiler needs to ensure this behavior is retained. However, if dart2js can determine during program compilation that x is never null, then dart2js can eliminate the extra checks and just emit the straightforward JavaScript code.

[Disclaimer! What follows is a snapshot of dart2js's behavior on 2013/03/28.]

Here is an example. Consider the following code:

 var x = null;  
 var y = 1;  
   
 var results = x + y;
 print(results);

Notice how x is null, which forces dart2js to emit this code:


 $.main = function() {  
  $.Primitives_printString($.toString$0($.JSNull_methods.$add(null, 1)));  
 };


However, if x is not null, dart2js can generate intelligent code that eliminates the null handling:


 $.main = function() {  
  $.Primitives_printString($.JSInt_methods.toString$0(3));  
 };  


Notice how dart2js inlines the addition into the literal value 3.

Here is a more complex example. Pay close attention to the complete lack of type annotations. This shows that dart2js performs its type inferencing based on how objects are used, not on how variables are annotated.  (Remember that Dart is an optionally typed language, so the type annotations are ignored at runtime. However, as you can see, the runtimes still make intelligent decisions.)



 add(x , y) {  
  var z = x * 2;  
  return z + y;  
 }  
   
 main() {  
  var x = null;  
  var y = 1;  
   
  var result = add(x, y);  
   
  print(result);  
 }  


Because x is null, dart2js outputs the following JavaScript code:


 $.main = function() {  
  $.Primitives_printString($.toString$0($.$add$ns($.JSNull_methods.$mul(null, 2), 1)));  
 };  
   
 $.$add$ns = function(receiver, a0) {  
  if (typeof receiver == "number" && typeof a0 == "number")  
   return receiver + a0;  
  return $.getInterceptor$ns(receiver).$add(receiver, a0);  
 };  


Now consider this code, where x is not null:


 add(x , y) {  
  var z = x * 2;  
  return z + y;  
 }  
   
 main() {  
  var x = 2;  
  var y = 1;  
   
  var result = add(x, y);  
   
  print(result);  
 }  


The dart2js compiler knows that both x and y are not null, and generates this code:


 $.main = function() {  
  $.Primitives_printString($.JSInt_methods.toString$0(5));  
 };  


Pretty impressive, if I do say so! Notice how dart2js inlines the call to add, and all the math, down to the literal number 5.

One more example of how dart2js can look at nulls. Consider this code, which explicitly checks for null parameters and throws an exception:


 add(x , y) {  
  if (x == null || y == null) throw new ArgumentError('must not be null');  
  var z = x * 2;  
  return z + y;  
 }  
   
 main() {  
  var x = null;  
  var y = 1;  
   
  var result = add(x, y);  
   
  print(result);  
 }  


In a sense, you're putting in your own message to dart2js: "assume that if variables get past this check, that they are not null." Therefore, dart2js can generate the following code:


 $.add = function(x, y) {  
  if (x == null || false)  
   throw $.$$throw($.ArgumentError$("must not be null"));  
  return $.$add$ns($.JSNull_methods.$mul(x, 2), y);  
 };  
   
 $.main = function() {  
  $.Primitives_printString($.toString$0($.add(null, 1)));  
 };  


Not as good as when both x and y are not null, but better than the the code generated without the null guards.

The main point here is that dart2js maintains Dart semantics whenever it compiles to JavaScript. With type inferencing, it's now generating smarter, smaller, and ultimately faster code without sacrificing semantics.

Preserving index out of bounds semantics

Another example of different behavior between Dart and JavaScript is what happens when you access an index that is out of bounds of an array or list. Consider this code:


 var fruits = ['apples', 'oranges'];  
    
 var fruit = fruits[99];  
   
  // Dart will throw a RangeError because fruits only has two elements.  
  // JavaScript will set fruit to undefined.  

Again, many developers appreciate being explicitly told when they try to access an index that is out of bounds. To bring this behavior to JavaScript, dart2js needs to insert code and logic. For example:


 $.main = function() {  
  var fruits = ["apples", "oranges"];  
  if (99 >= fruits.length)  
   throw $.ioore(99);  
  $.Primitives_printString($.toString$0(fruits[99]));  
 };  


However, if dart2js can determine that an index access is never out of bounds of the list, it can optimize the generated code. There are two ways to make a list whose length is known at compile time: constant lists and fixed-length lists.

Here is an example of using a constant list:


 main() {  
  var fruits = const ['apples', 'oranges'];  
  var fruit = fruits[99];  
   
  print(fruit);  
 }  


The dart2js compiler will output the following code, because it knows the length of the list at compile time:


$.main = function() {  
  throw $.ioore(99);  
  $.Primitives_printString($.toString$0($.List_apples_oranges[99]));  
 };  
 // ...  
 $.List_apples_oranges = Isolate.makeConstantList(["apples", "oranges"]);  


Notice how the exception is immediately thrown, because the compiler knows at compile time that 99 is out of the range of the list.

Summary

The dart2js compiler, which converts Dart code to JavaScript, must maintain Dart semantics in the generated output. Due to recent updates, dart2js can perform whole program analysis and in some cases eliminate bailouts, typechecks, range checks, and other code while keeping consistent with the semantics of the Dart language and libraries. This means smaller, and often faster, code.

The team isn't done yet, there's lots more work to be done. We caution developers from writing code specifically tuned for dart2js's behavior today, as there will be plenty of changes to the code generation algorithms. If you have some code that you believe should be generated more efficiently, please open a bug at dartbug.com/new so we can fix it for you.