A First Taste of InvokeDynamic (2008)

http://blog.headius.com/2008/09/first-taste-of-invokedynamic.html

I’m very curious about how much of this is still relevant and what invokedynamic looks like in 2020. Based on An Introduction to Invoke Dynamic in the JVM, there now exists an actual instruction named invokedynamic, so the java.dyn.Dynamic gymnastics don’t appear to be required anymore. Also it looks like Java has adopted invokedynamic for its own uses, like string concatenation (different strategies to be chosen at runtime, presumably for perf) and lambdas.

Java is a statically-typed language. That means the types of all variables, method arguments, method return values, and so on must be known before runtime. In Java’s case, this also means all variable types must be declared explicitly, everywhere. A variable cannot be untyped, pand a method cannot accept untyped parameters nor return an untyped value.

when implementing a dynamic language [on the JVM] that stubbornly refuses to yield type information until runtime, all this static-typing is a real pain in the neck.

If we peel the Java layer away, the situation changes a bit. At the JVM bytecode level, types are still visible, but they’re not nearly as prevalent.

Java provides what’s called an “operand stack” for bytecode it executes. The stack is analogous to registers in a “real” CPU, acting as temporary storage for values against which operations (like math, method calls, and so on) are to be performed. So most JVM bytecode spends its time either manipulating that stack by pushing, popping, duping, and swapping values, or executing operations that produce or consume values. It’s a pretty simple mechanism

  • “load” retrieves a local variable and pushes it on the stack.
  • “store” pops a value off the stack and stores it in a local variable.
  • The “invoke” bytecodes are what you might expect: method invocations, [which] consume zero or more arguments from the stack and in some cases a receiver object as well.
    • “virtual” refers to a normal call to a non-interface method on an object receiver. “interface” refers to an interface invocation on an object receiver. “static” refers to a static invocation, or one that does not require an object to call against.
    • “invokespecial”, which is used for calling constructors and superclass implementations of methods.
  • The “const” instructions push a constant on the stack.
  • “aaload” and all “*aload” operations are retrievals out of an array.

the opcodes themselves have no type information. Even beyond that, there are no actual variable declarations at the bytecode level whatsoever. The stack itself is also untyped; we push a reference type (aload) one minute and push a primitive type (iload) the next (though values on the stack do not “lose” their types).

the type signatures for each method invocation or object construction are simply strings stuffed into the class’s pool of constants

Because much of the rigid, static nature of Java is in the language itself (and not the JVM) we can in many cases ignore the rules. We don’t have to declare local variable types. We can juggle items on the stack at will. We can cheat in clever ways, allowing much of normal code execution to proceed with very little type information. In many cases we can get that code to run nearly as well as statically-typed code of twice the size, because the JVM is so dynamic already at its core. JVM bytecode is our assembly, and it’s a powerful tool in the right hands.

  • limitation #1: invocations are statically typed.
  • limitation #2: invocations must be against Java methods on Java types.

Using reflection to invoke methods works great…except for a few problems. Method objects must be retrieved from a specific type, and can’t be created in a general way. Second, reflected invocation is a lot slower than direct invocation.

language implementers have been forced to come up with new tricks. In JRuby’s case, this means we generate our own little invoker classes at build time, one per core class method.

Just core methods? What about user code? Reflection?

What we have here is called “wastefulness”. In order to provide optimal invocation performance for all core methods, we must generate hundreds of these these tiny methods into tiny classes with everything neatly tied up in a bow so the JVM will pretty please perform that invocation for us as quickly as possible. And the largest side effect of all this is that we generate the same bytecode, over and over again, with only the tiniest of changes. In fact, this case only changes one thing: the string name of the method we eventually call on RubyString. There are dozens of these cases in JRuby’s core classes, and if we attempted to extend this mechanism to all Java types we encountered (we don’t, for memory-saving purposes), there would be hundreds of cases of nearly-complete duplication.

What is the concrete downside here aside from DRY in principle? What does this overhead translate to in terms of JAR size? (answered below)

The dirty secret of several JVM implementations, Hotspot included, is that there’s a separate heap (or a separate generation of the heap) used for special types of data like class definitions, class metadata, and sometimes bytecode or JITted native code. And it couldn’t have a scarier name: The Permanent Generation. Except in rare cases, objects loaded into the PermGen are never garbage collected.

Does the PermGen have an artificial limit or does it compete for space with the regular heap?

Enter java.dyn.AnonymousClassLoader. First, classes loaded by AnonymousClassLoader are not given full-fledged symbolic names in the global symbol tables; they’re given rough numeric identifiers - naming conflicts essentially do not happen. Second, the classes are loaded without a parent ClassLoader, so there’s no overprotective mother keeping them on a short leash. When the last normal references to the class disappear, it’s eligible for garbage collection like any other object. Third, it provides a mechanism whereby an existing class can be loaded and slightly modified, producing a new class with those modifications but sharing the rest of its structure and data.

public static class Invoker implements InvokerIfc {
    public Object doit(Integer b) {
        return fake(new Something()).target(b);
    }
}

public static Class rewrite(Class old) throws IOException, InvalidConstantPoolFormatException {
    HashMap constPatchMap = new HashMap();
    constPatchMap.put("fake", "real");

    ConstantPoolPatch patch = new ConstantPoolPatch(Invoker.class);
    patch.putPatches(constPatchMap, null, null, true);

    return new AnonymousClassLoader(Invoker.class).loadClass(patch);
}

Here’s a very simple example of passing an existing class (Invoker) through AnonymousClassLoader, translating the method name “fake” in the constant pool into the name “real”. The resulting class has exactly the same bytecode for its “doIt” method and the same metadata for its fields and methods, but instead of calling the “fake” method it will call the “real” method.

This is very cool, almost magical!

Even if we accept that everything’s going to be an Object, we still want to avoid stuffing arguments into an Object[] every time we want to make a call. It’s wasteful, because of all those transient Object[] we create and collect, and it’s slow, because we need to populate those arrays and read from them on the other side. So you end up hand-generating many different methods to support signatures that don’t box arguments into Object[]. What we really need is a way to ask the JVM for a lightweight, non-reflected, statically-typed “handle” to a method that’s primitive enough for the JVM to treat it like a function pointer. MethodHandle is the next major piece of infrastructure added for InvokeDynamic.

MethodHandles also provides a way to adapt and compose handles. Perhaps the simplest adaptation is currying.

The culmination of InvokeDynamic is, of course, the ability to make a dynamic call that the JVM not only recognizes, but also optimizes in the same way it optimizes plain old static-typed calls.

In order to make dynamic languages truly first-class citizens on the JVM, they need to be able to actively participate in method dispatch decisions. The bootstrap method is simply a piece of code that the JVM can call when it encounters a dynamic invocation. The bootstrap receives all information about the call directly from the JVM itself, makes a decision about where that call needs to go, and provides that information to the JVM.

Because of the low probability of a new bytecode being approved, and because it really wasn’t necessary, John introduced a “special” new interface type called java.dyn.Dynamic. Dynamic does not include any methods, nor is it intended as a marker interface. You can implement it if you like, but its real purpose comes when paired with the invokeinterface bytecode. For you see, under InvokeDynamic, an invokeinterface against Dynamic is not really an interface invocation at all.

public java.lang.Object doDynamicCall(java.lang.Object);
  Code:
   0: aload_1
   1: invokeinterface #3; //Method java/dyn/Dynamic.myDynamicMethod:()V
   4:   areturn

Hooray! We’ve set up a dynamic call! Wasn’t that easy?

InvokeDynamic is a work in progress. It first successfully performed a dynamic invocation on August 26, 2008.

Edit