Что это тогда значит?
Давайте начнем с рассказа. Несколько недель назад я предложил внести изменения в список рассылки основных библиотек Java, чтобы переопределить некоторые методы, которые используются в настоящее время final. Это стимулировало несколько тем для обсуждения, одной из которых была степень, в которой регрессия производительности будет введена путем использования метода, который был, finalи прекращения его существования final.
У меня были некоторые идеи о том, будет ли снижение производительности или нет, но я отложил их в сторону, чтобы попытаться выяснить, были ли опубликованы какие-либо вменяемые тесты по этому вопросу. К сожалению, я не смог найти ни одного. Это не означает, что они не существуют или что другие люди не исследовали ситуацию, но я не видел ни одного публичного рецензируемого кода. Итак — время написать несколько тестов.
Методология сравнительного анализа
Поэтому я решил использовать потрясающую среду JMH , чтобы собрать воедино эти тесты. Если вы не уверены, что фреймворк поможет вам получить точные результаты бенчмаркинга, посмотрите на этот доклад Алексея Шипилева , который написал фреймворк, или на действительно классный пост в блоге Ницана Вакарта, в котором объясняется, как он помогает.
В моем случае я хотел понять, что повлияло на производительность вызова метода. Я решил попробовать разные варианты вызовов методов и измерить стоимость. Имея набор критериев и изменяя только один фактор за один раз, мы можем индивидуально исключить или понять, как различные факторы или комбинации факторов влияют на затраты на вызов метода.
Встраивание
Давайте раздавим эти методы вызова.
Одновременно самый и наименее очевидный фактор, влияющий на ситуацию — это то, есть ли вообще вызов метода! Возможно, что фактическая стоимость вызова метода будет полностью оптимизирована компилятором. Вообще говоря, есть два способа снизить стоимость звонка. Одним из них является непосредственное включение самого метода, другим является использование встроенного кэша. Не волнуйтесь — это довольно простые понятия, но здесь есть немного терминологии, которую необходимо ввести. Давайте представим, что у нас есть класс с именем Foo, который определяет метод с именем bar.
class Foo {
void bar() { ... }
}
Мы можем вызвать barметод, написав код, который выглядит следующим образом:
Foo foo = new Foo(); foo.bar();
Важной вещью здесь является место, где фактически вызывается панель foo.bar()— это называется местом вызова . Когда мы говорим, что метод «встроен», это означает, что тело метода берется и помещается в место вызова вместо вызова метода. Для программ, которые состоят из множества небольших методов (я бы сказал, правильно разработанная программа), встраивание может привести к значительному ускорению. Это потому, что программа не тратит большую часть своего времени на вызовы методов и фактически не выполняет работу! Мы можем контролировать, является ли метод встроенным или нет в JMH, используя CompilerControlаннотации. Мы вернемся к концепции встроенного кэша чуть позже.
Глубина иерархии и основные методы
Родители замедляют своих детей?
Если мы решили удалить finalключевое слово из метода, это означает, что мы сможем переопределить его. Это еще один фактор, который нам необходимо учитывать. Поэтому я взял методы и вызвал их на разных уровнях иерархии классов, а также имел методы, которые были переопределены на разных уровнях иерархии. Это позволило мне понять или устранить то, как глубокая иерархия классов мешает переопределению затрат.
Полиморфизм
Животные: как описывается любая концепция ОО.
Когда я упомянул идею создания сайта для вызовов ранее, я незаметно избежал довольно важной проблемы. Поскольку finalв подклассе можно переопределить не- метод, наши сайты вызовов могут в конечном итоге вызывать разные методы. Так что, возможно, я передаю Foo или его потомок — Baz, который также реализует панель (). Как ваш компилятор узнает, какой метод вызывать? Методы по умолчанию являются виртуальными (переопределяемыми) в Java, для каждого вызова необходимо искать правильный метод в таблице, называемой виртуальной таблицей. Это довольно медленно, поэтому оптимизирующие компиляторы всегда стараются снизить затраты на поиск. Один из подходов, который мы упомянули ранее, это встраивание, что замечательно, если ваш компилятор может доказать, что на данном месте вызова может быть вызван только один метод. Это называется мономорфным позывным.
К сожалению, большая часть времени, необходимого для доказательства того, что каллсит является мономорфным, может оказаться непрактичным. JIT-компиляторы, как правило, используют альтернативный подход для профилирования, какие типы вызываются на месте вызова, и предполагают, что если он был мономорфным для его первых N вызовов, то его стоит спекулятивно оптимизировать, исходя из предположения, что он всегда будет мономорфным. Эта спекулятивная оптимизация часто верна, но поскольку она не всегда правильна, компилятору необходимо ввести защитный код перед вызовом метода, чтобы проверить тип метода.
Мономорфные места вызова — не единственный случай, для которого мы хотим оптимизировать. Многие коллизии — это то, что называется биморфным — есть два метода, которые можно вызвать. Вы все еще можете встроить биморфные вызовы, используя свой защитный код, чтобы проверить, какую реализацию вызывать, а затем перейти к ней. Это все еще дешевле, чем полный вызов метода. Также возможно оптимизировать этот случай, используя встроенный кеш. Встроенный кэш на самом деле не включает тело метода в место вызова, но у него есть специальная таблица переходов, которая действует как кэш при полном поиске в vtable. JIT-компилятор горячей точки поддерживает биморфные встроенные кэши и объявляет, что любой CallSite с 3 или более возможными реализациями является мегаморфным .
Это разделяет еще 3 ситуации вызова для сравнения и исследования: мономорфный случай, биморфный случай и мегаморфный случай.
Полученные результаты
Давайте сгруппируем результаты, чтобы было легче видеть древесину на деревьях, я представил необработанные числа вместе с небольшим анализом вокруг них. Конкретные цифры / затраты не представляют особого интереса. Что интересно, так это соотношение между различными типами вызовов методов и низкой частотой связанных с ними ошибок. Происходит довольно существенная разница — 6,26х между самым быстрым и самым медленным. В действительности разница, вероятно, больше из-за накладных расходов, связанных с измерением времени пустого метода.
Исходный код для этих тестов доступен на github . Результаты не все представлены в одном блоке, чтобы избежать путаницы. Полиморфные тесты в конце приходят из бега PolymorphicBenchmark, а остальные изJavaFinalBenchmark
Простые Callsites
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
Our first set of results compare the call costs of a virtual method, a final method and a method which has a deep hierarchy and gets overridden. Note that in all these cases we’ve forced the compiler to not inline the methods. As we can see the difference between the times is pretty minimal and and our mean error rates show it to be of no great importance. So we can conclude that simply adding the final keyword isn’t going to drastically improve method call performance. Overriding the method also doesn’t seem to make much difference either.
Inlining Simple Callsites
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
Now, we’ve taken the same three cases and removed the inlining restriction. Again the final and virtual method calls end up being of a similar time to each other. They are about 4x faster than the non-inlineable case, which I would put down to the inlining itself. The always overridden method call here ends up being between the two. I suspect that this is because the method itself has multiple possible subclass implementations and consequently the compiler needs to insert a type guard. The mechanics of this are explained above in more detail under Polymorphism.
Class Hierachy Impact
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
Wow — that’s a big block of methods! Each of the numbered method calls (1-4) refer to how deep up a class hierarchy a method was invoked upon. So parentMethod4 means we called a method declared on the 4th parent of the class. If you look at the numbers there is very little difference between 1 and 4. So we can conclude that hierarchy depth makes no difference. The inlineable cases all follow the same pattern: hierarchy depth makes no difference. Our inlineable method performance is comparable to inlinableAlwaysOverriddenMethod, but slower than inlinableVirtualInvoke. I would again put this down to the type guard being used. The JIT compiler can profile the methods to figure out only one is inlined, but it can’t prove that this holds forever.
Class Hierachy Impact on final methods
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
This follows the same pattern as above — the final keyword seems to make no difference. I would have thought it was possible here, theoretically, for inlinableParentFinalMethod4 to be proved inlineable with no type guard but it doesn’t appear to be the case.
Polymorphism
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
Finally we come to the case of polymorphic dispatch. Monomorphoric call costs are roughly the same as our regular virtual invoke call costs above. As we need to do lookups on larger vtables, they become slower as the bimorphic and megamorphic cases show. Once we enable inlining the type profiling kicks in and our monomorphic and bimorphic callsites come down the cost of our «inlined with guard» method calls. So similar to the class hierarchy cases, just a bit slower. The megamorphic case is still very slow. Remember that we’ve not told hotspot to prevent inlining here, it just doesn’t implement polymorphic inline cache for callsites more complex than bimorphic.
What did we learn?
I think it’s worth noting that there are plenty of people who don’t have a performance mental model that accounts for different types of method calls taking different amounts of time and plenty of people who understand they take different amounts of time but don’t really have it quite right. I know I’ve been there before and made all sorts of bad assumptions. So I hope this investigation has been helpful to people. Here’s a summary of claims I’m happy to stand by.
- There is a big difference between the fastest and slowest types of method invocation.
- In practice the addition or removal of the
finalkeyword doesn’t really impact performance, but, if you then go and refactor your hierarchy things can start to slow down. - Deeper class hierarchies have no real influence on call performance.
- Monomorphic calls are faster than bimorphic calls.
- Bimorphic calls are faster than megamorphic calls.
- The type guard that we see in the case of profile-ably, but not provably, monomorphic callsites does slow things down quite a bit over a provably monomorphic callsite.
I would say that the cost of the type guard is my personal «big revelation». It’s something that I rarely see talked about and often dismissed as being irrelevant.
Caveats and Further Work
Of course this isn’t a conclusive treatment of the topic area!
- This blog has just focussed on type related factors surrounding method invoke performance. One factor I’ve not mentioned is the heuristics surrounding method inlining due to body size or call stack depth. If your method is too large it won’t get inlined at all, and you’ll still end up paying for the cost of the method call. Yet another reason to write small, easy to read, methods.
- I’ve not looked into how invoking over an interface affects any of these situations. If you’ve found this interesting then there’s an investigation of invoke interface performance on the Mechanical Sympathy blog.
- One factor that we’ve completely ignored here is the impact of method inlining on other compiler optimisations. When compilers are performing optimisations which only look at one method (intra-procedural optimisation) they really want as much information as they can get in order to optimize effectively. The limitations of inlining can significantly reduce the scope that other optimisations have to work with.
- Tying the explanation right down to the assembly level to dive into more detail on the issue.
Perhaps these are topics for a future blog post.
Thanks to Aleksey Shipilev for feedback on the benchmarks and to Martin Thompson, Aleksey, Martijn Verburg, Sadiq Jaffer and Chris West for the very helpful feedback on the blog post.