Instructions reordering in Java JVM

Question

I was reading this blogpost.

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.

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

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.

Answer 1

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.

Answer 2

I think the key thing to note is that in the thread that gets the wrong answer (returns 0), the body of the if statement is not executed - ignore it, could be anything.

The wrong read thread reads the non-volatile field twice but never writes it. So we are talking about just the ordering of two reads. The claim is that these are not ordered. In more complicated situations there might be aliasing, and it would be non-trivial for the compiler to check whether this was the same memory location or not. Taking the conservative route could prevent optimisations.

Answer 3

In layman's terms, I think this issue has to do with read (fetch) re-ordering.

Each thread, T1 and T2, want to get all their "inputs" to do processing (and without the strict volatile marking) they are given some freedom as to how/when to read their data.

The Bad Case:

Each thread needs to read the (instance) variable twice, once to check the if and once for the return value. Let's say for argument that T1 chooses to do the if read first and T2 chooses to do the return read first.

This creates the race condition that the hash variable is changed (by T1) between the update of hash by T1 and T2's second read (which T2 uses to check the if condition). So now T2's test is false, it does nothing and returns what it read (originally) for the instance variable, 0.

The Fixed Case:

Each thread only needs to read the (instance) variable once, and then immediately stores it in it's own local variable. This keeps the re-ordering read problem from occurring (as there is only one read).

Answer 4

First the bad code:

int hash = 0;

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;
 }

Clearly we can reduce this to its bare bones as:

int hash = 0;

public int hashCode() {
     if (hash == 0) {
         // Assume calculateHash does not return 0 and does not modify hash.
         hash = calculateHash();
     }
     return hash;
 }

now the theory suggests that a reordering on one thread interlaced in a particular way with a second thread can result in a zero return. The only scenario I can imagine would be something like:

// Pseudocode for thread 1 starts with <1>, thread 2 with <2>. 
// Rn are local registers.
public int hashCode() {
     <2> has not begun
     <1> load r1 with hash (==0) in preparation for return for when hash is != 0
     <2> begins execution - finds hash == 0 and starts the calculation
     <2> modifies hash to contain new value.
     <1> Check hash for zero - it is not so skip the contents of the if
     if (hash == 0) {
         // Assume calculateHash does not return 0 and does not modify hash.
         hash = calculateHash();
         <2> got here but at a time when <1> was up there ^^
     }
     <1> return r1 - supposedly containing a zero.
     return hash;
 }

but then - to me - a similar treatment can be made with the good code:

public int hashCode() {
     int h = hash;
     if (h == 0) {
         hash = h = calculateHash();
     }
     return h;
 }

and then

public int hashCode() {
     <2> has not begun
     <1> load r1 with hash (==0) in preparation for return for when h is != 0
     <2> begins execution - finds h == 0 and starts the calculation
     <2> modifies hash to contain new value.
     <1> load r2 with hash - from now on r2 is h
     int h = hash;
     <1> Check r2 for zero - it is not so skip the contents of the if
     if (h == 0) {
         hash = h = calculateHash();
     }
     <1> we know that when hash/h are non-zero it doesn't matter where we get our return from - both r1 and r2 must have the same value.
     <1> return r1 - supposedly containing a zero.
     return h;
 }

I don't understand why one is a real possibility and the other is not.