Optimizing dynamic JavaScript with inline caches

or, JavaScript inline caches for unmaintainable fun and profit

This is an overview of an optimization technique I've been using in JSIL for a while, where you create and update polymorphic inline caches in your JavaScript code at runtime so that it can stay fast while adapting to unexpected changes.

This post is still a draft, so please share your thoughts and comments with me on twitter at @antumbral or via email (kg at luminance dot org).

Already familiar with what an inline cache is, but not familiar with C# and you want to know why I'm using them?
Skip to Why are you using an inline cache in JavaScript?

Want the benchmark timings and an explanation of how my JavaScript inline caches work?
Skip to Just how slow is your code without inline caches?

How does it work?

Why not just use Function.call or Function.apply?

Just want to read some source code? Okay, let's see some source code.

What's an inline cache?

You may be familiar with the concept of an inline cache, or the term 'PIC' - polymorphic inline cache - used often in discussion of JIT compilers, like the ones used in the SpiderMonkey and V8 javascript runtimes.

If you already know what an inline cache is, skip down to the next section!

To summarize for the novice, a polymorphic inline cache takes an operation that typically requires a bunch of important checks and generates specialized code for specific, known scenarios, where the specialized code doesn't contain those checks. Conceptually, this can apply to much simpler scenarios!

To provide a simple, contrived example:

function divide (lhs, rhs) {
  return lhs / rhs;
}
function divideSomeNumbers (lhsArray, divisor, resultArray) {
  if (lhsArray.length !== resultArray.length)
    throw new Error("Arrays must be the same size");
  for (var i = 0, l = lhsArray.length; i < l; i++) {
    resultArray[i] = divide(lhsArray[i], divisor);
  }
}

This test case is pretty simple, there are many ways you can optimize it. Let's choose a toy optimization to demonstrate what kind of code an inline cache might generate in this scenario - using bitwise arithmetic to do division.

When dividing an integer by a power of two, you can use a bitwise shift instead of a divide to get the same result. A bitwise shift is considerably simpler to implement, so in cases where the divisor (the right hand side) is known to be a power of two, a compiler might turn a division into a bitwise shift.

If we want to do this ourselves, we might introduce a lookup somewhere:

var dividers = {
  2: function divideBy2 (lhs, unused) {
    return lhs >> 1
  },
  4: function divideBy4 (lhs, unused) {
    return lhs >> 2
  },
  undefined: function divideByNumber (lhs, rhs) {
    return lhs / rhs
  }
}
function divideSomeNumbers (lhsArray, divisor, resultArray) {
  if (lhsArray.length !== resultArray.length)
    throw new Error("Arrays must be the same size");
  var divider = dividers[divisor];
  for (var i = 0, l = lhsArray.length; i < l; i++) {
    resultArray[i] = divider(lhsArray[i], divisor);
  }
}

Cool, that looks good. But wait! We replaced a call to a known method - divide - with a call to a method that is chosen at runtime. And that method depends on the arguments to our function! Did we just make it slower? Quite possibly - unless the JIT is smart enough, every call to divider will be a virtual call of some sort, and this might prevent inlining and other key optimizations.

Let's take a look at a naive version of the code a compiler might generate for an inline cache:

function divideByNumber (lhs, rhs) {
  return lhs / rhs;
}
function divideBy2 (lhs) {
  return lhs >> 1;
}
function divideBy4 (lhs) {
  return lhs >> 2;
}
function divideSomeNumbers (lhsArray, divisor, resultArray) {
  if (lhsArray.length !== resultArray.length)
    throw new Error("Arrays must be the same size");
  // Inline cache
  if (divisor === 2) {
    return divideSomeNumbersBy2(lhsArray, resultArray);
  } else if (divisor === 4)
    return divideSomeNumbersBy4(lhsArray, resultArray);
  } else {
    // Cache miss! A JIT would likely record the miss here, and consider
    //  updating the cache. It'd notice eventually if most trips through
    //  the cache are misses, or if the cache has too many entries.
    // In these cases the IC might be removed entirely for performance.
    return divideSomeNumbersByUnknown(lhsArray, divisor, resultArray);
  }
}
function divideSomeNumbersBy2 (lhsArray, resultArray) {
  for (var i = 0, l = lhsArray.length; i < l; i++) {
    resultArray[i] = divideBy2(lhsArray[i]);
  }
}
function divideSomeNumbersBy4 (lhsArray, resultArray) {
  for (var i = 0, l = lhsArray.length; i < l; i++) {
    resultArray[i] = divideBy4(lhsArray[i]);
  }
}
function divideSomeNumbersByUnknown (lhsArray, divisor, resultArray) {
  for (var i = 0, l = lhsArray.length; i < l; i++) {
    resultArray[i] = divideByNumber(lhsArray[i], divisor);
  }
}

