java - Extraña pesimismo JIT de un lenguaje de bucle

cpu intel (1)

Al analizar los resultados de una pregunta reciente aquí , encontré un fenómeno bastante peculiar: aparentemente, una capa adicional de la optimización JIT de HotSpot en realidad ralentiza la ejecución en mi máquina.

Aquí está el código que he usado para la medición:

@OutputTimeUnit(TimeUnit.NANOSECONDS) @BenchmarkMode(Mode.AverageTime) @OperationsPerInvocation(Measure.ARRAY_SIZE) @Warmup(iterations = 2, time = 1) @Measurement(iterations = 5, time = 1) @State(Scope.Thread) @Threads(1) @Fork(2) public class Measure { public static final int ARRAY_SIZE = 1024; private final int[] array = new int[ARRAY_SIZE]; @Setup public void setup() { final Random random = new Random(); for (int i = 0; i < ARRAY_SIZE; ++i) { final int x = random.nextInt(); array[i] = x == 0? 1 : x; } } @GenerateMicroBenchmark public int normalIndex() { final int[] array = this.array; int result = 0; for (int i = 0; i < array.length; i++) { final int j = i & array.length-1; final int entry = array[i]; result ^= entry + j; } return result; } @GenerateMicroBenchmark public int maskedIndex() { final int[] array = this.array; int result = 0; for (int i = 0; i < array.length; i++) { final int j = i & array.length-1; final int entry = array[j]; result ^= entry + i; } return result; } @GenerateMicroBenchmark public int normalWithExitPoint() { final int[] array = this.array; int result = 0; for (int i = 0; i < array.length; i++) { final int j = i & array.length-1; final int entry = array[i]; result ^= entry + j; if (entry == 0) break; } return result; } @GenerateMicroBenchmark public int maskedWithExitPoint() { final int[] array = this.array; int result = 0; for (int i = 0; i < array.length; i++) { final int j = i & array.length-1; final int entry = array[j]; result ^= entry + i; if (entry == 0) break; } return result; } }

El código es bastante sutil, así que permítame señalar los bits importantes:

las variantes del "índice normal" usan la variable recta i para el índice de matriz. HotSpot puede determinar fácilmente el rango de i largo del bucle y eliminar la verificación de los límites de la matriz;
el índice de variantes de "índice enmascarado" por j , que en realidad es igual a i , pero ese hecho está "oculto" de HotSpot a través de la operación de enmascaramiento AND;
las variantes "con punto de salida" introducen un punto de salida de bucle explícito. La importancia de esto se explicará a continuación.

Loop desenrollado y reordenado.

Observe que los límites de verificación se calculan de dos maneras importantes:

tiene una sobrecarga de tiempo de ejecución asociada (una comparación seguida de una rama condicional);
constituye un punto de salida de bucle que puede interrumpir el bucle en cualquier paso. Esto tiene importantes consecuencias para las optimizaciones JIT aplicables.

Al inspeccionar el código de máquina emitido para los cuatro métodos anteriores, he notado lo siguiente:

en todos los casos el bucle se desenrolla;
en el caso de normalIndex , que se distingue como el único que no tiene puntos de salida de bucle prematuros, las operaciones de todos los pasos desenrrollados se reordenan de modo que primero se realicen todas las recuperaciones de la matriz, seguidas de XOR - ingrese todos los valores en el acumulador .

Resultados de medición esperados y reales

Ahora podemos clasificar los cuatro métodos de acuerdo con las características discutidas:

normalIndex no tiene controles de límites ni puntos de salida de bucle;
normalWithExitPoint no tiene comprobaciones de límites y 1 punto de salida;
maskedIndex tiene 1 comprobación de límites y 1 punto de salida;
maskedWithExitPoint tiene verificación de 1 límites y 2 puntos de salida.

La expectativa obvia es que la lista anterior debe presentar los métodos en orden descendente de desempeño; Sin embargo, estos son mis resultados reales:

Benchmark Mode Samples Mean Mean error Units normalIndex avgt 20 0.946 0.010 ns/op normalWithExitPoint avgt 20 0.807 0.010 ns/op maskedIndex avgt 20 0.803 0.007 ns/op maskedWithExitPoint avgt 20 1.007 0.009 ns/op

