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.