java bytecode jasmin

java - jasmin sourceforge



¿Diferencia entre LookupSwitch y TableSwitch de JVM? (4)

La diferencia es que un interruptor de búsqueda usa una tabla con claves y etiquetas , pero un conmutador de tablas usa una tabla con etiquetas solamente .

Cuando se realiza un conmutador de tabla , el valor int en la parte superior de la pila se usa directamente como un índice en la tabla para capturar el destino de salto y realizar el salto inmediatamente. Todo el proceso de búsqueda + salto es una operación O (1) , lo que significa que está ardiendo rápidamente.

Cuando se realiza un interruptor de búsqueda , el valor int en la parte superior de la pila se compara con las claves de la tabla hasta que se encuentra una coincidencia y luego se usa el destino de salto junto a esta clave para realizar el salto. Dado que una tabla de interruptores de búsqueda siempre debe estar ordenada de modo que keyX <keyY para cada X <Y, todo el proceso de búsqueda + salto sea una operación O (log n) ya que se buscará la clave utilizando un algoritmo de búsqueda binario (no es necesario comparar el valor int contra todas las claves posibles para encontrar una coincidencia o para determinar que ninguna de las claves coincide. O (log n) es algo más lento que O (1), sin embargo, todavía está bien ya que muchos algoritmos bien conocidos son O (log n) y, por lo general, se consideran rápidos; incluso O (n) u O (n * log n) todavía se considera un algoritmo bastante bueno (los algoritmos lentos / malos tienen O (n ^ 2), O (n ^ 3), o incluso peor).

La decisión sobre qué instrucción usar es hecha por el compilador basándose en el hecho de lo compacta que es la instrucción switch, por ejemplo

switch (inputValue) { case 1: // ... case 2: // ... case 3: // ... default: // ... }

El interruptor de arriba es perfectamente compacto, no tiene "agujeros" numéricos. El compilador creará un tablewitch como este:

tableswitch 1 3 OneLabel TwoLabel ThreeLabel default: DefaultLabel

El pseudo código de la página de Jasmin explica esto bastante bien:

int val = pop(); // pop an int from the stack if (val < low || val > high) { // if its less than <low> or greater than <high>, pc += default; // branch to default } else { // otherwise pc += table[val - low]; // branch to entry in table }

Este código es bastante claro acerca de cómo funciona un tablewitch de este tipo. val es inputValue , low sería 1 (el valor de caso más bajo en el switch) y high sería 3 (el valor de caso más alto en el switch).

Incluso con algunos orificios, un interruptor puede ser compacto, por ejemplo

switch (inputValue) { case 1: // ... case 3: // ... case 4: // ... case 5: // ... default: // ... }

El interruptor de arriba es "casi compacto", solo tiene un agujero. Un compilador podría generar la siguiente instrucción:

tableswitch 1 6 OneLabel FakeTwoLabel ThreeLabel FourLabel FiveLabel default: DefaultLabel ; <...code left out...> FakeTwoLabel: DefaultLabel: ; default code

Como puede ver, el compilador tiene que agregar un caso falso para 2 , FakeTwoLabel . Dado que 2 no es un valor real del conmutador, FakeTwoLabel es de hecho una etiqueta que cambia el flujo de código exactamente donde se encuentra el caso predeterminado, ya que un valor de 2 en realidad debería ejecutar el caso predeterminado.

Por lo tanto, un conmutador no tiene que ser perfectamente compacto para que el compilador cree un conmutador de tablas, pero al menos debería ser bastante compacto. Ahora considere el siguiente interruptor:

switch (inputValue) { case 1: // ... case 10: // ... case 100: // ... case 1000: // ... default: // ... }

Este interruptor no es ni mucho menos compacto, tiene más de cien veces más agujeros que valores . Uno llamaría a esto un interruptor de repuesto. El compilador tendría que generar casi mil casos falsos para expresar este interruptor como un conmutador de tablas. El resultado sería una gran mesa, que aumentaría dramáticamente el tamaño del archivo de clase. Esto no es práctico. En su lugar, generará un interruptor de búsqueda:

lookupswitch 1 : Label1 10 : Label10 100 : Label100 1000 : Label1000 default : DefaultLabel

Esta tabla tiene solo 5 entradas, en lugar de más de mil. La tabla tiene 4 valores reales, O (registro 4) es 2 (el registro se encuentra aquí en la base de 2 BTW, no en la base de 10, ya que la computadora opera con números binarios). Eso significa que la VM necesita a lo sumo dos comparaciones para encontrar la etiqueta para el inputValue o para llegar a la conclusión de que el valor no está en la tabla y, por lo tanto, el valor predeterminado debe ejecutarse. Incluso si la tabla tuviera 100 entradas, la VM necesitaría un máximo de 7 comparaciones para encontrar la etiqueta correcta o decidir saltar a la etiqueta predeterminada (y 7 comparaciones es mucho menos que 100 comparaciones, ¿no cree?).

Así que no tiene sentido que estas dos instrucciones sean intercambiables o que la razón de dos instrucciones tenga razones históricas. Hay dos instrucciones para dos tipos diferentes de situaciones, una para interruptores con valores compactos (para velocidad máxima) y otra para interruptores con valores de repuesto (no velocidad máxima, pero aún así es una buena velocidad y una representación de tabla muy compacta, independientemente de todos los orificios numéricos).

Tengo algunas dificultades para comprender LookUpSwitch y TableSwitch en el código de bytes de Java.

Si entiendo bien, ¿tanto LookUpSwitch como TableSwitch se corresponden con la instrucción switch de la fuente Java? ¿Por qué una declaración JAVA genera 2 bytecodes diferentes?

Jasmin documentación de cada uno:

Sospecho que es principalmente histórico, debido a algún enlace específico del código de bytes de Java para subrayar el código de la máquina (por ejemplo, la propia CPU de Sun).

El conmutador de tabla es esencialmente un salto computado, donde el destino se toma de una tabla de búsqueda. Por el contrario, el interruptor de búsqueda requiere la comparación de cada valor, básicamente una iteración a través de elementos de la tabla hasta que se encuentre un valor coincidente.

Obviamente, estos códigos de operación son intercambiables, pero en función de los valores, uno u otro podrían ser más rápidos o más compactos (por ejemplo, comparar un conjunto de claves con grandes espacios entre ellas y un conjunto secuencial de claves).

Especificación de la máquina virtual de Java describe la diferencia. "La instrucción tableswitch se usa cuando los casos del switch se pueden representar eficientemente como índices en una tabla de compensaciones de destino". La especificación describe los más detalles.

¿Cuándo exactamente javac 1.8.0_45 compila el cambio a cualquiera de los dos?

Para decidir cuándo usar cuál, podría usar el algoritmo de elección javac como base.

Sabemos que la fuente de javac está en el repositorio de langtools .

Entonces nosotros grep:

hg grep -i tableswitch

y el primer resultado es langtools/src/share/classes/com/sun/tools/javac/jvm/Gen.java :

// Determine whether to issue a tableswitch or a lookupswitch // instruction. long table_space_cost = 4 + ((long) hi - lo + 1); // words long table_time_cost = 3; // comparisons long lookup_space_cost = 3 + 2 * (long) nlabels; long lookup_time_cost = nlabels; int opcode = nlabels > 0 && table_space_cost + 3 * table_time_cost <= lookup_space_cost + 3 * lookup_time_cost ? tableswitch : lookupswitch;

Dónde:

  • hi : valor máximo del caso
  • lo : valor de caso mínimo

Así que concluimos que toma en consideración tanto la complejidad del tiempo como la del espacio, con un peso de 3 para la complejidad del tiempo.

TODO No entiendo por qué lookup_time_cost = nlabels y no log(nlabels) , ya que un tableswitch se puede hacer en O (log (n)) con búsqueda binaria.

Bonificación: las implementaciones de C ++ también hacen una elección análoga entre una tabla de salto O (1) y una búsqueda binaria O (larga (n)): ventaja de cambiar la instrucción if-else