Megamorphic virtual call - trying to optimize it

user_5382150 0
Viewed 110

we know that there are some techniques that make virtual calls not so expensive in JVM like Inline Cache or Polymorphic Inline Cache.

Let's consider the following situation:

Base is an interface.

public void f(Base[] b) {
    for(int i = 0; i < b.length; i++) {
          b[i].m();   
    }
}

I see from my profiler that calling virtual (interface) method m is relatively expensive. f is on the hot path and it was compiled to machine code (C2) but I see that call to m is a real virtual call. It means that it was not optimised by JVM.

The question is, how to deal with a such situation? Obviously, I cannot make the method m not virtual here because it requires a serious redesign.

Can I do anything or I have to accept it? I was thinking how to "force" or "convince" a JVM to

  1. use polymorphic inline cache here - the number of different types in b` is quite low - between 4-5 types.
  2. to unroll this loop - length of b is also relatively small. After an unroll it is possible that Inline Cache will be helpful here.

Thanks in advance for any advices. Regards,

jvm optimization
1 Answers

HotSpot JVM can inline up to two different targets of a virtual call, for more receivers there will be a call via vtable/itable [1].

To force inlining of more receivers, you may try to devirtualize the call manually, e.g.

if (b.getClass() == X.class) {
    ((X) b).m();
} else if (b.getClass() == Y.class) {
    ((Y) b).m();
} ...

During execution of profiled code (in the interpreter or C1), JVM collects receiver type statistics per call site. This statistics is then used in the optimizing compiler (C2). There is just one call site in your example, so the statistics will be aggregated throughout the entire execution.

However, for example, if b[0] always has just two receivers X or Y, and b[1] always has another two receivers Z or W, JIT compiler may benefit from splitting the code into multiple call sites, i.e. manual unrolling:

int len = b.length;
if (len > 0) b[0].m();
if (len > 1) b[1].m();
if (len > 2) b[2].m();
...

This will split the type profile, so that b[0].m() and b[1].m() can be optimized individually.

These are low level tricks relying on the particular JVM implementation. In general, I would not recommend them for production code, since these optimizations are fragile, but they definitely make the source code harder to read. After all, megamorphic calls are not that bad [2].

[1] https://shipilev.net/blog/2015/black-magic-method-dispatch/
[2] https://shipilev.net/jvm/anatomy-quarks/16-megamorphic-virtual-calls/

user_34484190
Related