normalWithExitPoint y maskedIndex son errores de medición de módulo idénticos, aunque solo este último tiene la verificación de límites;
la mayor anomalía se observa en el normalIndex que debería haber sido el más rápido, pero es significativamente más lento que el valor normalWithExitPoint de normalWithExitPoint , idéntico a él en todos los aspectos, salvo por tener una línea de código más , la que introduce el punto de salida.

Como normalIndex es el único método que tiene aplicada la "optimización" de reordenación adicional, la conclusión es que esta es la causa de la desaceleración.

Estoy probando en:

Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode) (Java 7, actualización 40)
OS X versión 10.9.1
Intel Core i7 a 2,66 GHz

También he reproducido con éxito los resultados en Java 8 EA b118.

Mi pregunta:

¿Es reproducible el fenómeno anterior en otras máquinas similares? De la pregunta mencionada al principio, ya tengo una pista de que al menos algunas máquinas no la reproducen, por lo que otro resultado de la misma CPU sería muy interesante.

Actualización 1: más mediciones inspiradas en los hallazgos de maaartinus

He reunido la siguiente tabla que relaciona los tiempos de ejecución con el argumento de línea de comando -XX:LoopUnrollLimit . Aquí me enfoco solo en dos variantes, con y sin la if (entry == 0) break; línea:

LoopUnrollLimit: 14 15 18 19 22 23 60 withExitPoint: 96 95 95 79 80 80 69 1/100 ns withoutExitPoint: 94 64 64 63 64 77 75 1/100 ns

Se pueden observar los siguientes cambios repentinos:

en la transición de 14 a 15, la variante withoutExitPoint recibe una transformación LCM ¹ beneficiosa y se acelera significativamente. Debido al límite de desenrollado del bucle, todos los valores cargados se ajustan a los registros;
en 18-> 19, la variante withExitPoint recibe una aceleración, menor que la anterior;
en 22-> 23, la variante withoutExitPoint se ralentiza. En este punto, veo el desbordamiento en las ubicaciones de la pila, como se describe en la respuesta de maaartinus , comenzando a suceder.

El valor predeterminado de loopUnrollLimit para mi configuración es 60, por lo que presento sus resultados en la última columna.

¹ LCM = Movimiento de código local. Es la transformación la que hace que todo el acceso a la matriz ocurra en la parte superior, seguido del procesamiento de los valores cargados.

Actualización 2: este es realmente un problema conocido, reportado

https://bugs.openjdk.java.net/browse/JDK-7101232

Apéndice: El bucle desenrollado y reordenado de `normalIndex` en código de máquina

