Java JVM中的指令重排序

Question

我在看这博客。

作者还讨论了在多线程环境下打破hashCode()在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;

那件事怎么可能？我以为重新排序只需要上下移动程序语句。它遵循什么规则？我在谷歌上搜索过，阅读过JSR133常见问题，在实践中查看过Java并发，但我似乎找不到一个地方来帮助我理解，特别是在重新排序时。如果有人能给我指明正确的方向，我会非常感激的。

感谢路易澄清了“重新排序”的含义，我没有用"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内存模型)的作者之一，所以我倾向于相信他;-)

更新

在各种编辑/注释之后--让我们看一下字节码，更详细地介绍这两种方法(我假设哈希代码总是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

在第一个示例中，有两个共享变量hash的读取: r1和r2。如上所述，由于没有同步，并且变量是共享的，因此Java内存模型将应用，并允许编译器/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。

Answer 2

我认为需要注意的关键是，在得到错误答案的线程中(返回0)，if语句的主体不会被执行-忽略它，可能是任何东西。

错误的读取线程两次读取非易失性字段，但从未写入该字段。所以我们讨论的只是两个读的顺序。索赔是，这些不是订购的。在更复杂的情况下，可能会出现混叠，编译器检查这是否是相同的内存位置将是非常重要的。采取保守的路线可以防止优化。

Answer 3

用外行的话说，我认为这个问题与读(取)序有关。

每个线程，T1和T2，都希望获得它们所有的“输入”来进行处理(而且没有严格的volatile标记)，它们在如何/何时读取数据方面获得了一些自由。

的坏案例：

每个线程需要读取(实例)变量两次，一次检查if，一次读取返回值。假设T1选择先读取if，T2选择先读取return。

这就创建了hash变量在、hash的更新( T1)和T2的第二读(T2用于检查if条件)之间更改(通过)的争用条件。所以现在T2的测试是假的，它什么也不做，并返回它为实例变量0读取的内容(最初)。

固定案例：

每个线程只需要读取(实例)变量一次，然后立即将其存储在它自己的局部变量中。这样就不会出现重新排序的读取问题(因为只有一个读取)。