What's up with JEP-303 or inventing invokedynamic

Bloggers and authors who are trying to be at the forefront have already written a lot about the Amber project in Java 10. These articles necessarily mention the output of types of local variables , the enum and lambda improvements , sometimes they write about pattern matching and data classes. But at the same time, JEP 303 : Intrinsics for the LDC and INVOKEDYNAMIC Instructions undeservedly does . Perhaps because few people understand what it is all about. Although it is curious that the guys from NIX_Solutions fantasized about this feature on Habr a year ago.

It is widely known that in the Java virtual machine, starting with version 7, there is an interesting invokedynamic instruction (aka indy). Many have heard about her, but few know what she is actually doing. Someone knows that it is used when compiling lambda expressions and method references in Java 8. Some have heard that string concatenation is implemented through it in Java 9. But although these are useful applications of indy, the original goal is still a bit different: make dynamic a call in which you can call different code in the same place. This feature is not used either in lambdas or in string concatenation: there the behavior is always generated on the first call and remains constant until the end of the program ( ConstantCallSite is always used ). Let's see what more can be done.

Suppose we would like to write a method that multiplies two type numbers longand returns BigInteger. It would seem, what is the difficulty? One line:

static BigInteger multiplyNaive(long l1, long l2) {
  return BigInteger.valueOf(l1).multiply(BigInteger.valueOf(l2));
}

We benchmarked and saw that it works, say, 40 nanoseconds. Here we notice that there seems to be a lot of overhead. Very often, the product of two longs in practice also fits into long. And in such cases, why do we need to create two honest BigInteger and multiply when it would be possible to multiply first, and then wrap the result in one BigInteger? Something like this:

static BigInteger multiplyIncorrect(long l1, long l2) {
  return BigInteger.valueOf(l1 * l2);
}

This version works about twice as fast, about 20 nanoseconds. But what's the point if it is wrong? If overflow does occur, then all, write is gone. How would I check if there is an overflow or not? It turns out you can. There is a multiplyExact method that multiplies, but throws an exception when overflowing. Its Java implementation is not very trivial, but you should not look at it. This is actually a JVM intrinsic: the JIT compiler can turn its invocation into a sequence of assembler instructions. On x86 it imul(multiply) and jo(jump at overflow), and there it is already necessary to watch how we handle the exception. But the bottom line is that if there is no overflow, then it costs us almost nothing. Let's write like this:

static BigInteger multiplyOverflow(long l1, long l2) {
  try {
    return BigInteger.valueOf(Math.multiplyExact(l1, l2));
  } catch (ArithmeticException e) {
    return BigInteger.valueOf(l1).multiply(BigInteger.valueOf(l2));
  }
}

If we give here only small numbers, we get the coveted 20 nanoseconds, excellent. But if you serve large, then it costs not 20 or even 40, but somewhere around 20 thousand nanoseconds. For the exception you have to pay a big price.

Well, let's start with a quick implementation, and if suddenly an overflow occurred at least once, then switch to slow:

private static boolean fast = true;
static BigInteger multiplySwitch(long a, long b) {
  if (fast) {
    try {
      return BigInteger.valueOf(Math.multiplyExact(a, b));
    } catch (ArithmeticException ex) {
      fast = false;
    }
  }
  return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b));
}

Great, this gives us 20 nanoseconds with small numbers and 40 nanoseconds with large. Here are just benchmarks - these are not real applications. In a real application, you multiply in a bunch of different places. Most likely, in most of them there is never an overflow, and it happens only in some places. For example, you have the following code:

return multiplySwitch(bigNum, bigNum).add(multiplySwitch(smallNum, smallNum));

According to the logic of the program, in the second case there are always small numbers, and in the first case they are often large. However, our multiplier will switch to slow implementation in both places, which is not very nice.

Let's make our flag non-static by wrapping the multiplier in an object:

class DynamicMultiplier {
  private boolean fast = true;
  BigInteger multiply(long a, long b) {
    if (fast) {
      try {
        return BigInteger.valueOf(Math.multiplyExact(a, b));
      } catch (ArithmeticException ex) {
        fast = false;
      }
    }
    return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b));
  }
}

