Странная JIT пессимизация идиомы цикла

Question

Странная JIT пессимизация идиомы цикла

Анализируя результаты недавнего вопроса здесь, я столкнулся с довольно странным явлением: очевидно, что дополнительный уровень JIT-оптимизации HotSpot фактически замедляет выполнение на моей машине.

Вот код, который я использовал для измерения:

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(Measure.ARRAY_SIZE)
@Warmup(iterations = 2, time = 1)
@Measurement(iterations = 5, time = 1)
@State(Scope.Thread)
@Threads(1)
@Fork(2)
public class Measure
{
  public static final int ARRAY_SIZE = 1024;
  private final int[] array = new int[ARRAY_SIZE];

  @Setup public void setup() {
    final Random random = new Random();
    for (int i = 0; i < ARRAY_SIZE; ++i) {
      final int x = random.nextInt();
      array[i] = x == 0? 1 : x;
    }
  }

  @GenerateMicroBenchmark public int normalIndex() {
    final int[] array = this.array;
    int result = 0;
    for (int i = 0; i < array.length; i++) {
      final int j = i & array.length-1;
      final int entry = array[i];
      result ^= entry + j;
    }
    return result;
  }

  @GenerateMicroBenchmark public int maskedIndex() {
    final int[] array = this.array;
    int result = 0;
    for (int i = 0; i < array.length; i++) {
      final int j = i & array.length-1;
      final int entry = array[j];
      result ^= entry + i;
    }
    return result;
  }

  @GenerateMicroBenchmark public int normalWithExitPoint() {
    final int[] array = this.array;
    int result = 0;
    for (int i = 0; i < array.length; i++) {
      final int j = i & array.length-1;
      final int entry = array[i];
      result ^= entry + j;
      if (entry == 0) break;
    }
    return result;
  }

  @GenerateMicroBenchmark public int maskedWithExitPoint() {
    final int[] array = this.array;
    int result = 0;
    for (int i = 0; i < array.length; i++) {
      final int j = i & array.length-1;
      final int entry = array[j];
      result ^= entry + i;
      if (entry == 0) break;
    }
    return result;
  }


}

Код довольно тонкий, поэтому позвольте мне указать на важные моменты:

варианты "нормального индекса" используют прямую переменную i для индекса массива. HotSpot может легко определить диапазон i по всему циклу и исключить проверку границ массива;
индекс вариантов "замаскированного индекса" j, который на самом деле равен i, но этот факт "скрыт" от HotSpot посредством операции маскировки AND;
варианты "с точкой выхода" вводят точку выхода цикла экспликации. Важность этого будет объяснена ниже.

Развертывание и переупорядочивание петли

Обратите внимание, что границы проверяют фигуры двумя важными способами:

с ним связаны накладные расходы времени выполнения (сравнение, за которым следует условная ветвь);
он представляет собой точку выхода из цикла, которая может прервать цикл на любом шаге. Оказывается, это имеет важные последствия для применяемой оптимизации JIT.

Изучив машинный код, выданный для вышеуказанных четырех методов, я заметил следующее:

во всех случаях цикл развернут;
в случае normalIndex, который выделяется как единственный, не имеющий точек выхода преждевременного цикла, операции всех развернутых шагов переупорядочиваются так, что сначала выполняются все выборки из массива, а затем выполняется XOR-ввод всех значений в накопитель.

Ожидаемые и фактические результаты измерений

Теперь мы можем классифицировать четыре метода в соответствии с обсуждаемыми функциями:

normalIndex не имеет проверок границ и точек выхода из цикла;
normalWithExitPoint не имеет проверок границ и 1 точки выхода;
maskedIndex имеет 1 проверку границ и 1 точку выхода;
maskedWithExitPoint имеет 1 проверку границ и 2 точки выхода.

Очевидное ожидание состоит в том, что приведенный выше список должен представлять методы в порядке убывания производительности; Тем не менее, это мои реальные результаты:

Benchmark               Mode   Samples         Mean   Mean error    Units
normalIndex             avgt        20        0.946        0.010    ns/op
normalWithExitPoint     avgt        20        0.807        0.010    ns/op
maskedIndex             avgt        20        0.803        0.007    ns/op
maskedWithExitPoint     avgt        20        1.007        0.009    ns/op

normalWithExitPoint а также maskedIndex идентичны по модулю погрешности измерения, хотя только последний имеет проверку границ;
наибольшая аномалия наблюдается на normalIndex который должен был быть самым быстрым, но значительно медленнее, чем normalWithExitPoint идентичный ему во всех отношениях, за исключением наличия еще одной строки кода, той, которая вводит точку выхода.

