Por que 2 * (i * i) é mais rápido que 2 * i * i em Java?

855

O seguinte programa Java leva em média entre 0,50 segundos e 0,55 segundos para executar:

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

Se eu substituir 2 * (i * i)por 2 * i * i, leva entre 0,60 e 0,65 segundos para executar. Por quê?

Eu executei cada versão do programa 15 vezes, alternando entre as duas. Aqui estão os resultados:

 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

A corrida mais rápida 2 * i * idemorou mais que a mais lenta 2 * (i * i). Se eles tivessem a mesma eficiência, a probabilidade de isso acontecer seria menor que 1/2^15 * 100% = 0.00305%.

Stefan
fonte
5
Eu obter resultados semelhantes (números ligeiramente diferentes, mas gap definitivamente visível e consistente, definitivamente mais do que erro de amostragem)
Krease
29
Também veja: stackoverflow.com/questions/504103/…
lexicore
3
@ Krease Bom que você pegou meu erro. De acordo com o novo benchmark que corri, 2 * i * ié mais lento. Vou tentar correr com Graal também.
Jorn Vernee
5
Para descobrir de verdade por que um é mais rápido que o outro, teríamos de obter os gráficos de desmontagem ou Ideal para esses métodos. O montador é muito irritante para tentar descobrir, então estou tentando obter uma compilação de depuração do OpenJDK que possa gerar bons gráficos.
Jorn Vernee
4
Você pode renomear sua pergunta para " Por que é i * i * 2mais rápido que 2 * i * i? " Para maior clareza de que o problema está na ordem das operações.
Cœur

Respostas:

1202

Há uma pequena diferença na ordem do bytecode.

2 * (i * i):

     iconst_2
     iload0
     iload0
     imul
     imul
     iadd

vs 2 * i * i:

     iconst_2
     iload0
     imul
     iload0
     imul
     iadd

À primeira vista, isso não deve fazer diferença; se alguma coisa a segunda versão é mais ideal, pois usa um slot a menos.

Portanto, precisamos nos aprofundar no nível mais baixo (JIT) 1 .

Lembre-se de que o JIT tende a desenrolar pequenos loops de forma muito agressiva. De fato, observamos um desenrolar de 16x para o 2 * (i * i)caso:

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

Vemos que há 1 registro "derramado" na pilha.

E para a 2 * i * iversão:

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

Aqui observamos muito mais "derramamento" e mais acessos à pilha [RSP + ...], devido a resultados mais intermediários que precisam ser preservados.

Portanto, a resposta para a pergunta é simples: 2 * (i * i)é mais rápida do que 2 * i * iporque o JIT gera um código de montagem mais ideal para o primeiro caso.


Mas é claro que é óbvio que nem a primeira nem a segunda versão são boas; o loop poderia realmente se beneficiar da vetorização, já que qualquer CPU x86-64 tem pelo menos suporte a SSE2.

Portanto, é uma questão do otimizador; como costuma ser o caso, ele se desenrola muito agressivamente e atira no próprio pé, perdendo o tempo todo em várias outras oportunidades.

De fato, as modernas CPUs x86-64 dividem ainda mais as instruções em micro-ops (µops) e com recursos como renomeação de registros, caches µop e buffers de loop, a otimização de loop requer muito mais requinte do que um simples desenrolar para obter o desempenho ideal. De acordo com o guia de otimização da Agner Fog :

O ganho no desempenho devido ao cache µop pode ser considerável se o comprimento médio das instruções for superior a 4 bytes. Os seguintes métodos para otimizar o uso do cache µop podem ser considerados:

  • Verifique se os loops críticos são pequenos o suficiente para caber no cache µop.
  • Alinhe as entradas de loop e entradas de função mais críticas por 32.
  • Evite desenrolar desnecessário o loop.
  • Evite instruções que tenham tempo extra de carregamento
    . . .

Com relação a esses tempos de carregamento - até o mais rápido acerto L1D custa 4 ciclos , um registro extra e µop, então sim, mesmo alguns acessos à memória prejudicam o desempenho em ciclos apertados.

Mas voltando à oportunidade de vetorização - para ver o quão rápido pode ser, podemos compilar um aplicativo C semelhante com o GCC , que o vetoriza completamente (AVX2 é mostrado, SSE2 é semelhante) 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

Com tempos de execução:

  • SSE: 0,24 s, ou 2 vezes mais rápido.
  • AVX: 0,15 s, ou 3 vezes mais rápido.
  • AVX2: 0,08 s, ou 5 vezes mais rápido.

1 Para obter a saída de montagem gerada pelo JIT, obtenha uma JVM de depuração e execute com-XX:+PrintOptoAssembly

2 A versão C é compilada com o -fwrapvsinalizador, que permite ao GCC tratar o excesso de número inteiro assinado como um complemento de dois.

