company_banner

Что под капотом компиляторных оптимизаций GraalVM?

Автор оригинала: Aleksandar Prokopec
  • Перевод

Продолжаем разбираться с работой GraalVM, и на этот раз у нас перевод статьи Aleksandar Prokopec «Under the hood of GraalVM JIT optimizations», изначально опубликованной в блоге на Medium. В статье есть несколько интересных ссылок, позже мы постараемся перевести и эти статьи.





В прошлый раз на Medium мы рассматривали вопросы производительности Java Streams API на GraalVM в сравнении с Java HotSpot VM. GraalVM отличается высокой производительностью, и в тех экспериментах мы достигли ускорения от 1.7 до 5 раз. Конечно, конкретные значения выигрыша в производительности всегда будут зависеть от запускаемого кода и нагрузочных данных, поэтому, прежде чем делать какие-то выводы, стоит самостоятельно попробовать запустить ваш код на GraalVM.


В этой статье мы глубже проникнем во внутренности GraalVM и посмотрим, как происходит JIT-компиляция.



JIT-оптимизации в GraalVM


Давайте взглянем на ряд высокоуровневых оптимизаций, которые применяет компилятор GraalVM. В этой статье мы коснемся только самых интересных оптимизаций вместе с конкретными примерами их работы. Если хочется разобраться глубже, хороший обзор компиляторных оптимизаций GraalVM есть в работе под названием «Making collection operations optimal with aggressive JIT compilation».


Инлайнинг


Если не трогать сборку в ahead-of-time, то большинство JIT-компиляторов в современных виртуальных машинах делают внутрипроцедурный анализ. Это означает, что в каждый конкретный момент времени идет анализ одного метода. По этой причине внутрипроцедруный анализ куда быстрее, чем межпроцедурный анализ всей программы целиком, который обычно не успевает выполниться за время, отведенное на работу JIT-компилятора. В компиляторе, применяющем внутрипроцедурные оптимизации (например, оптимизирующем один метод за раз), одной из важнейших фундаментальных оптимизаций является инлайнинг. Инлайнинг важен, поскольку он эффективно увеличивает метод, а значит, компилятору видно больше возможностей оптимизировать одновременно несколько кусков кода, использованного в казалось бы никак не связанных методах.


Возьмем, например, метод volleyballStars из предыдущей статьи:



@Benchmark
public double volleyballStars() {
  return Arrays.stream(people)
    .map(p -> 
      new Person(p.hair, p.age + 1, p.height))
    .filter(p -> p.height > 198)
    .filter(p -> p.age >= 18 && p.age <= 21)
    .mapToInt(p -> p.age)
    .average().getAsDouble();
}

На этой диаграмме мы видим части промужеточного представления (intermediate representation, IR) этого метода в GraalVM, в момент, непосредственно следующий за парсингом соответствующего Java-байткода.



Можно думать об этом IR как о каком-то абстрактном синтаксическом дереве на стероидах — благодаря нему кое-какие оптимизации выполнять проще. Неважно, как именно работает этот IR, но если уж вы захотите глубже разобраться в этой теме, то можно посмотреть на документ под названием «Graal IR: An Extensible Declarative Intermediate Representation».


Главный вывод тут в том, что поток управления метода, обозначенного желтыми узлами графа и красными линиями, последовательно выполняет методы интерфейса Stream: Stream.filter, Stream.mapToInt, IntStream.average. Не обладая точными знаниями о том, что находится в коде этих методов, компилятор не способен упростить метод — и вот тут на помощь приходит инлайнинг!


Трансформация под названием инлайнинг — очень понятная штука: она просто ищет места вызова методов и заменяет их на тело соответствующего заинлайненного метода, встраивает их внутрь. Давайте взглянем на IR метода volleyballStars после инлайнинга части методов. Здесь показана только та часть, что следует за вызовом IntStream.average:



