Optimizing Dynamically Typed Languages

Lately, I've been spending a lot of time with my friends the ACM digital library, SpringerLink, IEEE, and Google Scholar. The big overarching question is: how do we optimize compiled code for dynamically typed languages? It is difficult to generate efficient and fast native code if you don't know the types of objects you are working with.

Analyzing code to figure out the types of objects is known as type inference. Type inference tries to extract type information from code and hopefully a compiler can then use that information to generate better compiled code.

However, type inference is usually done at compile time, and can only try to approximate the type of an object. The nice thing about JITs is that you can get all the type information as you are executing. You don't have to try to approximate the type of an object, you can see what the real type is as the program is executing.

Many of the following approaches use this type information at runtime to increase performance. They are based on the fact that most code, even in dynamically typed languages, are type stable. Type Stability refers to an idea that most objects generally stay the same type throughout program execution. Garret has a study in Measurement and Application of Dynamic Receiver Class Distributions that shows that assuming type stability is a valid one. Therefore, it is possible to interpret code, see what the type of an object is, then compile the code assuming that the type of a given object remains the same.

Craig Chambers in Customization: Optimizing Compiler Technology for Self takes this approach to optimize methods in SELF. When making a method call in SELF, it is difficult to know which method is actually going to be called. The equivalent idea in Java would be taking two classes:

class Base {
public void foo() {
System.out.println("In Base");
};
}

class Derived extends Base {
public void foo() {
System.out.println("In Derived");
};
}

public static void main(String[] args) {
Base instance = new Derived();
instance.foo();
}

At compile time, the compiler does not know which method to call in instance.foo(). Does it call Base.foo() or Derived.foo()?. A compiler has to look up which method to invoke. Chambers' paper details a process where multiple copies of a function are created. Each function is specialized based on the type of the callee object. In this example, there would be two copies of the main method, one assuming instance.foo() resolves to Base.foo(), and one assuming Derived.foo().

Chamber's idea of cloning methods for each type is really a specialized application of Partial Evaluation. Neil Jones has an introduction to partial evaluation. The idea behind partial evaluation is to hold some portion of a program constant, and compile code assuming that constant. For example, imagine compiling the addition of two variables: x+y. We can assume that variable x is an integer, and generate native code with that assumption.

Holze extended Chamber's work by caching a method callee type at runtime in Optimizing Dynamically-Typed Object-Oriented Languages with Polymorphic Inline Caches. A Lookup Cache is a cache that maps the callee type to a specific method to execute. When executing a method, the address is looked for in the cache. If it exists, jump to the method implementation. If it does not, the system has to do a full lookup to find the target method. Inline Caches extends this idea by directly jumping to the method implementation that was resolved in a previous call, totally avoiding a cache lookup. The target method has code to check that the type of the callee object is the same. Polymorphic Inline Caches (PIC) builds on inline caches by storing ALL previous callee object types and target methods that have been seen during execution. Inline Caching is applicable only if there is one callee type while PICs are useful when there are multiple callee types.

Holze goes even further by using these PICs to optimize code based on the callee type of an object in Optimizing dynamically-dispatched calls with run-time type feedback. PICs only cache the callee of a method and therefore increases the performance related to calling a method. Holze's second paper introduces adaptive compilation, where code that calls a generic method is recompiled to inline a type specific target method. If we go back to the previous Java example, Holze can do the following for the main method:

public static void main(String[] args) {
Base instance = new Derived();
if (instance typeof Derived) {
System.out.println("In derived");
} else {
instance.foo();
}
}

Now the next step is to add a trace publication so I can add it to the list heh :).