JEP 196: Nashorn Optimistic Typing

Аннотация

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

Цели

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

• Добиться, угадывая типы, того, чтобы байт-код, генерируемый Nashorn, как можно шире использовал целочисленную арифметику Java.

• Итоговая производительность должна быть стабильной. Мы не можем допустить её снижения со временем или измерять только пиковую производительность. Это стало бы препятствием для Nashorn как продукта промышленного уровня.

• Добиться того, чтобы байт-код, генерируемый Nashorn, мог отменять оптимистические предположения описанного выше вида с помощью механизма передачи продолжений или выбрасывания исключений. Это необходимо, поскольку нельзя просто заменить в байт-коде целочисленную инструкцию, например, на инструкцию для double, не вызвав ошибок верификации и не изменяя метод на лету.

• Добиться того, чтобы встроенные библиотечные функции Nashorn были оптимальным кодом на Java и эффективно использовали примитивные типы.

• Добиться того, чтобы JVM гораздо лучше оптимизировала «чужой» (не Java) байт-код, например от Nashorn или JRuby, у которого похожие проблемы.

Что не является целью

Для этой работы нельзя поставить цель вида «мы должны достичь X % производительности нативной среды выполнения JavaScript, такой как v8», поскольку областей оптимизации много и они разнообразны. Начальный этап реализации будет считаться успешным, если он добавит не больше допустимых накладных расходов на прогрев, ускорит распространённые бенчмарки JavaScript на порядки, как обещает эта технология, и не вызовет регрессий на бенчмарках, нацеленных на ещё не исследованные области производительности.

Мотивация

Среде выполнения JavaScript Nashorn нужно взаимодействовать с JVM, чтобы генерировать более производительный код. Нативные среды выполнения JavaScript обычно превосходят Nashorn во многих задачах, например в чисто вычислительных. Нам нужно сделать всё возможное, чтобы наше решение на основе байт-кода поверх JVM как можно ближе подошло к этой производительности. Эта работа должна приблизить производительность Nashorn к производительности нативных сред выполнения JavaScript (но, вероятно, в первой итерации не превзойти её).

Если использовать только операции над Object (байт-коды с префиксом «a») и invokedynamic, получается байт-код, который выполняется в HotSpot слишком медленно, хотя он консервативно и корректно реализует JavaScript. Мы не уверены, что мир, состоящий только из упакованных объектов и invokedynamic, когда-нибудь станет быстрым, но это тоже нужно в какой-то мере исследовать в JIT-компиляторе.

Подходить к этому нужно с двух сторон: генерировать байт-код, содержащий как можно больше примитивов, и уметь откатывать код, если предположение о примитивных типах не оправдалось. HotSpot также нужно научиться лучше оптимизировать байт-код, не являющийся Java-байт-кодом, прежде всего конструкции вокруг invokedynamic и в java.lang.invoke.

Описание

Мы предлагаем следующее решение, состоящее из двух частей: для Nashorn и для JVM соответственно. Обратите внимание, что оно отчасти является предположением о том, что осуществимо в пространстве байт-кода и что JVM сможет оптимизировать. Поэтому в этом предложении ещё остаётся место для исследований как для Nashorn, так и для JVM.

Для Nashorn

Мы знаем, что жёсткое задание явных типов во время компиляции значительно повышает производительность получаемого байт-кода. Интересным дипломным проектом было бы написать фронтенд TypeScript для Nashorn, чтобы продемонстрировать эту идею. Это в любом случае стоит сделать в интересах реализаций динамических языков на JVM.

Создание оптимистических методов

Нам нужно генерировать оптимистические методы на основе типов в местах вызова, известных во время выполнения (код для этого уже есть, но отключён). То есть если метод вызывается с целочисленными параметрами, мы можем сгенерировать для него специализированную версию.

Постепенная деоптимизация

