Estoy trabajando en algún código Java que necesita ser altamente optimizado ya que se ejecutará en funciones activas que se invocan en muchos puntos de la lógica de mi programa principal. Parte de este código implica multiplicar doublevariables por 10elevadas a s arbitrarias no negativas int exponent. Una forma rápida (editar: pero no la más rápida posible, consulte la Actualización 2 a continuación) para obtener el valor multiplicado es switchen 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 arriba indican que las case intconstantes continúan incrementándose en 1, por lo que realmente hay 19 cases en el fragmento de código anterior. Ya que no estaba seguro de si iba a necesitar realmente todas las potencias de 10, en casedeclaraciones 10a través 18, me encontré con algunos microbenchmarks que comparan el tiempo para completar 10 millones de operaciones con esta switchdeclaración frente a un switchsólo cases 0thru 9(con la exponentlimitación a 9 o menos a evite romper el recortado switch). Obtuve el resultado bastante sorprendente (¡para mí, al menos!) De que cuanto más tiempo switchcon más casedeclaraciones realmente se ejecutaba más rápido.
En una alondra, intenté agregar aún más cases que solo devolvieron valores ficticios, y descubrí que podía hacer que el interruptor se ejecutara aún más rápido con alrededor de 22-27 cases declarados (a pesar de que esos casos ficticios nunca se golpean mientras el código se está ejecutando ) (Nuevamente, lacase se agregaron s de manera contigua incrementando la caseconstante anterior en 1). Estas diferencias en el tiempo de ejecución no son muy significativas: para un azar exponententre 0y 10, la switchinstrucción ficticia completa termina 10 millones de ejecuciones en 1.49 segundos versus 1.54 segundos para las sin relleno versión, para un gran ahorro total de 5ns por ejecución. Entonces, no es el tipo de cosa que hace que obsesionarse con rellenar unswitchdeclaración que vale la pena desde el punto de vista de la optimización. Pero todavía me parece curioso y contraintuitivo que a switchno se vuelve más lento (o tal vez, en el mejor de los casos, mantiene un tiempo O (1) constante ) para ejecutarse a medida que casese agregan más s.
Estos son los resultados que obtuve al ejecutar con varios límites en el generado aleatoriamente exponent valores . No incluí los resultados hasta 1el exponentlímite, pero la forma general de la curva sigue siendo la misma, con una cresta alrededor de la marca del caso 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 ejecuté las pruebas en orden, desde la switchdeclaración 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 repositorio de github si alguien quiere intentar reproducir estos resultados.
Entonces, ¿qué está pasando aquí? ¿Algunos caprichos de mi arquitectura o construcción de micro-benchmark? O es el Java switchen realidad un poco más rápido para ejecutar en el 18que28 case rango de lo que es de 11hasta 17?
prueba de github repo "interruptor-experimento"
ACTUALIZACIÓN: Limpié bastante la biblioteca de evaluación comparativa y agregué un archivo de texto en / resultados con algo de salida en un rango más amplio de exponentvalores posibles . También he añadido una opción en el código de prueba no lanzar una Exceptionde default, pero esto no parece afectar a los resultados.
ACTUALIZACIÓN 2: Encontré una discusión bastante buena sobre este tema desde 2009 en el foro xkcd aquí: http://forums.xkcd.com/viewtopic.php?f=11&t=33524 . La discusión del OP sobre el uso Array.binarySearch()me dio la idea de una implementación simple basada en una matriz del patrón de exponenciación anterior. No hay necesidad de la búsqueda binaria ya que sé cuáles son las entradas en el array. Parece correr aproximadamente 3 veces más rápido que el uso switch, obviamente a expensas de parte del flujo de control que switchofrece. Ese código también se ha agregado al repositorio de github.
fuente
switchdeclaraciones, ya que es claramente la solución más óptima. : D (No mostrar esto a mi ventaja, por favor.)lookupswitcha atableswitch. Desmontar su código conjavaple mostraría seguro.Respuestas:
Como se señaló en la otra respuesta , dado que los valores de los casos son contiguos (en lugar de dispersos), el código de bytes generado para sus diversas pruebas utiliza una tabla de interruptores (instrucción de código de bytes
tableswitch).Sin embargo, una vez que el JIT comienza su trabajo y compila el código de bytes en el ensamblaje, la
tableswitchinstrucción no siempre da como resultado una matriz de punteros: a veces, la tabla de interruptores se transforma en lo que parece unlookupswitch(similar a una estructuraif/else if).La descomposición del ensamblaje generado por el JIT (punto de acceso JDK 1.7) muestra que usa una sucesión de if / else if cuando hay 17 casos o menos, una matriz de punteros cuando hay más de 18 (más eficiente).
La razón por la cual se usa este número mágico de 18 parece reducirse al valor predeterminado de la
MinJumpTableSizebandera JVM (alrededor de la línea 352 en el código).He planteado el problema en la lista del compilador de puntos de acceso y parece ser un legado de pruebas anteriores . Tenga en cuenta que este valor predeterminado se ha eliminado en JDK 8 después de realizar más evaluaciones comparativas .
Finalmente, cuando el método se vuelve demasiado largo (> 25 casos en mis pruebas), ya no está alineado con la configuración predeterminada de JVM, esa es la causa más probable de la caída del rendimiento en ese punto.
Con 5 casos, el código descompilado se ve así (observe las instrucciones cmp / je / jg / jmp, el ensamblaje para if / goto):
Con 18 casos, el ensamblaje se ve así (observe la matriz de punteros que se usa y suprime la necesidad de todas las comparaciones:
jmp QWORD PTR [r8+r10*1]salta directamente a la multiplicación correcta), esa es la razón probable para la mejora del rendimiento:Y finalmente, el ensamblaje con 30 casos (a continuación) se parece a 18 casos, excepto por el adicional
movapd xmm0,xmm1que aparece hacia la mitad del código, como lo detectó @cHao ; sin embargo, la razón más probable para la caída en el rendimiento es que el método también largo para estar alineado con la configuración predeterminada de JVM:fuente
Interruptor: el caso es más rápido si los valores del caso se colocan en un rango estrecho, por ejemplo.
Porque, en este caso, el compilador puede evitar realizar una comparación para cada tramo de caso en la instrucción switch. El compilador crea una tabla de salto que contiene las direcciones de las acciones que se realizarán en diferentes tramos. El valor en el que se realiza el cambio se manipula para convertirlo en un índice en
jump table. En esta implementación, el tiempo empleado en la instrucción switch es mucho menor que el tiempo empleado en una cascada equivalente de instrucciones if-else-if. Además, el tiempo empleado en la declaración de cambio es independiente del número de tramos de casos en la declaración de cambio.Como se indica en wikipedia sobre la declaración de cambio en la sección de compilación.
fuente
La respuesta está en el código de bytes:
SwitchTest10.java
Código de bytes correspondiente; solo se muestran las partes relevantes:
SwitchTest22.java:
Código de bytes correspondiente; de nuevo, solo se muestran las partes relevantes:
En el primer caso, con rangos estrechos, el código de bytes compilado utiliza a
tableswitch. En el segundo caso, el bytecode compilado utiliza alookupswitch.En
tableswitch, el valor entero en la parte superior de la pila se usa para indexar en la tabla, para encontrar el objetivo de rama / salto. Este salto / rama se realiza inmediatamente. Por lo tanto, esta es unaO(1)operación.A
lookupswitches 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. Una vez que se encuentra la clave, el objetivo de salto / rama (al que se asigna esta clave) se usa para el salto. La tabla que se usalookupswitchse ordena y se puede usar un algoritmo de búsqueda binaria para encontrar la clave correcta. El rendimiento para una búsqueda binaria esO(log n), y todo el proceso también lo esO(log n), porque el salto todavía estáO(1). Entonces, la razón por la que el rendimiento es menor en el caso de rangos dispersos es que primero se debe buscar la clave correcta porque no se puede indexar directamente en la tabla.Si hay valores dispersos y solo tenía
tableswitchque usarlos, la tabla esencialmente contendría entradas ficticias que apuntan a ladefaultopción. Por ejemplo, suponiendo que la última entradaSwitchTest10.javafue en21lugar de10, obtienes:Entonces, el compilador básicamente crea esta enorme tabla que contiene entradas ficticias entre los huecos, apuntando al objetivo de la rama de la
defaultinstrucción. Incluso si no hay undefault, contendrá entradas que apunten a la instrucción después del bloqueo del interruptor. Hice algunas pruebas básicas y descubrí que si la brecha entre el último índice y el anterior (9) es mayor que35, se usa a enlookupswitchlugar de atableswitch.El comportamiento de la
switchdeclaración se define en la Especificación de máquina virtual Java (§3.10) :fuente
lookupswitch?Como la pregunta ya está respondida (más o menos), aquí hay un consejo. Utilizar
Ese código usa significativamente menos IC (caché de instrucciones) y siempre estará en línea. La matriz estará en la caché de datos L1 si el código está activo. La tabla de búsqueda es casi siempre una victoria. (especialmente en microbenchmarks: D)
Editar: si desea que el método esté en línea caliente, considere que las rutas no rápidas
throw new ParseException()son tan cortas como mínimo o muévalas a un método estático separado (por lo tanto, haga que sean cortas como mínimo). Esa esthrow new ParseException("Unhandled power of ten " + power, 0);una idea débil porque consume una gran parte del presupuesto de línea para el código que solo se puede interpretar: la concatenación de cadenas es bastante detallada en bytecode. Más información y un caso real con ArrayListfuente