Unterschied zwischen gepacktem Switch und Sparse-Switch-Dalvik-Opcode

Question

Ich möchte den Unterschied zwischen gepackten Switch- und Sparse-Switch-Opcodes in Dalvik wissen.Bitte geben Sie Beispiele an.Die Erklärung von Google ist mir unklar.

verpackter Schalter spärlicher Schalter

Danke.

Answer 1

Es hört sich so an, als ob packed-switch ist äquivalent zu Java tableswitch, Und sparse-switch Zu lookupswitch.

A packed-switch verwendet eine einfache Sprungtabelle, die durch das Formular indiziert wird low + n, Wo low ist der niedrigste Testwert unter den case Etiketten und n ist die Eingabe für die switch.Die Werte an jedem Index stellen die jeweiligen Bytecode-Offsets dar case.Das Finden der richtigen Sprungadresse ist ein Vorgang mit konstanter Zeit.

A sparse-switch verwendet eine sortierte Liste von Schlüssel-Wert-Paaren, wobei jeder Schlüssel ein Testwert von a ist case Label, und die Werte sind Sprungoffsets.Das richtige Sprungziel für a finden lookupswitch erfordert eine binäre Suche nach dem Schlüssel, es handelt sich also um eine Operation mit logarithmischer Zeit.

Der Compiler wählt aus, welche verwendet werden soll.Wenn die Schlüssel dazu neigen, geclustert zu sein oder verpackt eng zusammen, dann a packed-switch (oder, in Java-Begriffen, a tableswitch) effizient emittiert werden kann.Aber wenn die Schlüssel sind spärlich, und der Wertebereich (high - low + 1) groß ist, würde die Verwendung einer Sprungtabelle einen großen Bytecode-Block erfordern, da alle Werte in diesem Bereich in der Sprungtabelle vorhanden sein müssen, unabhängig davon, ob ein entsprechender Wert vorhanden ist case Etikett.In diesen Szenarien gibt der Compiler a aus sparse-switch (lookupswitch).

Interessanterweise entschieden sich die Dalvik-Ingenieure dafür, diese Opcodes so zu benennen, dass sie die Schlüsselverteilungen beschreiben, für die sie verwendet werden sollten, während die Java-Ingenieure Namen wählten, die die konzeptionellen Datenstrukturen beschreiben, denen die Bytecode-Operanden ähneln.

Schauen wir uns einige Beispiele an.Betrachten Sie den folgenden Java-Code, der a erzeugt tableswitch (und, bei Umwandlung 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";
    }
}

Konzeptionell ist die Nutzlast für die packed-switch Opcode würde etwa so aussehen:

Wie Sie sehen können, ist es ziemlich kompakt.Drei der fünf Slots weisen auf die Realität hin case Ziele, wobei die restlichen zwei zum Ziel springen default Ziel.Aber was wäre, wenn unsere Testwerte weiter gestreut wären?

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

Wenn der Compiler versucht hat, dies als auszugeben packed-switch, die Nutzlast würde etwa so aussehen:

Beachten Sie, dass nur drei von einigen hundert Slots tatsächlich darauf hinweisen case Etiketten aus dem Originalcode.Der Rest dient lediglich dazu, die Sprungtabelle aufzufüllen.Nicht sehr platzsparend, oder?Aus diesem Grund würde der Compiler a ausgeben sparse-switch, das für dieses spezielle Beispiel einen weitaus kompakteren Bytecode-Footprint aufweist:

Das ist doch viel vernünftiger, finden Sie nicht?Der Nachteil besteht jedoch darin, dass wir nicht anhand der Eingabe genau wissen, zu welchem ​​Index wir springen müssen, sondern eine binäre Suche in der Tabelle durchführen müssen, bis wir einen passenden Testwert finden.Je größer der Schalter, desto größer ist die Auswirkung auf die Leistung, obwohl der Effekt eine logarithmische Kurve hat.