Нам также нужно генерировать оптимистический код внутри методов, то есть использовать целочисленное сложение, даже если компилятор не может статически доказать, что мы имеем дело с int, предполагая, что на самом деле это так. Если мы ошиблись, нужно уметь сгенерировать новую версию кода, в которой больше нет неверного предположения (и которая поэтому несколько деоптимизирована по сравнению с предыдущей). Нам также нужно прервать выполнение неверного кода и продолжить выполнение с этой же точки в новом коде. Для этого нужен механизм замены кода на стеке на основе продолжений, реализованный исключительно существующими средствами JVM (байт-кодом и method handles).

Подробное объяснение того, как будут работать оптимистические типы, см. в Lagergren/JVMLS 2013

Обоснование

В JavaScript чаще всего невозможно точно вывести тип данных многих выражений статически. Такие выражения можно консервативно рассматривать как Object, но это сильно снижает скорость выполнения. Если начинать с самых быстрых для вычислений типов и по мере необходимости (just-in-time) выполнять постепенную деоптимизацию к более медленным типам, в итоге получается самая быстрая форма кода, способная работать с заданными входными данными.

Примитивное представление полей

Представление полей в Nashorn (объекты в области видимости представлены как поля в классах Java) нужно изменить так, чтобы это было не просто «Object». Мы экспериментировали с парой полей long/Object, где long используется для всех примитивных типов, а Object — для непримитивных. Микробенчмарки показали, что это даёт значительный прирост производительности для типов, примитивность которых доказуема статически, но в общем случае у нас снова слишком мало информации для ускорения. Скорее всего, результат станет намного, намного лучше, если совместить это с оптимистическим подходом, и ранние эксперименты это подтвердили.

Кроме того, в интересах снижения расхода памяти нам следует изучить более ранний POC для sun.misc.TaggedArray — обходной путь «и ссылка, и примитив, либо одно, либо другое», позволяющий обойти ограничения Object.

Прогрев идёт медленно

Для прогрева нам, возможно, понадобится ленивая генерация кода, которая уже реализована, но не включена. Для некоторых проектов, например «npm» в порте node.js на Java, мы показали, что ленивая генерация кода действительно значительно ускоряет запуск. Однако JVM тоже приходится выполнять большую работу по прогреву: см. ниже.

Классические оптимизации IR

Мы можем выполнять некоторые классические оптимизации кода в байт-коде, потому что знаем больше, чем VM. Например, в цикле

var sum = 0;
for (i = 0; i < 10; x++) {
    sum += y;
}

y может быть методом с побочными эффектами, а valueOf может быть переопределён, но если проверить это перед циклом, код можно преобразовать в

var sum = 0;
 var ytmp = y; //which will throw UnwarrantedOptimismException i y is not a nice primitive
 for (i = 0; i < 10; x++) {
     sum += ytmp;
 }

Анализ use/def

Нам также нужно наложить CFG поверх AST, чтобы строить более точные цепочки use/def, что позволило бы избавиться от предположений вроде

if (x) {
   z = y & f;
   operation_on_z(z)
} else {
   z = "string";
}

чтобы в ветви true можно было статически использовать z как int, что возможно, но сейчас мы из-за ветви else консервативно считаем z имеющим тип Object во всём методе.

См. Söderberg et al, где описана похожая методология

Для JVM

Интринсики для точной арифметики

Различные операции java.lang.Math для точной арифметики (которые выбрасывают ArithmeticException при переполнении) должны стать интринсиками. Каждое оптимистическое сложение в JavaScript должно будет проверять переполнение с помощью этого механизма, и если оно не компилируется всего лишь в арифметическую операцию и инструкцию перехода по переполнению, накладные расходы окажутся слишком большими.

Это необходимо для сохранения семантики JavaScript.

Вызов invoke

Случай MethodHandle.invoke (а не invokeExact), используемый, например, для реализации apply, должен работать быстрее. По словам John Rose, до сих пор там не проводилось никаких оптимизаций, но очень часто мешает упаковка.

Реализация invokedynamic в JRockit могла превратить тестовый метод из примера:

