Статьи

Слишком быстро, слишком мегаморфно: что влияет на производительность вызова метода в Java?

Что это тогда значит?

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

У меня были некоторые идеи о том, будет ли снижение производительности или нет, но я отложил их в сторону, чтобы попытаться выяснить, были ли опубликованы какие-либо вменяемые тесты по этому вопросу. К сожалению, я не смог найти ни одного. Это не означает, что они не существуют или что другие люди не исследовали ситуацию, но я не видел ни одного публичного рецензируемого кода. Итак — время написать несколько тестов.

Методология сравнительного анализа

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

В моем случае я хотел понять, что повлияло на производительность вызова метода. Я решил попробовать разные варианты вызовов методов и измерить стоимость. Имея набор критериев и изменяя только один фактор за один раз, мы можем индивидуально исключить или понять, как различные факторы или комбинации факторов влияют на затраты на вызов метода.

Встраивание

flat_cat Давайте раздавим эти методы вызова.

Одновременно самый и наименее очевидный фактор, влияющий на ситуацию — это то, есть ли вообще вызов метода! Возможно, что фактическая стоимость вызова метода будет полностью оптимизирована компилятором. Вообще говоря, есть два способа снизить стоимость звонка. Одним из них является непосредственное включение самого метода, другим является использование встроенного кэша. Не волнуйтесь — это довольно простые понятия, но здесь есть немного терминологии, которую необходимо ввести. Давайте представим, что у нас есть класс с именем Foo , который определяет метод с именем bar .

1
2
3
class Foo {
  void bar() { ... }
}

Мы можем вызвать метод bar , написав код, который выглядит следующим образом:

1
2
Foo foo = new Foo();
foo.bar();

Здесь важно то, где фактически вызывается bar — foo.bar() — это называется местом вызова . Когда мы говорим, что метод «встроен», это означает, что тело метода берется и помещается в область вызовов вместо вызова метода. Для программ, которые состоят из множества небольших методов (я бы сказал, правильно разработанная программа), встраивание может привести к значительному ускорению. Это потому, что программа не тратит большую часть своего времени на вызовы методов и фактически не выполняет работу! Мы можем контролировать, является ли метод встроенным или нет в JMH, используя аннотации CompilerControl . Мы вернемся к концепции встроенного кэша чуть позже.

Глубина иерархии и основные методы

IMG_3015 Родители замедляют своих детей?

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

Полиморфизм

полиморфизм Животные: как описывается любая концепция ОО.

Когда я упомянул идею создания сайта для вызовов ранее, я незаметно избежал довольно важной проблемы. Поскольку в подклассе можно переопределить неконечный метод, наши сайты вызовов могут в конечном итоге вызывать разные методы. Так что, возможно, я передаю Foo или его потомок — Baz, который также реализует панель (). Как ваш компилятор узнает, какой метод вызывать? Методы по умолчанию являются виртуальными (переопределяемыми) в Java, для каждого вызова необходимо искать правильный метод в таблице, называемой виртуальной таблицей. Это довольно медленно, поэтому оптимизирующие компиляторы всегда стараются снизить затраты на поиск. Один из подходов, который мы упомянули ранее, это встраивание, что замечательно, если ваш компилятор может доказать, что на данном месте вызова может быть вызван только один метод. Это называется мономорфным позывным.

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

Мономорфные места вызова — не единственный случай, для которого мы хотим оптимизировать. Многие коллизии — это то, что называется биморфным — есть два метода, которые можно вызвать. Вы все еще можете встроить биморфные вызовы, используя свой защитный код, чтобы проверить, какую реализацию вызывать, а затем перейти к ней. Это все еще дешевле, чем полный вызов метода. Также возможно оптимизировать этот случай, используя встроенный кеш. Встроенный кэш на самом деле не включает тело метода в место вызова, но у него есть специальная таблица переходов, которая действует как кэш при полном поиске в vtable. JIT-компилятор горячей точки поддерживает биморфные встроенные кэши и объявляет, что любой CallSite с 3 или более возможными реализациями является мегаморфным .

Это позволяет разделить еще 3 ситуации вызова для сравнения и исследования: мономорфный случай, биморфный случай и мегаморфный случай.

