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.