Too Fast, Too Megamorphic: what influences method call performance in Java?

Factors that influence method invocation performance.

Mon 12 May 2014

Whats this all about then?

Let’s start with a short story. A few weeks back I proposed a change on the a Java core libs mailing list to override some methods which are currently final. This stimulated several discussion topics - one of which was the extent to which a performance regression would be introduced by taking a method which was final and stopping it from being final.

I had some ideas about whether there would be a performance regression or not, but I put these aside to try and enquire as to whether there were any sane benchmarks published on the subject. Unfortunately I couldn’t find any. That’s not to say that they don’t exist or that other people haven’t investigated the situation, but that I didn't see any public peer-reviewed code. So - time to write some benchmarks.

Benchmarking Methodology

So I decided to use the ever-awesome JMH framework in order to put together these benchmarks. If you aren't convinced that a framework will help you get accurate benchmarking results then you should look at this talk by Aleksey Shipilev, who wrote the framework, or Nitsan Wakart's really cool blog post which explains how it helps.

In my case I wanted to understand what influenced the performance of method invocation. I decided to try out different variations of methods calls and measure the cost. By having a set of benchmarks and changing only one factor at a time, we can individually rule out or understand how different factors or combinations of factors influence method invocation costs.

Inlining

Let's squish these method callsites down.

Simultaneously the most and least obvious influencing factor is whether there is a method call at all! It's possible for the actual cost of a method call to be optimized away entirely by the compiler. There are, broadly speaking, two ways to reduce the cost of the call. One is to directly inline the method itself, the other is to use an inline cache. Don't worry - these are pretty simple concepts but there's a bit of terminology involved which needs to be introduced. Let's pretend that we have a class called Foo, which 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 important thing here is the location where bar is actually invoked - foo.bar() - this is referred to as a callsite. When we say a method is being "inlined" what is means is that the body of the method is taken and plopped into the callsite, in place of a method call. For programs which consist of lots of small methods (I'd argue, a properly factored program) the inlining can result in a significant speedup. This is because the program doesn't end up spending most of its time calling methods and not actually doing work! We can control whether a method is inlined or not in JMH by using the CompilerControl annotations. We'll come back to the concept of an inline cache a bit later.

Hierarchy Depth and Overriding Methods

Do parents slow their children down?

If we're choosing to remove the final keyword from a method it means that we'll be able to override it. This is another factor which we consequently need to take into account. So I took methods and called them at different levels of a class hierarchy and also had methods which were overridden at different levels of the hierarchy. This allowed me to understand or eliminate how deep class hierarchies interfere with overriding costs.

Polymorphism

Animals: how any OO concept is described.

When I mentioned the idea of a callsite earlier I sneakily avoided a fairly important issue. Since it's possible to override a non-final method in a subclass, our callsites can end up invoking different methods. So perhaps I pass in a Foo or it's child - Baz - which also implements a bar(). How does your compiler know which method to invoke? Methods are by default virtual (overridable) in Java it has to lookup the correct method in a table, called a vtable, for every invocation. This is pretty slow, so optimizing compilers are always trying to reduce the lookup costs involved. One approach we mentioned earlier is inlining, which is great if your compiler can prove that only one method can be called at a given callsite. This is called a monomorphic callsite.

Unfortunately much of the time the analysis required to prove a callsite is monomorphic can end up being impractical. JIT compilers tend to take an alternative approach of profiling which types are called at a callsite and guessing that if the callsite has been monomorphic for it's first N calls then it's worth speculatively optimising based on the assumption that it always will be monomorphic. This speculative optimisation is frequently correct, but because it's not always right the compiler needs to inject a guard before the method call in order to check the type of the method.

Monomorphic callsites aren't the only case we want to optimise for though. Many callsites are what is termed bimorphic - there are two methods which can be invoked. You can still inline bimorphic callsites by using your guard code to check which implementation to call and then jumping to it. This is still cheaper than a full method invocation. It's also possible to optimise this case using an inline cache. An inline cache doesn't actually inline the method body into a callsite but it has a specialised jump table which acts like a cache on a full vtable lookup. The hotspot JIT compiler supports bimorphic inline caches and declares that any callsite with 3 or more possible implementations is megamorphic.

This splits out 3 more invocation situations for us to benchmark and investigate: the monomorphic case, the bimorphic case and the megamorphic case.

Results

Let's groups up results so it's easier to see the wood from the trees, I've presented the raw numbers along with a bit of analysis around them. The specific numbers/costs aren't really of that much interest. What is interesting is the ratios between different types of method call and that the associated error rates are low. There's quite a significant difference going on - 6.26x between the fastest and slowest. In reality the difference is probably larger because of the overhead associated with measuring the time of an empty method.

The source code for these benchmarks is available on github. The results aren't all presented in one block to avoid confusion. The polymorphic benchmarks at the end come from running PolymorphicBenchmark, whilst the others are from JavaFinalBenchmark

Simple 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 final keyword 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.