java - respuestas - ¿Por qué este bucle interno es 4X más rápido que la primera iteración a través del bucle externo?
programa de preguntas y respuestas en java (1)
Estaba intentando reproducir algunos de los efectos de caché del procesador descritos here . Entiendo que Java es un entorno administrado, y estos ejemplos no se traducirán exactamente, pero me encontré con un caso extraño, que he tratado de destilar a un ejemplo simple que ilustra el efecto:
public static void main(String[] args) {
final int runs = 10;
final int steps = 1024 * 1024 * 1024;
for (int run = 0; run < runs; run++) {
final int[] a = new int[1];
long start = System.nanoTime();
for (int i = 0; i < steps; i++) {
a[0]++;
}
long stop = System.nanoTime();
long time = TimeUnit.MILLISECONDS.convert(stop - start, TimeUnit.NANOSECONDS);
System.out.printf("Time for loop# %2d: %5d ms/n", run, time);
}
}
Salida:
Time for loop# 0: 24 ms
Time for loop# 1: 106 ms
Time for loop# 2: 104 ms
Time for loop# 3: 103 ms
Time for loop# 4: 102 ms
Time for loop# 5: 103 ms
Time for loop# 6: 104 ms
Time for loop# 7: 102 ms
Time for loop# 8: 105 ms
Time for loop# 9: 102 ms
La primera iteración del bucle interno es aproximadamente 4 veces más rápida que las iteraciones posteriores. Esto es lo contrario de lo que normalmente esperaría, ya que generalmente el rendimiento aumenta a medida que el JIT se activa.
Por supuesto, uno podría hacer varios bucles de calentamiento en cualquier micro-punto de referencia serio, pero tengo curiosidad por saber qué podría estar causando este comportamiento, especialmente porque si sabemos que el bucle se puede realizar en 24 ms, no es muy satisfactorio. El tiempo de estado estable es superior a 100 ms.
Para referencia el JDK que estoy usando (en linux):
openjdk version "1.8.0_40"
OpenJDK Runtime Environment (build 1.8.0_40-b20)
OpenJDK 64-Bit Server VM (build 25.40-b23, mixed mode)
ACTUALIZAR:
Aquí hay algo de información actualizada, basada en algunos de los comentarios y algunos experimentos:
1) mover el System.out I / O fuera del bucle (almacenando la temporización en una matriz de tamaño ''ejecuciones'') no hace una diferencia significativa en el tiempo.
2) la salida que se muestra arriba es cuando ejecuto desde Eclipse. Cuando compilo y ejecuto desde la línea de comandos (con el mismo JDK / JVM) obtengo resultados más modestos, pero aún significativos (2x en lugar de 4x más rápido). Esto parece interesante, ya que usaully correr en eclipse hará que las cosas sean más lentas, en todo caso.
3) moviendo hacia arriba, fuera del bucle, para que se reutilice cada iteración no tiene efecto.
4) si int[] a se cambia a long[] a , la primera iteración se ejecuta incluso más rápido (alrededor del 20%), mientras que las otras iteraciones siguen siendo de la misma velocidad (más lenta).
ACTUALIZACIÓN 2:
Creo que la respuesta de apangin lo explica. Intenté esto con la JVM 1.9 de Sun y va desde:
openjdk version "1.8.0_40"
OpenJDK Runtime Environment (build 1.8.0_40-b20)
OpenJDK 64-Bit Server VM (build 25.40-b23, mixed mode)
Time for loop# 0: 48 ms
Time for loop# 1: 116 ms
Time for loop# 2: 112 ms
Time for loop# 3: 113 ms
Time for loop# 4: 112 ms
Time for loop# 5: 112 ms
Time for loop# 6: 111 ms
Time for loop# 7: 111 ms
Time for loop# 8: 113 ms
Time for loop# 9: 113 ms
a:
java version "1.9.0-ea"
Java(TM) SE Runtime Environment (build 1.9.0-ea-b73)
Java HotSpot(TM) 64-Bit Server VM (build 1.9.0-ea-b73, mixed mode)
Time for loop# 0: 48 ms
Time for loop# 1: 26 ms
Time for loop# 2: 22 ms
Time for loop# 3: 22 ms
Time for loop# 4: 22 ms
Time for loop# 5: 22 ms
Time for loop# 6: 22 ms
Time for loop# 7: 22 ms
Time for loop# 8: 22 ms
Time for loop# 9: 23 ms
Esa es toda la mejora!
Esta es una compilación subóptima de un método.
El compilador JIT se basa en estadísticas de tiempo de ejecución recopiladas durante la interpretación. Cuando se compila el método main por primera vez, el bucle externo aún no ha completado su primera iteración => las estadísticas de tiempo de ejecución indican que el código después del bucle interno nunca se ejecuta, por lo que JIT nunca se molesta en compilarlo. Más bien genera una trampa poco común.
Cuando el bucle interno termina por primera vez, se golpea la trampa poco común y se desoptimiza el método.
En la segunda iteración del bucle externo, el método main se vuelve a compilar con el nuevo conocimiento. Ahora JIT tiene más estadísticas y más contexto para compilar. Por alguna razón, ahora no almacena en caché el valor a[0] en el registro (probablemente porque el contexto más amplio engaña a JIT). Por lo tanto, genera instrucciones addl para actualizar la matriz en la memoria, que es efectivamente una combinación de carga y almacenamiento de memoria.
Por el contrario, durante la primera compilación JIT almacena en caché el valor de a[0] en el registro, solo hay instrucciones de mov para almacenar un valor en la memoria (sin carga).
Bucle rápido (primera iteración):
0x00000000029fc562: mov %ecx,0x10(%r14) <<< array store
0x00000000029fc566: mov %r11d,%edi
0x00000000029fc569: mov %r9d,%ecx
0x00000000029fc56c: add %edi,%ecx
0x00000000029fc56e: mov %ecx,%r11d
0x00000000029fc571: add $0x10,%r11d <<< increment in register
0x00000000029fc575: mov %r11d,0x10(%r14) <<< array store
0x00000000029fc579: add $0x11,%ecx
0x00000000029fc57c: mov %edi,%r11d
0x00000000029fc57f: add $0x10,%r11d
0x00000000029fc583: cmp $0x3ffffff2,%r11d
0x00000000029fc58a: jl 0x00000000029fc562
Bucle lento (después de la recompilación):
0x00000000029fa1b0: addl $0x10,0x10(%r14) <<< increment in memory
0x00000000029fa1b5: add $0x10,%r13d
0x00000000029fa1b9: cmp $0x3ffffff1,%r13d
0x00000000029fa1c0: jl 0x00000000029fa1b0
Sin embargo, este problema parece haberse solucionado en JDK 9. He comprobado esta prueba con una versión reciente de acceso temprano de JDK 9 y he comprobado que funciona como se esperaba:
Time for loop# 0: 104 ms
Time for loop# 1: 101 ms
Time for loop# 2: 91 ms
Time for loop# 3: 63 ms
Time for loop# 4: 60 ms
Time for loop# 5: 60 ms
Time for loop# 6: 59 ms
Time for loop# 7: 55 ms
Time for loop# 8: 57 ms
Time for loop# 9: 59 ms