Then we can create a static field for each multiplication in the code, and it will monitor whether there are overflows in this particular place:

static final DynamicMultiplier DYNAMIC1 = new DynamicMultiplier();
static final DynamicMultiplier DYNAMIC2 = new DynamicMultiplier();
return DYNAMIC1.multiply(bigNum, bigNum).add(DYNAMIC2.multiply(smallNum, smallNum));

We are already close to the goal. There are inconveniences in such an implementation: it is necessary to create a separate static field for each multiplication call. In addition, I would not want to initialize them before actual use. Suddenly we never do a method with multiplications at all? Then we need lazy initialization of each of these fields (it would be nice to be thread safe as well). This is what the invokedynamic does for us, for example: he himself associates a hidden static field with every call and is responsible for ensuring that it is initialized lazily and thread-safe. This field has a special type - Call Point ( CallSite ). By and large, it's just a reference to the target executable code that MethodHandle points to. But if the call point is mutable, then it can replace this same MethodHandle when it wants. A mutable dial peer can be created using the MutableCallSite class (or VolatileCallSite , if you need guarantees of visibility of changes in other threads). It is convenient to extend one of these classes to provide the necessary behavior. Let's write our call point to solve our problem. This is somewhat verbose, but try:

static class MultiplyCallSite extends MutableCallSite {
  // Тип: принимает два long'а, возвращает BigInteger
  static final MethodType TYPE = MethodType.methodType(BigInteger.class, long.class, long.class);
  private static final MethodHandle FAST;
  private static final MethodHandle SLOW;
  static {
    try {
      FAST = MethodHandles.lookup().findVirtual(MultiplyCallSite.class, "fast", TYPE);
      SLOW = MethodHandles.lookup().findStatic(MultiplyCallSite.class, "slow", TYPE);
    } catch (NoSuchMethodException | IllegalAccessException e) {
      throw new InternalError(e); // Дурацкие проверяемые исключения!
    }
  }
  MultiplyCallSite(MethodType type) {
    super(type);
    // привязываем нестатический метод FAST к this
    setTarget(FAST.bindTo(this).asType(type));
  }
  BigInteger fast(long a, long b) {
    try {
      return BigInteger.valueOf(Math.multiplyExact(a, b));
    } catch (ArithmeticException ex) {
      // Меняем реализацию на медленную: SLOW уже статический метод, он больше ничего не меняет
      setTarget(SLOW.asType(type()));
      return slow(a, b);
    }
  }
  static BigInteger slow(long a, long b) {
    return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b));
  }
}

The asType () transformations come in handy if the type of the expression at the call point does not exactly match our type (for example, type parameters are passed intinstead long). Further, in principle, we can use this without indy in the same way as we did above:

static final MethodHandle MULTIPLIER1 = new MultiplyCallSite(TYPE).dynamicInvoker();
static final MethodHandle MULTIPLIER2 = new MultiplyCallSite(TYPE).dynamicInvoker();
try {
  return ((BigInteger) MULTIPLIER1.invokeExact(bigNum, bigNum))
          .add((BigInteger) MULTIPLIER2.invokeExact(smallNum, smallNum));
} catch (Throwable throwable) {
  throw new InternalError(throwable); // Дурацкие! Дурацкие!
}

Here dynamicInvoker is a dynamic MethodHandle that pulls the current target from the call point. Despite the verbosity, this all works as fast as the previous DynamicMultiplier example, because the JIT compiler knows a lot about all these MethodHandles and knows how to inline through them very well.

But where is our indy? Here's the catch: even in Java 9 you cannot write a Java program that would create an arbitrary indy instruction in bytecode. Indy is used in very specific places that we have already talked about: lambdas, method references, string concatenation. You can use our MultiplyCallSite, but only if we generate a bytecode with some library like ASM. But simply writing Java code will not work.

