深度解析默认 hashCode() 的工作机制

2019 Java 开发者跳槽指南.pdf (吐血整理)….>>>

(给ImportNew加星标,提高Java技能)

编译:ImportNew/唐尤华

srvaroa.github.io/jvm/java/openjdk/biased-locking/2017/01/30/hashCode.html


本文由浅入深,由hashCode()表面入手,深入JVM源代码从对象布局、偏向锁角度分析默认hashCode()对程序性能产生的巨大影响。


非常感谢Gil Tene和Duarte Nunes对本文审查、建议和编辑,并且提出了非常宝贵的意见。文中如有错误都是我的问题。


细节之谜


上周,我在工作中对一个类进行了一次不起眼的修改,把toString()的实现做了改进,这样日志看起来更容易理解。结果让我大吃一惊,修改后测试通过率下降了近5%。我知道单元测试已经覆盖了所有新的代码,究竟哪里出了问题?比较测试报告时,一位同事敏锐地发现修改hashCode()前这些测试都没有问题。当然,这是有道理的:默认toString()会调用hashCode():


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


覆盖toString()后,自定义实现不再调用hashCode()。这里缺少一个测试。


大家都知道toString()的默认实现,但是……


hashCode()的默认实现是怎样的?


默认hashCode()返回值被称作identity hash code。接下来的文章中,我会用这个术语把它与重写后的hashCode()返回的哈希值进行区分。仅供参考:即使重写了hashCode(),还可以调用System.identityHashCode(o)得到对象的identity hash code。


众所周知,identity hash code使用了内存地址的整数表示。这也是J2SE JavaDocs中关于Object.hashCode()的描述:


...通常把对象内部地址

转换为整数,但这种实现不是 

Java™语言本身的要求。


这种实现似乎由问题,因为方法的定义要求:


执行Java程序时,在同一对象上多次调用

hashCode方法结果必须

返回相同的整数。


鉴于JVM会重定位对象(例如,在垃圾回收周期可能发生提升或压缩),因此在对象identity hash计算完成后需要能够确保不受重定位影响。


一种可能是首次调用hashCode()时获得对象当前内存位置,与对象一起保存在某个地方,比如对象头。这样,即使对象被移到内存其它地方也会保留原来的哈希值。采用这种方法需要注意一点,可能产生两个对象具有相同的identity hash,但这是规范允许的。


最好办法是通过源代码确认。不幸的是,默认的java.lang.Object::hashCode() 是一个原生函数:


public native int hashCode();


开始行动。


能否找到真正的hashCode()?


注意:hashCode()实现与JVM相关。本文只讨论OpenJDK源代码,下文中出现JVM时都特指OpenJDK。源代码请参考Hotspot tree中的changeset 5820:87ee5ee27509。尽管大部分实现在Oracle JVM上应该也使用,但其实际可能会有区别。


OpenJDK在src/share/vm/prims/jvm.h和src/share/vm/prims/jvm.cpp中定义了hashCode()入口。jvm.cpp中:


508 JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
509 JVMWrapper("JVM_IHashCode");
510 // 在经典虚拟机中实现;如果对象为NULL,则返回0
511 return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
512 JVM_END


ObjectSynchronizer::FastHashCode()还被identity_hash_value_for调用,后者有几个地方会调用(例如:System.identityHashCode())。


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


如果希望ObjectSynchronizer::FastHashCode()像下面这样实现:


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


事实会让你大失所望。这个函数有一百行,实际上要复杂得多。可以看到好几个if条件:


685   mark = monitor->header();
...
687 hash = mark->hash();
688 if (hash == 0) {
689 hash = get_next_hash(Self, obj);
...
701 }
...
703 return hash;


似乎证实了之前的假设。暂时先不考虑monitor,只要知道它为我们提供了对象头就好。对象头存储在mark中,它是一个指向markOop实例的指针,代表对象头中的低位mark word。因此,实际会先尝试从mark word中获取哈希值。如果哈希值不存在,会调用,get_next_hash生成哈希值,保存并返回。


生成identity hash


实际生成过程发生在get_next_hash中。该函数会根据hashCode变量值提供6种实现。