0x00000001044a37c0: mov ecx,eax 0x00000001044a37c2: and ecx,esi ;*iand ; - org.sample.Measure::normalIndex@20 (line 44) 0x00000001044a37c4: mov rbp,QWORD PTR [rsp+0x28] ;*iload_3 ; - org.sample.Measure::normalIndex@15 (line 44) 0x00000001044a37c9: add ecx,DWORD PTR [rbp+rsi*4+0x10] 0x00000001044a37cd: xor ecx,r8d 0x00000001044a37d0: mov DWORD PTR [rsp],ecx 0x00000001044a37d3: mov r10d,esi 0x00000001044a37d6: add r10d,0xf 0x00000001044a37da: and r10d,eax 0x00000001044a37dd: mov r8d,esi 0x00000001044a37e0: add r8d,0x7 0x00000001044a37e4: and r8d,eax 0x00000001044a37e7: mov DWORD PTR [rsp+0x4],r8d 0x00000001044a37ec: mov r11d,esi 0x00000001044a37ef: add r11d,0x6 0x00000001044a37f3: and r11d,eax 0x00000001044a37f6: mov DWORD PTR [rsp+0x8],r11d 0x00000001044a37fb: mov r8d,esi 0x00000001044a37fe: add r8d,0x5 0x00000001044a3802: and r8d,eax 0x00000001044a3805: mov DWORD PTR [rsp+0xc],r8d 0x00000001044a380a: mov r11d,esi 0x00000001044a380d: inc r11d 0x00000001044a3810: and r11d,eax 0x00000001044a3813: mov DWORD PTR [rsp+0x10],r11d 0x00000001044a3818: mov r8d,esi 0x00000001044a381b: add r8d,0x2 0x00000001044a381f: and r8d,eax 0x00000001044a3822: mov DWORD PTR [rsp+0x14],r8d 0x00000001044a3827: mov r11d,esi 0x00000001044a382a: add r11d,0x3 0x00000001044a382e: and r11d,eax 0x00000001044a3831: mov r9d,esi 0x00000001044a3834: add r9d,0x4 0x00000001044a3838: and r9d,eax 0x00000001044a383b: mov r8d,esi 0x00000001044a383e: add r8d,0x8 0x00000001044a3842: and r8d,eax 0x00000001044a3845: mov DWORD PTR [rsp+0x18],r8d 0x00000001044a384a: mov r8d,esi 0x00000001044a384d: add r8d,0x9 0x00000001044a3851: and r8d,eax 0x00000001044a3854: mov ebx,esi 0x00000001044a3856: add ebx,0xa 0x00000001044a3859: and ebx,eax 0x00000001044a385b: mov ecx,esi 0x00000001044a385d: add ecx,0xb 0x00000001044a3860: and ecx,eax 0x00000001044a3862: mov edx,esi 0x00000001044a3864: add edx,0xc 0x00000001044a3867: and edx,eax 0x00000001044a3869: mov edi,esi 0x00000001044a386b: add edi,0xd 0x00000001044a386e: and edi,eax 0x00000001044a3870: mov r13d,esi 0x00000001044a3873: add r13d,0xe 0x00000001044a3877: and r13d,eax 0x00000001044a387a: movsxd r14,esi 0x00000001044a387d: add r10d,DWORD PTR [rbp+r14*4+0x4c] 0x00000001044a3882: mov DWORD PTR [rsp+0x24],r10d 0x00000001044a3887: mov QWORD PTR [rsp+0x28],rbp 0x00000001044a388c: mov ebp,DWORD PTR [rsp+0x4] 0x00000001044a3890: mov r10,QWORD PTR [rsp+0x28] 0x00000001044a3895: add ebp,DWORD PTR [r10+r14*4+0x2c] 0x00000001044a389a: mov DWORD PTR [rsp+0x4],ebp 0x00000001044a389e: mov r10d,DWORD PTR [rsp+0x8] 0x00000001044a38a3: mov rbp,QWORD PTR [rsp+0x28] 0x00000001044a38a8: add r10d,DWORD PTR [rbp+r14*4+0x28] 0x00000001044a38ad: mov DWORD PTR [rsp+0x8],r10d 0x00000001044a38b2: mov r10d,DWORD PTR [rsp+0xc] 0x00000001044a38b7: add r10d,DWORD PTR [rbp+r14*4+0x24] 0x00000001044a38bc: mov DWORD PTR [rsp+0xc],r10d 0x00000001044a38c1: mov r10d,DWORD PTR [rsp+0x10] 0x00000001044a38c6: add r10d,DWORD PTR [rbp+r14*4+0x14] 0x00000001044a38cb: mov DWORD PTR [rsp+0x10],r10d 0x00000001044a38d0: mov r10d,DWORD PTR [rsp+0x14] 0x00000001044a38d5: add r10d,DWORD PTR [rbp+r14*4+0x18] 0x00000001044a38da: mov DWORD PTR [rsp+0x14],r10d 0x00000001044a38df: add r13d,DWORD PTR [rbp+r14*4+0x48] 0x00000001044a38e4: add r11d,DWORD PTR [rbp+r14*4+0x1c] 0x00000001044a38e9: add r9d,DWORD PTR [rbp+r14*4+0x20] 0x00000001044a38ee: mov r10d,DWORD PTR [rsp+0x18] 0x00000001044a38f3: add r10d,DWORD PTR [rbp+r14*4+0x30] 0x00000001044a38f8: mov DWORD PTR [rsp+0x18],r10d 0x00000001044a38fd: add r8d,DWORD PTR [rbp+r14*4+0x34] 0x00000001044a3902: add ebx,DWORD PTR [rbp+r14*4+0x38] 0x00000001044a3907: add ecx,DWORD PTR [rbp+r14*4+0x3c] 0x00000001044a390c: add edx,DWORD PTR [rbp+r14*4+0x40] 0x00000001044a3911: add edi,DWORD PTR [rbp+r14*4+0x44] 0x00000001044a3916: mov r10d,DWORD PTR [rsp+0x10] 0x00000001044a391b: xor r10d,DWORD PTR [rsp] 0x00000001044a391f: mov ebp,DWORD PTR [rsp+0x14] 0x00000001044a3923: xor ebp,r10d 0x00000001044a3926: xor r11d,ebp 0x00000001044a3929: xor r9d,r11d 0x00000001044a392c: xor r9d,DWORD PTR [rsp+0xc] 0x00000001044a3931: xor r9d,DWORD PTR [rsp+0x8] 0x00000001044a3936: xor r9d,DWORD PTR [rsp+0x4] 0x00000001044a393b: mov r10d,DWORD PTR [rsp+0x18] 0x00000001044a3940: xor r10d,r9d 0x00000001044a3943: xor r8d,r10d 0x00000001044a3946: xor ebx,r8d 0x00000001044a3949: xor ecx,ebx 0x00000001044a394b: xor edx,ecx 0x00000001044a394d: xor edi,edx 0x00000001044a394f: xor r13d,edi 0x00000001044a3952: mov r8d,DWORD PTR [rsp+0x24] 0x00000001044a3957: xor r8d,r13d ;*ixor ; - org.sample.Measure::normalIndex@34 (line 46) 0x00000001044a395a: add esi,0x10 ;*iinc ; - org.sample.Measure::normalIndex@36 (line 43) 0x00000001044a395d: cmp esi,DWORD PTR [rsp+0x20] 0x00000001044a3961: jl 0x00000001044a37c0 ;*if_icmpge ; - org.sample.Measure::normalIndex@12 (line 43)