На диаграмме видно, что вызов getAsDouble (узел под номером 71) исчез из IR. Заметьте, что метод getAsDouble объекта OptionalDouble, возвращенного из IntStream.average (последний вызов в методе volleyballStars), в JDK определен следующим образом:



public double getAsDouble() {
  if (!isPresent) {
    throw new NoSuchElementException("No value present");
  }
  return value;
}

Здесь мы можем отыскать загрузку поля isPresent (узел под номером 190, LoadField) и чтение поля value. Тем не менее, от исключения NoSuchElementException не осталось и следа, и нет больше кода, который его бросает.


Так происходит от того, что компилятор GraalVM догадывается: метод volleyballStars никогда не выбросит исключение. Это знание обычно недоступно во время компиляции getAsDouble — его могут вызывать из множества различных мест в программе, и в каком-то другом случае исключение все-таки сработает. Тем не менее, в конкретном методе volleyballStars исключение вряд ли проявится, потому что набор потенциальных звезд волейбола не бывает пустым. По этой причине GraalVM удаляет ветвление и вместо него вставляет FixedGuard — узел, деоптимизирующий код в случае нарушения нашего предположения. Это довольно минималистичный пример, а в реальной жизни существуют намного более сложные случаи того, как инлайнинг помогает другим оптимизациям.


Мы знаем, что дерево вызовов программы обычно очень глубокое или может быть даже бесконечное. Значит, инлайнинг в какой-то момент нужно прекратить — у него есть вполне конкретные ограничения на время работы и объем памяти. Зная об этом, становится понятно: определить, что и когда инлайнить — очень непросто.


Полиморфный инлайнинг


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


К примеру, возьмем метод IntStream.average. Его типичная реализация выглядит так:



@Override public final OptionalDouble average() {
  long[] avg = collect(
    () -> new long[2],
    (ll, i) -> { ll[0]++; ll[1] += i; },
    (ll, rr) -> { ll[0] += rr[0]; ll[1] += rr[1]; });
  return avg[0] > 0 ?
    OptionalDouble.of((double) avg[1] / avg[0]) :
    OptionalDouble.empty();
}

Не дайте кажущейся простоте кода обмануть вас! Этот метод определен в терминах вызовов collect, и здесь происходит магия. Дерево вызовов этого метода (например, иерархия вызовов) быстро разрастается по мере того, как мы глубже проваливаемся в collect. Только взгляните на эту диаграмму:



Начиная с какого-то момента в процессе обхода дерева вызовов, инлайнер упирается в вызов opWrapSink из фреймворка Java-стримов, который представляет из себя абстрактный метод:




abstract<P_IN> Sink<P_IN> wrapSink(Sink<P_OUT> sink);

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


В случае с GraalVM происходит другое: он сохраняет профиль типа целевого метода для каждой непрямой точки вызова. Этот профиль, в сущности — просто таблица, которая говорит, как часто вызывалась каждая из реализаций wrapSink. В нашем случае профиль знает о трех различных реализациях в анонимных классах: ReferencePipeline$2, ReferencePipeline$3, ReferencePipeline$4. Эти реализации вызываются с вероятностью 50%, 25% и 25% соответственно.



0.500000:    Ljava/util/stream/ReferencePipeline$2;
0.250000:    Ljava/util/stream/ReferencePipeline$4;
0.250000:    Ljava/util/stream/ReferencePipeline$3;
notRecorded: 0.000000

Эта информация оказывает компилятору неоценимую помощь, позволяя генерировать typeswitch — короткий оператор switch, проверяющий тип метода в рантайме, далее вызывающий конкретный метод для каждого из перечисленных случаев. На картинке ниже изображена часть промежуточного представления, показывающая typeswitch (три узла if) с проверкой, является ли тип получателя кем-то из ReferencePipeline$2, ReferencePipeline$3 или ReferencePipeline$4. Каждый прямой вызов в успешном ветвлении каждой из проверок InstanceOf теперь можно заинлайнить или подключить к нему какие-то дополнительные оптимизации. Если ни один из типов не прошел проверку, код деоптимизируется в узле Deopt (в качестве альтернативы можно запустить виртуальную диспетчеризацию).



