Performance/ Implement type tracking

[Bablakeluke]

SpiderMonkey and V8 run close to native speeds by tracking the flow of variable types throughout the system and essentially being able to directly call a method/ read a field rather than performing a prototypical lookup.

We're currently in the process of implementing this with first looks being very encouraging - the changes are very widespread though so more updates and a repo will be coming shortly for you guys to play with. I'm personally focusing on getting Route9.js to function at a respectable framerate which also requires full typed array support, so I'll likely be finishing off that as well unless someone else gets there first.

The current change set that has occurred in order to make this possible is roughly as follows:

• No longer need special classes to declare functionality; it 'just works' with general .NET types.
• Automatically drops the case of the first letter of a .NET method name unless told otherwise.
• All public properties on an exposed type are exposed to JS unless they are explicitly hidden.
• Removed stack frames and instead used the .NET internal stack. (Method call overhead reduced).
• Removed unsafe code requirements.
• Globals resolve as fast as ordinary .NET fields do.
• Scope chain is statically resolved. This now means that method signatures have nothing particularly special about them so methods can be directly invoked at the call site.
• Added a traditional hoisting mechanism (incomplete).
• Reduced property overhead significantly by removing the schema duplication process as it ended up being unnecessary.
• Removed the boxing-but-not-really construction of e.g. a Number object around the double value to access its methods. It just remains a double at all times, and those methods were made static instead.
• Removed a lot of type casting as it was no longer necessary
• We need it to precompile so it's also heading towards this as well.

But it did come at the cost of a few things at the moment:

• Eval can only access variables in the global scope (because the scope chain is static).
• With statement got a little broken. Fixing!
• Hoisting through more than 1 scope depth is also broken. Also fixing!
• Can't set a hoisted variable in its host scope, essentially 'un-hoisting' it. Although possible to implement, I'm personally viewing this as a minor at the moment.
• Generally making a bundle assumption that all code is loaded at once, although this assumption will not affect the final result.

The end result is a totally different beast which I've been nicknaming Nitrassic (a combo of Nitro, our own home-grown .NET JS engine which runs fast but has very limited spec coverage). I wanted to drop this here so we could a) thank you guys, Jurassic rocks! and b) open up a discussion on the type tracking system as there are probably thoughts floating around on the implementation. The current approach that is in the process of being implemented is roughly summarized as follows:

Type introduction into the system. Types are introduced into the system in a set number of ways. These points essentially provide the 'roots' of the type flow graph:

• A .NET constructor call such as var a=new Date(); // a is Library.Date
• Inline constants such as var a='hello!'; // a is System.String
• A .NET method call such as var a=Math.abs(-2); // a is System.double
• External imports, i.e. ScriptEngine.CallGlobalFunction('myFunction',known,type,objects); or SetGlobalValue.
• Creating a JS object with {} notation.
• Creating a JS object with the new keyword and a function.

The premise We make the assumption that a variables type is always known by the compiler. There are three major unknowns and those are function arguments, new object properties and global variables - everywhere else the types can be known - so we must essentially find a way of tracking their types too.

Function arguments Fortunately this one's relatively simple - we simply compile a method when it gets called. Based on our assumption, the call site always knows the types of the variables its passing as arguments. Hoisted variables will all be known too. Thus, we can know exactly which types are in use at a given call site and compile the method accordingly. A method can potentially be compiled multiple times if it's being called in a few different ways.

Object properties We need to know all properties that are being added to a given object prototype. As we're compiling at the function scope level, then we essentially have to watch for new properties being added either in this function scope or any function scope that is being called from. In order to do this, a function tracks the side effects it has on its arguments whilst its being compiled. The call site of that function can then be aware of any new properties that may be getting added and their type too.

Global variables Globals are awkward because 'anyone' can change them. Whenever a global is set, we check to see if the type being set matches that of the global. If they are different, i.e. a global is being set to some different type, then the global is said to have 'collapsed' and has its type set to typeof(object). However, functions may have been compiled that used it as its previous type. So, each global tracks the functions which use it. If that global collapses, it then simply requests that those functions recompile. When a function attempts to compile with a collapsed global, it emits runtime type checking. Interestingly, this is the only situation where runtime type checking actually occurs - essentially only if someone sets a global to more than one type.

Thoughts/ opinions/ 'you're crazy!'s/ ideas all welcome!

[paulbartrum]

Wow, that is one epic comment! I'm enthusiastic about seeing what you have come up with. Jurassic currently does only very limited type inference (for loop variables, IIRC) and unfortunately it complicated things quite a lot. I have however recently implemented compile-time generation JS --> .NET binder methods, where they used to be generated at runtime (this has greatly improved the "startup time" to execute a single line of JS but hasn't had much effect on benchmarks).

Regarding your type inference plan, I have a few comments.

One, overall performance is going to depend on the incremental gain you get from type specialization versus the loss from having to compile functions multiple times. The browser JS engines tend to do type specialization only for "hot" code, i.e. the inside of hot loops, or functions that are called hundreds of times. The downside of course being that the instrumentation code to determine what is "hot" itself takes CPU cycles.

Two, I think you are underestimating the problem slightly when you say that it's only global variables that are problematic. Sure, there are various JS features that make inferring types at compile-time difficult, like eval("") or new Function("") or abc["def"], but my main concern is more subtle. The main problem I see is that while it is possible to track the type of each named variable, you can't track the value ahead of time. Which means that it is not possible to know, in general, which function is being called when a function call is made. For example, a = Math.sin(3) returns a double, right? Well, maybe not; Math is a global which can be replaced or modified at any time. Even if the type does not change, if the value of Math.sin changes your assumptions about the function return value and side-effects go out the window. I'm not sure how this could be worked around or mitigated -- I need to give it more thought :-)

