Diferencia entre el interruptor empaquetado y el interruptor disperso Dalvik Opcode

Question

Quiero saber la diferencia entre el interruptor empaquetado y los códigos de operación de interruptor disperso en Dalvik. Por favor, si puede proporcionar ejemplos. La explicación proporcionada por Google no está clara para mí.

pollito interruptor escaso

Gracias.

Answer 1

Suena como si packed-switch es equivalente a Java's tableswitch, y sparse-switch a lookupswitch.

A packed-switch Utiliza una mesa de salto simple, indexada por el formulario low + n, dónde low es el valor de prueba más bajo entre el case etiquetas y n es la entrada al switch. Los valores en cada índice representan las compensaciones de Bytecode para cada case. Encontrar la dirección de salto correcta es una operación de tiempo constante.

A sparse-switch Utiliza una lista ordenada de pares de valor clave, donde cada clave es un valor de prueba de un case etiqueta, y los valores son saltos de salto. Encontrar el objetivo de salto correcto para un lookupswitch Requiere una búsqueda binaria en la clave, por lo que es una operación de tiempo logarítmico.

El compilador elegirá cuál usar. Si las teclas tienden a agruparse o lleno estrechamente juntos, luego un packed-switch (o, en términos de Java, un tableswitch) se puede emitir de manera eficiente. Pero si las teclas son escaso, y el rango de valores (high - low + 1) es grande, entonces el uso de una tabla de salto requeriría un gran bloque de bytecode, ya que todos los valores en ese rango deben existir en la tabla de salto, independientemente de si existe un correspondiente case etiqueta. En estos escenarios, el compilador emitirá un sparse-switch (lookupswitch).

Curiosamente, los ingenieros de Dalvik eligieron nombrar estos códigos de operación de una manera que describe las distribuciones clave para las cuales deben usarse, mientras que los ingenieros de Java eligieron nombres que describen las estructuras de datos conceptuales que los operandos de bytecode se parecen.

Veamos algunos ejemplos. Considere el siguiente código Java, que producirá un tableswitch (y, cuando se convierte a Dalvik, un packed-switch):

static String packedSwitch(final int n) {
    switch (n) {
        case 5:
            return "Five";
        case 3:
            return "Three";
        case 1:
            return "One";
        default:
            return "Other";
    }
}

Conceptualmente, la carga útil del packed-switch OpCode se vería algo así:

Como puede ver, es bastante compacto. Tres de las cinco ranuras apuntan a case objetivos, con los dos restantes saltando al default objetivo. Pero, ¿qué pasaría si nuestros valores de prueba estuvieran más distribuidos?

static String sparseSwitch(final int n) {
    switch (n) {
        case 500:
            return "Five Hundred";
        case 300:
            return "Three Hundred";
        case 100:
            return "One Hundred";
        default:
            return "Other";
    }
}

Si el compilador intentó emitir esto como un packed-switch, la carga útil se vería algo así:

Observe cómo solo tres de unos pocos cientos de ranuras apuntan realmente case Etiquetas del código original. El resto está allí simplemente para llenar la mesa de salto. No es muy eficiente en el espacio, ¿verdad? Por eso el compilador emitiría un sparse-switch, que tiene una huella de código de byto mucho más compacta para este ejemplo en particular:

Ahora, eso es mucho más razonable, ¿no te parece? Sin embargo, la desventaja es que, en lugar de saber exactamente a qué índice saltar en función de la entrada, tenemos que realizar una búsqueda binaria en la tabla hasta que encontremos un valor de prueba coincidente. Cuanto mayor sea el interruptor, más significativo es el impacto en el rendimiento, aunque el efecto tiene una curva logarítmica.