Высокая производительность
Java
Блог компании «Maxifier Development»
30 мая 2014

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

Перевод
Оригинал:
Richard Warburton
От переводчика:
спор сторонников написания final везде и всюду и их противников сродни спору остроконечников и тупоконечников. Как и в некоторых других сообществах, в нашей компании этот вялотекущий спор шел годами. И только эта статья Ричарда Вэрбёртона (Richard Warburton) позволила нашим остроконечникам взять верх.


О чём речь?

Начнем с небольшого рассказа. Несколько недель назад я отправил в список рассылки Java core libs своё предложение убрать модификатор final с некоторых методов. В результате возникло несколько тем для дискуссии. Одна из них, например, — выяснить, в какой степени ухудшится производительность вызова метода, который был final, если этот final с него убрать.

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

Методология бенчмаркинга

Итак, я решил использовать замечательный фреймворк JMH для того, чтобы провести бенчмаркинг. Если вы не уверены, что фреймворк поможет вам получить точные результаты бенчмаркинга, то вам стоит посмотреть это выступление Алексея Шипилёва (@TheShade), автора фреймворка, или по-настоящему крутой блог Нитсана Вакарта (Nitsan Wakart), который объясняет, как это помогает.

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

Inlining

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

class Foo {
  void bar() { ... }
}

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

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

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

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

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

Полиморфизм

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

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

Однако мономорфные callsite-ы — это не единственный случай, когда мы хотим прооптимизировать. Многие callsite-ы являются, что называется, биморфными (bimorphic) — т.е. есть два метода, которые могут быть вызваны. Вы все еще можете встроить биморфные callsite-ы, используя ваш код защиты, проверив, какую реализацию вызвать, а затем приступить к ней. Это все еще дешевле, чем полный вызов метода. Кроме того, можно оптимизировать этот кейс с помощью inline cache. Inline cache на самом деле не встраивает тело метода в callsite, но это имеет специализированную таблицу переходов, которая действует, как кэш на полной таблице виртуальных методов. JIT-компилятор Hotspot поддерживает биморфные встроенные кэши, а любой callsite с 3мя и более возможными реализациями считает мегаморфным.

Таким образом, выделяются 3 вида вызовов для сравнения и исследования: случаи мономорфного, биморфного и мегаморфного вызова.

Результаты

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

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

Простые callsite-ы

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

Встраивание простых callsite-ов

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 раза быстрее, чем в случае запрета встраивания, что я записал бы на счет, собственно, встраивания. Вызов всюду переопределённого метода в конечном итоге оказывается между ними двумя. Я подозреваю, что это потому, что сам метод имеет несколько возможных реализаций подклассов и, следовательно, компилятор должен вставить проверку типа. Механика этого объясняется выше более подробно в разделе «Полиморфизм».

Влияние иерархии классов

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

Влияние иерархии классов на final методы

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 встраиваем и исключить проверку типа, но, похоже, это не так.

Полиморфизм

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

Наконец мы подошли к случаю полиморфного вызова. Стоимость мономорфного вызова, грубо говоря, такая же, как и у наших обычных виртуальных вызовов, описанных выше. По мере того, как нам надо осуществить поиски на больших таблицах виртуальных методов, они становятся медленнее по мере появлений биоморфных и мегаморфных случаев. Как только мы разрешаем встраивание, профилирование выбрасывает лишнее, и наш мономорфный и биоморфный callsite опускается до стоимости наших встроенных вызовов с проверкой типа. Очень похоже на случай иерархии классов, только немного медленнее. Мегаморфный случай все ещё очень медленный. Напомню, что здесь мы не настроили Hotspot на предотвращение встраивания, он просто не реализует полиморфный inline cache для callsite-ов более сложных, чем биморфные.

Что мы поняли?

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


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

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

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


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

Благодарности:
Алексею Шипилёву за фидбек к бенчмарку,
— пользователям Martin Thompson, Martijn Verburg, Sadiq Jaffer and Chris West — за очень полезные отзывы и комментарии к моему блогу.
+42
19,8k 174
Комментарии 5
Похожие публикации
Популярное за сутки