rustyx
fonte
11
O maior problema que o otimizador encontra no exemplo C é o comportamento indefinido invocado pelo estouro de número inteiro assinado. O que, caso contrário, provavelmente resultaria no simples carregamento de uma constante, pois todo o loop pode ser calculado em tempo de compilação.
Damon
44
@ Damon Por que o comportamento indefinido seria um problema para o otimizador? Se o otimizador vê um excesso de fluxo ao tentar calcular o resultado, isso significa que ele pode otimizá-lo da maneira que desejar, porque o comportamento é indefinido.
13
@Runemoro: se o otimizador provar que chamar a função resultará inevitavelmente em um comportamento indefinido, ele pode optar por assumir que a função nunca será chamada e não emitir um corpo para ela. Ou emita apenas uma retinstrução, ou emita um rótulo e nenhuma instrução ret, para que a execução caia completamente. De fato, o GCC se comporta de vez em quando quando encontra o UB. Por exemplo: por que ret desaparecer com otimização? . Você definitivamente deseja compilar um código bem formado para garantir que o asm esteja correto.
22818 Peter Cordes
8
Provavelmente é apenas um gargalo de taxa de transferência de front-end devido à ineficiente geração de código. Nem está usando o LEA como olho mágico para mov/ add-immediate. por exemplo, movl RBX, R9/ addl RBX, #8deveria ser leal ebx, [r9 + 8], 1 cópia para copiar e adicionar. Ou leal ebx, [r9 + r9 + 16]para fazer ebx = 2*(r9+8). Então, sim, desenrolar-se a ponto de derramar é estúpido, e também é ingênuo o codegen braindead que não tira proveito das identidades inteiras e da matemática associativa.
Peter Cordes
7
A vetorização para redução sequencial foi desativada no C2 ( bugs.openjdk.java.net/browse/JDK-8078563 ), mas agora está sendo considerada para reativação ( bugs.openjdk.java.net/browse/JDK-8188313 ).
pron
131

Quando a multiplicação ocorre 2 * (i * i), a JVM pode fatorar a multiplicação pelo 2loop, resultando neste código equivalente, mas mais eficiente:

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

mas quando a multiplicação ocorre (2 * i) * i, a JVM não a otimiza, pois a multiplicação por uma constante não está mais logo antes da adição.

Aqui estão algumas razões pelas quais eu acho que esse é o caso:

  • A adição de uma if (n == 0) n = 1instrução no início do loop resulta em ambas as versões tão eficientes, já que fatorar a multiplicação não garante mais que o resultado será o mesmo
  • A versão otimizada (fatorando a multiplicação por 2) é exatamente tão rápida quanto a 2 * (i * i)versão

Aqui está o código de teste que eu usei para tirar essas conclusões:

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

E aqui estão os resultados:

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

fonte
3
Eu acho que na n *= 2000000000;
versão
4
@StefansArya - Não. Considere o caso em que o limite é 4 e estamos tentando calcular 2*1*1 + 2*2*2 + 2*3*3. É óbvio que calcular 1*1 + 2*2 + 3*3e multiplicar por 2 está correto, enquanto que multiplicar por 8 não seria.
Martin Bonner apoia Monica
5
A equação matemática era assim 2(1²) + 2(2²) + 2(3²) = 2(1² + 2² + 3²). Isso foi muito simples e eu esqueci porque o loop aumenta.
StefansArya
5
Se você imprimir a montagem usando uma jvm de depuração, isso não parece estar correto. Você verá um monte de sall ..., # 1, que são multiplicados por 2, no loop. Curiosamente, a versão mais lenta não parece ter multiplicações no loop.
Daniel Berlin
2
Por que a JVM pode separar os 2 de, 2 * (i * i)mas não de (2 * i) * i? Eu pensaria que eles são equivalentes (essa pode ser minha suposição ruim). Nesse caso, a JVM não canonizaria a expressão antes de otimizar?
RedSpikeyThing #
41

Códigos de bytes: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Visualizador de códigos de bytes: https://github.com/Konloch/bytecode-viewer

No meu JDK (Windows 10 de 64 bits, 1.8.0_65-b17), posso reproduzir e explicar:

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

Resultado:

...
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

Então por que? O código de byte é este:

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

A diferença é: entre parênteses (2 * (i * i) ):

  • push const stack
  • empurre local na pilha
  • empurre local na pilha
  • multiplique o topo da pilha
  • multiplique o topo da pilha

Sem colchetes ( 2 * i * i):

  • push const stack
  • empurre local na pilha
  • multiplique o topo da pilha
  • empurre local na pilha
  • multiplique o topo da pilha

Carregar tudo na pilha e depois voltar a trabalhar é mais rápido do que alternar entre colocar a pilha e operar nela.