Если хочется глубже разобраться в полиморфном инлайнинге, рекомендую классическую работу по этой теме, «Inlining of Virtual Methods».


Частичный эскейп-анализ


Давайте вернемся к нашему примеру с волейболом. Заметьте, что ни один из объектов Person, аллоцированных внутри лямбды, передающейся в функцию map, не убегает из области видимости метода volleyballStars. Другими словами, в момент, когда заканчивается метод volleyballStars, не существует такой области памяти, которая указывала бы на объекты типа Person. В частности, запись значения getHeight в дальнейшем используется только для фильтрации по высоте.


В какой-то момент по ходу компиляции метода volleyballStars мы приходим к IR, показанному на диаграмме ниже. Блок, начинающийся с узла Begin-1621, начинается аллокацией объекта Person (в узле Alloc), которая инициализируется как значением поля age с инкрементом на 1, так и предыдущим значением поля height. Поле height до этого прочитано в узле LoadField-1539. Результат аллокации инкапсулируется в AllocatedObject-2137 и пересылается в вызов метода accept-1625. Ничего большего компилятор в этот момент сделать уже не может — с его точки зрения, объект убежал из метода volleyballStars. (прим. переводчика: «убегание объекта» по-английски называется «escape», отсюда и название оптимизации «escape analysis»).



После этого компилятор решает заинлайнить вызов accept — это кажется разумным. В результате приходим ко следующему IR:



И вот тут JIT-компилятор запускает частичный эскейп-анализ: он замечает, что AllocatedObject используется, только чтобы читать поле height (напоминаю, height используется только в условии фильтрации, проверить, что высота больше 198). Поэтому компилятор может переназначить чтение поля height-2167 так, чтобы напрямую работать с узлом, который предварительно записан в объект Person (узел Alloc-2136), и это наш LoadField-1539. Более того, узел Alloc здесь и далее не идет на вход никакому другому узлу, поэтому его можно просто удалить — это мертвый код!


Эта оптимизация, на самом деле, является основной причиной, почему в примере с volleyballStars случилось пятикратное ускорение после перехода на GraalVM. Даже несмотря на то, что все объекты Person не нужны и выбрасываются сразу же после создания, их все равно нужно аллоцировать в куче, их память все еще нужно инициализировать. Частичный эскейп-анализ позволяет устранять аллокации или откладывать их, перемещая в те ветвления кода, где объекты действительно убегают и которые случаются куда реже.


Вы можете глубже разобраться в частичном эскейп-анализе в работе под названием «Partial Escape Analysis and Scalar Replacement for Java».


Итоги


В этой статье мы рассмотрели три оптимизации GraalVM: инлайнинг, полиморфный инлайнинг и частичный эскейп-анализ. Существует еще множество разных оптмизаций: раскрутка и расщепление циклов, дублирование путей, нумерация глобальных значений, свертка констант, удаление мертвого кода, спекулятивное выполнение и так далее.


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




От переводчика: дополнительные материалы


На конференциях JPoint и Joker часто рассказывают про GraalVM. Например, на прошлом JPoint 2019 к нам приезжал Thomas Wuerthinger (директор по исследованиям в Oracle Labs, отвечающий за GraalVM) и Олег Шелаев – один из двух официальных евангелистов технологии.

Посмотреть эти и другие видео можно на нашем YouTube-канале:


Напоминаем, что следующий JPoint состоится 15-16 мая 2020 в Москве, и билеты уже можно приобретать на официальном сайте.

JUG Ru Group
Конференции для программистов и сочувствующих. 18+

Комментарии 1

    +4
    Не дайте кажущейся простоте кода обмануть вас!

    О, да! Проще некуда…

    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

    Самое читаемое