InvokeDynamic

From APIDesign

When I was younger I used to believe that having invokeDynamic instruction in HotSpot VM can be beneficial. I even argued that the instruction should not be used just for dynamic languages like Ruby but rather by the core Java to implement lambdas. Now, after spending time to implement lambdas in my Bck2Brwsr VM and seeing things from the other side I have to admit I was wrong. invokeDynamic is wrong idea (especially for implementation of lambdas).

Benefits

Implementing different languages on top of HotSpot virtual machine is of different complexity. When John Rose pushed forward his invokeDynamic vision, he claimed that the most problematic thing is to properly and effectively dispatch methods calls. Not every language uses the Java rules. Some support type conversions, implicit arguments. Some can dynamically alter the existing dispatch target or strategies. More about that in an excellent summary Bytecodes meet Combinators. I really liked that paper and I continue to like it. It matches my functional heart: with MethodHandle a method invocation is finally first class citizen in the VM. One can do currying & co. - all the goodies functional languages had for ages.

What is a MethodHandle? A pointer to method of some signature (for example plus would take two ints and return their sum as an int) and an object - a receiver to call the method on. However this is nothing else than a closure - hence the idea to use it to implement lambdas. But there is a hidden catch...

Getting Dynamic

The primary goal of John R. was to support dynamic languages - e.g. languages where one knows (almost) no type information until the program actually runs. That means one can effectively type (in this JVM context: effectively generate bytecode) only when one knows the actual types. To address all these "deffered" needs the new invokeDynamic bytecode operand had been introduced. It does not hardcode the actual invocation, but once invoked, it calls back to let the "supervising" software (like your JRuby implementation) to analyse the actual call parameters and generate sequence of MethodHandle transformation (possibly a bit of currying, mostly type conversions) to effectively match the actual types of method arguments.

Drawbacks

The major problem with invokeDynamic is, well, that it is dynamic! Java is statically typed language and all variable, field, method and parameter types are known to JavaC before its emits the bytecode. Yet (as JavaC from JDK8 is emulating lambdas with invokeDynamic) it forgets all the derived type information and generates invokeDynamic - which is supposed to do late binding - e.g. find out the right types at the invocation time.

One of the key ideas that I had in mind when advocating use of MethodHandles for implementation of lambdas was reduction in the size of constant pool - you know, the list of referenced symbols like Ljava/lang/String which generally needs to be repeated in every Java class. If lambdas were simulated by inner classes, the constant pools might get enormous (all the symbols might be duplicated in each lambda-innerclass). With invokeDynamic I was hoping for the pool to be reduced to one shared pool for a single source code (with as many lambdas as needed).

However the JDK8 lambdas are generating innerclasses behind the scene and on the fly! So the main benefit is in my opinion gone.

The Problem

The unnecessary loose of types is problematic for VMs that are supposed to run in restricted environment - e.g. Bck2Brwsr or (as far as I heard) Java ME 8. We are running in restricted environment, we can't consume these resources by trying to generate new classes. Just in time compilation may be too expensive, it is much easier to generate the right execution format ahead-of-time (both for Bck2Brwsr and for Java ME 8).

Another issue is related to reflection. Method Handles are (due to their dynamic nature) a specific form or reflection. While doing method lookup one identifies the desired method (or field, or setter) by name. One can reference public or private methods. It is not known in advance which methods will be requested - one needs to invoke the bootstrap method to find that out. As such it is really hard to do compile time optimizations (like shortening method names). Again problem for for small, limited environments.

Summary so far

As a result we have implementation of lambdas that is needlessly forgetting the type information gained during compilation, re-creates it during each startup, is generating bytecode on the fly. It is even surprising it performs acceptably (which probalby took many nights of the HotSpot team members, but again John R. was motivated to make it work, so he did it).

No surprise InvokeDynamic is not supported by Android's Dalvik VM (and in fact it should never be, unless Android wants to attract Ruby developers). Java language does not need it.

Having a Hammer Every Problem Looks like a Nail!