поскольку normalIndex это единственный метод, к которому применяется дополнительная "оптимизация" переупорядочения, вывод заключается в том, что это является причиной замедления.

Я тестирую на:

Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode) (Java 7, обновление 40)
Версия OS X 10.9.1
Intel Core i7 с частотой 2,66 ГГц

Я также успешно воспроизвел результаты на Java 8 EA b118.

Мой вопрос:

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

Обновление 1: больше измерений, вдохновленных открытиями Маартинуса

Я собрал следующую таблицу, которая коррелирует время выполнения с -XX:LoopUnrollLimit аргумент командной строки. Здесь я остановлюсь только на двух вариантах, с и без if (entry == 0) break; линия:

LoopUnrollLimit:   14 15 18 19 22 23 60
withExitPoint:     96 95 95 79 80 80 69   1/100 ns
withoutExitPoint:  94 64 64 63 64 77 75   1/100 ns

Могут наблюдаться следующие внезапные изменения:

на переходе с 14 на 15 г. withoutExitPoint вариант получает выгодное преобразование LCM ¹ и значительно ускоряется. Из-за предела развертывания цикла все загруженные значения помещаются в регистры;
18->19 withExitPoint вариант получает ускорение, меньшее, чем указано выше;
22->23 года withoutExitPoint Вариант замедлен. В этот момент я вижу, что переливание в ячейки стека, как описано в ответе maaartinus, начинает происходить.

По умолчанию loopUnrollLimit для моей установки 60, поэтому я представляю его результаты в последнем столбце.

¹ LCM = местное кодовое движение. Это преобразование, которое приводит к тому, что доступ ко всему массиву происходит сверху, а затем обрабатывается загруженные значения.

Обновление 2: это на самом деле известная, заявленная проблема

https://bugs.openjdk.java.net/browse/JDK-7101232

Приложение: развернутый и переупорядоченный цикл `normalIndex` в машинном коде

0x00000001044a37c0: mov    ecx,eax
0x00000001044a37c2: and    ecx,esi            ;*iand
                                              ; - org.sample.Measure::normalIndex@20 (line 44)
0x00000001044a37c4: mov    rbp,QWORD PTR [rsp+0x28]  ;*iload_3
                                              ; - org.sample.Measure::normalIndex@15 (line 44)
