Differenza tra interruttore confezionato e interruttore sparso Dalvik Opcode

Question

Voglio conoscere la differenza tra interruttore confezionato e switch sparse in Dalvik. Si prega di fornire esempi. La spiegazione fornita da Google non è chiara per me.

switch impacchettato interruttore sparso

Grazie.

Answer 1

Sembra che se packed-switch è equivalente a Java tableswitch, e sparse-switch a lookupswitch.

UN packed-switch utilizza una semplice tabella di salto, indicizzata dal modulo low + n, dove low è il valore di prova più basso tra i case Etichette e n è l'input per il switch. I valori su ciascun indice rappresentano gli offset bytecode per ciascuno case. Trovare l'indirizzo di salto corretto è un'operazione a tempo costante.

UN sparse-switch utilizza un elenco ordinato di coppie di valore chiave, in cui ogni chiave è un valore di test da a case Etichetta e i valori sono offset di salto. Trovare il bersaglio di salto corretto per un file lookupswitch Richiede una ricerca binaria sulla chiave, quindi è un'operazione logaritmica.

Il compilatore sceglierà quale usare. Se i tasti tendono ad essere raggruppati o confezionato strettamente insieme, poi a packed-switch (o, in termini Java, a tableswitch) può essere emesso in modo efficiente. Ma se le chiavi sono scarso, e l'intervallo di valori (high - low + 1) è grande, quindi l'uso di una tabella di salto richiederebbe un grande blocco di bytecode, poiché tutti i valori in tale intervallo devono esistere nella tabella di salto indipendentemente dal fatto che ci sia un corrispondente case etichetta. In questi scenari, il compilatore emetterà a sparse-switch (lookupswitch).

È interessante notare che gli ingegneri di Dalvik hanno scelto di nominare questi codici opportuno in un modo che descrive le distribuzioni chiave per le quali dovrebbero essere utilizzate, mentre gli ingegneri Java hanno scelto nomi che descrivono le strutture di dati concettuali a cui assomigliano i bytecode.

Diamo un'occhiata ad alcuni esempi. Considera il seguente codice Java, che produrrà un tableswitch (e, quando convertito in Dalvik, a 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";
    }
}

Concettualmente, il carico utile per il packed-switch OpCode assomigliare a questo:

Come puoi vedere, è abbastanza compatto. Tre delle cinque slot indicano l'attuale case bersagli, con i restanti due che saltano al default obbiettivo. E se i nostri valori di test fossero più distribuiti?

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 il compilatore ha provato a emetterlo come a packed-switch, il payload sembrerebbe qualcosa di simile:

Notate come solo tre su poche centinaia di slot indicano effettivamente case Etichette dal codice originale. Il resto è lì semplicemente per riempire il tavolo da salto. Non è molto efficiente dallo spazio, vero? Ecco perché il compilatore emetterebbe a sparse-switch, che ha un'impronta bytecode molto più compatta per questo particolare esempio:

Ora, è molto più ragionevole, non credi? Il rovescio della medaglia, tuttavia, è che invece di sapere esattamente quale indice saltare in base all'input, dobbiamo eseguire una ricerca binaria sulla tabella fino a quando non troviamo un valore di test corrispondente. Più grande è l'interruttore, più significativo è l'impatto sulle prestazioni, sebbene l'effetto abbia una curva logaritmica.