深度解析默认 hashCode() 的工作机制
发布于 14 天前 作者 yan 30 次浏览

(给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展示了这个过程:

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

图中顶部的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对象布局以及偏向锁的资料整理。主要参考文档如下:

推荐阅读

(点击标题可跳转阅读)

浅谈 Java 中的 hashcode 方法

如何正确实现 Java 中的 HashCode

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

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

关注「ImportNew」,提升Java技能

好文章,我在看❤️

回到顶部