在Java JVM中重新排序的说明

Question

我正在阅读这篇博文.

作者正在谈论在多线程环境中打破hashCode()in String.

有了:

public int hashCode() {
     int h = hash;
     if (h == 0) {
         int off = offset;
         char val[] = value;
         int len = count;

         for (int i = 0; i < len; i++) {
             h = 31*h + val[off++];
         }
         hash = h;
     }
     return h;
 }

变成:

public int hashCode() {
     if (hash == 0) {
         int off = offset;
         char val[] = value;
         int len = count;

         int h = 0;
         for (int i = 0; i < len; i++) {
             h = 31*h + val[off++];
         }
         hash = h;
     }
     return hash;
 }

作者说,我引用:

"我在这里做的是添加一个额外的读取:在返回之前第二次读取哈希.听起来很奇怪,并且不太可能发生,第一次读取可以返回正确计算的哈希值,第二次读取可以返回0!这是在内存模型下允许的,因为该模型允许对操作进行大量重新排序.第二次读取实际上可以在代码中移动,以便处理器在第一次读取之前完成!"

所以进一步通过评论,有人说它可以重新排序

int h = hash;
if (hash == 0) {
  ...
}
return h;

怎么可能？我认为重新排序只涉及上下移动程序语句.遵循什么规则？我已经Google搜索了,阅读了JSR133常见问题解答,检查了Java Concurrency in Practice一书,但我似乎无法找到一个可以帮助我理解重新排序的地方.如果有人能指出我正确的方向,我会非常感激.

感谢路易斯澄清"重新排序"的含义,我没有想到"byteCode"

但是,我仍然不明白为什么允许将第二个读取移到前面,这是我天真的尝试将其转换为某种"字节码"格式.

出于简化目的,用于计算哈希码的操作表示为calchash().因此,我将该计划表达为:

if (hash == 0)  {       
    h = calchash();
    hash = h;
}
return hash;

我尝试用"字节码"形式表达它:

R1,R2,R3 are in the operands stack, or the registers
h is in the array of local variables

按程序顺序:

if (hash == 0)  {       ---------- R1 = read hash from memory (1st read)
                        ---------- Compare (R1 == 0)
    h = calchash();     ---------- R2 = calchash()
                        ---------- h = R2 (Storing the R2 to local variable h)
    hash = h;           ---------- Hash = h (write to hash)
}
return hash             ---------- R3 = read hash from memory again(2nd read)
                        ---------- return R3

重新排序转换(我的版本基于评论):

                        ---------- R3 = read hash from memory (2nd read) *moved*
if (hash == 0)  {       ---------- R1 = read hash from memory (1st read)
                        ---------- Compare (R1 == 0)
    h = calchash();     ---------- R2 = calchash()
                        ---------- h = R2 (Storing the R2 to local variable h)
    hash = h;           ---------- hash = h (write to hash)
}
return hash             ---------- return R3

再次检查评论,我发现作者回答:

重新排序转换(来自博客)

r1 = hash;
if (hash == 0) {
  r1 = hash = // calculate hash
}
return r1;

这种情况实际上适用于单线程,但是可能会因多个线程而失败.

似乎JVM正在进行简化

h = hash and it simplifies the use of R1, R2, R3 to single R1

因此,JVM不仅可以重新排序指令,还可以减少使用的寄存器数量.

Answer 1

在您修改的代码中:

public int hashCode() {
     if (hash == 0) { // (1)
         int off = offset;
         char val[] = value;
         int len = count;

         int h = 0;
         for (int i = 0; i < len; i++) {
             h = 31*h + val[off++];
         }
         hash = h;
     }
     return hash; // (2)
 }

(1)和(2)可以重新排序:(1)可以读取非空值而(2)读取0.这在String类的实际实现中不会发生,因为计算是在局部变量上进行的返回值也是局部变量,根据定义,它是线程安全的.

问题是Java内存模型无法保证在hash没有正确同步的情况下访问共享变量()时 - 特别是它不能保证所有执行都是顺序一致的.如果hash不稳定,修改后的代码就没有问题了.

ps:我相信,该博客的作者是JLS第17章(Java内存模型)的作者之一 - 所以无论如何我都倾向于相信他;-)

UPDATE

在各种编辑/评论之后 - 让我们用这两种方法更详细地看一下字节码(我假设哈希码总是1来保持简单):

public int hashcode_shared() {
    if (hash == 0) { hash = 1; }
    return hash;
}

public int hashcode_local() {
    int h = hash;
    if (h == 0) { hash = h = 1; }
    return h;
}

我机器上的java编译器生成以下字节码:

public int hashcode_shared();
   0: aload_0                           //read this
   1: getfield      #6                  //read hash (r1)
   4: ifne          12                  //compare r1 with 0
   7: aload_0                           //read this
   8: iconst_1                          //constant 1
   9: putfield      #6                  //put 1 into hash (w1)
  12: aload_0                           //read this
  13: getfield      #6                  //read hash (r2)
  16: ireturn                           //return r2

public int hashcode_local();
   0: aload_0                           //read this
   1: getfield      #6                  //read hash (r1)
   4: istore_1                          //store r1 in local variable h
   5: iload_1                           //read h
   6: ifne          16                  //compare h with 0
   9: aload_0                           //read this
  10: iconst_1                          //constant 1
  11: dup                               //constant again
  12: istore_1                          //store 1 into h
  13: putfield      #6                  //store 1 into hash (w1)
  16: iload_1                           //read h
  17: ireturn                           //return h

在第一个示例中,共享变量有2个读取hash:r1和r2.如上所述,因为没有同步并且变量是共享的,所以应用Java Memory Model并允许编译器/ JVM对两个读取重新排序:可以在第1行*之前插入第13行.

在第二个示例中,h局部变量上的所有操作都需要按顺序一致,因为非线程语义和非共享变量的程序顺序保证.

注意:一如既往,允许重新排序的事实并不意味着它将被执行.它实际上不太可能发生在当前的x86 /热点组合上.但它可能发生在其他当前或未来的架构/ JVM上.

*这是一个捷径,在实践中可能发生的事情是编译器可能会hashcode_shared像这样重写:

public int hashcode_shared() {
    int h = hash;
    if (hash != 0) return h;
    return (hash = 1);
}

代码在单线程环境中严格等效(它将始终返回与原始方法相同的值),因此允许重新排序.但是在多线程环境中,很明显,如果hash前两行之间的另一个线程从0更改为1,则此重新排序的方法将错误地返回0.