Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is hashCode slower than a similar method?

Normally, Java optimizes the virtual calls based on the number of implementations encountered on a given call side. This can be easily seen in the results of my benchmark, when you look at myCode, which is a trivial method returning a stored int. There's a trivial

static abstract class Base {     abstract int myCode(); } 

with a couple of identical implementation like

static class A extends Base {     @Override int myCode() {         return n;     }     @Override public int hashCode() {         return n;     }     private final int n = nextInt(); } 

With increasing number of implementations, the timing of the method call grows from 0.4 ns through 1.2 ns for two implementations to 11.6 ns and then grows slowly. When the JVM has seen multiple implementation, i.e., with preload=true the timings differ slightly (because of an instanceof test needed).

So far it's all clear, however, the hashCode behaves rather differently. Especially, it's 8-10 times slower in three cases. Any idea why?

UPDATE

I was curious if the poor hashCode could be helped by dispatching manually, and it could a lot.

timing

A couple of branches did the job perfectly:

if (o instanceof A) {     result += ((A) o).hashCode(); } else if (o instanceof B) {     result += ((B) o).hashCode(); } else if (o instanceof C) {     result += ((C) o).hashCode(); } else if (o instanceof D) {     result += ((D) o).hashCode(); } else { // Actually impossible, but let's play it safe.     result += o.hashCode(); } 

Note that the compiler avoids such optimizations for more than two implementation as most method calls are much more expensive than a simple field load and the gain would be small compared to the code bloat.

The original question "Why doesn't JIT optimize the hashCode like other methods" remains and hashCode2 proofs that it indeed could.

UPDATE 2

It looks like bestsss is right, at least with this note

calling hashCode() of any class extending Base is the same as calling Object.hashCode() and this is how it compiles in the bytecode, if you add an explicit hashCode in Base that would limit the potential call targets invoking Base.hashCode().

I'm not completely sure about what's going on, but declaring Base.hashCode() makes a hashCode competitive again.

results2

UPDATE 3

OK, providing a concrete implementation of Base#hashCode helps, however, the JIT must know that it never gets called, as all subclasses defined their own (unless another subclass gets loaded, which can lead to a deoptimization, but this is nothing new for the JIT).

So it looks like a missed optimization chance #1.

Providing an abstract implementation of Base#hashCode works the same. This makes sense, as it provides ensures that no further lookup is needed as each subclass must provide its own (they can't simply inherit from their grandparent).

Still for more than two implementations, myCode is so much faster, that the compiler must be doing something subobtimal. Maybe a missed optimization chance #2?

like image 825
maaartinus Avatar asked Jun 14 '14 18:06

maaartinus


People also ask

Why we check hashCode () equality before equals () method?

If an object's hashcode is not the same as another object's hashcode, there is no reason to execute the equals() method: you just know the two objects are not the same. On the other hand, if the hashcode is the same, then you must execute the equals() method to determine whether the values and fields are the same.

What is the difference between hashCode and equals?

The value returned by hashCode() is the object's hash code, which is the object's memory address in hexadecimal. equals() checks if the two object references are same. If two objects are equal then their hashCode must be the same, but the reverse is not true.

What happens if hashCode is different from same return?

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result. It is not required that if two objects are unequal according to the equals(java. lang.

Does not overriding hashCode () method have any impact on performance?

Yes you can degrade the performance of a hashed collection if the hashCode method is implemented in a bad way.


1 Answers

hashCode is defined in java.lang.Object, so defining it in your own class doesn't do much at all. (still it's a defined method but it makes no difference)

JIT has several ways to optimize call sites (in this case hashCode()):

  • no overrides - static call (no virtual at all) - best case scenario with full optimizations
  • 2 sites - ByteBuffer for instance: exact type check and then static dispatch. The type check is very simple but depending on the usage it may or may not be predicted by the hardware.
  • inline caches - when few different class instances have been used in the caller body, it's possible to keep them inlined too - that's it some methods might be inlined, some may be called via virtual tables. Inline budget is not very high. This is exactly the case in the question - a different method not named hashCode() would feature the inline caches as there are only four implementations, instead of the v-table
  • Adding more classes going through that caller body results in real virtual call as the compiler gives up.

The virtual calls are not inlined and require an indirection through the table of virtual methods and virtually ensured cache miss. The lack of inlining actually requires full function stubs with parameters passed through the stack. Overall when the real performance killer is the inability to inline and apply optimizations.

Please note: calling hashCode() of any class extending Base is the same as calling Object.hashCode() and this is how it compiles in the bytecode, if you add an explicit hashCode in Base that would limit the potential call targets invoking Base.hashCode().

Way too many classes (in JDK itself) have hashCode() overridden so in cases on not inlined HashMap alike structures the invocation is performed via vtable - i.e. slow.

As extra bonus: While loading new classes the JIT has to deoptimize existing call sites.


I may try to look up some sources, if anyone is interested in further reading

like image 131
bestsss Avatar answered Sep 22 '22 13:09

bestsss