This is exactly what JEP 303 aims at: letting people use indy anywhere and anytime, and as a bonus also load objects like MethodHandle with one ldc bytecode instruction. To do this, the Intrinsics class was created , which is specially interpreted by the javac compiler. These are the intrinsics of the bytecode (the method call is replaced with a specific bytecode instruction). Do not confuse them with the intrinsics of the JIT compiler (where the method call is replaced with assembler instructions). Helper classes have also been created that implement the Constable interface : to collapse a bytecode into a single instruction, the values ​​of all the corresponding arguments must be combined from these same Constable and be known at the compilation stage.

Using ldc, by the way, will simplify our ours MultiplyCallSite:

static class MultiplyCallSite extends MutableCallSite {
  // Тип: теперь MethodTypeConstant (J = long)
  private static final MethodTypeConstant TYPE = MethodTypeConstant.of(
    ClassConstant.of("Ljava/math/BigInteger;"), ClassConstant.of("J"), ClassConstant.of("J"));
  // К сожалению, пока нельзя сослаться на класс просто через MultiplyCallSite.class
  private static final ClassConstant ME = ClassConstant.of("LIndyTest$MultiplyCallSite;");
  // Никаких исключений!
  private static final MethodHandle FAST = Intrinsics.ldc(MethodHandleConstant.ofVirtual(
    ME, "fast", TYPE));
  private static final MethodHandle SLOW = Intrinsics.ldc(MethodHandleConstant.ofStatic(
    ME, "slow", TYPE));
  ...
}

Since some MethodHandle objects can be referenced directly from the pool of constants of the class file, Intrinsics.ldcit just generates such a constant and loads it using the ldc instruction . We still need a bootstrap method that constructs our call point:

public static CallSite multiplyFactory(MethodHandles.Lookup lookup, String name, MethodType type) {
  return new MultiplyCallSite(type);
}

And it’s convenient to create a constant like BootstrapSpecifier that points to it:

public static final BootstrapSpecifier MULT = BootstrapSpecifier.of(MethodHandleConstant.ofStatic(
    ClassConstant.of("LIndyTest;"), "multiplyFactory", 
    // Вот это жёстко смотрится, конечно.
    MethodTypeConstant.of("(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;")));

In fact, this MULT constant is all that you need to know about in library code. The rest are implementation details that don't bother you. Now the main thing is to finally generate an indy instruction!

try {
  // вместо "foo" может быть любое имя - нам не важно
  return ((BigInteger) Intrinsics.invokedynamic(MULT, "foo", bigNum, bigNum))
          .add((BigInteger) Intrinsics.invokedynamic(MULT, "foo", smallNum, smallNum));
} catch (Throwable throwable) {
  throw new InternalError(throwable); // И тут от них спасу нет!
}

And it really works! The patched compiler replaces the call with an indy instruction, and we get the same result, but without additional explicit static fields.

It looks, of course, so far not very beautiful. But if you compile the user code once with indy, you can replace the library implementation as much as you like. For example, you can make an intermediate implementation that defines overflow without exception (slower if there is no overflow, but significantly faster if there is one). Then you can read the statistics and switch to it, if both small and large numbers often come to this place. You can also optimize for the signature of the dial peer. Say, if a method is actually called in some place with arguments (int, int), you know that longthere will definitely not be an overflow . For such a signature, you can returnConstantCallSite, which simply multiplies two ints without any overflow checks. These changes can be made already after the publication of the library code, and everything that was compiled earlier will work faster.

To experiment with this API, you have to download the Amber hg-forest yourself , switch to the constant-folding branch and build OpenJDK via configure and make (assembly instructions here ). After you build, run javac with the option -XDdoConstantFold.

You might be interested in this API, but it seems like a waste of time experimenting with it now. It is clear that the API is raw, you need to write a bunch of boilerplate and obviously still change ten times. Maybe it's better to wait until everything settles down? No, this is the wrong approach. If the API is interesting, you need to experiment now, because right now you can influence how it changes ten times. Try it now and if you have ideas or comments, write to amber-dev . If you come in a couple of years, no one will want to change anything.