How does hashCode () work by default?

Attempting to peer into hashCode() led to a speleological journey through the source code of the JVM, examining the structure of the objects and the associated locking (biased locking), as well as surprising performance implications associated with the use of hashCode() by default.

Trivial mystery

Recently, in a working draft, I made a trivial change to the class: the implementation of toString() , so that the logs were useful. To my surprise, this resulted in about a 5 percent reduction in coverage (coverage drop) of the class. I knew that the whole new code was covered by already existing unit tests, so what's the matter? When analyzing coverage reports, my colleague noticed that the implementation of hashCode() covered only before the changes were made, not after. The reason was clear: by default, toString() calls hashCode() :

 public String toString() { return getClass().getName() + "@" + Integer.toHexString(hashCode()); }

After adjusting toString() our custom hashCode() stopped being called. We missed the test.

Everyone knew what the default implementation of toString() , but ...
')

What is the default implementation of hashCode ()?

The default hashCode() returns a value that is called an identity hash code . I will continue to use this value to distinguish it from hashes generated by the overridden implementations of hashCode() . For information: even if the class overrides hashCode() , you can always get the identification hash of the object o by calling System.identityHashCode(o) .

Common sense dictates that the identification hash uses an integer representation of the memory address. This is evidenced by the J2SE documentation on Object.hashCode () :

... , Java .

However, there are problems with this, since the method contract requires:

Java- hashCode .

Given that the JVM will move objects (for example, during garbage collection during promotion or compaction), after calculating the object's identification hash, we must make sure that it somehow tracks the location of the object itself.

For example, you can take the current position of an object in memory when you first call hashCode() and save it somewhere, for example, in the object header. Then, when the object is moved to another place, the source hash will move with it. The disadvantage of the method is that two objects can have the same hash, but this is allowed by the specification .

The best confirmation will be to look at the source code. Unfortunately, the default java.lang.Object::hashCode() is a native function :

 public native int hashCode();

Wear a helmet!

Real hashCode ()

Note that the hashCode() authentication implementation depends on the JVM . I’ll only consider OpenJDK source code, remember this with every further mention of the JVM. All links refer to the changeset 5934: 87ee5ee27509 of the Hotspot tree, and I believe that most of them are applicable to Oracle JVM, but other machines have their own nuances.

OpenJDK defines the hashCode() input point in src/share/vm/prims/jvm.h and src/share/vm/prims/jvm.cpp . The latter contains:

 JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle)) JVMWrapper("JVM_IHashCode"); //      ;  0,   NULL return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ; JVM_END

ObjectSynchronizer :: FastHashCode () is also called from identity_hash_value_for , which is used by several other call points (for example, System.identityHashCode() )

 intptr_t ObjectSynchronizer::identity_hash_value_for(Handle obj) { return FastHashCode (Thread::current(), obj()) ; }

You can naively expect ObjectSynchronizer :: FastHashCode () to do something like:

 if (obj.hash() == 0) { obj.set_hash(generate_new_hash()); } return obj.hash();

But it turns out that there is a function for a hundred lines. And this is much more complicated. At the very least, we can mark a couple of “if-not-exist-then-generate” blocks:

 mark = monitor->header(); ... hash = mark->hash(); if (hash == 0) { hash = get_next_hash(Self, obj); ... } ... return hash;

This confirms our hypothesis. For now, ignore monitor and be satisfied with getting the object header. It is stored in mark , a pointer to an instance of markOop , which represents the word mark belonging to the lower bits of the object's header. So, we will try to thrust a hash into the word mark. If it is missing, then generate it with get_next_hash , save and return.

Real-time identification hash generation

As we have seen, this is done in get_next_hash . The function offers six methods based on the value of the hashCode variable.