DSchmidt
fonte
Mas por que empurrar-empurrar-multiplicar-multiplicar mais rápido que empurrar-multiplicar-empurrar-multiplicar?
M0skit0
35

Kasperd perguntou em um comentário da resposta aceita:

Os exemplos Java e C usam nomes de registro bem diferentes. Os dois exemplos estão usando o 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

Não tenho reputação suficiente para responder a isso nos comentários, mas esses são os mesmos ISA. Vale ressaltar que a versão do GCC usa lógica inteira de 32 bits e a versão compilada da JVM usa lógica inteira de 64 bits internamente.

R8 a R15 são apenas novos X86_64 registros . EAX para EDX são as partes inferiores dos registros de uso geral RAX para RDX. A parte importante da resposta é que a versão do GCC não é desenrolada. Ele simplesmente executa uma rodada do loop por loop de código de máquina real. Embora a versão da JVM tenha 16 rodadas de loop em um loop físico (com base na resposta da rustyx, não reinterpretei o assembly). Essa é uma das razões pelas quais há mais registros sendo usados, já que o corpo do loop é na verdade 16 vezes mais longo.

Intrigado
fonte
2
Pena que o gcc não percebe que pode afundar o *2fora do loop. Embora neste caso, não seja nem uma vitória fazer isso, porque está fazendo isso de graça com o LEA. Em CPUs Intel, lea eax, [rax+rcx*2]possui a mesma latência 1c que add eax,ecx. No entanto, nas CPUs AMD, qualquer índice escalado aumenta a latência do LEA para 2 ciclos. Portanto, a cadeia de dependência transportada por loop aumenta para 2 ciclos, tornando-se o gargalo da Ryzen. (a imul ecx,edxtaxa de transferência é de 1 por relógio no Ryzen e na Intel).
Peter Cordes
31

Embora não esteja diretamente relacionado ao ambiente da pergunta, apenas por curiosidade, fiz o mesmo teste no .NET Core 2.1, x64, modo de lançamento.

Aqui está o resultado interessante, confirmando fonomena semelhante (ao contrário) acontecendo no lado escuro da força. Código:

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

Resultado:

2 * (i * i)

  • resultado: 4398 ms, 119860736
  • resultado: 119860736, 433 ms
  • resultado: 119860736, 437 ms
  • resultado: 4398 ms, 119860736
  • resultado: 119860736, 436 ms
  • resultado: 4398 ms, 119860736
  • resultado: 4398 ms, 119860736
  • resultado: 119860736, 439 ms
  • resultado: 119860736, 436 ms
  • resultado: 119860736, 437 ms

2 * i * i

  • resultado: 119860736, 417 ms
  • resultado: 119860736, 417 ms
  • resultado: 119860736, 417 ms
  • resultado: 119860736, 418 ms
  • resultado: 119860736, 418 ms
  • resultado: 119860736, 417 ms
  • resultado: 119860736, 418 ms
  • resultado: 119860736, 416 ms
  • resultado: 119860736, 417 ms
  • resultado: 119860736, 418 ms
Ünsal Ersöz
fonte
1
Embora essa não seja uma resposta para a pergunta, ela agrega valor. Dito isto, se algo é vital para a sua postagem, inclua-a na postagem em vez de vincular a um recurso externo. Os links ficam mortos.
Jared Smith
1
@JaredSmith Obrigado pelo feedback. Considerando que o link mencionado é o link "resultado", essa imagem não é uma fonte externa. Fiz upload para o stackoverflow através de seu próprio painel.
Ünsal Ersöz 28/11
1
É um link para imgur, então sim, é, não importa como você adicionou o link. Não consigo ver o que é tão difícil sobre copiar e colar alguma saída do console.
Jared Smith
5
Só que esse é o contrário
leppie 30/11
2
O @SamB ainda está no domínio imgur.com, o que significa que sobreviverá apenas enquanto o imgur.
P91paul 01/12/19
21

Eu obtive resultados semelhantes:

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

Eu obtive os mesmos resultados se ambos os loops estavam no mesmo programa ou cada um estava em um arquivo .java / .class separado, executado em uma execução separada.

Finalmente, aqui está uma javap -c -v <.java>descompilação de cada um:

     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

vs.

     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