0x00000001044a37c9: add    ecx,DWORD PTR [rbp+rsi*4+0x10]
0x00000001044a37cd: xor    ecx,r8d
0x00000001044a37d0: mov    DWORD PTR [rsp],ecx
0x00000001044a37d3: mov    r10d,esi
0x00000001044a37d6: add    r10d,0xf
0x00000001044a37da: and    r10d,eax
0x00000001044a37dd: mov    r8d,esi
0x00000001044a37e0: add    r8d,0x7
0x00000001044a37e4: and    r8d,eax
0x00000001044a37e7: mov    DWORD PTR [rsp+0x4],r8d
0x00000001044a37ec: mov    r11d,esi
0x00000001044a37ef: add    r11d,0x6
0x00000001044a37f3: and    r11d,eax
0x00000001044a37f6: mov    DWORD PTR [rsp+0x8],r11d
0x00000001044a37fb: mov    r8d,esi
0x00000001044a37fe: add    r8d,0x5
0x00000001044a3802: and    r8d,eax
0x00000001044a3805: mov    DWORD PTR [rsp+0xc],r8d
0x00000001044a380a: mov    r11d,esi
0x00000001044a380d: inc    r11d
0x00000001044a3810: and    r11d,eax
0x00000001044a3813: mov    DWORD PTR [rsp+0x10],r11d
0x00000001044a3818: mov    r8d,esi
0x00000001044a381b: add    r8d,0x2
0x00000001044a381f: and    r8d,eax
0x00000001044a3822: mov    DWORD PTR [rsp+0x14],r8d
0x00000001044a3827: mov    r11d,esi
0x00000001044a382a: add    r11d,0x3
0x00000001044a382e: and    r11d,eax
0x00000001044a3831: mov    r9d,esi
0x00000001044a3834: add    r9d,0x4
0x00000001044a3838: and    r9d,eax
0x00000001044a383b: mov    r8d,esi
0x00000001044a383e: add    r8d,0x8
0x00000001044a3842: and    r8d,eax
0x00000001044a3845: mov    DWORD PTR [rsp+0x18],r8d
0x00000001044a384a: mov    r8d,esi
0x00000001044a384d: add    r8d,0x9
0x00000001044a3851: and    r8d,eax
0x00000001044a3854: mov    ebx,esi
0x00000001044a3856: add    ebx,0xa
0x00000001044a3859: and    ebx,eax
0x00000001044a385b: mov    ecx,esi
0x00000001044a385d: add    ecx,0xb
0x00000001044a3860: and    ecx,eax
0x00000001044a3862: mov    edx,esi
0x00000001044a3864: add    edx,0xc
0x00000001044a3867: and    edx,eax
0x00000001044a3869: mov    edi,esi
0x00000001044a386b: add    edi,0xd
0x00000001044a386e: and    edi,eax
0x00000001044a3870: mov    r13d,esi
0x00000001044a3873: add    r13d,0xe
0x00000001044a3877: and    r13d,eax
0x00000001044a387a: movsxd r14,esi
0x00000001044a387d: add    r10d,DWORD PTR [rbp+r14*4+0x4c]
0x00000001044a3882: mov    DWORD PTR [rsp+0x24],r10d
0x00000001044a3887: mov    QWORD PTR [rsp+0x28],rbp
0x00000001044a388c: mov    ebp,DWORD PTR [rsp+0x4]
0x00000001044a3890: mov    r10,QWORD PTR [rsp+0x28]
0x00000001044a3895: add    ebp,DWORD PTR [r10+r14*4+0x2c]
0x00000001044a389a: mov    DWORD PTR [rsp+0x4],ebp
0x00000001044a389e: mov    r10d,DWORD PTR [rsp+0x8]
0x00000001044a38a3: mov    rbp,QWORD PTR [rsp+0x28]
0x00000001044a38a8: add    r10d,DWORD PTR [rbp+r14*4+0x28]
0x00000001044a38ad: mov    DWORD PTR [rsp+0x8],r10d
0x00000001044a38b2: mov    r10d,DWORD PTR [rsp+0xc]
0x00000001044a38b7: add    r10d,DWORD PTR [rbp+r14*4+0x24]
0x00000001044a38bc: mov    DWORD PTR [rsp+0xc],r10d
0x00000001044a38c1: mov    r10d,DWORD PTR [rsp+0x10]
0x00000001044a38c6: add    r10d,DWORD PTR [rbp+r14*4+0x14]
0x00000001044a38cb: mov    DWORD PTR [rsp+0x10],r10d
0x00000001044a38d0: mov    r10d,DWORD PTR [rsp+0x14]
0x00000001044a38d5: add    r10d,DWORD PTR [rbp+r14*4+0x18]
0x00000001044a38da: mov    DWORD PTR [rsp+0x14],r10d
0x00000001044a38df: add    r13d,DWORD PTR [rbp+r14*4+0x48]
0x00000001044a38e4: add    r11d,DWORD PTR [rbp+r14*4+0x1c]
0x00000001044a38e9: add    r9d,DWORD PTR [rbp+r14*4+0x20]
0x00000001044a38ee: mov    r10d,DWORD PTR [rsp+0x18]
0x00000001044a38f3: add    r10d,DWORD PTR [rbp+r14*4+0x30]
0x00000001044a38f8: mov    DWORD PTR [rsp+0x18],r10d
0x00000001044a38fd: add    r8d,DWORD PTR [rbp+r14*4+0x34]
0x00000001044a3902: add    ebx,DWORD PTR [rbp+r14*4+0x38]
0x00000001044a3907: add    ecx,DWORD PTR [rbp+r14*4+0x3c]
0x00000001044a390c: add    edx,DWORD PTR [rbp+r14*4+0x40]
0x00000001044a3911: add    edi,DWORD PTR [rbp+r14*4+0x44]
0x00000001044a3916: mov    r10d,DWORD PTR [rsp+0x10]
0x00000001044a391b: xor    r10d,DWORD PTR [rsp]
0x00000001044a391f: mov    ebp,DWORD PTR [rsp+0x14]
0x00000001044a3923: xor    ebp,r10d
0x00000001044a3926: xor    r11d,ebp
0x00000001044a3929: xor    r9d,r11d
0x00000001044a392c: xor    r9d,DWORD PTR [rsp+0xc]
0x00000001044a3931: xor    r9d,DWORD PTR [rsp+0x8]
0x00000001044a3936: xor    r9d,DWORD PTR [rsp+0x4]
0x00000001044a393b: mov    r10d,DWORD PTR [rsp+0x18]
0x00000001044a3940: xor    r10d,r9d
0x00000001044a3943: xor    r8d,r10d
0x00000001044a3946: xor    ebx,r8d
0x00000001044a3949: xor    ecx,ebx
0x00000001044a394b: xor    edx,ecx
0x00000001044a394d: xor    edi,edx
0x00000001044a394f: xor    r13d,edi
0x00000001044a3952: mov    r8d,DWORD PTR [rsp+0x24]
0x00000001044a3957: xor    r8d,r13d           ;*ixor
                                              ; - org.sample.Measure::normalIndex@34 (line 46)
