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

    Блогеры и авторы, пытающиеся быть на передовой, уже немало писали про проект 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 = 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));
    }

    Прекрасно, это даёт нам 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. Если вы придёте через пару лет, никто уже ничего менять не захочет.

    Share post

    Similar posts

    Comments 15

      +1

      Ох, не надо, пусть indy остается только для лямбд — там фиксированный шаблон, можно статически скомпилировать, все хорошо. А то ведь произвольный indy — ад для AOT компиляторов. :(
      Но это так, о наболевшем. :)

        0

        Почему ад? Можно же просто вставлять в соответствующих местах вызов JIT...

          0

          Эм, AOT компиляторы не для того существуют, чтобы в JIT ходить. Конечно, это неизбежно в случае indy, но хотелось бы избегать.
          Вот те же лямбды можно статически заменять на new специально класса и программа с лямбдами будет работать без единой динамической загрузки.

          0

          Ну так напиши в мейлинг-лист о своём наболевшем :-) Как я понимаю, AOT-компиляция Oracle тоже интересует.

          +2
          напомнило https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition
          не совсем понятно как один статический MULT заменяет несколько статических полей, каждое упоминание MULT создает новое поле?
            0

            Каждое упоминание Intrinsics.invokedynamic вставляет инструкцию invokedynamic, а она уже сохраняет точку вызова, привязанную к конкретному месту в байткоде, что по большому счёту есть лениво инициализируемое статическое поле в этом классе.


            MULT для удобства сделан, можно его заинлайнить в точки использования, эффект будет тот же, только ещё больше энтерпрайза.

          0

          К сожалению, в подобном сценарии использования это все равно неприменимо. Ну не буду же я везде писать "(BigInteger) Intrinsics.invokedynamic(MULT, "foo", bigNum, bigNum)"! А вынести в метод нельзя.

            0

            Да, в текущем прототипе есть такая проблема. Но ведь никто не сказал, что так и будет всегда. Если есть идеи лучше, высказывайтесь в мейлинг-листе! От Intrinsics. уже сейчас легко избавиться статическим импортом. Я пытаюсь протолкнуть мысль, что BootstrapSpecifier может быть параметризован возвращаемым типом, и тогда удастся обойтись без каста, что уже полдела. Пока не проталкивается.

              0

              Так даже "invokedynamic(MULT, "foo", bigNum, bigNum)" не выглядит хорошим для пользовательского кода. Так что я считаю что пока не будет чего-то подобного async из c# (т.е. что полная сигнатура метода при реализации одна, а при вызове другая) особого улучшения от возможности писать indy через джаву не появится. Основной плюс данной инструкции именно в том, что можно во многих разных местах кода получить разный CallSite. А если таких мест всего 2-3, то я и руками могу разные методы вызвать.


              Т.е. я говорю про что-нибудь в духе


              //в библиотеке
              bootstrap public static CallSite multiplyFactory(MethodHandles.Lookup lookup, String name, MethodType type) {
                return new MultiplyCallSite(type);
              }
              
              //а вызывать в коде его как будто это простой метод:
              BigInteger res = multiplyFactory(num1, num2);

              Но такой штуки не будет абсолютно точно (как минимум, совершенно неясно откуда брать сигнатуру метода).

                0

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

                  0

                  Полиморфная сигнатура — это все-таки другое. Там я могу вызвать метод с любыми аргументами и он просто так будет записан. Здесь же мне нужна конкретная сигнатура. Разве что добавить еще аннотацию.


                  @MethodSignature(parameterTypes = {long.class, long.class}, returnType = BigInteger.class)
                    0

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


                    inline BigInteger multiply(long x, long y) throws Throwable {
                      return (BigInteger)Intrinsics.invokedynamic(MULT, "foo", x, y);
                    }

                    Однако часть рулезности invokedynamic ещё и в самой полиморфной сигнатуре. К примеру то самое, о чём я писал — если переданы два инта, то можно дополнительно оптимизировать, а здесь получится, что они сразу расширятся до лонгов.

                      0

                      Блин, это то решение, про которое я думал в процессе чтения поста, но забыл при чтении предыдущего комментария. Да, так действительно гораздо лучше.

                  0

                  Если уж сравнивать с C#, то не с async, а с dynamic надо сравнивать...

            Only users with full accounts can post comments. Log in, please.