Diferença entre o interruptor embalado e o interruptor esparso Dalvik Opcode

Question

Quero saber a diferença entre o comutador embalado e os códigos de chave esparsa no Dalvik. Por favor, se você pode fornecer exemplos. A explicação fornecida pelo Google não é clara para mim.

comutado embalado interruptor esparso

Obrigado.

Answer 1

Parece como se packed-switch é equivalente ao de Java tableswitch, e sparse-switch para lookupswitch.

UMA packed-switch usa uma tabela de salto simples, indexada pelo formulário low + n, Onde low é o menor valor de teste entre os case rótulos e n é a entrada para o switch. Os valores em cada índice representam as compensações de bytecode para cada case. Encontrar o endereço de salto correto é uma operação em tempo constante.

UMA sparse-switch usa uma lista classificada de pares de valor-chave, onde cada chave é um valor de teste de um case Etiqueta e os valores são compensações de salto. Encontrando o alvo de salto correto para um lookupswitch Requer uma pesquisa binária na chave, por isso é uma operação de tempo logarítmico.

O compilador escolherá qual usar. Se as chaves tendem a ser agrupadas ou embalado juntos, então um packed-switch (ou, em termos java, um tableswitch) pode ser emitido com eficiência. Mas se as chaves são escasso, e a gama de valores (high - low + 1) é grande, depois usar uma tabela de salto exigiria um grande bloco de bytecode, pois todos os valores nesse intervalo devem existir na tabela de salto, independentemente de haver um correspondente case etiqueta. Nesses cenários, o compilador emitirá um sparse-switch (lookupswitch).

Curiosamente, os engenheiros de Dalvik optaram por nomear esses códigos de operações de uma maneira que descreva as principais distribuições para as quais devem ser usadas, enquanto os engenheiros da Java escolherem nomes que descrevem as estruturas de dados conceituais que os operando de bytecode se assemelham.

Vejamos alguns exemplos. Considere o seguinte código Java, que produzirá um tableswitch (e, quando convertido para dalvik, um 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";
    }
}

Conceitualmente, a carga útil para o packed-switch Opcode ficaria assim:

Como você pode ver, é bastante compacto. Três dos cinco slots apontam para o real case alvos, com os dois restantes pulando para o default alvo. Mas e se nossos valores de teste estivessem mais espalhados?

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";
    }
}

Se o compilador tentasse emitir isso como um packed-switch, a carga útil seria algo assim:

Observe como apenas três de algumas centenas de slots realmente apontam para case Rótulos do código original. O resto está lá simplesmente para encher a mesa de salto. Não é muito eficiente em termos de espaço, é? É por isso que o compilador emitia um sparse-switch, que tem uma pegada de bytecode muito mais compacta para este exemplo específico:

Agora, isso é muito mais razoável, você não acha? A desvantagem, no entanto, é que, em vez de saber exatamente para qual índice pular com base na entrada, precisamos executar uma pesquisa binária na tabela até encontrarmos um valor de teste correspondente. Quanto maior o interruptor, mais significativo o impacto no desempenho, embora o efeito tenha uma curva logarítmica.