High cost of polymorphism in Java Hotspot server

Question

When I run my timing test program in Java Hotspot client, I get consistent behavior. However, when I run it in Hotspot server, I get unexpected result. Essentially, the cost of polymorphism is unacceptably high in certain situations that I've tried to duplicate bellow.

Is this a known issue/bug with Hotspot server, or am I doing something wrong?

Test program and timing are given bellow:

Intel i7, Windows 8
Java HotSpot(TM) 64-Bit Server VM (build 24.45-b08, mixed mode)
Mine2: 0.387028831 <--- polymorphic call with expected timing
Trivial: 1.545411765 <--- some more polymorphic calls
Mine: 0.727726371 <--- polymorphic call with unexpected timing. Should be about 0.38
Mine: 0.383132698 <--- direct call with expected timing

The situation gets worse as I add additional tests. Timing of the tests near the end of the list are completely off.

interface canDoIsSquare {
    boolean isSquare(long x);
}

final class Trivial implements canDoIsSquare {
    @Override final public boolean isSquare(long x) {
        if (x > 0) {
            long t = (long) Math.sqrt(x);
            return t * t == x;
        }
        return x == 0;
    }
    @Override public String toString() {return "Trivial";}
}

final class Mine implements canDoIsSquare {
    @Override final public boolean isSquare(long x) {
        if (x > 0) {
            while ((x & 3) == 0)
                x >>= 2;
            if ((x & 2) != 0 || (x & 7) == 5)
                return false;
            final long t = (long) Math.sqrt(x);
            return (t * t == x);
        }
        return x == 0;
    }

    @Override public String toString() {return "Mine";}
}

final class Mine2 implements canDoIsSquare {
    @Override final public boolean isSquare(long x) {
        // just duplicated code for this test
        if (x > 0) {
            while ((x & 3) == 0)
                x >>= 2;
            if ((x & 2) != 0 || (x & 7) == 5)
                return false;
            final long t = (long) Math.sqrt(x);
            return (t * t == x);
        }
        return x == 0;
    }
    @Override final public String toString() {return "Mine2";}
}

public class IsSquared {
    static final long init = (long) (Integer.MAX_VALUE / 8)
            * (Integer.MAX_VALUE / 2) + 1L;

    static long test1(final canDoIsSquare fun) {
        long r = init;
        long startTimeNano = System.nanoTime();
        while (!fun.isSquare(r))
            ++r;
        long taskTimeNano = System.nanoTime() - startTimeNano;
        System.out.println(fun + ": " + taskTimeNano / 1e9);
        return r;
    }

    static public void main(String[] args) {
        Mine mine = new Mine();
        Trivial trivial = new Trivial();
        Mine2 mine2 = new Mine2();

        test1(mine2);
        test1(trivial);
        test1(mine);

        long r = init;
        long startTimeNano = System.nanoTime();
        while (!mine.isSquare(r))
            ++r;
        long taskTimeNano = System.nanoTime() - startTimeNano;
        System.out.println(mine + ": " + taskTimeNano / 1e9);
        System.out.println(r);
    }
}

Answer 1

The cost is high, indeed, but your benchmark doesn't measure anything really relevant. The JIT can optimize away most of the overhead, but you didn't give it any chance. See e.g. here.

In any case, there's no benchmark warmup and there's On Stack Replacement.

The explanation is probably that the Server Hotspot optimizes better but slower. It assumes that it has enough time and collects the necessary stats longer. So while the Client Hotspot optimized your program, the Server Hotspot was preparing itself to produce better code.

The reason for the worsening with additional tests is that the initially monomorphic call site became bimorphic and then megamorphic.

In reality it's possible that only one of the methods gets called. If you want benchmark this, you have to run each test in its own JVM. This is a real pain, but existing benchmarking frameworks do it for you.

Or you may want to measure the polymorphic case, but then you need to warm up the code with all cases first. This way you can find out which method is faster even in a single JVM (though each will be slowed down by the megamorphic call overhead.

Update

The explanation seems to be the change from monomorphic to megamorhic. When the first test was run, the JVM was knew all the classes (as the instances were already created), but was optimistically assuming that only Mine2 occurs on the call site. So it did a quick check (translated as a conditional branch, which was always correctly predicted and thus very fast), and called the proper method. As it later saw the other two instances being used there, it had to create a branch table for them (the branch prediction still works, but the overhead is higher).

Question

What's unclear: The JVM can move this test out of the loop and thus reduce it's cost to nearly nothing. I can't tell why it doesn't happen.

Answer 2

In short, the JIT can optimises a single method call, and two method calls, in ways it cannot with more multi-polymorphic calls. The number of possible methods which might be called on any given line is what matters and the JIT builds up this picture over time. When a method is inlined further optimisations are possible, but in your case the line in question increases the number of possible method calls from test1 over the life of the run and so it gets slower.

The way I get around this is to duplicate the short test code so each class is tested equally (assuming this is realistic) If you program will be multi-polymorphic when it is running, this is what you should test to be realistic as you can see it can change the results.

When you run the method from a fresh loop you see the benefit of only calling one method from that line of code.

Here is a table of different costs you might see depending on the number of possible methods any individual line can call. http://vanillajava.blogspot.co.uk/2012/12/performance-of-inlined-virtual-method.html

Polymorphism is not designed to improve performance and for me it is entirely reasonable that as the complexity of the polymorphism increases it should be slower.

BTW making methods final doesn't improve the performance any more. The JIT works out if you have called a sub-class on a line by line basis (as discussed)

---

EDIT As you can see the client JVM doesn't optimise the code as much as it is designed fr relatively light eight startup times. This means the client JVM is more consistent, but consistently slower. If you want the best performance you need to consider a number of optimisation strategies which leads to multiple possible outcomes depending on whether the optimisation is applied or not.