InvokeDynamic is not a Java (language) feature. It is a HotSpot feature to make HotSpot more attractive for other languages than Java. That is of course good intention. HotSpot is still one of the best performing VMs out there - making it more attractive to non-Java langauges makes sense.

However using InvokeDynamic to implement a core Java8 feature (e.g. lambdas) is a mistake. I know I had advocated that in the past too - but the consequences are horrible. Original Java was easy to get ported to small devices - InvokeDynamic is not - and as such the whole Java8 is not portable either!

When one has InvokeDynamic one may be tempted to see solutions to all problems with the help of InvokeDynamic. But sometimes too much may be an overkill.

Solution for the JVM

All Java8 actually needs is to be able to represent a call to a method as implementation of an instance of an interface. However this specific goal can be achieved using simple tools than InvokeDynamic - of course one can generate the necessary inner classes during compile time, but if we want to stick with the effective (from the point of view of constant pools) way of recording lambdas, the best way is to create new bytecode instruction specialized for the task.

Something like newFromAMethod that would specify the resulting interface to generate, the method to call and additional parameters to pass to it.

Some may say that adding new instruction into JVM needs to be done with care. But those who have seen John's new attempt in the area of Value classes have to realize that adding new instructions into JVM is no longer tabu. In such case adding newFromAMethod that closely mimics necessary Java8 semantics should be no brainer.

Solution for dynamic languages

InvokeDynamic has been originally introduced as a helper for implementation of dynamic languages on top of JVM. That is indeed valuable goal from the point of view of HotSpot team. The question is: could the goal have been satisfied without unnecessarily (from the point of view of a Java language) complicating JVM specification?

I believe it could have been done. Have you heard about AsmJs? It is an extension of JavaScript designed by Mozilla. It solves completely different needs (it is an attempt to make JavaScript more typed language - e.g. something opposite to InvokeDynamic), yet the way it has been introduced worth analysis.

Rather than extending JavaScript with new keywords (which is similar to to adding new JVM bytecode instructions), the AsmJs decided to create additional syntax on top of the JavaScript language. For example if one wants to declare that variable x is an integer, one can do so by:

x = x | 0;

The above is valid JavaScript assignment and according to the language specification it guarantees that the result of the or operation is 32-bit integer. Using this to provide hint to the JavaScript VM that x is an integer is a clever way to embed additional semantics into existing language. As a result AsmJs program is parseable by any JavaScript implementation, just on Mozilla it runs way faster than on any other JavaScript implementation.

I believe the same style could have been used for InvokeDynamic. If HotSpot wanted to give Ruby & co. more effective way to handle method dispatch, there could be some extension of the base ByteCode that Ruby could use.

Probably the same alternative approach would be used, if the JVM team and HotSpot team would not be one. If there were more implementations of JVM spec that would be treated seriously (which was true in case of AsmJs as Mozilla needs to negotiate changes to JavaScript specification with others Safari, Chrome, etc.).

Diverging Future

Looks like the JDK guys got adrenalized by the "success" of using InvokeDynamic in recent introduction of lambdas in JDK8 and are willing to boost this kind of inovation in next JDK release. Adding new instructions into the JVM is no longer tabu (as it has been for first fifteen years of Java existence): the Value classes proposal wants to add ten(!?) new bytecode!

On the other hand, it turned out that invokeDynamic may not be the best way to speed up dynamic language. The the Truffle project's Ruby implementation running on top of enhanced HotSpot (and using no invokeDynamic) is ten times faster than invokeDynamic. Turns out that in future we are likely to have fast dynamic languages on top of HotSpot not using invokeDynamic, yet the heavy burden of the invokeDynamic specification will remain the core JVM spec!

Let's also note that Truffle is using sort of AsmJs approach: rather than complicated the JVM, it creates additional Java APIs that dynamic language vendors may use. The API patterns are then recognized by the enhanced HotSpot compiler to emit more effective code. All of that without modification to the JVM spec.

Java and JVM needs to get smaller, not bigger to compete with emerging and improving competitive technologies. Complicating it just makes is harder to bring it to new, small areas of use. Should not we rather think twice before repeating the invokeDynamic failure again?