¿Por qué 2 * (i * i) es más rápido que 2 * i * i en Java?
El siguiente programa Java tarda una media de entre 0,50 y 0,55 segundos en ejecutarse:
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);
}
Si lo reemplazo 2 * (i * i)con 2 * i * i, tardará entre 0,60 y 0,65 segundos en ejecutarse. ¿Cómo?
Ejecuté cada versión del programa 15 veces, alternando entre las dos. Aquí están los 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
La ejecución más rápida de 2 * i * itomó más tiempo que la ejecución más lenta de 2 * (i * i). Si tuvieran la misma eficiencia, la probabilidad de que esto sucediera sería menor que 1/2^15 * 100% = 0.00305%.
Hay una ligera diferencia en el orden del código de bytes.
2 * (i * i):
iconst_2
iload0
iload0
imul
imul
iadd
frente a 2 * i * i:
iconst_2
iload0
imul
iload0
imul
iadd
A primera vista esto no debería suponer ninguna diferencia; en todo caso, la segunda versión es más óptima ya que utiliza una ranura menos.
Por eso necesitamos profundizar en el nivel inferior (JIT) 1 .
Recuerde que JIT tiende a desenrollar pequeños bucles de forma muy agresiva. De hecho observamos un desarrollo de 16x para el 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 hay 1 registro que está "derramado" en la pila.
Y para la 2 * i * iversión:
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
Aquí observamos muchos más "derrames" y más accesos a la pila [RSP + ...], debido a que hay más resultados intermedios que deben conservarse.
Por lo tanto, la respuesta a la pregunta es simple: 2 * (i * i)es más rápido 2 * i * iporque el JIT genera un código ensamblador más óptimo para el primer caso.
Pero, por supuesto, es obvio que ni la primera ni la segunda versión son buenas; el bucle realmente podría beneficiarse de la vectorización, ya que cualquier CPU x86-64 tiene al menos soporte SSE2.
Entonces es una cuestión del optimizador; Como suele ocurrir, se desenrolla demasiado agresivamente y se dispara en el pie, perdiendo al mismo tiempo otras oportunidades.
De hecho, las CPU x86-64 modernas dividen las instrucciones en microoperaciones (μops) y con funciones como cambio de nombre de registros, cachés de μop y buffers de bucle, la optimización del bucle requiere mucha más delicadeza que un simple desenrollado para un rendimiento óptimo. Según la guía de optimización de Agner Fog :
La ganancia de rendimiento debida a la caché µop puede ser bastante considerable si la longitud media de las instrucciones es superior a 4 bytes. Se pueden considerar los siguientes métodos para optimizar el uso de la caché µop:
- Asegúrese de que los bucles críticos sean lo suficientemente pequeños como para caber en la caché µop.
- Alinee las entradas de bucle y funciones más críticas en 32.
- Evite desenrollar bucles innecesarios.
- Evite instrucciones que tengan tiempo de carga extra
. . .
Con respecto a esos tiempos de carga, incluso el acceso L1D más rápido cuesta 4 ciclos , un registro adicional y µop, por lo que sí, incluso unos pocos accesos a la memoria afectarán el rendimiento en bucles cerrados.
Pero volvamos a la oportunidad de la vectorización: para ver qué tan rápido puede ser, podemos compilar una aplicación C similar con GCC , que la vectoriza directamente (se muestra AVX2, SSE2 es similar) 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
Con tiempos de ejecución:
- SSE: 0,24 s, o 2 veces más rápido.
- AVX: 0,15 s, o 3 veces más rápido.
- AVX2: 0,08 s, o 5 veces más rápido.
1 Para obtener la salida del ensamblado generado por JIT, obtenga una JVM de depuración y ejecútela con-XX:+PrintOptoAssembly
2 La versión C se compila con el -fwrapvindicador, que permite a GCC tratar el desbordamiento de enteros con signo como un complemento de dos.
(Nota del editor: esta respuesta se contradice con la evidencia obtenida al observar el conjunto, como lo muestra otra respuesta. Esta fue una suposición respaldada por algunos experimentos, pero resultó no ser correcta).
Cuando la multiplicación es 2 * (i * i), la JVM puede factorizar la multiplicación por 2del bucle, lo que da como resultado este código equivalente pero más eficiente:
int n = 0;
for (int i = 0; i < 1000000000; i++) {
n += i * i;
}
n *= 2;
pero cuando la multiplicación es (2 * i) * i, la JVM no la optimiza ya que la multiplicación por una constante ya no está justo antes de la n +=suma.
Aquí hay algunas razones por las que creo que este es el caso:
- Agregar una
if (n == 0) n = 1declaración al comienzo del ciclo da como resultado que ambas versiones sean igual de eficientes, ya que factorizar la multiplicación ya no garantiza que el resultado será el mismo. - La versión optimizada (descontando la multiplicación por 2) es exactamente tan rápida como la
2 * (i * i)versión
Aquí está el código de prueba que utilicé para sacar estas conclusiones:
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;
}
Y aquí están los 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
Nov 23 '2018 21:11
Códigos de bytes: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Visor de códigos de bytes: https://github.com/Konloch/bytecode-viewer
En mi JDK (Windows 10 de 64 bits, 1.8.0_65-b17) puedo reproducir y 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;
}
Producción:
...
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
¿Entonces por qué? El código de bytes es 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 {
}
}
La diferencia es: Con corchetes ( 2 * (i * i)):
- empujar pila constante
- empujar local en la pila
- empujar local en la pila
- multiplicar la parte superior de la pila
- multiplicar la parte superior de la pila
Sin corchetes ( 2 * i * i):
- empujar pila constante
- empujar local en la pila
- multiplicar la parte superior de la pila
- empujar local en la pila
- multiplicar la parte superior de la pila
Cargar todo en la pila y luego volver a trabajar es más rápido que cambiar entre colocar la pila y operar en ella.
Kasperd preguntó en un comentario de la respuesta aceptada:
Los ejemplos de Java y C utilizan nombres de registros bastante diferentes. ¿Ambos ejemplos utilizan 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
No tengo suficiente reputación para responder esto en los comentarios, pero son la misma ISA. Vale la pena señalar que la versión GCC usa lógica entera de 32 bits y la versión compilada JVM usa lógica entera de 64 bits internamente.
R8 a R15 son solo nuevos registros X86_64 . EAX a EDX son las partes inferiores de los registros de propósito general de RAX a RDX. La parte importante de la respuesta es que la versión GCC no se desenrolla. Simplemente ejecuta una ronda del bucle por bucle de código de máquina real. Mientras que la versión JVM tiene 16 rondas del bucle en un bucle físico (según la respuesta de Rustyx, no reinterpreté el ensamblaje). Esta es una de las razones por las que se utilizan más registros, ya que el cuerpo del bucle es en realidad 16 veces más largo.
Si bien no está directamente relacionado con el entorno de la pregunta, solo por curiosidad, hice la misma prueba en .NET Core 2.1, x64, modo de lanzamiento.
Aquí está el interesante resultado, que confirma fenómenos similares (al revés) que ocurren en el lado oscuro de la fuerza. 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 * (yo * yo)
- resultado: 119860736, 438 ms
- resultado: 119860736, 433 ms
- resultado: 119860736, 437 ms
- resultado: 119860736, 435 ms
- resultado: 119860736, 436 ms
- resultado: 119860736, 435 ms
- resultado: 119860736, 435 ms
- resultado: 119860736, 439 ms
- resultado: 119860736, 436 ms
- resultado: 119860736, 437 ms
2 * yo * yo
- 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
