Saturday, March 22, 2014

melonJS should be *All About Speed*

I've been working on melonJS since I first used it in July 2012. It's now over 1.5 years later, and we've learned a lot as a team. One particular area of melonJS that I have focused a lot of time is performance. And in this article, I will try to describe current pain points and what we are doing to make them better.

TL;DR: A super fast prototypal inheritance microlib for the modern web. https://github.com/parasyte/jay-extend

Simple Inheritance

melonJS has always used John Resig's Simple Inheritance pattern, like many of the HTML5 game engines available. While looking for things to optimize, I stumbled upon some funny code with regular expressions in the Object.extend helper function. If you've never looked at the source, you can head over to John's original article where he introduced it. The RegExp is a hack to determine if the browser can coalesce functions into a string; in other words, it is a test to determine if the browser is capable of decompiling functions. But why on earth would it need to decompile functions? Well, for syntactic sugar, of course! To save the programmer from typing prototype so often.

To see how that regular expression got there, we first have to do some code archeology. One of the best ways to illustrate is to reinvent it. All the code I will be showing here was run using jsfiddle with my browser's web console open.

Let's start with prototypal inheritance; the concept of creating a function in a prototype form (a class), then instantiating objects from that class. Here is a very simple example of a class which shows a constructor and an accessor method:

function Foobar() {
    this.num = 123;
}

Foobar.prototype.setNum = function (num) {
    return this.num = (typeof(num) === "number") ? num : this.num;
};

In this example, the function named Foobar is the class, and its body is the constructor. Then the class prototype is modified to include an accessor method. Let's instantiate an object with this class and try it out:

console.clear();

var f = new Foobar();
console.log("Expect 123:", f.num);
console.log("Expect 9000:", f.setNum(9000));
console.log("Expect 9000:", f.setNum("abc"));

If you run the code, you'll see that it does work as intended! This is the classic example of prototypal inheritance in JavaScript, and you will see it used in tons of libraries today. But as you start to add more and more methods to your class, you will be typing prototype quite a lot. A little syntactic sugar can hide prototype by iterating over a descriptor which defines the methods you want added to the prototype.

Object.prototype.extend = function (Class, descriptor) {
    for (var method in descriptor) {
        Class.prototype[method] = descriptor[method];
    }
}

function Foobar() {
    this.num = 123;
    this.str = "xyz";
}

Object.extend(Foobar, {
    "setNum" : function (num) {
        return this.num = (typeof(num) === "number") ? num : this.num;
    },
    "setStr" : function (str) {
        return this.str = (typeof(str) === "string") ? str : this.str;
    }
});

I've added a second accessor method to our Foobar class, and also created a new function called Object.extend (same name as used in Simple Inheritance, by the way) which provides the syntactic sugar we were looking for. Hooray! No more prototype in our class definitions. And here's another quick test to prove that it works:

console.clear();

var f = new Foobar();
console.log("Expect 123:", f.num);
console.log("Expect 9000:", f.setNum(9000));
console.log("Expect 9000:", f.setNum("abc"));
console.log("Expect xyz:", f.str);
console.log("Expect abc:", f.setStr("abc"));
console.log("Expect abc:", f.setStr(9000));

Now what about inheritance? In JavaScript, you can do single inheritance quite simply by replacing the class prototype with a copy of the prototype from another class. There's a function built into the language for doing exactly that: Object.create.