public class Test {
      private final static MethodHandle CALC = MethodHandles.publicLookup().findStatic(Test.class, "calc", int.class, int.class, Object.class);

      static int test() throws Throwable {
          MethodHandle mh = CALC;
          Object aString = "A";
          int a = mh.invoke(1, aString);
          int b = mh.invoke(2, "B");
          Integer c = mh.invoke((Integer)3, 3);
          return a+b+c;
      }

      static int calc(int x, Object o) {
          return x + o.hashCode();
      }
}

в простой return 140. Чтобы HotSpot мог делать то же самое, требуется как минимум улучшить обобщённый случай invoke.

Источник: доклад Fredrik Öhrström на JavaOne 2010

Источник: блог Fredrik Öhrström

java.lang.invoke и LambdaForms

Реализацию LambdaForms нужно улучшить. Они порождают много генерируемого байт-кода, из-за чего прогрев становится проблемой (даже большей, чем просто наличие bootstrap-метода для каждого invokedynamic, чего не избежать). Вероятно, это можно смягчить кэшированием lambda forms. Однако это не должно загрязнять профильную информацию JIT-компилятора.

Накладные расходы на интерпретацию lambda forms — ещё одна проблема, с которой мы часто сталкиваемся. Когда Nashorn достигает устойчивого состояния, новые MethodHandles больше не должны создаваться, а lambda forms — интерпретироваться.

Кэшированные lambda forms при попытке повторно их интерпретировать должны извлекаться в скомпилированном виде, чтобы после однократной компиляции они больше никогда не интерпретировались.

Кроме того, нужно добиться того, чтобы у всех комбинаторов в java.lang.invoke был быстрый путь, позволяющий избежать упаковки или семантики, подобной apply. Сейчас пример того, что мы часто используем и что нуждается в такой оптимизации, — комбинатор catchException. Вероятно, есть и другие примеры, особенно среди комбинаторов, принимающих много параметров.

Нужен более точный анализ типов

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

То, что нужно сделать в JVM, изучено меньше, и нам потребуется как минимум один сотрудник команды компилятора на полную ставку, чтобы помочь нам в этом.

Тестирование

Для проверки семантической корректности подойдут стандартные наборы тестов Nashorn.

Для проверки производительности подойдут существующие бенчмарки, которые следует дополнить набором микробенчмарков, проверяющих инвалидацию оптимистических предположений.

Все стресс-тесты, которые SQE запускает в течение долгого времени, должны по-прежнему выполняться, чтобы гарантировать отсутствие новых утечек ресурсов.

Риски и допущения

Основной риск состоит в том, что JIT-компилятор всё равно не сможет генерировать эффективный код на основе нашей оптимистической информации о типах.

Есть риск, что байт-код окажется слишком узким представлением для эффективных реализаций динамических языков. Возможно, нам придётся делать генерируемый код гораздо более явным и, возможно, придумать механизм, позволяющий передавать JIT-компиляторам HotSpot больше информации, чем позволяет текущий формат байт-кода. Существующий пример системы, способной взаимодействовать с JIT-компилятором более напрямую, — проект Truffle в Oracle Labs, который с помощью аннотаций в интерпретаторе на Java сообщает компилятору Graal, какие предположения делать. Эксперименты показали, что так действительно можно добиться очень высокой пиковой производительности.

В долгосрочной перспективе LambdaForms, возможно, придётся полностью переписать и заменить чем-то другим. JVM JRockit по сути просто генерировала IR для места вызова и передавала его обратно JIT-компилятору, благодаря чему все его оптимизации, такие как распространение констант и устранение распаковки, прозрачно применялись к месту вызова. В C2 это не так просто из-за различных проблем со сращиванием графов, платформенных и глобальных зависимостей.

Наконец, по мере того как генерация кода становится оптимистической, время прогрева будет расти.

Зависимости

• JIT-компиляторы HotSpot.

• Улучшения генерации кода в HotSpot.

• Эффективная реализация MethodHandles.

Влияние

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