Now that dynamic call to 'divider' has been replaced: At the top of the function, we do a simple check to see whether we can use any of our existing bitshift functions, and if so, we call out to a specific function - this call's not dynamic - that calls one of our bitshift functions. Because none of these calls are dynamic, it is pretty easy for the compiler to go from this step to inlining everything, and the end result is one big function with fully-optimized sections for each power of two.

Inlining enables all sorts of powerful optimizations, so an inline cache like this is essential to set an optimizer up so it can do even more work on your code to make it run quickly.

Why are you using an inline cache in JavaScript?

JSIL is a compiler that translates .NET applications - statically typed, written in languages like C# - to JavaScript. At runtime it implements most of the semantics of .NET, including user-defined value types and overloaded methods. For simple applications, this is trivial - the first JSIL prototype was a C# decompiler, changed to produce JavaScript syntax.

Things get complicated when you want to translate complex applications, and you want to make them fast. Specific operations in .NET are not easy to express in JavaScript, and they're particularly difficult to express if you want to expose .NET libraries to user-authored JavaScript, instead of just translate whole applications.

For example, let's say you have an overloaded method in C#:

float Divide (float lhs, float rhs) {
  return lhs / rhs;
}
int Divide (int lhs, int rhs) {
  return lhs / rhs;
}
void Test () {
  float a = Divide(1.5, 3);
  int b = Divide(5, 2);
} 

There's no obvious way to express this in javascript. A compiler would probably assign them unique names, and then propagate them through the output code:

function float_Divide_float_float (lhs, rhs) {
  return +((+lhs) / (+rhs));
}
function int_Divide_int_int (lhs, rhs) {
  return ((lhs | 0) / (rhs | 0)) | 0;
}
function Test () {
  var a = float_Divide_float_float(1.5, +3);
  var b = int_Divide_int_int(5, 2);
}

Not great to deal with, but it works. Things get trickier when your language is statically typed, but allows you to manipulate types and methods at runtime. C# provides the concept of a 'generic type', where you define an abstract 'generic' form of a type, that has multiple placeholders for real types, and then you create a real type by combining the generic type with some real types. So, for example, the 'generic type' List<T> combined with the type argument int produces the real type List<int>, which is a list containing a bunch of ints. This is all done statically, so there aren't any type checks at runtime and arrays will be nice and efficient. Great!

Except C# has reflection. Reflection lets you examine types, methods & values, and manipulate them at runtime. In .NET, you can even create a new 'real' generic type at runtime, then create an instance of it! When you do this, .NET's JIT compiler helpfully obliges your request by compiling brand new code for that new type so you can use it.

Suddenly the idea of generating a bunch of JavaScript functions with carefully mangled names isn't quite sufficient anymore. And it turns out that there are other scenarios like this where it's not easy to write code that handles everything correctly up front.

So, where was I?

Inline caches. Why inline caches?

Oh, right. So, once we give up and decide that some things have to happen at runtime - as it turns out they happen at runtime even in our nice static language, C# - we have to figure out how to make all this work. Where before you would have had the compiler do the heavy lifting, now we have to do a bunch of this type system magic in JavaScript and try to do it efficiently.

One commonly used feature in C#, interfaces, turns out to require this kind of magic - albeit in a less common case. A simple C# interface and implementation would look like this:

public interface ValueProvider<out T> {
  T GetValue();
}
public class GenericProvider<T> : ValueProvider<T> {
  public T TValue;
  T ValueProvider<T>.GetValue () {
    return TValue;
  }
}

Given that implementation, it's probably obvious that this works:

public static class Program {
  public static void Main () {
    var provider = new GenericProvider<string> {
      TValue = "string"
    };
    ValueProvider<string> stringProvider = provider;
    Console.WriteLine(stringProvider.GetValue()); // prints "string"
  }
}

Run the above in your browser

But what about this? Why does it work?