Too fast, too megamorphic: what affects the performance of a method call in Java? / Maxifier Development Blog

From a translator: a
dispute between proponents of final writing everywhere and everywhere and their opponents is akin to a pointy and blunt point dispute. As in some other communities, in our company this sluggish dispute has been going on for years. And only this article by Richard Warburton allowed our geniuses to gain the upper hand.

What are you talking about?

Let's start with a short story. A few weeks ago, I sent my suggestion to the Java core libs mailing list to remove the final modifier from some methods. As a result, several topics for discussion arose. One of them, for example, is to find out to what extent the performance of a method call that was final will deteriorate if this final is removed from it.

I had some thoughts about whether a performance regression would occur or not, but I first tried to find out if anyone had already published benchmark results on this issue. Unfortunately, I could not find anything. This does not mean that they do not exist or that other people did not investigate the situation, but I did not see any code that passed the expert review. So it's time to write a few benchmarks.

Benchmarking methodology

So, I decided to use the wonderful JMH framework for benchmarking. If you are not sure that the framework will help you get accurate benchmarking results, then you should watch this presentation by Alexei Shipilev (@TheShade), the author of the framework, or the really cool Nitsan Wakart blog , which explains how this helps.

In my case, I wanted to understand what affected the performance of a method call. I decided to try various variations of method calls and measure the costs of them. Having a set of criteria and varying only one factor at a time, we can understand how various factors or their combinations affect the cost of a method call.

Inlining

At the same time, the most and least obvious influencing factor is whether the method is called at all! The actual method call can be so optimized by the compiler that it will not remain at all. Generally speaking, there are two ways to reduce the cost of a call. One of them is to directly embed the method itself, the other is to use inline cache. Don’t worry - these are fairly simple concepts, but there is a bit of terminology to understand. Imagine that we have a class called Foo that defines a method called bar.

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

We can call the bar method by writing code that looks like this:

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

The main thing here is the place where bar is actually called - foo.bar () - it is called callsite . When we say that the method was inline (built-in), this means that the body of the method is taken and inserted into callsite, instead of calling the method. For programs that consist of many small methods (I think it’s more correct to write programs), embedding can lead to significant acceleration. This is because the program does not spend most of its time on method calls instead of doing the work! We can control whether a method is built-in or not in JMH using the CompilerControl annotation. We will return to the concept of inline cache a bit later.

Depth of hierarchy and redefinition of methods

If we decide to remove the final keyword from the method, this means that we will be able to override it. This is another factor to consider. So I took the methods and called them at different levels of the class hierarchy; there were also methods overridden at different levels of the hierarchy. This allowed me to determine how deeply class hierarchies interact with method overrides.

Polymorphism

When I mentioned the idea of ​​callsite before, I secretly wanted to get around a pretty important question. Since non- finalthe method can be overridden in a subclass, our callsites can end up calling various methods. So maybe I'm dealing with Foo or its child class Baz, which also implements bar (). How does the compiler know which method to call? All methods in Java are virtual (redefined) by default, and for each call you have to look for the correct method in the so-called virtual method table (vtable). This is rather slow, therefore optimizing compilers always try to reduce the cost of such searches. The approach mentioned earlier - inlining or embedding - works great if your compiler can prove that a given callsite can only call one specific method implementation. This is called monomorphic callsite.

Unfortunately, for the most part, proving that callsite is strictly monomorphic is ultimately impractical. JIT compilers generally take an alternative approach, profiling which types are called in callsite and assuming that if callsite was monomorphic in its first N calls, then it is worthy of speculative optimization based on the assumption that it will always be monomorphic. Such speculative optimization is usually true, but not always; therefore, the compiler must implement security before calling the method to verify the type of object the method is being called on.

However, monomorphic callsites are not the only case when we want to optimize. Many callsites are, as they say, bimorphic - i.e. There are two methods that can be called. You can still embed bimorphic callsites using your security code, checking which implementation to call, and then proceed with it. This is still cheaper than a full method call. In addition, you can optimize this case using inline cache. The inline cache does not actually embed the body of the method in callsite, but it does have a specialized branch table that acts like a cache on the full table of virtual methods. The Hotspot JIT compiler supports bimorphic built-in caches, and considers any callsite with 3 or more possible implementations to be megamorphic.

Thus, 3 types of calls are distinguished for comparison and research: cases of monomorphic, bimorph, and megamorphic calls.

results

Group the results so that you can see the forest among the trees; I will present dry numbers along with a little analysis of them. The specific numbers / costs are not really what we are interested in. The relation between different types of method calls is interesting, so that the statistical errors are small. There is a rather significant difference - 6.26 times - between the fastest and the slowest. In reality, this difference will probably be larger due to the costs associated with measuring the time of an empty method.