0x00000001044a395a: add    esi,0x10           ;*iinc
                                              ; - org.sample.Measure::normalIndex@36 (line 43)
0x00000001044a395d: cmp    esi,DWORD PTR [rsp+0x20]
0x00000001044a3961: jl     0x00000001044a37c0  ;*if_icmpge
                                              ; - org.sample.Measure::normalIndex@12 (line 43)

18

java cpu intel microbenchmark jmh

Источник

user1103872 12 фев '14 в 20:17

1 ответ

Решение

Другие вопросы по тегам java cpu intel microbenchmark jmh

user581205 15 фев '14 в 09:26 2014-02-15 09:26 · Accepted Answer · 2014-02-15 09:26

Причина, по которой JITC пытается объединить все воедино, мне неясна. AFAIK Существуют (были?) Архитектуры, для которых группировка двух нагрузок приводит к лучшей производительности (я думаю, что это был ранний Pentium).

Поскольку JITC знает "горячие точки", он может работать гораздо агрессивнее, чем опережающий компилятор, поэтому в этом случае он делает это 16 раз. Я не вижу здесь никакого явного преимущества, за исключением того, что зацикливание обходится относительно дешевле. Я также сомневаюсь, что есть какая-то архитектура, которая извлекает выгоду из группировки 16 нагрузок вместе.

Код вычисляет 16 временных значений, по одному на итерацию

int j = i & array.length-1;
int entry = array[i];
int tmp = entry + j;
result ^= tmp;

Каждое вычисление довольно тривиально: один AND, одна LOAD и один ADD. Значения должны быть сопоставлены с регистрами, но их недостаточно. Таким образом, значения должны быть сохранены и загружены позже.

Это происходит для 7 из 16 регистров и значительно увеличивает затраты.

Обновить

Я не очень уверен в проверке этого с помощью -XX:LoopUnrollLimit:

LoopUnrollLimit Benchmark   Mean   Mean error    Units

 8 ..normalIndex           0.902        0.004    ns/op
 8 ..normalWithExitPoint   0.913        0.005    ns/op
 8 ..maskedIndex           0.918        0.006    ns/op
 8 ..maskedWithExitPoint   0.996        0.008    ns/op

16 ..normalIndex           0.769        0.003    ns/op
16 ..normalWithExitPoint   0.930        0.004    ns/op
16 ..maskedIndex           0.937        0.004    ns/op
16 ..maskedWithExitPoint   1.012        0.003    ns/op

32 ..normalIndex           0.814        0.003    ns/op
32 ..normalWithExitPoint   0.816        0.005    ns/op
32 ..maskedIndex           0.838        0.003    ns/op
32 ..maskedWithExitPoint   0.978        0.002    ns/op

 - ..normalIndex           0.830        0.002    ns/op
 - ..normalWithExitPoint   0.683        0.002    ns/op
 - ..maskedIndex           0.791        0.005    ns/op
 - ..maskedWithExitPoint   0.908        0.003    ns/op

Лимит 16 составляет normalIndex быть самым быстрым вариантом, который указывает, что я был прав с "штрафом за перераспределение". Но, по словам Марко, сгенерированная сборка изменяется с пределом развертывания и в других аспектах, поэтому все становится сложнее.

Странная JIT пессимизация идиомы цикла

Развертывание и переупорядочивание петли

Ожидаемые и фактические результаты измерений

Мой вопрос:

Обновление 1: больше измерений, вдохновленных открытиями Маартинуса

Обновление 2: это на самом деле известная, заявленная проблема

Приложение: развернутый и переупорядоченный цикл normalIndex в машинном коде

1 ответ

Обновить

Приложение: развернутый и переупорядоченный цикл `normalIndex` в машинном коде