0.随机生成数字。
1.根据对象的内存地址生成。
2.对实现1硬编码(用于敏感性测试)。
3.一个序列。
4.对象内存地址,强制转换为int
5.使用线程状态结合xorshift算法生成。(https://en.wikipedia.org/wiki/Xorshift)


那么默认方法是什么?根据globals.hppOpenJDK 8似乎默认采用了第5种方法:


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


OpenJDK 9采用了相同的默认实现。查看早期版本, OpenJDK7 和OpenJDK 6采用了第1种实现,即随机数生成器。


因此除非我看错了地方,否则至少从JDK 6开始,OpenJDK中的hashCode默认实现已经与内存地址无关。


对象头与同步


让我们回顾一下之前没有检查过的几点。首先ObjectSynchronizer::FastHashCode()看起来似乎过于复杂,用了100多行代码来执行get/generate操作。其次,这个monitor是什么?为什么它会存储对象头?


可以从mark word结构入手。在OpenJDK中,mark word看起来是这样:


30 // markOop用来描述对象头信息.
31 //
32 // 注意,mark不是真正的标记,只是一个单词.
33 // 由于历史原因,它被定义在oop结构中.
34 //
35 // 对象头位格式(下面为大端模式):
36 //
37 // 32 bits:
38 // --------
39 // hash:25 ------------>| age:4 biased_lock:1 lock:2 (normal object)
40 // JavaThread*:23 epoch:2 age:4 biased_lock:1 lock:2 (biased object)
41 // size:32 ------------------------------------------>| (CMS free block)
42 // PromotedObject*:29 ---------->| promo_bits:3 ----->| (CMS promoted object)
43 //
44 // 64 bits:
45 // --------
46 // unused:25 hash:31 -->| unused:1 age:4 biased_lock:1 lock:2 (normal object)
47 // JavaThread*:54 epoch:2 unused:1 age:4 biased_lock:1 lock:2 (biased object)
48 // PromotedObject*:61 --------------------->| promo_bits:3 ----->| (CMS promoted object)
49 // size:64 ----------------------------------------------------->| (CMS free block)
50 //
51 // unused:25 hash:31 -->| cms_free:1 age:4 biased_lock:1 lock:2 (COOPs && normal object)
52 // JavaThread*:54 epoch:2 cms_free:1 age:4 biased_lock:1 lock:2 (COOPs && biased object)
53 // narrowOop:32 unused:24 cms_free:1 unused:4 promo_bits:3 ----->| (COOPs && CMS promoted object)
54 // unused:21 size:35 -->| cms_free:1 unused:7 ------------------>| (COOPs && CMS free block)


根据32位或64位格式略有不同。后者根据是否启用压缩对象指针有两种变体。默认情况下,Oracle和OpenJDK默认都会启用。


因此,对象头可能与空闲块或实际对象有关。这种情况下,存在多种可能的状态。“normal object”的处理最简单,identity hash会直接存储到对象头的低地址。


其它情况,则会得到一个指向JavaThread或者PromotedObject的指针。情况愈加复杂:如果把identity hash放入“normal object”中,会有人把它取走吗?在哪里获取呢?如果是biased object,会在哪里存取哈希值?biased object又是怎样的对象?


让我们试着回答这些问题。


偏向锁(Biased Locking)


biased object是偏向锁定的结果。这个功能获得了专利,自HotSpot 6开始引入,用来降低对象锁定带来的开销。由于具体实现依赖CPU原子指令(CAS),因此对来自不同线程的对象安全地进行锁定和解锁开销很大。据观察,大部分应用程序中,多数对象仅被一个线程锁定,因此采用原子操作是一种浪费。为了避免这种情况,JVM采取偏向锁,即允许线程尝试让对象“偏向”自己。当对象处于已偏向状态,这个幸运的线程可以无需原子指令完成对象锁定与解锁。只要没有线程争用相同的对象,这种方案就可以提高性能。


对象头中的biased_lock位表示该对象是否已经被JavaThread*指向的线程获得偏向锁。lock位表示对象是否已被锁定。


因为OpenJDK实现偏向锁时需要在标记字中写入指针,所以对象地址发生变化时还需要重新定位真正的mark word(其中包含了identity hash)。


这样就可以解释FastHashCode实现为什么变得如此复杂。对象头不仅包含了identity hash code,还包含锁定状态,比如指向加锁线程的指针。因此,我们需要考虑所有可能的情况才能找到identity hash真正的位置。


继续阅读FastHashCode代码。首先会看到:


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


等等。这里只是撤销了现有的偏向状态,并禁用对象的偏向锁(false表示“不再尝试为对象设置偏向”)。下面几行表明,对象确实是不变的:


637   // 对象应不再适用于设置偏向锁
638 assert (!mark->has_bias_pattern(), "invariant") ;


如果我没看错,这意味着获取对象identity hash code将禁用偏向锁,反过来会让锁定对象采用原子指令,进而增大开销。即使只有一个线程也是如此。


好家伙。


为什么保持偏向锁定状态与保存identity hash code会产生冲突?


要回答这个问题,就必须了解对象处于不同的锁定状态时,mark word(包含identity hash)可能会存在什么位置。下图来自HotSpot Wiki展示了这个过程:


深度解析默认 hashCode() 的工作机制


我的推理如下(可能不准确)。


图中顶部的4个状态,OpenJDK会用“轻量级”锁表示。在最简单的(无锁)情况下,identity hash和其他数据会直接存到对象的mark word中:


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


在更复杂情况下,这里存储的是指向“锁定记录”的指针。与此同时,mark word会被“置换”到其它地方。


因此,虽然只有一个线程锁定对象,但实际上这里还是会保存一个指针,指向线程堆栈的内存地址。这样做会带来两个好处:速度快(访问该内存地址没有争用也不需要协调),线程可以确认自己拥有该锁(地址中的指针指向线程自己的堆栈)。


但这种方案并非所有情况都能奏效。如果出现对象竞争(例如,多个线程调用synchronized语句中的对象),需要一个更复杂的结构,不仅能保存对象头信息副本(发生“置换”),还能保存一个waiter列表。当线程执行object.wait()时,也需要waiter列表。


这种内容更丰富的数据结构就是ObjectMonitor,在图中被称为“heavyweight”monitor。保留在对象头中的值不再指向“被置换的mark word”,而是指向实际的monitor对象。现在,访问identity hash code需要“inflate monitor”:找到对象指针,读取或修改包含mark word字段。这种操作开销很大并且需要协调。


FastHashCode会完成一些工作。


L640至L680行,查找对象头并检查identity hash缓存。我相信这是一种快速方法,不需要对monitor执行inflate。


从L682开始只能硬上了:


682   // 对monitor执行inflate,设置hash code
683 monitor = ObjectSynchronizer::inflate(Self, obj);

684 // 加载置换后的对象头,检查其是否具有hash code
685 mark = monitor->header();
...
687 hash = mark->hash();


如果存在id. hash(hash != 0),JVM将会返回。否则,将从get_next_hash中生成一个hash code。接着把存到ObjectMonitor置换过的对象头中。


这似乎提供了一种合理的解释,说明了为什么如果对象不重写默认hashCode()实现会让该对象不再适用偏向锁:


  • 为了让对象在重新定位后保持identity hash一致,需要把hash存入对象头。

  • 获取identity hash的线程可能并不关心对象是否加锁,但实际上这个操作会与锁机制使用相同的数据结构。这个过程异常复杂,不仅可能修改,还会移动(置换)对象头里的内容。

  • 如果只有一个线程锁定对象,通过把锁定状态存入mark word,偏向锁可以不借助原子操作高效执行锁定与解锁操作。这里我也不是100%确定,但我知道其他线程也会请求identity hash,即使只有一个线程为对象加锁,对象头中的mark word可能也会发生争用,需要原子操作解决。偏向锁的存在就变得毫无意义。


总结


  • 至少在OpenJDK中,hashCode()的默认实现(identity hash code)与对象的内存地址无关。在OpenJDK 6和7中,它是一个随机生成的数字。在OpenJDK 8(现在是9)中,它是一个基于线程状态的数字。下面的测试给出了同样的结论。

  • 下面的内容证明了“HashCode()依赖于JVM实现”:Azul Zing的确用对象内存地址生成的identity hash。

  • HotSpot的实现,仅生成一次identity hash并缓存在对象头的mark word中。

  • Zing采用了不同的解决方案保持一致,即延迟存储id. hash,直到重定位完成再进行保存。在此之前,会把它存储在“pre-header”中。

  • 在HotSpot中,调用默认hashCode()或者System.identityHashCode()会让对象不适合使用偏向锁。

  • 这意味着,如果要在不发生争用的对象上进行同步,则最好覆盖默认hashCode()实现,否则JVM不会优化。

  • 在HotSpot中,可以针对对象禁用偏向锁。

  • 非常有用。在实践中,我看到过很多竞争激烈的生产者消费者队列,偏向锁带来的麻烦比好处大得多。因此最后完全禁用了这个功能。事实证明,只要在指定对象或者类上调用System.identityHashCode()就可以解决。

  • 我没有找到更改默认生成器的HotSpot标志,因此要启用其他选项可能需要从源代码开始编译。

  • 我承认自己文档看得不够多。Michael Rasmussen提醒我 -XX:hashCode=2可以用来修改默认值。非常感谢!


基准测试


我写了一组简单的JMH测试来验证上述结论。


基准测试执行了类似下面的操作(源代码):


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


第一种配置(带有IdHash)在使用identity hash的对象上进行同步。因此期望的结果是,一旦调用hashCode()就会禁用偏向锁。第二种配置(不带IdHash)实现了自定义hash code,因此不会禁用偏向锁。每种配置会先运行一个线程,然后启动两个线程(后缀名为“Contended”)。


顺便说一句,出于测试的目的必须启用-XX:BiasedLockingStartupDelay=0 ,否则JVM会在4秒钟后启动优化让结果失真。


第一次执行:


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


可以看到,使用自定义hash code比用identity hash code(禁用偏向锁)执行加锁解锁速度快4倍。当两个线程发生锁竞争时,都会禁用偏向锁,因此这两个hash方法执行结果没有明显差异。


第二次运行,对所有配置都禁用偏向锁(-XX:-UseBiasedLocking)。


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


hash方法不再对结果产生影响,因此withoutIdHash优势不再。


(所有基准测试均在2.7 Ghz Intel Core i5上运行。


参考文档


文中所有的推理,来自我对JVM源代码、Java对象布局以及偏向锁的资料整理。主要参考文档如下:


深度解析默认 hashCode() 的工作机制


推荐阅读

(点击标题可跳转阅读)

浅谈 Java 中的 hashcode 方法

如何正确实现 Java 中的 HashCode

详解 equals() 方法和 hashCode() 方法


看完本文有收获?请转发分享给更多人

关注「ImportNew」,提升Java技能

好文章,我在看❤️

原文始发于微信公众号(ImportNew):深度解析默认 hashCode() 的工作机制