Что там с JEP-303 или изобретаем invokedynamic

в 10:40, , рубрики: bytecode, invokedynamic, java, java10, Программирование, умножение, метки: ,

Блогеры и авторы, пытающиеся быть на передовой, уже немало писали про проект Amber в Java 10. В этих статьях обязательно упоминается вывод типов локальных переменных, улучшения enum и лямбд, иногда пишут про pattern matching и data-классы. Но при этом незаслуженно обходится стороной JEP 303: Intrinsics for the LDC and INVOKEDYNAMIC Instructions. Возможно, потому что мало кто понимает, к чему это вообще. Хотя любопытно, что именно об этой фиче ребята из NIX_Solutions фантазировали на Хабре год назад.

Широко известно, что в виртуальной машине Java, начиная с версии 7, есть интересная инструкция invokedynamic (она же indy). Про неё многие слышали, однако мало кто знает, что она делает на самом деле. Кто-то знает, что она используется при компиляции лямбда-выражений и ссылок на методы в Java 8. Некоторые слышали, что через неё реализована конкатенация строк в Java 9. Но хотя это полезные применения indy, изначальная цель всё же немного другая: делать динамический вызов, при котором вы можете вызывать разный код в одном и том же месте. Эта возможность не используется ни в лямбдах, ни в конкатенации строк: там поведение всегда генерируется при первом вызове и остаётся постоянным до конца работы программы (всегда используется ConstantCallSite). Давайте посмотрим, что можно сделать ещё.

Предположим, мы хотели бы написать метод, который перемножает два числа типа long и возвращает BigInteger. Казалось бы, в чём сложность? Одна строчка:

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

Мы побенчмаркали и увидели, что это работает, скажем, 40 наносекунд. Тут мы замечаем, что вроде как накладных расходов много. Очень часто произведение двух long-ов на практике тоже влазит в long. И в таких случаях зачем же нам создавать два честных BigInteger и перемножать, когда можно бы было сперва умножить, а потом завернуть результат в один BigInteger? Как-то так:

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

Эта версия работает примерно вдвое быстрее, около 20 наносекунд. Но толку-то, если она неправильная? Если переполнение всё же произойдёт, то всё, пиши пропало. Как бы проверить, есть переполнение или нет? Оказывается, можно. Есть метод multiplyExact, который умножает, но при переполнении кидает исключение. Java-реализация у него не очень тривиальная, но на неё смотреть не стоит. На самом деле это JVM-интринсик: JIT-компилятор умеет превратить его вызов в последовательность ассемблерных инструкций. На x86 это imul (перемножить) и jo (прыгнуть при переполнении), а там уже надо смотреть, как мы исключение обрабатываем. Но суть в том, что если переполнения нет, то нам это почти ничего не стоит. Давайте вот так напишем:

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));
  }
}

Если мы подаём сюда только маленькие числа, то получаем заветные 20 наносекунд, отлично. Но вот если подаём большие, то это стоит уже не 20 и даже не 40, а где-то 20 тысяч наносекунд. За исключение приходится платить большую цену.

Ну хорошо, давайте начнём с быстрой реализации, а если вдруг переполнение произошло хоть раз, то переключимся на медленную:

private static boolean fast = false;

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));
}

Прекрасно, это даёт нам 20 наносекунд с маленькими числами и 40 наносекунд с большими. Вот только бенчмарки — это же не реальные приложения. В реальном приложении вы умножаете в куче разных мест. Скорее всего в большинстве из них переполнения никогда не бывает, а случается оно только в некоторых местах. Например, у вас такой код:

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

По логике программы во втором случае всегда маленькие числа, а в первом частенько большие. Однако наш умножатор переключится на медленную реализацию в обоих местах, что не очень-то приятно.

Давайте сделаем наш флажок нестатическим, завернув умножатор в объект:

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));
  }
}

Тогда мы можем для каждого умножения в коде завести статическое поле, и в нём будет отслеживаться, бывают ли переполнения конкретно в данном месте:

static final DynamicMultiplier DYNAMIC1 = new DynamicMultiplier();
static final DynamicMultiplier DYNAMIC2 = new DynamicMultiplier();

return DYNAMIC1.multiply(bigNum, bigNum).add(DYNAMIC2.multiply(smallNum, smallNum));

Мы уже близки к цели. В такой реализации есть неудобства: надо на каждый вызов умножения создать отдельное статическое поле. Кроме того, не хотелось бы их инициализировать до фактического использования. Вдруг мы метод с умножениями вообще ни разу не выполняем? Тогда нам потребуется ленивая инициализация каждого из этих полей (хорошо бы ещё и потокобезопасная). Примерно это за нас и делает invokedynamic: он сам связывает скрытое статическое поле с каждым вызовом и сам отвечает за то, чтобы оно было инициализировано лениво и потокобезопасно. Это поле имеет специальный тип — «точка вызова» (CallSite). По большому счёту это просто ссылка на целевой исполняемый код, на который указывает MethodHandle. Но если точка вызова изменяемая, то она может подменять этот самый MethodHandle, когда захочет. Изменяемую точку вызова можно создать с помощью класса MutableCallSite (или VolatileCallSite, если вам требуются гарантии видимости изменений в других потоках). Удобно расширить один из этих классов, чтобы обеспечить необходимое поведение. Давайте напишем свою точку вызова для решения нашей проблемы. Это несколько многословно, но попробуем:

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));
  }
}

