¿Por qué Java activa las entradas contiguas parece ejecutarse más rápido con casos adicionales?

Estoy trabajando en un código Java que debe ser altamente optimizado, ya que se ejecutará en funciones activas que se invocan en muchos puntos en la lógica de mi progtwig principal. Parte de este código implica multiplicar variables double por 10 elevado a exponent int no negativo arbitrario s. Una forma rápida (editar: pero no la más rápida posible, ver la Actualización 2 a continuación) para obtener el valor multiplicado es switch el exponent :

 double multiplyByPowerOfTen(final double d, final int exponent) { switch (exponent) { case 0: return d; case 1: return d*10; case 2: return d*100; // ... same pattern case 9: return d*1000000000; case 10: return d*10000000000L; // ... same pattern with long literals case 18: return d*1000000000000000000L; default: throw new ParseException("Unhandled power of ten " + power, 0); } } 

Las elipses comentadas más arriba indican que las constantes int case continúan incrementándose en 1, por lo que hay realmente 19 case en el fragmento de código anterior. Como no estaba seguro de si realmente necesitaría todos los poderes de 10 en las sentencias de case 10 a 18 , ejecuté algunas microbenchmarks comparando el tiempo para completar 10 millones de operaciones con esta instrucción de switch frente a un switch con solo case 0 a 9 ( con el exponent limitado a 9 o menos para evitar romper el switch reducido). Obtuve el resultado bastante sorprendente (¡al menos para mí!) De que el switch más largo con más declaraciones de case realidad funcionaba más rápido.

Por diversión, traté de agregar incluso más case que simplemente devolvieran valores ficticios, y encontré que podía hacer que el interruptor corriera más rápido con alrededor de 22-27 case declarados (incluso aunque esos casos falsos nunca sean golpeados mientras el código Esta corriendo). (De nuevo, los case se agregaron de forma contigua al boost la constante de case anterior en 1 ). Estas diferencias de tiempo de ejecución no son muy significativas: para un exponent aleatorio entre 0 y 10 , la instrucción de switch acolchada simulada finaliza 10 millones de ejecuciones en 1,49 segundos versus 1.54 segundos para la versión sin relleno, para un gran ahorro total de 5ns por ejecución. Por lo tanto, no es el tipo de cosa que hace que obsesionarse con rellenar una statement de switch valga la pena desde el punto de vista de la optimización. Pero todavía me resulta curioso y contradictorio que un switch no se vuelva más lento (o que, en el mejor de los casos, mantenga un tiempo O (1) constante) para ejecutarse a medida que se agregan más case .

cambiar los resultados de evaluación comparativa

Estos son los resultados que obtuve al ejecutar con varios límites en los valores de exponent generados aleatoriamente. No incluí los resultados hasta el 1 para el límite del exponent , pero la forma general de la curva sigue siendo la misma, con una cresta alrededor de la marca de la caja de 12-17 y un valle entre 18-28. Todas las pruebas se ejecutaron en JUnitBenchmarks utilizando contenedores compartidos para los valores aleatorios para garantizar entradas de prueba idénticas. También realicé las pruebas en orden, desde la statement de switch más larga hasta la más corta, y viceversa, para tratar de eliminar la posibilidad de problemas de prueba relacionados con el pedido. He puesto mi código de prueba en un repository github si alguien quiere tratar de reproducir estos resultados.

Entonces, ¿qué está pasando aquí? Algunos caprichos de mi architecture o construcción micro-benchmark? ¿O es el switch Java realmente un poco más rápido de ejecutar en el rango de 18 a 28 case que de 11 a 17 ?

github test repo “cambio-experimento”

ACTUALIZACIÓN: Limpié un poco la biblioteca de evaluación comparativa y agregué un archivo de texto en / resultados con algunos resultados en un rango más amplio de posibles valores de exponent . También agregué una opción en el código de prueba para no arrojar una Exception de manera default , pero esto no parece afectar los resultados.

ACTUALIZACIÓN 2: Encontré una discusión bastante buena sobre este tema desde el año 2009 en el foro xkcd aquí: http://forums.xkcd.com/viewtopic.php?f=11&t=33524 . La discusión del OP sobre el uso de Array.binarySearch() me dio la idea de una implementación simple basada en arreglos del patrón de exponenciación anterior. No hay necesidad de la búsqueda binaria ya que sé cuáles son las entradas en la array . Parece correr aproximadamente 3 veces más rápido que usar el switch , obviamente a expensas de parte del flujo de control que proporciona el switch . Ese código ha sido agregado al repo github también.

Como se señala en la otra respuesta , dado que los valores de los casos son contiguos (en lugar de dispersos), el bytecode generado para sus diversas pruebas utiliza una tabla de conmutadores (bytecode instruction tableswitch ).

Sin embargo, una vez que el JIT comienza su trabajo y comstack el bytecode en ensamblaje, la instrucción de cambio de tabla no siempre da como resultado una matriz de punteros: a veces la tabla de conmutación se transforma en lo que parece un lookupswitch (similar a una estructura if / else if ) .

Descomstackr el conjunto generado por el JIT (punto de conexión JDK 1.7) muestra que utiliza una sucesión de if / else si, cuando hay 17 casos o menos, una matriz de punteros cuando hay más de 18 (más eficiente).

La razón por la que se usa este número mágico de 18 parece reducirse al valor predeterminado de la bandera JVM MinJumpTableSize (alrededor de la línea 352 en el código).

He planteado el problema en la lista del comstackdor del punto de acceso y parece ser un legado de las pruebas pasadas . Tenga en cuenta que este valor predeterminado se ha eliminado en JDK 8 después de que se realizó más evaluación comparativa .

Finalmente, cuando el método se vuelve demasiado largo (> 25 casos en mis pruebas), ya no está alineado con la configuración de JVM predeterminada: esa es la causa más probable del descenso en el rendimiento en ese punto.


Con 5 casos, el código descomstackdo se ve así (observe las instrucciones cmp / je / jg / jmp, el conjunto para if / goto):

 [Verified Entry Point] # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1' # parm0: xmm0:xmm0 = double # parm1: rdx = int # [sp+0x20] (sp of caller) 0x00000000024f0160: mov DWORD PTR [rsp-0x6000],eax ; {no_reloc} 0x00000000024f0167: push rbp 0x00000000024f0168: sub rsp,0x10 ;*synchronization entry ; - javaapplication4.Test1::multiplyByPowerOfTen@-1 (line 56) 0x00000000024f016c: cmp edx,0x3 0x00000000024f016f: je 0x00000000024f01c3 0x00000000024f0171: cmp edx,0x3 0x00000000024f0174: jg 0x00000000024f01a5 0x00000000024f0176: cmp edx,0x1 0x00000000024f0179: je 0x00000000024f019b 0x00000000024f017b: cmp edx,0x1 0x00000000024f017e: jg 0x00000000024f0191 0x00000000024f0180: test edx,edx 0x00000000024f0182: je 0x00000000024f01cb 0x00000000024f0184: mov ebp,edx 0x00000000024f0186: mov edx,0x17 0x00000000024f018b: call 0x00000000024c90a0 ; OopMap{off=48} ;*new ; - javaapplication4.Test1::multiplyByPowerOfTen@72 (line 83) ; {runtime_call} 0x00000000024f0190: int3 ;*new ; - javaapplication4.Test1::multiplyByPowerOfTen@72 (line 83) 0x00000000024f0191: mulsd xmm0,QWORD PTR [rip+0xffffffffffffffa7] # 0x00000000024f0140 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@52 (line 62) ; {section_word} 0x00000000024f0199: jmp 0x00000000024f01cb 0x00000000024f019b: mulsd xmm0,QWORD PTR [rip+0xffffffffffffff8d] # 0x00000000024f0130 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@46 (line 60) ; {section_word} 0x00000000024f01a3: jmp 0x00000000024f01cb 0x00000000024f01a5: cmp edx,0x5 0x00000000024f01a8: je 0x00000000024f01b9 0x00000000024f01aa: cmp edx,0x5 0x00000000024f01ad: jg 0x00000000024f0184 ;*tableswitch ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56) 0x00000000024f01af: mulsd xmm0,QWORD PTR [rip+0xffffffffffffff81] # 0x00000000024f0138 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@64 (line 66) ; {section_word} 0x00000000024f01b7: jmp 0x00000000024f01cb 0x00000000024f01b9: mulsd xmm0,QWORD PTR [rip+0xffffffffffffff67] # 0x00000000024f0128 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@70 (line 68) ; {section_word} 0x00000000024f01c1: jmp 0x00000000024f01cb 0x00000000024f01c3: mulsd xmm0,QWORD PTR [rip+0xffffffffffffff55] # 0x00000000024f0120 ;*tableswitch ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56) ; {section_word} 0x00000000024f01cb: add rsp,0x10 0x00000000024f01cf: pop rbp 0x00000000024f01d0: test DWORD PTR [rip+0xfffffffffdf3fe2a],eax # 0x0000000000430000 ; {poll_return} 0x00000000024f01d6: ret 

Con 18 casos, el conjunto se ve así (observe el conjunto de punteros que se utiliza y suprime la necesidad de todas las comparaciones: jmp QWORD PTR [r8+r10*1] salta directamente a la multiplicación correcta): ese es el motivo probable para la mejora del rendimiento:

 [Verified Entry Point] # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1' # parm0: xmm0:xmm0 = double # parm1: rdx = int # [sp+0x20] (sp of caller) 0x000000000287fe20: mov DWORD PTR [rsp-0x6000],eax ; {no_reloc} 0x000000000287fe27: push rbp 0x000000000287fe28: sub rsp,0x10 ;*synchronization entry ; - javaapplication4.Test1::multiplyByPowerOfTen@-1 (line 56) 0x000000000287fe2c: cmp edx,0x13 0x000000000287fe2f: jae 0x000000000287fe46 0x000000000287fe31: movsxd r10,edx 0x000000000287fe34: shl r10,0x3 0x000000000287fe38: movabs r8,0x287fd70 ; {section_word} 0x000000000287fe42: jmp QWORD PTR [r8+r10*1] ;*tableswitch ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56) 0x000000000287fe46: mov ebp,edx 0x000000000287fe48: mov edx,0x31 0x000000000287fe4d: xchg ax,ax 0x000000000287fe4f: call 0x00000000028590a0 ; OopMap{off=52} ;*new ; - javaapplication4.Test1::multiplyByPowerOfTen@202 (line 96) ; {runtime_call} 0x000000000287fe54: int3 ;*new ; - javaapplication4.Test1::multiplyByPowerOfTen@202 (line 96) 0x000000000287fe55: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe8b] # 0x000000000287fce8 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@194 (line 92) ; {section_word} 0x000000000287fe5d: jmp 0x000000000287ff16 0x000000000287fe62: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe86] # 0x000000000287fcf0 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@188 (line 90) ; {section_word} 0x000000000287fe6a: jmp 0x000000000287ff16 0x000000000287fe6f: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe81] # 0x000000000287fcf8 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@182 (line 88) ; {section_word} 0x000000000287fe77: jmp 0x000000000287ff16 0x000000000287fe7c: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe7c] # 0x000000000287fd00 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@176 (line 86) ; {section_word} 0x000000000287fe84: jmp 0x000000000287ff16 0x000000000287fe89: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe77] # 0x000000000287fd08 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@170 (line 84) ; {section_word} 0x000000000287fe91: jmp 0x000000000287ff16 0x000000000287fe96: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe72] # 0x000000000287fd10 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@164 (line 82) ; {section_word} 0x000000000287fe9e: jmp 0x000000000287ff16 0x000000000287fea0: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe70] # 0x000000000287fd18 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@158 (line 80) ; {section_word} 0x000000000287fea8: jmp 0x000000000287ff16 0x000000000287feaa: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe6e] # 0x000000000287fd20 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@152 (line 78) ; {section_word} 0x000000000287feb2: jmp 0x000000000287ff16 0x000000000287feb4: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe24] # 0x000000000287fce0 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@146 (line 76) ; {section_word} 0x000000000287febc: jmp 0x000000000287ff16 0x000000000287febe: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe6a] # 0x000000000287fd30 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@140 (line 74) ; {section_word} 0x000000000287fec6: jmp 0x000000000287ff16 0x000000000287fec8: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe68] # 0x000000000287fd38 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@134 (line 72) ; {section_word} 0x000000000287fed0: jmp 0x000000000287ff16 0x000000000287fed2: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe66] # 0x000000000287fd40 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@128 (line 70) ; {section_word} 0x000000000287feda: jmp 0x000000000287ff16 0x000000000287fedc: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe64] # 0x000000000287fd48 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@122 (line 68) ; {section_word} 0x000000000287fee4: jmp 0x000000000287ff16 0x000000000287fee6: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe62] # 0x000000000287fd50 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@116 (line 66) ; {section_word} 0x000000000287feee: jmp 0x000000000287ff16 0x000000000287fef0: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe60] # 0x000000000287fd58 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@110 (line 64) ; {section_word} 0x000000000287fef8: jmp 0x000000000287ff16 0x000000000287fefa: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe5e] # 0x000000000287fd60 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@104 (line 62) ; {section_word} 0x000000000287ff02: jmp 0x000000000287ff16 0x000000000287ff04: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe5c] # 0x000000000287fd68 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@98 (line 60) ; {section_word} 0x000000000287ff0c: jmp 0x000000000287ff16 0x000000000287ff0e: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe12] # 0x000000000287fd28 ;*tableswitch ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56) ; {section_word} 0x000000000287ff16: add rsp,0x10 0x000000000287ff1a: pop rbp 0x000000000287ff1b: test DWORD PTR [rip+0xfffffffffd9b00df],eax # 0x0000000000230000 ; {poll_return} 0x000000000287ff21: ret 

Y finalmente el conjunto con 30 cajas (abajo) se ve similar a 18 casos, excepto el movapd xmm0,xmm1 que aparece hacia la mitad del código, como lo vio @cHao , sin embargo, la razón más probable para la caída en el rendimiento es que el método es demasiado largo para ser incluido con la configuración de JVM predeterminada:

 [Verified Entry Point] # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1' # parm0: xmm0:xmm0 = double # parm1: rdx = int # [sp+0x20] (sp of caller) 0x0000000002524560: mov DWORD PTR [rsp-0x6000],eax ; {no_reloc} 0x0000000002524567: push rbp 0x0000000002524568: sub rsp,0x10 ;*synchronization entry ; - javaapplication4.Test1::multiplyByPowerOfTen@-1 (line 56) 0x000000000252456c: movapd xmm1,xmm0 0x0000000002524570: cmp edx,0x1f 0x0000000002524573: jae 0x0000000002524592 ;*tableswitch ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56) 0x0000000002524575: movsxd r10,edx 0x0000000002524578: shl r10,0x3 0x000000000252457c: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe3c] # 0x00000000025243c0 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@364 (line 118) ; {section_word} 0x0000000002524584: movabs r8,0x2524450 ; {section_word} 0x000000000252458e: jmp QWORD PTR [r8+r10*1] ;*tableswitch ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56) 0x0000000002524592: mov ebp,edx 0x0000000002524594: mov edx,0x31 0x0000000002524599: xchg ax,ax 0x000000000252459b: call 0x00000000024f90a0 ; OopMap{off=64} ;*new ; - javaapplication4.Test1::multiplyByPowerOfTen@370 (line 120) ; {runtime_call} 0x00000000025245a0: int3 ;*new ; - javaapplication4.Test1::multiplyByPowerOfTen@370 (line 120) 0x00000000025245a1: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe27] # 0x00000000025243d0 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@358 (line 116) ; {section_word} 0x00000000025245a9: jmp 0x0000000002524744 0x00000000025245ae: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe22] # 0x00000000025243d8 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@348 (line 114) ; {section_word} 0x00000000025245b6: jmp 0x0000000002524744 0x00000000025245bb: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe1d] # 0x00000000025243e0 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@338 (line 112) ; {section_word} 0x00000000025245c3: jmp 0x0000000002524744 0x00000000025245c8: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe18] # 0x00000000025243e8 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@328 (line 110) ; {section_word} 0x00000000025245d0: jmp 0x0000000002524744 0x00000000025245d5: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe13] # 0x00000000025243f0 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@318 (line 108) ; {section_word} 0x00000000025245dd: jmp 0x0000000002524744 0x00000000025245e2: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe0e] # 0x00000000025243f8 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@308 (line 106) ; {section_word} 0x00000000025245ea: jmp 0x0000000002524744 0x00000000025245ef: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe09] # 0x0000000002524400 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@298 (line 104) ; {section_word} 0x00000000025245f7: jmp 0x0000000002524744 0x00000000025245fc: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe04] # 0x0000000002524408 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@288 (line 102) ; {section_word} 0x0000000002524604: jmp 0x0000000002524744 0x0000000002524609: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffdff] # 0x0000000002524410 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@278 (line 100) ; {section_word} 0x0000000002524611: jmp 0x0000000002524744 0x0000000002524616: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffdfa] # 0x0000000002524418 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@268 (line 98) ; {section_word} 0x000000000252461e: jmp 0x0000000002524744 0x0000000002524623: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffd9d] # 0x00000000025243c8 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@258 (line 96) ; {section_word} 0x000000000252462b: jmp 0x0000000002524744 0x0000000002524630: movapd xmm0,xmm1 0x0000000002524634: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe0c] # 0x0000000002524448 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@242 (line 92) ; {section_word} 0x000000000252463c: jmp 0x0000000002524744 0x0000000002524641: movapd xmm0,xmm1 0x0000000002524645: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffddb] # 0x0000000002524428 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@236 (line 90) ; {section_word} 0x000000000252464d: jmp 0x0000000002524744 0x0000000002524652: movapd xmm0,xmm1 0x0000000002524656: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffdd2] # 0x0000000002524430 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@230 (line 88) ; {section_word} 0x000000000252465e: jmp 0x0000000002524744 0x0000000002524663: movapd xmm0,xmm1 0x0000000002524667: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffdc9] # 0x0000000002524438 ;*dmul ; - javaapplication4.Test1::multiplyByPowerOfTen@224 (line 86) ; {section_word} [etc.] 0x0000000002524744: add rsp,0x10 0x0000000002524748: pop rbp 0x0000000002524749: test DWORD PTR [rip+0xfffffffffde1b8b1],eax # 0x0000000000340000 ; {poll_return} 0x000000000252474f: ret 

Switch – case es más rápido si los valores de la caja se colocan en un rango estrecho, por ejemplo.

 case 1: case 2: case 3: .. .. case n: 

Porque, en este caso, el comstackdor puede evitar realizar una comparación para cada tramo de caso en la instrucción switch. El comstackdor crea una tabla de salto que contiene direcciones de las acciones que se tomarán en diferentes patas. El valor en el que se realiza el cambio se manipula para convertirlo en un índice en la jump table . En esta implementación, el tiempo empleado en la instrucción switch es mucho menor que el tiempo empleado en una cascada de declaraciones if-else-if equivalente. Además, el tiempo tomado en la statement de cambio es independiente del número de patas de caso en la instrucción de cambio.

Como se indica en la wikipedia sobre la statement de cambio en la sección Comstackción.

Si el rango de valores de entrada es identificable como “pequeño” y tiene pocos vacíos, algunos comstackdores que incorporan un optimizador pueden implementar realmente la instrucción de conmutación como una tabla de ramificación o una matriz de punteros de función indexados en lugar de una larga serie de instrucciones condicionales. Esto permite que la instrucción switch determine instantáneamente qué twig ejecutar sin tener que pasar por una lista de comparaciones.

La respuesta está en el bytecode:

SwitchTest10.java

 public class SwitchTest10 { public static void main(String[] args) { int n = 0; switcher(n); } public static void switcher(int n) { switch(n) { case 0: System.out.println(0); break; case 1: System.out.println(1); break; case 2: System.out.println(2); break; case 3: System.out.println(3); break; case 4: System.out.println(4); break; case 5: System.out.println(5); break; case 6: System.out.println(6); break; case 7: System.out.println(7); break; case 8: System.out.println(8); break; case 9: System.out.println(9); break; case 10: System.out.println(10); break; default: System.out.println("test"); } } } 

Código de bytes correspondiente; solo se muestran las partes relevantes:

 public static void switcher(int); Code: 0: iload_0 1: tableswitch{ //0 to 10 0: 60; 1: 70; 2: 80; 3: 90; 4: 100; 5: 110; 6: 120; 7: 131; 8: 142; 9: 153; 10: 164; default: 175 } 

SwitchTest22.java:

 public class SwitchTest22 { public static void main(String[] args) { int n = 0; switcher(n); } public static void switcher(int n) { switch(n) { case 0: System.out.println(0); break; case 1: System.out.println(1); break; case 2: System.out.println(2); break; case 3: System.out.println(3); break; case 4: System.out.println(4); break; case 5: System.out.println(5); break; case 6: System.out.println(6); break; case 7: System.out.println(7); break; case 8: System.out.println(8); break; case 9: System.out.println(9); break; case 100: System.out.println(10); break; case 110: System.out.println(10); break; case 120: System.out.println(10); break; case 130: System.out.println(10); break; case 140: System.out.println(10); break; case 150: System.out.println(10); break; case 160: System.out.println(10); break; case 170: System.out.println(10); break; case 180: System.out.println(10); break; case 190: System.out.println(10); break; case 200: System.out.println(10); break; case 210: System.out.println(10); break; case 220: System.out.println(10); break; default: System.out.println("test"); } } } 

Código de bytes correspondiente; nuevamente, solo se muestran las partes relevantes:

 public static void switcher(int); Code: 0: iload_0 1: lookupswitch{ //23 0: 196; 1: 206; 2: 216; 3: 226; 4: 236; 5: 246; 6: 256; 7: 267; 8: 278; 9: 289; 100: 300; 110: 311; 120: 322; 130: 333; 140: 344; 150: 355; 160: 366; 170: 377; 180: 388; 190: 399; 200: 410; 210: 421; 220: 432; default: 443 } 

En el primer caso, con rangos estrechos, el bytecode comstackdo utiliza un tableswitch . En el segundo caso, el bytecode comstackdo utiliza un lookupswitch .

En el cambio de tableswitch , el valor entero en la parte superior de la stack se usa para indexar en la tabla, para encontrar el objective de salto / twig. Este salto / twig se realiza inmediatamente. Por lo tanto, esta es una operación O(1) .

Un lookupswitch es más complicado. En este caso, el valor entero debe compararse con todas las claves de la tabla hasta que se encuentre la clave correcta. Después de encontrar la clave, el objective de sucursal / salto (al que se asigna esta clave) se usa para el salto. La tabla que se utiliza en el lookupswitch de lookupswitch se ordena y se puede usar un algoritmo de búsqueda binaria para encontrar la clave correcta. El rendimiento para una búsqueda binaria es O(log n) , y todo el proceso también es O(log n) , porque el salto sigue siendo O(1) . Por lo tanto, la razón por la cual el rendimiento es más bajo en el caso de rangos dispersos es que primero se debe buscar la clave correcta porque no se puede indexar en la tabla directamente.

Si hay valores escasos y solo tiene un tableswitch de tabla para usar, la tabla esencialmente contendría entradas ficticias que apuntan a la opción default . Por ejemplo, suponiendo que la última entrada en SwitchTest10.java fuera 21 lugar de 10 , obtiene:

 public static void switcher(int); Code:  0: iload_0  1: tableswitch{ //0 to 21 0: 104; 1: 114; 2: 124; 3: 134; 4: 144; 5: 154; 6: 164; 7: 175; 8: 186; 9: 197; 10: 219; 11: 219; 12: 219; 13: 219; 14: 219; 15: 219; 16: 219; 17: 219; 18: 219; 19: 219; 20: 219; 21: 208; default: 219 } 

Así que el comstackdor básicamente crea esta gran tabla que contiene entradas ficticias entre las brechas, apuntando al destino de la twig de la instrucción default . Incluso si no hay un default , contendrá las entradas que apuntan a la instrucción después del bloque de cambio. Hice algunas pruebas básicas, y encontré que si la brecha entre el último índice y el anterior ( 9 ) es mayor que 35 , usa un lookupswitch de lookupswitch lugar de un tableswitch de tableswitch .

El comportamiento de la instrucción switch se define en la Especificación de máquina virtual de Java (§3.10) :

Cuando los casos del cambio son escasos, la representación de la tabla de la instrucción de cambio de tabla se vuelve ineficiente en términos de espacio. La instrucción lookupswitch se puede usar en su lugar. La instrucción lookupswitch empareja claves int (los valores de las tags de casos) con compensaciones de objectives en una tabla. Cuando se ejecuta una instrucción lookupswitch, el valor de la expresión del interruptor se compara con las claves de la tabla. Si una de las claves coincide con el valor de la expresión, la ejecución continúa en el desplazamiento de destino asociado. Si ninguna clave coincide, la ejecución continúa en el destino predeterminado. […]

Dado que la pregunta ya está respondida (más o menos), aquí hay un consejo. Utilizar

 private static final double[] mul={1d, 10d...}; static double multiplyByPowerOfTen(final double d, final int exponent) { if (exponent<0 || exponent>=mul.length) throw new ParseException();//or just leave the IOOBE be return mul[exponent]*d; } 

Ese código usa significativamente menos IC (caché de instrucciones) y siempre estará en línea. La matriz estará en la memoria caché de datos L1 si el código está activo. La tabla de búsqueda es casi siempre una ganancia. (especialmente en microbenchmarks: D)

Editar: si desea que el método esté alineado en caliente, considere que las rutas no rápidas como throw new ParseException() sean tan cortas como mínimas o throw new ParseException() a un método estático separado (de ahí que sean cortas como mínimo). Eso es throw new ParseException("Unhandled power of ten " + power, 0); es una idea débil porque consume una gran parte del presupuesto inicial para el código que se puede interpretar: la concatenación de cadenas es bastante detallada en bytecode. Más información y un caso real con ArrayList