Полученные результаты

Давайте сгруппируем результаты, чтобы было легче видеть древесину на деревьях, я представил необработанные цифры вместе с небольшим анализом вокруг них. Конкретные цифры / затраты не представляют особого интереса. Что интересно, так это соотношение между различными типами вызовов методов и низкой частотой связанных с ними ошибок. Происходит довольно существенная разница — 6,26х между самым быстрым и самым медленным. В действительности разница, вероятно, больше из-за накладных расходов, связанных с измерением времени пустого метода.

Исходный код для этих тестов доступен на github . Результаты не все представлены в одном блоке, чтобы избежать путаницы. Полиморфные тесты в конце приходят от запуска PolymorphicBenchmark , в то время как остальные от JavaFinalBenchmark

Простые Callsites

1
2
3
4
Benchmark                                                    Mode   Samples         Mean   Mean error    Units
c.i.j.JavaFinalBenchmark.finalInvoke                         avgt        25        2.606        0.007    ns/op
c.i.j.JavaFinalBenchmark.virtualInvoke                       avgt        25        2.598        0.008    ns/op
c.i.j.JavaFinalBenchmark.alwaysOverriddenMethod              avgt        25        2.609        0.006    ns/op

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

Встраивание Простых Callsites

1
2
3
4
Benchmark                                                    Mode   Samples         Mean   Mean error    Units
c.i.j.JavaFinalBenchmark.inlinableFinalInvoke                avgt        25        0.782        0.003    ns/op
c.i.j.JavaFinalBenchmark.inlinableVirtualInvoke              avgt        25        0.780        0.002    ns/op
c.i.j.JavaFinalBenchmark.inlinableAlwaysOverriddenMethod     avgt        25        1.393        0.060    ns/op

Теперь мы взяли те же три случая и сняли ограничение на встраивание. Опять же, final и виртуальный вызовы методов в конечном итоге будут похожи друг на друга. Они примерно в 4 раза быстрее, чем не встроенный корпус, который я бы отнес к самому встроенному. Вызов всегда переопределенного метода в конечном итоге оказывается между ними. Я подозреваю, что это потому, что сам метод имеет несколько возможных реализаций подкласса и, следовательно, компилятор должен вставить защиту типа. Механика этого объясняется выше более подробно в разделе « Полиморфизм» .

Класс Hierachy Impact

1
2
3
4
5
6
7
8
9
Benchmark                                                    Mode   Samples         Mean   Mean error    Units
c.i.j.JavaFinalBenchmark.parentMethod1                       avgt        25        2.600        0.008    ns/op
c.i.j.JavaFinalBenchmark.parentMethod2                       avgt        25        2.596        0.007    ns/op
c.i.j.JavaFinalBenchmark.parentMethod3                       avgt        25        2.598        0.006    ns/op
c.i.j.JavaFinalBenchmark.parentMethod4                       avgt        25        2.601        0.006    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentMethod1              avgt        25        1.373        0.006    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentMethod2              avgt        25        1.368        0.004    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentMethod3              avgt        25        1.371        0.004    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentMethod4              avgt        25        1.371        0.005    ns/op

Вау — это большой блок методов! Каждый из пронумерованных вызовов методов (1-4) относится к тому, как глубоко в иерархии классов был вызван метод. Поэтому parentMethod4 означает, что мы вызвали метод, объявленный для 4-го родителя класса. Если вы посмотрите на числа, разница между 1 и 4 будет очень небольшой. Таким образом, мы можем заключить, что глубина иерархии не имеет значения. Все встроенные случаи следуют одному и тому же шаблону: глубина иерархии не имеет значения. Производительность нашего встроенного метода сравнима с inlinableAlwaysOverriddenMethod , но медленнее, чем inlinableVirtualInvoke . Я бы снова отнес это к типу охранника. JIT-компилятор может профилировать методы, чтобы выяснить, что только один встроен, но он не может доказать, что это выполняется вечно.

Класс Hierachy Влияние на final методы

