在Java JVM中重新排序的指令 [英] Instructions reordering in Java JVM

问题描述

我在阅读这篇文章： http://jeremymanson.blogspot.hk /2008/12/benign-data-races-in-java.html

作者所说的是打破 hashCode

通过具有：

在多线程环境中，

  public int hashCode（）{
 int h = hash; 
 if（h == 0）{
 int off = offset; 
 char val [] = value; 
 int len = count; 
 
 for（int i = 0; 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  h = 31 * h + val [off ++]; 
} 
 hash = h; 
} 
 return hash; 
} 
  

作者说，我引用：

我在这里做的是添加一个额外的读：第二次读取散列，在返回之前。奇怪， ，并且不太可能发生，第一次读取可以返回正确计算的散列值，第二次读取可以返回0！这是在存储器模型下允许的，因为该模型允许操作的大量重新排序，第二次读取可以实际上

因此，进一步阅读评论，有人说它可以重新排序为

  int h = hash; 
 if（hash == 0）{
 ... 
} 
 return h; 
  

怎么可能？我认为重新排序只涉及向上和向下移动程序语句。它遵循什么规则？我googled，阅读JSR133常见问题，检查Java并发实践书，但我似乎找不到一个地方，帮助我了解特别是关于重新排序。

编辑：感谢路易斯澄清重新排序的意思，我was not' t思考的byteCode

但是，我仍然不明白为什么允许将第二读取移动到前面，这是为了简单起见，用于计算哈希码的操作表示为 calchash（）。为了简化起见，我们将其简单地转换为一些字节码格式。



< （）。因此，我将程序表示为：

  if（hash == 0）{
 h = calchash 
 hash = h; 
} 
 return hash; 
  

我尝试用bytecode形式表示：

  R1，R2，R3在操作数堆栈中，或寄存器
h在局部变量数组
  

在程序顺序中：

  if == 0）{---------- R1 =从内存中读取哈希值（第1次读取）
 ----------比较（R1 == 0）
h = calchash（）; ---------- R2 = calchash（）
 ---------- h = R2（将R2存储到局部变量h）
 hash = h; ---------- Hash = h（写入散列）
} 
返回散列---------- R3 =从内存中读取散列（第2次读取） 
 ---------- return R3 
  

重新排序变换基于评论）：

  ---------- R3 =从内存读取哈希值（第2次读取） * 
 if（hash == 0）{---------- R1 =从内存中读取哈希值（第1次读取）
 ----------比较R1 == 0）
h = calchash（）; ---------- R2 = calchash（）
 ---------- h = R2（将R2存储到局部变量h）
 hash = h; ---------- hash = h（写入散列）
} 
返回散列----------返回R3 
  
 
 
 
 编辑：再次检查评论，我发现作者回答了这个问题 
 
 
 
重新排序的转换（从博客）
  r1 = 
 if（hash == 0）{
 r1 = hash = // calculate hash 
} 
 return r1; 
  
这种情况实际上适用于单线程，但可能会因多线程而失败。
 
 
 
看起来JVM正在根据
 
 
 
  h = hash进行简化，它简化了R1的使用， R2，R3到单个R1  
 
 
 
因此，JVM不仅仅是重新排序指令，而且似乎减少了使用的寄存器数量。 
 
 
 
任何想法？
解决方案
 p> 
 
 
  public int hashCode（）{
 if（hash == 0）{//（1）
 int off = offset; 
 char val [] = value; 
 int len = count; 
 
 int h = 0; 
 for（int i = 0; i  h = 31 * h + val [off ++]; 
} 
 hash = h; 
} 
 return hash; //（2）
} 
  
（1）和（2） （1）可以读取非空值，而（2）将读取0.这在String类的实际实现中不会发生，因为计算是对局部变量进行的，返回值也是局部变量， 
 
 
 
问题是Java内存模型不能保证当共享变量（ hash ）被访问而没有适当的同步 - 特别是它不保证所有的执行将是顺序一致的。  
 
 
 ps：该博客的作者，我相信，是JLS的第17章（Java内存模型）的作者之一 - 所以我倾向于相信他 -   - ）
 
 
 
 
 
 
  UPDATE  
 
 
 
按照各种编辑/注释 - 让我们看看字节码方法（我假设hashcode总是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 //读这个
 1：getfield＃6 //读散列（r1）
 4：ifne 12 //比较r1和0 
 7：aload_0 //读取这个
 8：iconst_1 //常量1 
 9：putfield＃6 //将1放入散列（w1）
 12：aload_0 //读取此
 13：getfield＃ 6 // read hash（r2）
 16：ireturn // return r2 
 
 public int hashcode_local（）; 
 0：aload_0 //读取
 1：getfield＃6 //读散列（r1）
 4：istore_1 //将r1存储在本地变量h 
 5：iload_1 / / read h 
 6：ifne 16 //比较h和0 
 9：aload_0 //读取
 10：iconst_1 //常量1 
 11：dup //常量
 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存储器模型适用，并且编译器/ JVM被允许重新排序这两个读取：行＃13可以在行＃1 *之前插入。
 
 
 
