Sunday, February 5, 2012

Hybrid Type Inference support in SpiderMonkey

Few days ago, Firefox prompted me with the pop up window to download and update itself with its recently released version 9.0. I got curious to know about what is new in this version and hence went to read the release notes from Mozilla.

In a very small duration of time, I got delighted with the fact that this release has JavaScript performance improvements as one of the major highlights. I got fascinated with performance improvement claims (~30%) in JavaScript execution. Upon further digging in, my curiosity kept on increasing, when I started reading about its “Hybrid Type Inference” support in its JavaScript engine “SpiderMonkey”.  After studying in detail, it became pretty clear that this is a very significant change in execution strategy for JavaScript and has the potential to set a new trend altogether.

JavaScript as a language has established itself as the de-facto language for client side programming in the world of web development. Its vast popularity across the globe has generated immense interest of global developer’s community and many corporates in this language. This has created a very healthy competition amongst different vendors who want to dominate in the browser war. Google’s Chrome was the first one, which actually introduced a lot many new radical changes in its V8 engine, which forked huge performance improvements in the language execution.

One of the most important was the introduction of JIT compilation in JavaScript. Use of JIT compilation rather than interpretation has generated huge performance benefits. Still the language takes a back seat when you compare the performance of the language with some of the other established languages which use JIT compilation like Java, C# etc.

Where is the gap?
This gap is mostly because JavaScript provides a lot of freedom to its developers. Execution engine pays the cost of this freedom. What kind of freedom, we are talking about here? This freedom is primarily the freedom of developers to treat any variable as any type and the freedom of type extension at runtime.

Let’s get into the detail of the first type of freedom (Typeless nature of language): Languages like JavaScript don’t have the notion of static type, which becomes a bottleneck in generating a very efficient machine code. Let’s consider a very simple case of adding two integer variables and assign the sum to a third variable. If the compiler has to generate a code, where in it has no idea that it is a sum operation of integers then it will emit code which should be able to handle addition of any two types of variables be it int, float, string etc. But assume when the compiler has the knowledge of the types of the variables, which are going to be added then in such cases it become very easy and straightforward for the compiler to generate machine code, which can handle integer addition and the sum results into an integer.

Pure static analysis for Type inference a rescue?
It becomes quite clear that to achieve the performance of languages like Java, C#, generation of Type specific code is quite important. Unfortunately, for wild language like JavaScript, this is not a straightforward task. One way to achieve this is by performing purely static analysis of the code. But the challenge here is that because of the openness of the language, any pure static analysis for inferring Types becomes so computationally heavy that it does not pay for the performance improvements, which it brings in. Also, because the language is Type less and supports prototype for object extension at runtime, it becomes almost impossible for any static Type analyzer to emit out precise code with all type variants. And not generating code for all possible Types is like changing the expected behavior of the code, which by no means can be regarded as a sound strategy.

Here comes the very interesting strategy for type inference implemented in SpiderMonkey shipped with firefox version 9. It supports a hybrid approach to achieve Type inference. This strategy is an outcome of the acceptance of following facts explained earlier.
1. Compiled machine code, which does not have Type notion can’t be as efficient as the one, which gets generated after Type inference.
2. For any pure static analyzer for Type inference, it is quite impossible to do justice on all the fronts:
a. Sound code: The emitted code should be able to take care of all possible Types and object extension at runtime.
b. Cost of analysis: The analyzer should not be very computationally heavy, otherwise the static analysis offsets the performance benefits at the runtime.
3. If we also take into consideration the usage pattern of JavaScript code for many different websites, then it can be realized that many of the times, we end up loading huge amount of JavaScript code for the website but only end up using a small fraction of it.

The Hybrid approach is nothing but to account for only a subset of Types during static analysis and the ones, which are not accounted during the static Type inference analysis, there should be a way to catch those cases dynamically. This approach not only generates the optimized machine code for the most expected Types in the code by doing static Type inference, but also keeps a provision to catch dynamically at the run time for all those cases, which do not score very high as a candidate for possible Type during static analysis.

Of course this approach is not so simple in implementation as it has to provide the capability of dynamically catching the uncommon cases. If you combine the object’s Type extension capability in the language with the earlier challenge then it actually becomes quite complicated scenario. There are many things, which need to be considered while having such a flexible strategy.  

1. Precise and efficient static analyzer.
2. Capability to dynamically catch cases which are not handled through the static analyzer.
3. Dynamically catching the uncommon cases also comes with a cost, which  is not there in the Typed languages. To reduce this further, have provision of supplemental analysis like overflow scenario, definite properties inside objects etc.
4. Recompilation of the code at the runtime to handle the case where in a new Type is identified at the runtime, which was not taken into consideration by the static analyzer.
5. More complicated memory management: Type inference by static analyzer and capability to recompile the code while it is running also brings in additional overhead to memory management. The execution engine needs to ensure that it is only keeping the relevant compiled code in memory and the garbage collector is collecting the rest.

To handle these things, Firefox has not only changed its JavaScript engine (SpiderMonkey) but also had to made relevant changes in its JIT compiler (JaegerMonkey).  If you go into the details of the implementation there are so many things being introduced like sematic triggers, Type constraints, Type barriers etc… But yes these core changes have definitely justified the performance benefits, which it has created. I can’t even imaging, how many million man-hours are being saved by enhancing the performance of the most popular language for client side web development. Hats off to those engineers involved in this improvement.

Here are some of the relevant links related to this topic:

Signing off for this time with a request to provide your fruitful comments…