Friday, December 24, 2010

jSuneido Compiler Optimizations

For my own reference, and to justify my month of work, I thought I'd go over some of the optimizations I've done recently. The changes involve:
  • how functions/methods/blocks are compiled
  • how calls are compiled
  • the run-time support code e.g. in Ops, SuValue, SuClass, SuInstance, etc.
My original scheme was that arguments were passed in an array i.e. in the style of Java's variable arguments. For simplicity additional local variables were also stored in this array. This had a nice side benefit that the array could be used to capture the local variables for blocks (aka closures).

The downside is that every call had to allocate an argument array, and often re-allocate it to accommodate default arguments or local variables. And access to variables requires larger and presumably slower code. (ALOAD, ICONST, AALOAD/STORE instead of just ALOAD/STORE)

To keep the calling code smaller I was generating calls via helper functions (with variations for 1 to 9 arguments) that built the argument array. One drawback of this approach is that it added another level to the call stack. This can impede optimization since the Hotspot JVM only in-lines a limited depth.

The first step was to compile with Java arguments and locals for functions (and methods) that did not use blocks.

Then I realized that if a block didn't share any variables with its containing scope, it could be compiled as a standalone function. Which is nice because blocks require allocating a new instance of the block for each instantiation, whereas standalone functions don't since they are "static". And it meant that the outer function could then be compiled without the argument array. Determing if a function shares variables with blocks is a little tricky e.g. you have to ignore block parameters, except when you have nested blocks and an inner block references an outer blocks parameter. See AstSharesVars

Where I still needed the argument array I changed the calling code to build it in-line, without a helper function. This is what the Java compiler does with varargs calls. Generating code that is similar to what javac produces is a good idea because the JVM JIT compiler is tuned for that kind of code.

One of the complications of a dynamic language is that when you're compiling a call you don't know anything about what you'll end up calling.

On top of this, Suneido allows "fancier" argument passing and receiving than Java. This means there can be mismatches where a call is "simple" and the function is "fancy", or where the call is "fancy" and the function is simple. So there needs to be adapter functions to handle this. But you still want a "simple" call to a "simple" function to be direct.

Each Suneido function/method is compiled into a Java class that has Java methods for simple calls and fancy calls. If the Suneido function/method is simple, then it implements the simple method and the fancy method is an adapter (that pulls arguments out of a varargs array). (for example, see SuFunction2, the base class for two argument functions) If the Suneido function/method is fancy, then it implements the fancy method and the simple method is an adapter (that builds an argument array).

In cSuneido, all values derive from SuValue and you can simply call virtual methods. But jSuneido uses native types e.g. for strings and numbers. (To avoid the overhead of wrappers.) So you need something between calls and implementations that uses "companion" objects for methods on Java native types. For example, Ops.eval2 (simple method calls with two arguments) looks like:

Object eval2(Object x, Object method, Object arg1, Object arg2) {
    return target(x).lookup(method).eval2(x, arg1, arg2);

For SuValue's (which have a lookup method) target simply returns x. For Java native types it returns a companion object (which has a lookup method). lookup then returns the method object.

One issue I ran into is that now I'm using actual Java locals, the code has to pass the Java verifier's checking for possibly uninitialized variables. I ran into a bunch of our Suneido code that wouldn't compile because of this. In some cases the code was correct - the variable would always be initialized, but the logic was too complex for the verifier to confirm it. In other cases the code was just plain wrong, but only in obscure cases that probably never got used. I could have generated code to initialize every variable to satisfy the verifier, but it was easier just to "fix" our Suneido code.

The "fast path" is now quite direct, and doesn't involve too deep a call stack so the JIT compiler should be able to in-line it.

The remaining slow down over Java comes from method lookup and from using "boxed" integers (i.e. Integer instead of int). The usual optimization for method lookup is call site caching. I could roll my own, but it probably makes more sense to wait for JSR 292 in Java 7. Currently, there's not much you can do about having to use boxed integers in a dynamic language. Within functions it would be possible to recognize that a variable was only ever an int and generate code based on that. I'm not sure it's worth it - Suneido code doesn't usually do a lot of integer calculations. It's much more likely to be limited by database speed.

No comments: