Анализируя результаты недавнего вопроса здесь, я столкнулся с довольно своеобразным явлением: очевидно, дополнительный слой HotSpot JIT-оптимизации фактически замедляет выполнение на моей машине.
Вот код, который я использовал для измерения:
@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-ing all значения в аккумуляторе.
Ожидаемые и фактические результаты измерений
Теперь мы можем классифицировать четыре метода в соответствии с обсуждаемыми функциями:
-
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 Version 10.9.1
- 2.66 ГГц Intel Core i7
Я успешно воспроизвел результаты на Java 8 EA b118.
Мой вопрос:
Является ли это явление воспроизводимым на других аналогичных машинах? Из вопроса, упомянутого в начале, у меня уже есть намек на то, что по крайней мере некоторые машины не воспроизводят его, поэтому другой результат от того же CPU будет очень интересным.
Обновление 1: больше измерений, основанных на выводах maaartinus
Я собрал следующую таблицу, которая сопоставляет время выполнения с аргументом командной строки -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 1 и значительно ускоряется. Из-за предела разворачивания цикла все загруженные значения вписываются в регистры; -
на 18- > 19, вариант
withExitPoint
получает ускорение, меньшее, чем указано выше; -
на 22- > 23, вариант
withoutExitPoint
замедляется. На этом этапе я вижу, как разброс в местах стека, как описано в ответе maaartinus, начинает происходить.
По умолчанию loopUnrollLimit
для моей установки - 60, поэтому я представляю результаты в последнем столбце.
1 LCM = Движение локального кода. Это преобразование, которое приводит к тому, что весь доступ к массиву происходит сверху, а затем обработка загруженных значений.
Обновление 2: на самом деле это известная проблема с сообщением
https://bugs.openjdk.java.net/browse/JDK-7101232
Приложение: развернутый и переупорядоченный цикл normalIndex
в машинный код
0x00000001044a37c0: mov ecx,eax
0x00000001044a37c2: and ecx,esi ;*iand
; - org.sample.Measure::[email protected] (line 44)
0x00000001044a37c4: mov rbp,QWORD PTR [rsp+0x28] ;*iload_3
; - org.sample.Measure::[email protected] (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::[email protected] (line 46)
0x00000001044a395a: add esi,0x10 ;*iinc
; - org.sample.Measure::[email protected] (line 43)
0x00000001044a395d: cmp esi,DWORD PTR [rsp+0x20]
0x00000001044a3961: jl 0x00000001044a37c0 ;*if_icmpge
; - org.sample.Measure::[email protected] (line 43)