在第二个例子中，局部变量 h 上的所有操作都需要顺序一致，因为线程内的语义和非共享变量的程序顺序保证。
 
 
 
注意：和以往一样，允许重新排序的事实并不意味着它会被执行。它实际上不可能发生在当前的x86 /热点组合。但它可能在其他当前或未来的架构/ JVM上发生。
 
 
 
 
 
 
 *这是一个快捷方式，实际上是编译器可能会重写 hashcode_shared ：
  public int hashcode_shared（）{
 int h = hash; 
 if（hash！= 0）return h; 
 return（hash = 1）; 
} 
  
代码在单线程环境中是完全等效的与原始方法相同的值），因此允许重新排序。但在多线程环境中，很明显，如果 hash 由前两行之间的另一个线程从0更改为1，则此重新排序的方法将不正确地返回0。 
 
I was reading this blogpost: http://jeremymanson.blogspot.hk/2008/12/benign-data-races-in-java.html

And the author was talking about breaking the hashCode() in String in multithread environment.

By having:
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;
 }
Changed to:
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;
 }
Which the author says and I quote:

  
"What I've done here is to add an additional read: the second read of hash, before the return. As odd as it sounds, and as unlikely as it is to happen, the first read can return the correctly computed hash value, and the second read can return 0! This is allowed under the memory model because the model allows extensive reordering of operations. The second read can actually be moved, in your code, so that your processor does it before the first!"
So further going through comments, someone says it can be reordered to
int h = hash;
if (hash == 0) {
  ...
}
return h;
How is that possible? I thought reordering only involves moving program statements up and down. What rules is it following? I've googled, read the JSR133 FAQ, checked the Java Concurrency in Practice book, but I can't seem to find a place that helps me to understand particularly on reordering. If anyone can point me to the right direction, I would really appreciate it.

Edit: Thanks to Louis clarifying the meaning of "Reordering", I wasn't thinking in terms of "byteCode"

However, I still don't understand why is it allowed to move the 2nd Read to the front, this is my naive attempt to translate it to somewhat "bytecode" format.

For simplification purpose, operations that are used to calculate the hashcode are express as calchash(). Therefore, I express the program as:
if (hash == 0)  {       
    h = calchash();
    hash = h;
}
return hash;
And my attempt to express it in "bytecode" form:
R1,R2,R3 are in the operands stack, or the registers
h is in the array of local variables
In program order:
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
Reordered transformation(My version based on comments):
                        ---------- 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
Edit: Checking the comments again, I found this answered by the author

Reordered Transformation(From the blog)
r1 = hash;
if (hash == 0) {
  r1 = hash = // calculate hash
}
return r1;
This case actually works on single thread, but it's possible to fail with multiple threads.

It seems that the JVM are making simplifications based on

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

Therefore, JVM does more than reordering instructions, it also seems reducing the amount of registers being used. 

Any thoughts?
解决方案
In your modified code:
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) and (2) could be reordered: (1) could read a non null value while (2) would read 0. That can't happen in the actual implementation in the String class because the calculation is made on the local variable and the return value is also that local variable, which, by definition, is thread safe.

The issue is that the Java Memory Model provides no guarantee when a shared variable (hash) is accessed without proper synchronization - in particular it does not guarantee that all executions will be sequentially consistent. Had hash been volatile, there would be no problem with the modified code.

ps: the author of that blog, I believe, is one of the writers of the Chapter 17 (Java Memory Model) of the JLS - so I would tend to believe him anyway ;-)



UPDATE

Following the various edits / comments - let's look at the bytecode in more details with these two methods (I assume that the hashcode is always 1 to keep things simple):
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;
}
The java compiler on my machine generates the following bytecode:
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
In the first example, there are 2 reads of the shared variable hash: r1 and r2. As discussed above, because there is no synchronization and the variable is shared, the Java Memory Model applies and a compiler/JVM is allowed to reorder the two reads: line #13 could be inserted before line #1*.

In the second example, all the operations on h, the local variable, need to be sequentially consistent because because of intra-thread semantics and program order guarantee on non-shared variables.

Note: as always, the fact that the reordering is allowed does not mean it will be performed. It is actually unlikely to happen on current x86/hotspot combinations. But it could happen on other current or future architectures/JVM.



*That is a bit of a shortcut, what could happen in practice is that the compiler might rewrite hashcode_shared like this:
public int hashcode_shared() {
    int h = hash;
    if (hash != 0) return h;
    return (hash = 1);
}
The code is strictly equivalent in a single threaded environment (it will always return the same value as the original method) so the reordering is allowed. But in a multi-threaded environment, it is clear that if hash is changed from 0 to 1 by another thread between the first two lines, this reordered method will incorrectly return 0.

                        
这篇关于在Java JVM中重新排序的指令的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！