The source code for these benchmarks is available on GitHub . To avoid confusion, I presented in the part of the results in different blocks. Polymorphic benchmarks are produced using the Polymorphic Benchmark, and the rest using the JavaFinalBenchmark.

Simple Calls

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 result set shows the cost of invoking a virtual method, a final method, and a method that is included in a deep hierarchy and is redefined. Note that in all of these cases, we forced the compiler not to embed methods. As you can see, the difference between the times is minimal and our standard deviations show that this does not matter much. Thus, we can conclude that simply adding a final keyword will not be able to significantly improve call performance. Overriding the method also does not seem to make much difference.

Embedding 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, take the same three cases and remove the embed restriction. Again final and virtual method calls end up having the same duration. They are 4 times faster than in the case of a ban on embedding, which I would write to the account, in fact, embedding. A call to an overridden method everywhere ends up between the two. I suspect that this is because the method itself has several possible implementations of subclasses and, therefore, the compiler must insert a type check. The mechanics of this are explained in more detail in the Polymorphism section.

The influence of the class hierarchy

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, this is a big block of methods! Each of the numbered method calls (1-4) shows how deeply in the class hierarchy the method was called. So parentMethod4 means that we call the method declared in the 4th parent class. If you look at the numbers, the difference between 1 and 4 is very small. Thus, we can conclude that the depth of the hierarchy does not matter. When embedding, everyone follows the same pattern: the depth of the hierarchy does not matter. Our inline method performance is comparable to inlinableAlwaysOverriddenMethod, but slower than inlinableVirtualInvoke. I would relate this to type checking again. The JIT compiler can profile methods to find out that only one has been built in, but it cannot prove that it will always be so.

Effect of class hierarchy 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

Here the same scheme as above - the final keyword seems to have no meaning. I thought it could theoretically prove here that inlinableParentFinalMethod4 is embeddable and exclude type checking, but it doesn't seem to be that way.

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 challenge. The cost of a monomorphic call, roughly speaking, is the same as that of our usual virtual calls described above. As we need to search large tables of virtual methods, they become slower as biomorphic and megamorphic cases appear. As soon as we enable embedding, profiling throws out superfluous, and our monomorphic and biomorphic callsite falls to the cost of our built-in calls with type checking. Very similar to the case of class hierarchy, only a little slower. The megamorphic case is still very slow. Let me remind you that here we did not configure Hotspot to prevent embedding, it just does not implement a polymorphic inline cache for callsites more complex than bimorphs.

What do we understand?

I think it is worth noting that there are many people who do not have a speculative model of productivity that calculates different types of method calls, taking a different amount of time and many people who understand that they use different amounts of time, but actually do not understand it right. I know, because I myself was so and made wrong assumptions. So I hope this study was useful to you. The following briefly summarizes the theses that I advocated in this article:

• There is a big difference between the fastest and slowest type of method call.
• In practice, adding or removing the final keyword does not really affect performance, but if you later reorganize your hierarchy, the process may begin to slow down.
• Deeper class hierarchies have no real impact on call performance.
• Monomorphic calls are faster than bimorph calls.
• Bimorph calls are faster than megamorphic calls.
• When checking the type that we see in the case of profiling, when it is impossible to prove monomorphism, the call slows down a little, compared with monomorphic.

I would say that the price of type checking is my personal "big revelation." This is something that I see is rarely discussed and often neglected.

Cautions and Further Work

Of course, this is not the only possible approach to this issue!

• This article focuses on factors that affect the performance of method calls related to call types. One factor that I did not mention is the heuristic surrounding the method, which is embedded depending on the size or depth of the call stack. If your method is too large, it will not be embedded at all, and you will still end up paying for the cost of calling the method. Another reason to write small, easy to read methods.
• I have not considered how calling through an interface affects any of these situations. If you find this interesting, then there is an interface performance study on the Mechanical Sympathy Blog
• One factor that we completely ignored is the effect of the embed method on other compiler optimizations. When compilers perform optimization in which only one method is analyzed (intra-process optimization), they really need as much information as possible to optimize effectively. Limiting embedding can significantly reduce the context other optimizations will have to work with.
• Linking explanations down to the level of assembler to dive into this issue in more detail.

Perhaps these are topics for future posts.

Thanks:
- to Alexei Shipilev for a feedback to the benchmark,
- to users of Martin Thompson , Martijn Verburg, Sadiq Jaffer and Chris West - for very useful feedback and comments on my blog.