PARA SUA INFORMAÇÃO -

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
fonte
1
Uma resposta melhor e talvez você possa votar para anular a exclusão - stackoverflow.com/a/53452836/1746118 ... Observação: eu não sou o defensor de qualquer maneira.
Naman
@ nullpointer - eu concordo. Definitivamente votaria para recuperar, se eu pudesse. Eu também gostaria de Stefan "double upvote" para dar uma definição quantitativa de "significativo"
paulsm4
Aquele foi auto-excluídos, uma vez que mediu a coisa errada - ver comentário que do autor sobre a pergunta acima
Krease
2
Obtenha um debug jre e execute com -XX:+PrintOptoAssembly. Ou apenas use vtune ou similar.
Rustyx
1
@ rustyx - Se o problema for a implementação do JIT ... então "obter uma versão de depuração" DE UM JRE COMPLETAMENTE DIFERENTE não ajudará necessariamente. No entanto: parece que o que você encontrou acima com a desmontagem do JIT no JRE também explica o comportamento no JRE do OP e no meu. E também explica por que outros JREs se comportam "de maneira diferente". +1: obrigado pelo excelente trabalho de detetive!
paulsm4
18

Observação interessante usando Java 11 e desativando o desenrolamento de loop com a seguinte opção de VM:

-XX:LoopUnrollLimit=0

O loop com a 2 * (i * i)expressão resulta em código nativo 1 mais compacto :

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

em comparação com a 2 * i * iversão:

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

Versão 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)

Resultados de referência:

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

Código fonte de referência:

@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 - Opções de VM usadas: -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0

Oleksandr Pyrohov
fonte
2
Uau, isso é um absurdo. Em vez de incrementar i antes de copiá-lo para calcular 2*i, ele faz isso depois, portanto, é necessária uma add r11d,2instrução extra . (Além disso, ele perde o add same,sameolho mágico em vez de shl1 (o add é executado em mais portas). Ele também perde o olho mágico de LEA para x*2 + 2( lea r11d, [r8*2 + 2]) se ele realmente deseja fazer as coisas nessa ordem por algum motivo maluco de programação de instruções. a versão desenrolada que a falta de LEA estava custando-lhe um monte de UOPs, mesmo que ambos os loops aqui.
Peter Cordes
2
lea eax, [rax + r11 * 2]substituiria duas instruções (em ambos os loops) se o compilador JIT tivesse tempo para procurar essa otimização em loops de longa execução. Qualquer compilador decente com antecedência encontraria. (A não ser que talvez ajuste somente para AMD, onde índice escalado LEA tem 2 ciclo de latência talvez por isso não vale a pena.)
Peter Cordes
15

Tentei um JMH usando o arquétipo padrão: também adicionei uma versão otimizada com base na explicação de Runemoro .

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

O resultado está aqui:

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

No meu PC ( Core i7 860 - não está fazendo nada além de ler no meu smartphone):

  • n += i*ientão n*2é o primeiro
  • 2 * (i * i) é o segundo.

A JVM claramente não está otimizando da mesma maneira que um humano (com base na resposta de Runemoro).

Agora, então, lendo o bytecode: javap -c -v ./target/classes/org/sample/MyBenchmark.class

Não sou especialista em bytecode, mas iload_2antes de nós imul: provavelmente é aí que você obtém a diferença: suponho que a JVM otimize a leitura iduas vezes ( ijá está aqui e não há necessidade de carregá-la novamente) enquanto estiver no 2*i*imodo ' t.

Nenhum dado encontrado
fonte
4
O bytecode AFAICT é bastante irrelevante para o desempenho, e eu não tentaria estimar o que é mais rápido com base nele. É apenas o código-fonte do compilador JIT ... com certeza as linhas de código-fonte de reordenação que preservam o significado podem alterar o código resultante e sua eficiência, mas tudo isso é imprevisível.
Maaartinus 26/1118
13

Mais um adendo. Eu reproduzi o experimento usando o Java 8 JVM mais recente da 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)

E isso mostra resultados muito semelhantes:

0.374653912 s
n = 119860736
0.447778698 s
n = 119860736

(segundos resultados usando 2 * i * i).

Curiosamente, ao executar na mesma máquina, mas usando o 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)

os resultados são, em média, um pouco mais lentos:

0.414331815 s
n = 119860736
0.491430656 s
n = 119860736

Resumindo: até o número menor de versão do HotSpot é importante aqui, pois diferenças sutis na implementação do JIT podem ter efeitos notáveis.

GhostCat
fonte
5

Os dois métodos de adição geram código de bytes ligeiramente diferente:

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

Para 2 * (i * i)vs:

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

Para 2 * i * i.

E ao usar um benchmark JMH como este:

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

}

A diferença é clara:

# 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

O que você observa está correto, e não apenas uma anomalia do seu estilo de benchmarking (ou seja, sem aquecimento, consulte Como redigir um micro-benchmark correto em Java? )

Correndo novamente com Graal:

# 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

Você vê que os resultados são muito mais próximos, o que faz sentido, já que Graal é um compilador de melhor desempenho e mais moderno.

Portanto, isso depende apenas de quão bem o compilador JIT é capaz de otimizar uma parte específica do código e não necessariamente tem uma razão lógica para isso.

Jorn Vernee
fonte