(Side note: Object.create is a relatively recent addition to the JavaScript language, and Simple Inheritance pre-dates its inclusion. So Simple Inheritance uses a trick involving the instantiation of the object itself with a little hack to prevent the constructor from running during the prototype creation phase. See John's article for more details on that little catch.)

In order to create the inheritance chain, we need to modify Object.extend to return an empty class whose prototype is given a copy of the base class (thanks to Object.create). Because the empty class has its own constructor, we need a way to run the user's constructor. Again, following the Simple Inheritance API, we'll adopt init as the name of the user's constructor, and simply call that if it exists.

Object.prototype.extend = function (descriptor) {
    function Class() {
        if (this.init) {
            this.init.apply(this, arguments);
        }
        return this;
    }

    Class.prototype = Object.create(this.prototype);

    for (var method in descriptor) {
        Class.prototype[method] = descriptor[method];
    }

    return Class;
}

We'll use this updated Object.extend to recreate our base class Foobar, then create a Duck class that inherits from Foobar.

var Foobar = Object.extend({
    "init" : function () {
        this.num = 123;
        this.str = "xyz";
    },
    "setNum" : function (num) {
        return this.num = (typeof(num) === "number") ? num : this.num;
    },
    "setStr" : function (str) {
        return this.str = (typeof(str) === "string") ? str : this.str;
    }
});

var Duck = Foobar.extend({
    "speak" : function () {
        return "quack";
    }
});

And then we'll write a simple test to verify it all works as I claim:

console.clear();

var d = new Duck();
console.log("Expect 123:", d.num);
console.log("Expect 9000:", d.setNum(9000));
console.log("Expect 9000:", d.setNum("abc"));
console.log("Expect xyz:", d.str);
console.log("Expect abc:", d.setStr("abc"));
console.log("Expect abc:", d.setStr(9000));
console.log("Expect quack:", d.speak());

There you go! The reinvention of Simple Inheritance is complete. Well, almost! What happens if you want to override a method, instead of just adding new ones? You can do that with the above code, sure, but you probably want to run the overridden method, as well. This is done by going back to the prototype chain, again! Let's modify Duck to append "quack" to every string set:

var Duck = Foobar.extend({
    "speak" : function () {
        return "quack";
    },
    "setStr" : function (str) {
        return Foobar.prototype.setStr.call(this, str + " quack");
    }
});

This prototype mess is how we call a method on the super class in JavaScript! Yes, it's normal. Yes, it's ugly. Yes, that's why Simple Inheritance adds more sugar in the form of this._super! The problem to recognize is that binding the instantiated object reference (this) to a method on the prototype chain is hard to do in a generic way. John's solution is creating a proxy method called _super which redirects method invocations to the same method name on the super constructor. It manages this via a series of closures to retain scope in the prototype chain.

In order to create each proxy method, Simple Inheritance adds checks to the descriptor iteration to find methods (functions). For each method found, a RegExp test (!) is run to determine whether a proxy should be added. This, at long last, answers our original question, "why does Simple Inheritance need to decompile functions?" Frankly, it doesn't need to decompile anything! But as an optimization, it won't add the proxy to methods that don't need it. And it determines which methods need the proxy by decompiling the function; looking for a string that matches _super. So if _super is ever used in the method, it gets a proxy that adds the _super property!

"But isn't decompiling functions slow?" ... Yeah, probably!

"And isn't running a regular expression over a long function-as-a-string also slow?" ... I would say so!

*sigh*

And so began my adventure to make Simple Inheritance fast! Actually, I did so much of my own work here to reinvent Simple Inheritance that I'm just going to release it on its own, with a nod to John Resig for the inspiration.

I made _super fast by adding the proxy within the Class constructor, rather than during prototype creation time. This means that none of the methods get proxied automatically; instead, _super is the proxy. After going through multiple failed tests, I found the best interface for _super is actually closer to Python than Simple Inheritance. Notice that the Python super() function takes two arguments; a reference to the super class, and a reference to the instantiated object.

All that means is _super in Jay Inheritance looks like this:

var B = A.extend({
    "foo" : function (arg1, arg2) {
        this._super(A, "foo");
        this._super(B, "bar", [ arg1, arg2 ]);
    },
    "bar" : function (arg1, arg2) {
        // ...
    }
}

Quite a bit different from Simple Inheritance! And there is also a big difference between my final implementation and Python's super() function, which returns a proxy to the super class. If I were to do that, it would require another iteration, which I'm not willing to do, for the sake of raw performance. So instead, my _super interface accepts a reference to the super class, and a method name, followed by an array of arguments that will be proxied to the super class method.

Requiring a reference to the super class also allows calling sibling methods on the class, without going through the normal prototype chain. This is useful for base classes where you don't want to call overridden methods. Simple Inheritance does not have this functionality in syntactic sugar form; you'll have to use the ugly prototype mess for that.

As an added bonus, I also include mixin support, which allows adopting methods from a class without inheriting its prototype.

Finally, I've wrapped all of this knowledge into a single project called Jay Inheritance, named after yours truly. Here is the official gist: https://gist.github.com/parasyte/9712366 and I also have the same code on jsfiddle, where the tests can be run directly: http://jsfiddle.net/Qb7e8/6/ (Update, July 2015: the project has been release as jay-extend: https://github.com/parasyte/jay-extend and is available through dependency managers npm and bower.)


Jay Inheritance is as screaming fast as classical inheritance patterns can get in JavaScript. From here, we need to refactor melonJS classes to use it, and also to make the classes much smaller! Objects with too many properties are hard for JavaScript engines to optimize. For example, the V8 engine in Chrome switches to slow-mode when an object has about 30 properties. Source: http://youtu.be/XAqIpGU8ZZk?t=25m07s Property access also uses type-specialized optimizations, so we should not be changing the data type stored in any properties, nor adding or removing properties outside of the constructor.

In the next article, I'll talk about some modifications that were recently made to Simple Inheritance in melonJS, and why this was a bad idea from a performance perspective. I'll also go over some ideas that we can use to improve the situation in the future with the inheritance pattern.