La razón por la que el JITC trata de agrupar todo junto no me queda clara. AFAIK hay (¿eran?) Arquitecturas para las cuales la agrupación de dos cargas conduce a un mejor rendimiento (algunos Pentium tempranos, creo).

Como JITC conoce los puntos críticos, puede en línea mucho más agresivamente que un compilador adelantado, por lo que lo hace 16 veces en este caso. No puedo ver ninguna ventaja clara de esto aquí, excepto por hacer el bucle relativamente más barato. También dudo que haya alguna arquitectura que se aproveche al agrupar 16 cargas.

El código calcula 16 valores temporales, uno por iteración de

int j = i & array.length-1; int entry = array[i]; int tmp = entry + j; result ^= tmp;

Cada cálculo es bastante trivial, un AND, un LOAD y un ADD. Los valores deben asignarse a los registros, pero no hay suficientes. Así que los valores tienen que ser almacenados y cargados más tarde.

Esto sucede en 7 de los 16 registros y aumenta los costos significativamente.

Actualizar

No estoy muy seguro de verificar esto usando -XX:LoopUnrollLimit :

LoopUnrollLimit Benchmark Mean Mean error Units 8 ..normalIndex 0.902 0.004 ns/op 8 ..normalWithExitPoint 0.913 0.005 ns/op 8 ..maskedIndex 0.918 0.006 ns/op 8 ..maskedWithExitPoint 0.996 0.008 ns/op 16 ..normalIndex 0.769 0.003 ns/op 16 ..normalWithExitPoint 0.930 0.004 ns/op 16 ..maskedIndex 0.937 0.004 ns/op 16 ..maskedWithExitPoint 1.012 0.003 ns/op 32 ..normalIndex 0.814 0.003 ns/op 32 ..normalWithExitPoint 0.816 0.005 ns/op 32 ..maskedIndex 0.838 0.003 ns/op 32 ..maskedWithExitPoint 0.978 0.002 ns/op - ..normalIndex 0.830 0.002 ns/op - ..normalWithExitPoint 0.683 0.002 ns/op - ..maskedIndex 0.791 0.005 ns/op - ..maskedWithExitPoint 0.908 0.003 ns/op

El límite de 16 hace que el normalIndex sea la variante más rápida, lo que indica que tenía razón con la "penalización de globalización". Según Marko, el ensamblaje generado cambia con el límite de desenrollado también en otros aspectos, por lo que las cosas son más complicadas.