Three, remember that type specialization is not the end all and be all of performance improvements. The code generation stage could be improved a LOT (it is currently about as non-optimized as you can get). Code generation improvements could include dead code elimination, arithmetic optimization, peephole optimization and more. Function inlining would help for certain workloads. Improving compilation speed or building an interpreter would improve latency, which is good for functions which are only ever called once and have no hot loops.

I hope you don't take this as discouragement; I know first hand that what you are attempting is challenging, but I do think all of these problems can be solved. Nothing worth doing is ever easy :-)

[Bablakeluke]

Hi Paul, thanks very much for your reply! I completely agree - the challenge is always the best bit too!

Yep the only spot I've seen any type resolving is inside the for loop, and I know exactly what you mean by it complicated things! That particular optimisation actually backfired considerably with Route9.js (which is what initially lead me to spot it in the first place); Route9 apparently has a lot of chunky loops which resulted in some thrashing severe enough to cause it to take the best part of 25 minutes to compile :P

1. This one's the biggie; my assumption is that people generally call a function with a very limited set of types, so on the whole your typical function will only compile just the once. However, at the other end of the spectrum you have things like the jQuery $() function causing total chaos through accepting basically everything as an argument. My general thinking is that if a function is requested to recompile more than a fixed number of times, e.g. 3, then it compiles as a semi-traditional Jurassic method with an object[] args set instead rather than the specific types and falls back on runtime type resolving instead. Hoisting gets a bit odd in this situation though, however the current modified engine already deals with hoisted variables and the object[] args set.
2. In this instance, changing the Math object to a custom object would trigger a recompile of anything that already used it (and the Math global would also have collapsed, so it falls back to runtime type resolution). Overwriting Math.sin with some other function would trigger only the sin property to collapse instead. Extending an already defined object with new properties is where things get a bit weird though; my thoughts here are that it essentially creates a new type which 'inherits' the old one; consider something like this:

function myGenerator(){
 return {Hello:"this is an object"};
}

var a=myGenerator();

a.Test="And this is a new property";

Ideally the above would end up translating to the following (described in C#):

public class __proto_1{ public string Hello; }
public class __proto_2 { public __proto_1 __Internal_Derived; public string Test; }

public static __proto_1 myGenerator()
{
 __proto_1 result=new __proto_1();
 result.Hello="this is an object";
 return result;
}

public static void __global_2(){
  __proto_1 generated=myGenerator();
  __proto_2 result=new __proto_2();
  result.__Internal_Derived=generated;
  result.Test="And this is a new property";
}

It's worth noting that the compiler would not necessarily output this due to the property side-effects tracking; the myGenerator function is already aware that its returned type is expecting to be extended with a property called 'Test' when the call site compiles. So essentially assume that the myGenerator function returns an already determined type which it's attempting to extend. It's a bit of a toss-up between this and actual inheritance though, i.e. lets say __proto_2 directly inherited __proto_1, then the 'Hello' property would need to be copied over which introduces a whole awkward world of pain, but it at least has the advantage of them sharing the same heritage which is more 'correct'.

1. (<- this should be 3 but Github has other ideas) Very true; the code generation stage is something that's also been getting targeted (the parser saw a speed improvement of 3-4x as well). Usefully though, the .NET runtime does a lot of hot code optimization in a very similar way to SM/V8 and some basic IL optimizations, so Jurassic at least has that as a baseline advantage. Is it possible to get Jurassic up to SM/V8 speeds? Probably not, but I'm certainly willing to give it a best shot :)

A little more context behind the semi-random drive to do this: Our Nitro JS engine is fairly widely used in Unity3D games; it's entirely type tracked and emits IL similar to the C# compiler, but it's veerry spec limited and currently requires types being defined in function signatures which immediately distances it from ordinary JS. We need WebM and H.264 support in Unity and started creating an entirely .NET WebM video loader but it was essentially taking way too long, so we had the thought that we could extend our JS engine to being fully ECMAScript5 compatible and run Route9/ Broadway on top of it instead, plus a whole host of other awesome JS libraries. Because of runtime compiling being blocked on most consoles and iOS, precompiling is a requirement. Then the scale of the ECMAScript 5 spec was really starting to daunt us, especially as we had already gone through the crazy process of reinventing the web wheel by implementing a HTML5/CSS3 renderer entirely in .NET, and doing it 'again' wasn't super appealing. So, then came the idea of taking an engine with spec coverage and merging it with the performance properties of Nitro - with a little luck, lots of junk food and many hours later, hopefully we can get there!

[Bablakeluke]

So far the results are all looking extremely positive! A rough benchmark comparison brought up a rather interesting statistic:

Incrementing 100m times (Repeated 10 times and averaged, on a relatively old laptop):

console.time("hello");
var c=0;
for(var i=0;i<100000000;i++){
    c++;
}
console.timeEnd("hello");

Classic Jurassic: 30466ms Nitrassic: 473ms

64.4x

Running the same loop directly in Firebug/ the Chrome console on a blank page resulted in some crazy ~150000ms in both browsers; running directly on SpiderMonkey/ V8 would be a fairer test though of course but interesting numbers none the less.

Still a long way to go yet but so far so good!

[paulbartrum]

Looking good :-) Regarding running this test in Firebug/Chrome, you might want to try pasting your script into https://jsfiddle.net/