Преобразования asType() пригодятся, если в точке вызова тип выражения не точно соответствует нашему типу (например, передаются параметры типа int вместо long). Далее мы в принципе можем использовать это без indy точно так же, как делали выше:

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); // Дурацкие! Дурацкие!
}

Здесь dynamicInvoker — это динамический MethodHandle, который достаёт текущую цель из точки вызова. Несмотря на многословность, это всё работает так же быстро, как и предыдущий пример с DynamicMultiplier'ом, потому что JIT-компилятор очень много знает про все эти MethodHandle и умеет сквозь них очень хорошо инлайнить.

Но где же наш indy? Вот вся заковыка в том, что даже в Java 9 нельзя написать Java-программу, которая бы создала произвольную indy-инструкцию в байткоде. Indy используется в очень конкретных местах, о которых мы уже говорили: лямбды, ссылки на методы, конкатенация строк. Нашим MultiplyCallSite можно воспользоваться, но только если мы сгенерируем байткод какой-нибудь библиотекой вроде ASM. А просто написать Java-код не получится.

На это и нацелен JEP 303: дать людям использовать indy где угодно и как угодно, а бонусом ещё и загружать объекты типа MethodHandle одной инструкцией байткода ldc. Для этого создан класс Intrinsics, который специальным образом интерпретируется компилятором javac. Это интринсики байткода (вызов метода заменяется на определённую инструкцию байткода). Не путайте их с интринсиками JIT-компилятора (где вызов метода заменяется на ассемблерные инструкции). Также созданы вспомогательные классы, реализующие интерфейс Constable: чтобы свернуть в одну инструкцию байткода, значения всех соответствующих аргументов должны комбинироваться из этих самых Constable и быть известными на этапе компиляции.

Использование ldc, кстати, упростит нам наш 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));
  ...
}

Так как на некоторые MethodHandle-объекты можно ссылаться прямо из пула констант класс-файла, Intrinsics.ldc как раз генерирует такую константу и загружает её с помощью инструкции ldc. Нам ещё потребуется bootstrap-метод, который сконструирует нашу точку вызова:

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

И удобно создать константу типа BootstrapSpecifier, которая на него укажет:

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;")));

По сути эта константа MULT — всё, про что вам надо знать в библиотечном коде. Остальное — это детали реализации, которые вас не волнуют. Теперь главное — сгенерируем наконец indy-инструкцию!

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); // И тут от них спасу нет!
}

И это действительно работает! Пропатченный компилятор заменяет вызов на indy-инструкцию, и мы получаем тот же самый результат, но без дополнительных явных статических полей.

Выглядит, конечно, пока не очень красиво. Зато если пользовательский код один раз скомпилировать с indy, вы можете сколько угодно подменять библиотечную реализацию. Например, вы можете сделать промежуточную реализацию, которая определяет переполнение без исключения (медленнее, если переполнения нет, но существенно быстрее, если есть). Далее вы можете считать статистику и переключаться на неё, если в данное место часто приходят как маленькие, так и большие числа. Ещё вы можете оптимизировать под сигнатуру точки вызова. Скажем, если метод в каком-то месте вызван фактически с аргументами (int, int), вы знаете, что переполнения long точно не будет. Для такой сигнатуры можно вернуть ConstantCallSite, который просто перемножает два int'а без всяких проверок на переполнение. Эти изменения можно сделать уже после публикации библиотечного кода и всё, что было скомпилировано ранее, станет работать быстрее.

Чтобы поэкспериментировать с этим API, вам придётся самим выкачать hg-лес Amber, переключиться в ветку constant-folding и собрать OpenJDK через configure и make (инструкция по сборке здесь). После того как вы соберёте, запускайте javac с опцией -XDdoConstantFold.

Возможно, вам это API интересно, но кажется бесполезной тратой времени экспериментировать с ним сейчас. Видно же, что API сырое, кучу бойлерплейта надо писать и явно всё ещё десять раз поменяется. Может лучше подождать, когда всё устаканится? Нет, это подход неправильный. Если API интересно, экспериментировать нужно сейчас, потому что как раз сейчас вы можете повлиять на то, как именно оно десять раз поменяется. Пробуйте сейчас и если у вас есть идеи или замечания, пишите в amber-dev. Если вы придёте через пару лет, никто уже ничего менять не захочет.

Автор: lany

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js