1
2
3
4
5
6
7
8
9
Benchmark                                                    Mode   Samples         Mean   Mean error    Units
c.i.j.JavaFinalBenchmark.parentFinalMethod1                  avgt        25        2.598        0.007    ns/op
c.i.j.JavaFinalBenchmark.parentFinalMethod2                  avgt        25        2.596        0.007    ns/op
c.i.j.JavaFinalBenchmark.parentFinalMethod3                  avgt        25        2.640        0.135    ns/op
c.i.j.JavaFinalBenchmark.parentFinalMethod4                  avgt        25        2.601        0.009    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentFinalMethod1         avgt        25        1.373        0.004    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentFinalMethod2         avgt        25        1.375        0.016    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentFinalMethod3         avgt        25        1.369        0.005    ns/op
c.i.j.JavaFinalBenchmark.inlinableParentFinalMethod4         avgt        25        1.371        0.003    ns/op

Это происходит по той же схеме, что и выше — final ключевое слово, похоже, не имеет значения. Я бы подумал, что теоретически здесь возможно, чтобы inlinableParentFinalMethod4 оказался встроенным без защиты типов, но, похоже, это не так.

Полиморфизм

1
2
3
4
5
6
Monomorphic: 2.816 +- 0.056 ns/op
Bimorphic: 3.258 +- 0.195 ns/op
Megamorphic: 4.896 +- 0.017 ns/op
Inlinable Monomorphic: 1.555 +- 0.007 ns/op
Inlinable Bimorphic: 1.555 +- 0.004 ns/op
Inlinable Megamorphic: 4.278 +- 0.013 ns/op

Наконец мы подошли к случаю полиморфной отправки. Стоимость мономорфного вызова примерно равна стоимости наших обычных виртуальных вызовов выше. Поскольку нам нужно выполнять поиск на более крупных vtables, они становятся медленнее, как показывают случаи биморфизма и мегаморфизма. Как только мы включим встраивание профилирования типа, пики и наши мономорфные и биморфные коллситы уменьшают стоимость наших вызовов метода «inlined with guard». Так похоже на случаи иерархии классов, только немного медленнее. Мегаморфный случай все еще очень медленный. Помните, что мы не указали горячей точке предотвращать встраивание здесь, она просто не реализует полиморфный встроенный кэш для вызовов более сложных, чем биморфных.

Что мы узнали?

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

  • Существует большая разница между самым быстрым и самым медленным типами вызова методов.
  • На практике добавление или удаление final ключевого слова на самом деле не влияет на производительность, но, если вы потом идете и реорганизуете свою иерархию, все может начать замедляться.
  • Более глубокие иерархии классов не имеют реального влияния на производительность вызовов.
  • Мономорфные вызовы быстрее, чем биморфные вызовы.
  • Биморфные звонки быстрее, чем мегаморфные звонки.
  • Защита типов, которую мы видим в случае профильно, но не доказуемо, мономорфных узлов вызова, немного замедляет работу над доказуемо мономорфным местом вызова.

Я бы сказал, что стоимость охранника — это мое личное «большое откровение». Это то, о чем я редко вижу, и о котором часто говорят, что оно не имеет значения.

Предостережения и дальнейшая работа

Конечно, это не окончательное рассмотрение тематической области!

  • Этот блог только что сфокусирован на связанных с типом факторах, связанных с производительностью метода. Один из факторов, которые я не упомянул, — это метод эвристического окружения, встроенный из-за размера тела или глубины стека вызовов. Если ваш метод слишком велик, он вообще не будет встроен, и вы все равно будете платить за вызов метода. Еще одна причина, чтобы написать небольшие, легко читаемые методы.
  • Я не изучал, как вызов через интерфейс влияет на любую из этих ситуаций. Если вы нашли это интересным, тогда в блоге Mechanical Sympathy есть исследование производительности интерфейса.
  • Один из факторов, который мы здесь полностью проигнорировали, — это влияние встраивания методов на другие оптимизации компилятора. Когда компиляторы выполняют оптимизацию, которая рассматривает только один метод (внутрипроцедурная оптимизация), им действительно нужно столько информации, сколько они могут получить для эффективной оптимизации. Ограничения встраивания могут значительно уменьшить область, с которой должны работать другие оптимизации.
  • Связывание объяснения вплоть до уровня сборки, чтобы погрузиться в более подробную информацию по этому вопросу.

Возможно, это темы для будущего поста в блоге.