Почему 2 * (i * i) быстрее, чем 2 * i * i в Java?

855

Следующая Java-программа выполняется в среднем от 0,50 до 0,55 с:

public static void main(String[] args) {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += 2 * (i * i);
    }
    System.out.println((double) (System.nanoTime() - startTime) / 1000000000 + " s");
    System.out.println("n = " + n);
}

Если я заменяю 2 * (i * i)на 2 * i * i, это занимает от 0,60 до 0,65 секунды для запуска. Как так?

Я запускал каждую версию программы 15 раз, чередуя их. Вот результаты:

 2*(i*i)  |  2*i*i
----------+----------
0.5183738 | 0.6246434
0.5298337 | 0.6049722
0.5308647 | 0.6603363
0.5133458 | 0.6243328
0.5003011 | 0.6541802
0.5366181 | 0.6312638
0.515149  | 0.6241105
0.5237389 | 0.627815
0.5249942 | 0.6114252
0.5641624 | 0.6781033
0.538412  | 0.6393969
0.5466744 | 0.6608845
0.531159  | 0.6201077
0.5048032 | 0.6511559
0.5232789 | 0.6544526

Самый быстрый пробег 2 * i * iзанял больше времени, чем самый медленный 2 * (i * i). Если бы они имели одинаковую эффективность, вероятность этого бы была меньше 1/2^15 * 100% = 0.00305%.

Стефан
источник
5
Я получаю аналогичные результаты (немного другие цифры, но определенно заметный и последовательный разрыв, определенно больше, чем ошибка выборки)
Krease
29
Также, пожалуйста, смотрите: stackoverflow.com/questions/504103/…
lexicore
3
@Krease Хорошо, что ты поймал мою ошибку. В соответствии с новым тестом я бежал 2 * i * iмедленнее. Я тоже попробую бегать с Граалем.
Йорн Верни
5
@nullpointer Чтобы по-настоящему выяснить, почему один из них быстрее другого, нам нужно получить графики разборки или идеальные для этих методов. Ассемблер очень раздражает, пытаясь разобраться, поэтому я пытаюсь получить отладочную сборку OpenJDK, которая может выводить хорошие графики.
Джорн Верни
4
Вы можете переименовать свой вопрос в « Почему i * i * 2быстрее, чем 2 * i * i? », Чтобы лучше понять, что проблема в порядке операций.
Cœur

Ответы:

1202

Существует небольшая разница в порядке следования байт-кода.

2 * (i * i):

     iconst_2
     iload0
     iload0
     imul
     imul
     iadd

против 2 * i * i:

     iconst_2
     iload0
     imul
     iload0
     imul
     iadd

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

Поэтому нам нужно копать глубже в нижний уровень (JIT) 1 .

Помните, что JIT очень агрессивно разворачивает маленькие петли. Действительно, мы наблюдаем 16-кратное развертывание для 2 * (i * i)случая:

030   B2: # B2 B3 <- B1 B2  Loop: B2-B2 inner main of N18 Freq: 1e+006
030     addl    R11, RBP    # int
033     movl    RBP, R13    # spill
036     addl    RBP, #14    # int
039     imull   RBP, RBP    # int
03c     movl    R9, R13 # spill
03f     addl    R9, #13 # int
043     imull   R9, R9  # int
047     sall    RBP, #1
049     sall    R9, #1
04c     movl    R8, R13 # spill
04f     addl    R8, #15 # int
053     movl    R10, R8 # spill
056     movdl   XMM1, R8    # spill
05b     imull   R10, R8 # int
05f     movl    R8, R13 # spill
062     addl    R8, #12 # int
066     imull   R8, R8  # int
06a     sall    R10, #1
06d     movl    [rsp + #32], R10    # spill
072     sall    R8, #1
075     movl    RBX, R13    # spill
078     addl    RBX, #11    # int
07b     imull   RBX, RBX    # int
07e     movl    RCX, R13    # spill
081     addl    RCX, #10    # int
084     imull   RCX, RCX    # int
087     sall    RBX, #1
089     sall    RCX, #1
08b     movl    RDX, R13    # spill
08e     addl    RDX, #8 # int
091     imull   RDX, RDX    # int
094     movl    RDI, R13    # spill
097     addl    RDI, #7 # int
09a     imull   RDI, RDI    # int
09d     sall    RDX, #1
09f     sall    RDI, #1
0a1     movl    RAX, R13    # spill
0a4     addl    RAX, #6 # int
0a7     imull   RAX, RAX    # int
0aa     movl    RSI, R13    # spill
0ad     addl    RSI, #4 # int
0b0     imull   RSI, RSI    # int
0b3     sall    RAX, #1
0b5     sall    RSI, #1
0b7     movl    R10, R13    # spill
0ba     addl    R10, #2 # int
0be     imull   R10, R10    # int
0c2     movl    R14, R13    # spill
0c5     incl    R14 # int
0c8     imull   R14, R14    # int
0cc     sall    R10, #1
0cf     sall    R14, #1
0d2     addl    R14, R11    # int
0d5     addl    R14, R10    # int
0d8     movl    R10, R13    # spill
0db     addl    R10, #3 # int
0df     imull   R10, R10    # int
0e3     movl    R11, R13    # spill
0e6     addl    R11, #5 # int
0ea     imull   R11, R11    # int
0ee     sall    R10, #1
0f1     addl    R10, R14    # int
0f4     addl    R10, RSI    # int
0f7     sall    R11, #1
0fa     addl    R11, R10    # int
0fd     addl    R11, RAX    # int
100     addl    R11, RDI    # int
103     addl    R11, RDX    # int
106     movl    R10, R13    # spill
109     addl    R10, #9 # int
10d     imull   R10, R10    # int
111     sall    R10, #1
114     addl    R10, R11    # int
117     addl    R10, RCX    # int
11a     addl    R10, RBX    # int
11d     addl    R10, R8 # int
120     addl    R9, R10 # int
123     addl    RBP, R9 # int
126     addl    RBP, [RSP + #32 (32-bit)]   # int
12a     addl    R13, #16    # int
12e     movl    R11, R13    # spill
131     imull   R11, R13    # int
135     sall    R11, #1
138     cmpl    R13, #999999985
13f     jl     B2   # loop end  P=1.000000 C=6554623.000000

Мы видим, что есть 1 регистр, который «проливается» на стек.

И для 2 * i * iверсии:

05a   B3: # B2 B4 <- B1 B2  Loop: B3-B2 inner main of N18 Freq: 1e+006
05a     addl    RBX, R11    # int
05d     movl    [rsp + #32], RBX    # spill
061     movl    R11, R8 # spill
064     addl    R11, #15    # int
068     movl    [rsp + #36], R11    # spill
06d     movl    R11, R8 # spill
070     addl    R11, #14    # int
074     movl    R10, R9 # spill
077     addl    R10, #16    # int
07b     movdl   XMM2, R10   # spill
080     movl    RCX, R9 # spill
083     addl    RCX, #14    # int
086     movdl   XMM1, RCX   # spill
08a     movl    R10, R9 # spill
08d     addl    R10, #12    # int
091     movdl   XMM4, R10   # spill
096     movl    RCX, R9 # spill
099     addl    RCX, #10    # int
09c     movdl   XMM6, RCX   # spill
0a0     movl    RBX, R9 # spill
0a3     addl    RBX, #8 # int
0a6     movl    RCX, R9 # spill
0a9     addl    RCX, #6 # int
0ac     movl    RDX, R9 # spill
0af     addl    RDX, #4 # int
0b2     addl    R9, #2  # int
0b6     movl    R10, R14    # spill
0b9     addl    R10, #22    # int
0bd     movdl   XMM3, R10   # spill
0c2     movl    RDI, R14    # spill
0c5     addl    RDI, #20    # int
0c8     movl    RAX, R14    # spill
0cb     addl    RAX, #32    # int
0ce     movl    RSI, R14    # spill
0d1     addl    RSI, #18    # int
0d4     movl    R13, R14    # spill
0d7     addl    R13, #24    # int
0db     movl    R10, R14    # spill
0de     addl    R10, #26    # int
0e2     movl    [rsp + #40], R10    # spill
0e7     movl    RBP, R14    # spill
0ea     addl    RBP, #28    # int
0ed     imull   RBP, R11    # int
0f1     addl    R14, #30    # int
0f5     imull   R14, [RSP + #36 (32-bit)]   # int
0fb     movl    R10, R8 # spill
0fe     addl    R10, #11    # int
102     movdl   R11, XMM3   # spill
107     imull   R11, R10    # int
10b     movl    [rsp + #44], R11    # spill
110     movl    R10, R8 # spill
113     addl    R10, #10    # int
117     imull   RDI, R10    # int
11b     movl    R11, R8 # spill
11e     addl    R11, #8 # int
122     movdl   R10, XMM2   # spill
127     imull   R10, R11    # int
12b     movl    [rsp + #48], R10    # spill
130     movl    R10, R8 # spill
133     addl    R10, #7 # int
137     movdl   R11, XMM1   # spill
13c     imull   R11, R10    # int
140     movl    [rsp + #52], R11    # spill
145     movl    R11, R8 # spill
148     addl    R11, #6 # int
14c     movdl   R10, XMM4   # spill
151     imull   R10, R11    # int
155     movl    [rsp + #56], R10    # spill
15a     movl    R10, R8 # spill
15d     addl    R10, #5 # int
161     movdl   R11, XMM6   # spill
166     imull   R11, R10    # int
16a     movl    [rsp + #60], R11    # spill
16f     movl    R11, R8 # spill
172     addl    R11, #4 # int
176     imull   RBX, R11    # int
17a     movl    R11, R8 # spill
17d     addl    R11, #3 # int
181     imull   RCX, R11    # int
185     movl    R10, R8 # spill
188     addl    R10, #2 # int
18c     imull   RDX, R10    # int
190     movl    R11, R8 # spill
193     incl    R11 # int
196     imull   R9, R11 # int
19a     addl    R9, [RSP + #32 (32-bit)]    # int
19f     addl    R9, RDX # int
1a2     addl    R9, RCX # int
1a5     addl    R9, RBX # int
1a8     addl    R9, [RSP + #60 (32-bit)]    # int
1ad     addl    R9, [RSP + #56 (32-bit)]    # int
1b2     addl    R9, [RSP + #52 (32-bit)]    # int
1b7     addl    R9, [RSP + #48 (32-bit)]    # int
1bc     movl    R10, R8 # spill
1bf     addl    R10, #9 # int
1c3     imull   R10, RSI    # int
1c7     addl    R10, R9 # int
1ca     addl    R10, RDI    # int
1cd     addl    R10, [RSP + #44 (32-bit)]   # int
1d2     movl    R11, R8 # spill
1d5     addl    R11, #12    # int
1d9     imull   R13, R11    # int
1dd     addl    R13, R10    # int
1e0     movl    R10, R8 # spill
1e3     addl    R10, #13    # int
1e7     imull   R10, [RSP + #40 (32-bit)]   # int
1ed     addl    R10, R13    # int
1f0     addl    RBP, R10    # int
1f3     addl    R14, RBP    # int
1f6     movl    R10, R8 # spill
1f9     addl    R10, #16    # int
1fd     cmpl    R10, #999999985
204     jl     B2   # loop end  P=1.000000 C=7419903.000000

Здесь мы наблюдаем гораздо больше «разливов» и больше обращений к стеку [RSP + ...]из-за более промежуточных результатов, которые необходимо сохранить.

Таким образом, ответ на вопрос прост: 2 * (i * i)быстрее, чем 2 * i * iпотому, что JIT генерирует более оптимальный код сборки для первого случая.


Но, конечно, очевидно, что ни первая, ни вторая версии не годятся; цикл может действительно выиграть от векторизации, поскольку любой процессор x86-64 имеет по крайней мере поддержку SSE2.

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

Фактически, современные процессоры x86-64 разбивают инструкции дальше на микрооперации (µop) и с такими функциями, как переименование регистров, µop кеши и буферы циклов, оптимизация цикла требует гораздо больше изящества, чем простое развертывание для оптимальной производительности. Согласно руководству по оптимизации Agner Fog :

Увеличение производительности благодаря кэш-памяти µop может быть весьма значительным, если средняя длина команды превышает 4 байта. Могут быть рассмотрены следующие методы оптимизации использования кэша µop:

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

Что касается времени загрузки - даже самое быстрое попадание L1D стоит 4 цикла , дополнительный регистр и µop, так что да, даже несколько обращений к памяти повредят производительность в тесных циклах.

Но вернемся к возможности векторизации - чтобы увидеть, насколько быстро это может быть, мы можем скомпилировать аналогичное приложение C с GCC , которое прямо его векторизует (показан AVX2, SSE2 похож) 2 :

  vmovdqa ymm0, YMMWORD PTR .LC0[rip]
  vmovdqa ymm3, YMMWORD PTR .LC1[rip]
  xor eax, eax
  vpxor xmm2, xmm2, xmm2
.L2:
  vpmulld ymm1, ymm0, ymm0
  inc eax
  vpaddd ymm0, ymm0, ymm3
  vpslld ymm1, ymm1, 1
  vpaddd ymm2, ymm2, ymm1
  cmp eax, 125000000      ; 8 calculations per iteration
  jne .L2
  vmovdqa xmm0, xmm2
  vextracti128 xmm2, ymm2, 1
  vpaddd xmm2, xmm0, xmm2
  vpsrldq xmm0, xmm2, 8
  vpaddd xmm0, xmm2, xmm0
  vpsrldq xmm1, xmm0, 4
  vpaddd xmm0, xmm0, xmm1
  vmovd eax, xmm0
  vzeroupper

Время выполнения:

  • SSE: 0,24 с или в 2 раза быстрее.
  • AVX: 0,15 с или в 3 раза быстрее.
  • AVX2: 0,08 с или в 5 раз быстрее.

1 Чтобы получить сгенерированный JIT вывод сборки, получите отладочную JVM и запустите-XX:+PrintOptoAssembly

2 Версия C компилируется с -fwrapvфлагом, который позволяет GCC обрабатывать целочисленное переполнение со знаком как обертку из двух дополнений.

rustyx
источник
11
Единственная самая большая проблема, с которой сталкивается оптимизатор в примере C, это неопределенное поведение, вызванное переполнением целых чисел со знаком. Что, в противном случае, вероятно, приведет к простой загрузке константы, поскольку весь цикл может быть вычислен во время компиляции.
Деймон
44
@ Damon Почему неопределенное поведение будет проблемой для оптимизатора? Если оптимизатор видит, что он переполняется при попытке вычислить результат, это просто означает, что он может оптимизировать его так, как он хочет, потому что поведение не определено.
13
@Runemoro: если оптимизатор докажет, что вызов функции неизбежно приведет к неопределенному поведению, он может предпочесть, что функция никогда не будет вызываться, и для нее не будет тела. Или выдает только retинструкцию, или выдает метку, а не команду ret, поэтому выполнение просто проваливается. На самом деле GCC ведет себя так, как иногда, когда он сталкивается с UB. Например: почему рет исчезают с оптимизацией? , Вы определенно хотите скомпилировать правильно сформированный код, чтобы убедиться, что ассм является нормальным.
Питер Кордес
8
Вероятно, это просто узкое место в пропускной способности UOP из-за неэффективного кода. Он даже не использует LEA как глазок для mov/ add-immediate. например, movl RBX, R9/ addl RBX, #8должно быть leal ebx, [r9 + 8], 1 моп для копирования и добавления. Или leal ebx, [r9 + r9 + 16]делать ebx = 2*(r9+8). Так что да, разворачиваться до такой степени глупо, как и наивный мозговой кодеин, который не использует в своих интересах целочисленные тождества и ассоциативную целочисленную математику.
Питер Кордес
7
Векторизация для последовательного сокращения была отключена в C2 ( bugs.openjdk.java.net/browse/JDK-8078563 ), но сейчас рассматривается возможность ее повторного включения ( bugs.openjdk.java.net/browse/JDK-8188313 ).
прон
131

Когда это умножение 2 * (i * i), JVM может вычленить умножение 2из цикла, что приводит к следующему эквивалентному, но более эффективному коду:

int n = 0;
for (int i = 0; i < 1000000000; i++) {
    n += i * i;
}
n *= 2;

но когда умножение есть (2 * i) * i, JVM не оптимизирует его, так как умножение на константу больше не прямо перед сложением.

Вот несколько причин, почему я думаю, что это так:

  • Добавление if (n == 0) n = 1оператора в начале цикла приводит к тому, что обе версии оказываются настолько эффективными, поскольку разложение умножения больше не гарантирует, что результат будет одинаковым
  • Оптимизированная версия (с учетом умножения на 2) работает так же быстро, как и 2 * (i * i)версия

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

public static void main(String[] args) {
    long fastVersion = 0;
    long slowVersion = 0;
    long optimizedVersion = 0;
    long modifiedFastVersion = 0;
    long modifiedSlowVersion = 0;

    for (int i = 0; i < 10; i++) {
        fastVersion += fastVersion();
        slowVersion += slowVersion();
        optimizedVersion += optimizedVersion();
        modifiedFastVersion += modifiedFastVersion();
        modifiedSlowVersion += modifiedSlowVersion();
    }

    System.out.println("Fast version: " + (double) fastVersion / 1000000000 + " s");
    System.out.println("Slow version: " + (double) slowVersion / 1000000000 + " s");
    System.out.println("Optimized version: " + (double) optimizedVersion / 1000000000 + " s");
    System.out.println("Modified fast version: " + (double) modifiedFastVersion / 1000000000 + " s");
    System.out.println("Modified slow version: " + (double) modifiedSlowVersion / 1000000000 + " s");
}

private static long fastVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += 2 * (i * i);
    }
    return System.nanoTime() - startTime;
}

private static long slowVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += 2 * i * i;
    }
    return System.nanoTime() - startTime;
}

private static long optimizedVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += i * i;
    }
    n *= 2;
    return System.nanoTime() - startTime;
}

private static long modifiedFastVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        if (n == 0) n = 1;
        n += 2 * (i * i);
    }
    return System.nanoTime() - startTime;
}

private static long modifiedSlowVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        if (n == 0) n = 1;
        n += 2 * i * i;
    }
    return System.nanoTime() - startTime;
}

И вот результаты:

Fast version: 5.7274411 s
Slow version: 7.6190804 s
Optimized version: 5.1348007 s
Modified fast version: 7.1492705 s
Modified slow version: 7.2952668 s

источник
3
Я думаю, что на оптимизированной версии, это должно бытьn *= 2000000000;
StefansArya
4
@StefansArya - Нет. Рассмотрим случай, когда предел равен 4, и мы пытаемся вычислить 2*1*1 + 2*2*2 + 2*3*3. Очевидно, что вычисление 1*1 + 2*2 + 3*3и умножение на 2 является правильным, тогда как умножение на 8 не будет.
Мартин Боннер поддерживает Монику
5
Математическое уравнение было так же, как это 2(1²) + 2(2²) + 2(3²) = 2(1² + 2² + 3²). Это было очень просто, и я просто забыл это, потому что цикл увеличивается.
StefansArya
5
Если вы распечатываете сборку с использованием отладочной jvm, это не будет правильным. Вы увидите связку sall ..., # 1, которая умножается на 2, в цикле. Интересно, что более медленная версия не имеет множителей в цикле.
Даниэль Берлин
2
Почему JVM может отделить 2 от, 2 * (i * i)но не от (2 * i) * i? Я думаю, что они эквивалентны (это может быть моим плохим предположением). Если это так, разве JVM не сможет канонизировать выражение перед оптимизацией?
RedSpikeyThing
41

Байт-коды: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Байт-коды Просмотрщик: https://github.com/Konloch/bytecode-viewer

На моем JDK (Windows 10 64 бит, 1.8.0_65-b17) я могу воспроизвести и объяснить:

public static void main(String[] args) {
    int repeat = 10;
    long A = 0;
    long B = 0;
    for (int i = 0; i < repeat; i++) {
        A += test();
        B += testB();
    }

    System.out.println(A / repeat + " ms");
    System.out.println(B / repeat + " ms");
}


private static long test() {
    int n = 0;
    for (int i = 0; i < 1000; i++) {
        n += multi(i);
    }
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 1000000000; i++) {
        n += multi(i);
    }
    long ms = (System.currentTimeMillis() - startTime);
    System.out.println(ms + " ms A " + n);
    return ms;
}


private static long testB() {
    int n = 0;
    for (int i = 0; i < 1000; i++) {
        n += multiB(i);
    }
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 1000000000; i++) {
        n += multiB(i);
    }
    long ms = (System.currentTimeMillis() - startTime);
    System.out.println(ms + " ms B " + n);
    return ms;
}

private static int multiB(int i) {
    return 2 * (i * i);
}

private static int multi(int i) {
    return 2 * i * i;
}

Вывод:

...
405 ms A 785527736
327 ms B 785527736
404 ms A 785527736
329 ms B 785527736
404 ms A 785527736
328 ms B 785527736
404 ms A 785527736
328 ms B 785527736
410 ms
333 ms

Так почему же? Байт-код таков:

 private static multiB(int arg0) { // 2 * (i * i)
     <localVar:index=0, name=i , desc=I, sig=null, start=L1, end=L2>

     L1 {
         iconst_2
         iload0
         iload0
         imul
         imul
         ireturn
     }
     L2 {
     }
 }

 private static multi(int arg0) { // 2 * i * i
     <localVar:index=0, name=i , desc=I, sig=null, start=L1, end=L2>

     L1 {
         iconst_2
         iload0
         imul
         iload0
         imul
         ireturn
     }
     L2 {
     }
 }

Разница в следующем: с скобками ( 2 * (i * i)):

  • push const stack
  • вставьте локально в стек
  • вставьте локально в стек
  • умножить вершину стека
  • умножить вершину стека

Без скобок ( 2 * i * i):

  • push const stack
  • вставьте локально в стек
  • умножить вершину стека
  • вставьте локально в стек
  • умножить вершину стека

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

DSchmidt
источник
Но почему push-push-multiply-multiply быстрее, чем push-multiply-push-multiply?
m0skit0
35

Касперд спросил в комментарии принятого ответа:

Примеры Java и C используют совершенно разные имена регистров. Оба примера используют AMD64 ISA?

xor edx, edx
xor eax, eax
.L2:
mov ecx, edx
imul ecx, edx
add edx, 1
lea eax, [rax+rcx*2]
cmp edx, 1000000000
jne .L2

У меня недостаточно репутации, чтобы ответить на это в комментариях, но это тот же ISA. Стоит отметить, что в версии GCC используется 32-разрядная целочисленная логика, а в скомпилированной версии JVM внутренне используется 64-разрядная целочисленная логика.

R8-R15 являются только новыми x86_64 регистров . EAX-EDX - это нижние части регистров общего назначения RAX-RDX. Важной частью в ответе является то, что версия GCC не развернута. Он просто выполняет один цикл цикла для каждого фактического цикла машинного кода. Хотя версия JVM имеет 16 циклов цикла в одном физическом цикле (основываясь на ответе rustyx, я не интерпретировал сборку). Это одна из причин, почему используется больше регистров, поскольку тело цикла на самом деле в 16 раз длиннее.

недоуменный
источник
2
Жаль, что GCC не замечает, что он может потечь *2из цикла. Хотя в этом случае это даже не победа, потому что это делается бесплатно с LEA. На процессорах Intel lea eax, [rax+rcx*2]имеет такую ​​же задержку 1с, как и add eax,ecx. Однако на процессорах AMD любой масштабированный индекс увеличивает задержку LEA до 2 циклов. Таким образом, цепочка зависимостей, переносимая циклами, удлиняется до 2 циклов, становясь узким местом для Райзена. ( imul ecx,edxпропускная способность равна 1 за такт на Ryzen и на Intel).
Питер Кордес
31

Хотя это не было напрямую связано со средой вопроса, просто для любопытства, я провел тот же тест на .NET Core 2.1, x64, режим релиза.

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

static void Main(string[] args)
{
    Stopwatch watch = new Stopwatch();

    Console.WriteLine("2 * (i * i)");

    for (int a = 0; a < 10; a++)
    {
        int n = 0;

        watch.Restart();

        for (int i = 0; i < 1000000000; i++)
        {
            n += 2 * (i * i);
        }

        watch.Stop();

        Console.WriteLine($"result:{n}, {watch.ElapsedMilliseconds} ms");
    }

    Console.WriteLine();
    Console.WriteLine("2 * i * i");

    for (int a = 0; a < 10; a++)
    {
        int n = 0;

        watch.Restart();

        for (int i = 0; i < 1000000000; i++)
        {
            n += 2 * i * i;
        }

        watch.Stop();

        Console.WriteLine($"result:{n}, {watch.ElapsedMilliseconds}ms");
    }
}

Результат:

2 * (я * я)

  • результат: 119860736, 438 мс
  • результат: 119860736, 433 мс
  • результат: 119860736, 437 мс
  • результат: 119860736, 435 мс
  • результат: 119860736, 436 мс
  • результат: 119860736, 435 мс
  • результат: 119860736, 435 мс
  • результат: 119860736, 439 мс
  • результат: 119860736, 436 мс
  • результат: 119860736, 437 мс

2 * я * я

  • результат: 119860736, 417 мс
  • результат: 119860736, 417 мс
  • результат: 119860736, 417 мс
  • результат: 119860736, 418 мс
  • результат: 119860736, 418 мс
  • результат: 119860736, 417 мс
  • результат: 119860736, 418 мс
  • результат: 119860736, 416 мс
  • результат: 119860736, 417 мс
  • результат: 119860736, 418 мс
Ünsal Ersöz
источник
1
Хотя это не ответ на вопрос, это действительно добавляет ценность. При этом, если что-то имеет жизненно важное значение для вашего сообщения, пожалуйста , укажите это в сообщении, а не ссылки на сторонний ресурс. Ссылки не работают.
Джаред Смит
1
@JaredSmith Спасибо за отзыв. Учитывая, что ссылка, которую вы упоминаете, является ссылкой "результата", это изображение не является сторонним источником. Я загрузил его в stackoverflow через его собственную панель.
Юнсал Эрсез
1
Это ссылка на imgur, так что да, это не имеет значения, как вы добавили ссылку. Я не вижу, что такого сложного в копировании-вставке какого-либо консольного вывода.
Джаред Смит
5
За исключением того, что это наоборот
Леппи
2
@SamB он все еще находится в домене imgur.com, а это значит, что он будет существовать только до тех пор, пока imgur.
p91paul
21

Я получил похожие результаты:

2 * (i * i): 0.458765943 s, n=119860736
2 * i * i: 0.580255126 s, n=119860736

Я получил те же результаты, если оба цикла были в одной и той же программе или каждый был в отдельном файле .java / .class, выполняемом по отдельности.

Наконец, вот javap -c -v <.java>декомпиляция каждого:

     3: ldc           #3                  // String 2 * (i * i):
     5: invokevirtual #4                  // Method java/io/PrintStream.print:(Ljava/lang/String;)V
     8: invokestatic  #5                  // Method java/lang/System.nanoTime:()J
     8: invokestatic  #5                  // Method java/lang/System.nanoTime:()J
    11: lstore_1
    12: iconst_0
    13: istore_3
    14: iconst_0
    15: istore        4
    17: iload         4
    19: ldc           #6                  // int 1000000000
    21: if_icmpge     40
    24: iload_3
    25: iconst_2
    26: iload         4
    28: iload         4
    30: imul
    31: imul
    32: iadd
    33: istore_3
    34: iinc          4, 1
    37: goto          17

против

     3: ldc           #3                  // String 2 * i * i:
     5: invokevirtual #4                  // Method java/io/PrintStream.print:(Ljava/lang/String;)V
     8: invokestatic  #5                  // Method java/lang/System.nanoTime:()J
    11: lstore_1
    12: iconst_0
    13: istore_3
    14: iconst_0
    15: istore        4
    17: iload         4
    19: ldc           #6                  // int 1000000000
    21: if_icmpge     40
    24: iload_3
    25: iconst_2
    26: iload         4
    28: imul
    29: iload         4
    31: imul
    32: iadd
    33: istore_3
    34: iinc          4, 1
    37: goto          17

К вашему сведению -

java -version
java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)
paulsm4
источник
1
Лучший ответ, и, возможно, вы можете проголосовать за восстановление - stackoverflow.com/a/53452836/1746118 ... Примечание: я в любом случае не являюсь downvoter.
Наман
@nullpointer - я согласен. Я бы определенно проголосовал за восстановление, если бы мог. Я также хотел бы, чтобы Стефан "удвоил голос" за количественное определение "значительного"
paulsm4
Этот был удален самостоятельно, так как он измерял неправильную вещь - см. Комментарий автора по вышеуказанному вопросу
Krease
2
Получи отладочную версию и беги с -XX:+PrintOptoAssembly. Или просто используйте vtune или подобное.
rustyx
1
@ rustyx - Если проблема в реализации JIT ... тогда «получение отладочной версии» ПОЛНОСТЬЮ РАЗЛИЧНОЙ JRE не обязательно поможет. Тем не менее: похоже на то, что вы обнаружили выше с разборкой JIT на вашей JRE, также объясняет поведение JRE и моей OP. А также объясняет, почему другие JRE ведут себя «по-другому». +1: спасибо за отличную детективную работу!
paulsm4
18

Интересное наблюдение с использованием Java 11 и выключение циклического развертывания со следующей опцией VM:

-XX:LoopUnrollLimit=0

Цикл с 2 * (i * i)выражением приводит к более компактному нативному коду 1 :

L0001: add    eax,r11d
       inc    r8d
       mov    r11d,r8d
       imul   r11d,r8d
       shl    r11d,1h
       cmp    r8d,r10d
       jl     L0001

по сравнению с 2 * i * iверсией:

L0001: add    eax,r11d
       mov    r11d,r8d
       shl    r11d,1h
       add    r11d,2h
       inc    r8d
       imul   r11d,r8d
       cmp    r8d,r10d
       jl     L0001

Версия Java:

java version "11" 2018-09-25
Java(TM) SE Runtime Environment 18.9 (build 11+28)
Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11+28, mixed mode)

Результаты тестов:

Benchmark          (size)  Mode  Cnt    Score     Error  Units
LoopTest.fast  1000000000  avgt    5  694,868 ±  36,470  ms/op
LoopTest.slow  1000000000  avgt    5  769,840 ± 135,006  ms/op

Исходный код теста:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@State(Scope.Thread)
@Fork(1)
public class LoopTest {

    @Param("1000000000") private int size;

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
            .include(LoopTest.class.getSimpleName())
            .jvmArgs("-XX:LoopUnrollLimit=0")
            .build();
        new Runner(opt).run();
    }

    @Benchmark
    public int slow() {
        int n = 0;
        for (int i = 0; i < size; i++)
            n += 2 * i * i;
        return n;
    }

    @Benchmark
    public int fast() {
        int n = 0;
        for (int i = 0; i < size; i++)
            n += 2 * (i * i);
        return n;
    }
}

1 - используемые параметры виртуальной машины: -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0

Александр Пирохов
источник
2
Вау, это какой-то мозговой мертвец. Вместо того, чтобы увеличивать i перед копированием для вычисления 2*i, он делает это после, поэтому ему нужна дополнительная add r11d,2инструкция. (Кроме того, он пропускает add same,sameглазок вместо shl1 (добавление работает на большем количестве портов). Он также пропускает глазок LEA для x*2 + 2( lea r11d, [r8*2 + 2]), если он действительно хочет делать вещи в таком порядке по какой-то сумасшедшей причине планирования инструкций. Мы уже могли видеть из развернутая версия, которая упускала LEA, стоила ему много мопов, так же, как обе петли здесь
Питер Кордес
2
lea eax, [rax + r11 * 2]заменил бы 2 инструкции (в обоих циклах), если бы JIT-компилятор успел найти эту оптимизацию в длительных циклах. Любой приличный опережающий компилятор найдет его. (Если, возможно, настройка не только для AMD, где масштабированный индекс LEA имеет задержку в 2 цикла, так что, может быть, и не стоит.)
Питер Кордес
15

Я попробовал JMH, используя архетип по умолчанию: я также добавил оптимизированную версию на основе объяснения Рунеморо .

@State(Scope.Benchmark)
@Warmup(iterations = 2)
@Fork(1)
@Measurement(iterations = 10)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
//@BenchmarkMode({ Mode.All })
@BenchmarkMode(Mode.AverageTime)
public class MyBenchmark {
  @Param({ "100", "1000", "1000000000" })
  private int size;

  @Benchmark
  public int two_square_i() {
    int n = 0;
    for (int i = 0; i < size; i++) {
      n += 2 * (i * i);
    }
    return n;
  }

  @Benchmark
  public int square_i_two() {
    int n = 0;
    for (int i = 0; i < size; i++) {
      n += i * i;
    }
    return 2*n;
  }

  @Benchmark
  public int two_i_() {
    int n = 0;
    for (int i = 0; i < size; i++) {
      n += 2 * i * i;
    }
    return n;
  }
}

Результат здесь:

Benchmark                           (size)  Mode  Samples          Score   Score error  Units
o.s.MyBenchmark.square_i_two           100  avgt       10         58,062         1,410  ns/op
o.s.MyBenchmark.square_i_two          1000  avgt       10        547,393        12,851  ns/op
o.s.MyBenchmark.square_i_two    1000000000  avgt       10  540343681,267  16795210,324  ns/op
o.s.MyBenchmark.two_i_                 100  avgt       10         87,491         2,004  ns/op
o.s.MyBenchmark.two_i_                1000  avgt       10       1015,388        30,313  ns/op
o.s.MyBenchmark.two_i_          1000000000  avgt       10  967100076,600  24929570,556  ns/op
o.s.MyBenchmark.two_square_i           100  avgt       10         70,715         2,107  ns/op
o.s.MyBenchmark.two_square_i          1000  avgt       10        686,977        24,613  ns/op
o.s.MyBenchmark.two_square_i    1000000000  avgt       10  652736811,450  27015580,488  ns/op

На моем ПК ( Core i7 860 - он ничего не делает, кроме чтения на моем смартфоне):

  • n += i*iтогда n*2первый
  • 2 * (i * i) второй

JVM явно не оптимизирует так же, как человек (основываясь на ответе Рунеморо).

Теперь, читая байт-код: javap -c -v ./target/classes/org/sample/MyBenchmark.class

Я не эксперт по байт-коду, но мы iload_2раньше, чем мы imul: вероятно, в этом и заключается разница: могу предположить, что JVM оптимизирует чтение iдважды ( iуже здесь, и нет необходимости загружать его снова), пока 2*i*iоно может ' т.

Данные не найдены
источник
4
Байт-код AFAICT довольно не важен для производительности, и я бы не стал оценивать, что быстрее, основываясь на нем. Это всего лишь исходный код для JIT-компилятора ... конечно, сохраняющий смысл переупорядочение строк исходного кода может изменить результирующий код и его эффективность, но все это довольно непредсказуемо.
Maaartinus
13

Больше из дополнения. Я повторил эксперимент, используя последнюю версию Java 8 JVM от IBM:

java version "1.8.0_191"
Java(TM) 2 Runtime Environment, Standard Edition (IBM build 1.8.0_191-b12 26_Oct_2018_18_45 Mac OS X x64(SR5 FP25))
Java HotSpot(TM) 64-Bit Server VM (build 25.191-b12, mixed mode)

И это показывает очень похожие результаты:

0.374653912 s
n = 119860736
0.447778698 s
n = 119860736

(второй результат с использованием 2 * i * i).

Интересно, что при работе на той же машине, но с использованием Oracle Java:

Java version "1.8.0_181"
Java(TM) SE Runtime Environment (build 1.8.0_181-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.181-b13, mixed mode)

результаты в среднем немного медленнее:

0.414331815 s
n = 119860736
0.491430656 s
n = 119860736

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

GhostCat
источник
5

Два метода добавления генерируют немного другой байт-код:

  17: iconst_2
  18: iload         4
  20: iload         4
  22: imul
  23: imul
  24: iadd

Для 2 * (i * i):

  17: iconst_2
  18: iload         4
  20: imul
  21: iload         4
  23: imul
  24: iadd

Для 2 * i * i.

И при использовании теста JMH, как это:

@Warmup(iterations = 5, batchSize = 1)
@Measurement(iterations = 5, batchSize = 1)
@Fork(1)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
public class MyBenchmark {

    @Benchmark
    public int noBrackets() {
        int n = 0;
        for (int i = 0; i < 1000000000; i++) {
            n += 2 * i * i;
        }
        return n;
    }

    @Benchmark
    public int brackets() {
        int n = 0;
        for (int i = 0; i < 1000000000; i++) {
            n += 2 * (i * i);
        }
        return n;
    }

}

Разница очевидна:

# JMH version: 1.21
# VM version: JDK 11, Java HotSpot(TM) 64-Bit Server VM, 11+28
# VM options: <none>

Benchmark                      (n)  Mode  Cnt    Score    Error  Units
MyBenchmark.brackets    1000000000  avgt    5  380.889 ± 58.011  ms/op
MyBenchmark.noBrackets  1000000000  avgt    5  512.464 ± 11.098  ms/op

То, что вы наблюдаете, является правильным, а не просто аномалией вашего стиля бенчмаркинга (т.е. без разминки, см. Как написать правильный микро-бенчмарк в Java? )

Бегом снова с Граалем:

# JMH version: 1.21
# VM version: JDK 11, Java HotSpot(TM) 64-Bit Server VM, 11+28
# VM options: -XX:+UnlockExperimentalVMOptions -XX:+EnableJVMCI -XX:+UseJVMCICompiler

Benchmark                      (n)  Mode  Cnt    Score    Error  Units
MyBenchmark.brackets    1000000000  avgt    5  335.100 ± 23.085  ms/op
MyBenchmark.noBrackets  1000000000  avgt    5  331.163 ± 50.670  ms/op

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

Так что на самом деле это зависит только от того, насколько хорошо JIT-компилятор способен оптимизировать определенный фрагмент кода, и не обязательно имеет логическую причину для этого.

Йорн Верни
источник