0. Randomly generated number.
1. The function of the address of the object in memory.
2. Rigidly programmed value of 1 (used for sensitivity testing).
3. Consistency.
4. The address of the object in memory, reduced to an integer value.
5. Flow status combined with xorshift (https://en.wikipedia.org/wiki/Xorshift)

What is the default method? According to globals.hpp , in OpenJDK 8, this is method 5:

 product(intx, hashCode, 5, "(Unstable) select hashCode generation algorithm")

The same is true in OpenJDK 9. In OpenJDK 7 and OpenJDK 6 , the first method, the random number generator , is used .

So, if I'm not mistaken, at least since version 6 , the default implementation of hashCode in OpenJDK has nothing to do with the memory address.

Object Headers and Sync

Let's go back a bit and consider a couple of missed moments. First, the ObjectSynchronizer :: FastHashCode () function looks too complicated, it uses more than 100 lines of code to accomplish what we considered to be a “get-or-generate” operation. Secondly, what is it all about - monitor - and why does it have the headers of our object?

The structure of the word mark is a good place to start research. In OpenJDK, it looks like this :

 // markOop   . // //  ,  mark —    oop,   . //     oop   . // // -   (  ,   ): // // 32 : // -------- // hash:25 ------------>| age:4 biased_lock:1 lock:2 ( ) // JavaThread*:23 epoch:2 age:4 biased_lock:1 lock:2 ( (biased) ) // size:32 ------------------------------------------>| (  CMS (CMS free block)) // PromotedObject*:29 ---------->| promo_bits:3 ----->| (,  (promoted) CMS) // // 64 bits: // -------- // unused:25 hash:31 -->| unused:1 age:4 biased_lock:1 lock:2 ( ) // JavaThread*:54 epoch:2 unused:1 age:4 biased_lock:1 lock:2 ( ) // PromotedObject*:61 --------------------->| promo_bits:3 ----->| (,  CMS) // size:64 ----------------------------------------------------->| (  CMS) // // unused:25 hash:31 -->| cms_free:1 age:4 biased_lock:1 lock:2 (COOP &&  ) // JavaThread*:54 epoch:2 cms_free:1 age:4 biased_lock:1 lock:2 (COOP &&  ) // narrowOop:32 unused:24 cms_free:1 unused:4 promo_bits:3 ----->| (COOP && ,  CMS) // unused:21 size:35 -->| cms_free:1 unused:7 ------------------>| (COOP &&   CMS)

For 32 and 64 bits, the format is slightly different. In the second case, there may be two options, depending on whether the compressed Object Pointers are included. In Oracle and OpenJDK 8, they are enabled by default.

Thus, object headers can refer to a free block or to a real object, so that several different states are possible. In the simplest case (“normal object”), the identification hash is stored directly into the lower bits of the header.

But in other states, the pointer is associated with JavaThread or PromotedObject . The case is complicated: if you put the identification hash in a “normal object”, will someone take it out? And where? If the object is biased, then where can we put the hash? What is an anchored object?

Let's try to answer all these questions.

Tied lock (biased locking)

Bound objects are the result of a bound lock . This is the patented mechanism, the default used since HotSpot 6. It tries to reduce the cost of blocking objects. Such operations are expensive because, for the sake of safely processing requests for blocking / unlocking an object from different threads, their implementation is often based on atomic processor instructions ( comparison with exchange ). But it is noticed that in many implementations most objects are ever blocked by only one thread, so the use of atomic operations is often wasteful. To avoid this, JVMs with anchored lock allow threads to try to “snap” an object on their own. When the thread succeeds, it can block / unblock the object without using atomic instructions. And since we do not have threads fighting for the same object, we get a performance boost.

The biased_lock bit in the header indicates whether the object is bound to the stream specified in JavaThread* . The lock bits indicate whether the object is locked.

In OpenJDK, the implementation of an associated lock requires you to write a pointer to the word mark, and as a result you also need to move the word mark itself (containing the identification hash).
This may explain the increased complexity of FastHashCode . The header contains not only the identification hash, but also the blocking state (a pointer to the stream that has established the blocking). Therefore, we need to consider all cases and determine the location of the identification hash.

Let's start with FastHashCode . The first thing we discover is:

 intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) { if (UseBiasedLocking) { if (obj->mark()->has_bias_pattern()) { ... BiasedLocking::revoke_and_rebias(hobj, false, JavaThread::current()); ... assert(!obj->mark()->has_bias_pattern(), "biases should be revoked by now"); } }

Wait a minute Here, the binding and the associated object lock are simply canceled (the false method means "do not try to bind again"). A few lines below it remains really unchanged:

 //        assert (!mark->has_bias_pattern(), "invariant") ;

If I read it correctly, a simple request for an object's identification hash disables the associated lock , which prevents any attempts to block the object to use expensive atomic instructions.

Hell.

Why does storing a locked lock state conflict with saving an identification hash?

To answer this question, we must understand where the word mark (containing the identification hash) may be located, depending on the blocking state of the object. The following transitions are shown:

My (possibly erroneous) opinion is as follows.

For the four states at the top of the schema, OpenJDK will be able to use thin-lock views. In the simplest case (without locks), this means storing the identification hash and other data directly in the space of the word mark in the object:

 unused:25 hash:31 -->| unused:1 age:4 biased_lock:1 lock:2 ( )

In more complex cases, this space is used to store a pointer to a “lock record”. Then the word mark will be “moved” to another place.

Since only one thread is trying to block an object, this pointer actually refers to the memory area in the thread's own stack. This is good for two reasons:

speed (no disagreement or coordination of access to the memory area),
this is enough for the thread to know that it owns the lock (the memory area refers to its own stack).

But it will not always work. If we have competing objects (for example, objects used in synchronized expressions on which several threads intersect), then we need a more complex structure, suitable not only for copying object headers (again “moved”), but also for a waiting list . A similar list is also required if the stream executes object.wait() .

Our needs are met by the ObjectMonitor structure, which is called a “heavy monitor” in the diagram. The value remaining in the object header does not refer to the “moved word mark”, but to a real object (monitor). To access the identification hash, it is now necessary to “get the monitor” (inflating the monitor): make a pointer to the object and read / modify it depending on the field containing the moved word mark. It is more expensive and requires coordination.

There is work for FastHashCode .

In lines L640 through L680 , a header is searched and a check for the presence of a cached identification hash. I believe this is a quick way to check when we don’t need a monitor.

Starting with L682, you 'll have to bite the bullet:

 //      monitor = ObjectSynchronizer::inflate(Self, obj); //         mark = monitor->header(); ... hash = mark->hash();

If there is an id. hash ( hash != 0 ), then the JVM can return it. Otherwise, we can get it from get_next_hash and safely save it in the moved header that is contained in ObjectMonitor .

This gives a reasonable explanation of why the hashCode() call, as applied to a class object that does not override the default implementation, makes the objects inaccessible for the associated lock:

To preserve the consistency of the identity cache after the move, we need to store the hash in the object header.
Streams requesting an identification hash may not bother with blocking an object at all. But in practice they will share the data structures used by the lock mechanism. This is a very complex system, since it can not only change, but also move the contents of the headers.
A tied lock helps to perform lock / unlock operations without using atomic operations. This is effective as long as the object is blocked by only one thread, because we need to store the lock state in the word mark. I’m not quite sure, but as I understand it, since other threads may request an identification hash, even if only one thread needs blocking , the header word will be concurrent and you will need to use atomic operations for correct processing. What makes sense an attached lock.

Subtotals

The default hashCode() (identification hash) is not related to the memory address of the object , at least in OpenJDK. In versions 6 and 7, this is a randomly generated number. In versions 8 and 9, this number is derived from the state of the stream. Here is a test that led to the same conclusion .
- The proof of implementation-dependent warnings is not for aesthetics: Azul's Zing does generate an identification hash based on the memory address of the object.
In HotSpot, an identification hash is generated only once, and then cached in the mark word in the object header.
- In Zing, in order to preserve consistency when moving, a delaying mechanism for saving id.hash is used until the object is moved. In this case, the hash is stored in the “overhead”.
In HotSpot, a default hashCode() or System.identityHashCode() call causes the object to become unavailable for the associated lock.
- This means that when synchronizing objects that do not have disagreements, you should better override the default implementation of hashCode() , otherwise you will not be able to use JVM optimizations.
In HotSpot, you can disable the associated lock for each object separately.
- This is a very useful feature. I have encountered applications in which very often there are disagreements between production / consumption queues; an attached lock was more disturbing than helping, so I had to turn it off. We did this only for specific objects / classes, simply calling System.identityHashCode () with reference to them.
I did not find the flag in HotSpot that allows changing the generator by default, so experimenting with other options may require compiling from source.

Benchmarks

To test my conclusions, I wrote a simple JMH test.

The benchmark ( source ) does something like this:

 object.hashCode(); while(true) { synchronized(object) { counter++; } }

One configuration ( withIdHash ) synchronizes an object that uses an identification hash, so you can expect the withIdHash lock to be disabled when you call hashCode() . The second configuration ( withoutIdHash ) implements a custom hash, in which the withoutIdHash lock is not disabled. Each configuration is first run with one thread, then with two (they get the Contended suffix).

By the way, you need to enable -XX:BiasedLockingStartupDelay=0 , otherwise the JVM will take four seconds to start the optimization, which distorts the result.

First start:

 Benchmark Mode Cnt Score Error Units BiasedLockingBenchmark.withIdHash thrpt 100 35168,021 ± 230,252 ops/ms BiasedLockingBenchmark.withoutIdHash thrpt 100 173742,468 ± 4364,491 ops/ms BiasedLockingBenchmark.withIdHashContended thrpt 100 22478,109 ± 1650,649 ops/ms BiasedLockingBenchmark.withoutIdHashContended thrpt 100 20061,973 ± 786,021 ops/ms

A custom hash quadruples the lock / unlock cycle four times compared to the ID hash (which disables the lock lock). When two threads compete for a lock, the associated lock is disabled anyway, so there is no significant difference between the two hashing methods.

On the second launch, the -XX:-UseBiasedLocking lock is disabled ( -XX:-UseBiasedLocking ) in all configurations.

 Benchmark Mode Cnt Score Error Units BiasedLockingBenchmark.withIdHash thrpt 100 37374,774 ± 204,795 ops/ms BiasedLockingBenchmark.withoutIdHash thrpt 100 36961,826 ± 214,083 ops/ms BiasedLockingBenchmark.withIdHashContended thrpt 100 18349,906 ± 1246,372 ops/ms BiasedLockingBenchmark.withoutIdHashContended thrpt 100 18262,290 ± 1371,588 ops/ms

The hashing method no longer affects the result, and withoutIdHash loses its advantage.

All benchmarks were run on Intel Core i5 2.7 GHz.

Links

Everything that is not wild speculation and my weak reasoning in an attempt to comprehend the source code JVM, collected from various sources. The main ones are:

Source: https://habr.com/ru/post/321306/

All Articles