Переупорядочение инструкций в Java JVM

Ответ 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: автор этого блога, я считаю, является одним из авторов 17-й главы (модель памяти Java) JLS, поэтому я все равно склоняюсь к нему; -)

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, и компилятор /JVM разрешено изменять порядок чтения двух строк: строка # 13 может быть вставлена ​​перед строкой # 1 *.

Во втором примере все операции с h, локальная переменная, должны быть последовательно последовательными, потому что из-за семантики внутри потока и гарантии порядка программ для не общих переменных.

Примечание. Как всегда, тот факт, что переупорядочение разрешено, не означает, что он будет выполнен. На самом деле это вряд ли произойдет в текущих комбинациях x86/hotspot. Но это может произойти и в других текущих или будущих архитектурах /JVM.

* Это немного ярлык, что может произойти на практике, так это то, что компилятор может переписать hashcode_shared следующим образом:

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

Код строго эквивалентен в одной потоковой среде (он всегда будет возвращать то же значение, что и исходный метод), поэтому допускается переупорядочение. Но в многопоточной среде ясно, что если hash изменяется от 0 до 1 другим потоком между двумя первыми двумя строками, этот переупорядоченный метод будет неправильно возвращать 0.

Ответ 2

Я думаю, что главное, что в потоке, который получает неправильный ответ (возвращает 0), тело оператора if не выполняется - игнорировать его, может быть что угодно.

Неправильный поток чтения дважды читает поле энергонезависимости, но никогда не записывает его. Поэтому мы говорим только о порядке двух чтения. Утверждение состоит в том, что они не упорядочены. В более сложных ситуациях может быть сглаживание, и для компилятора было бы нетривиально проверять, было ли это то же место памяти или нет. Использование консервативного маршрута может предотвратить оптимизацию.

Ответ 3

В условиях неспециалиста я думаю, что эта проблема связана с переупорядочением чтения (выборки).

Каждый поток, T1 и T2, хочет получить все свои "входы" для обработки (и без строгой маркировки volatile) им предоставляется некоторая свобода относительно того, как/когда читать свои данные.

Плохой случай:

Каждый поток должен прочитать переменную (экземпляр) дважды, один раз, чтобы проверить if и один раз для возвращаемого значения. Предположим, что для аргумента T1 выбирает сначала читать if, а T2 выбирает сначала читать return.

Это создает условие гонки, в котором переменная hash изменяется (по T1) между обновлением hash на T1 и T2 во втором чтении (которое T2 использует для проверки if состояние). Итак, теперь тест T2 является ложным, он ничего не делает и возвращает то, что он читал (изначально) для переменной экземпляра, 0.

Фиксированный случай:

Каждому потоку нужно только прочитать переменную (экземпляр) один раз, а затем сразу же сохранить ее в своей локальной переменной. Это предотвращает возникновение проблемы переупорядочения чтения (так как есть только одно чтение).

Ответ 4

Сначала плохой код:

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

Ясно, что мы можем уменьшить это до своих голых костей, как:

int hash = 0;

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

теперь теория предполагает, что переупорядочение на одном потоке, чередующемся определенным образом со вторым потоком, может привести к возврату нуля. Единственный сценарий, который я могу себе представить, будет примерно таким:

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

но затем - для меня - аналогичное лечение можно сделать с хорошим кодом:

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

а затем

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

Я не понимаю, почему это реальная возможность, а другая - нет.