Différence entre le commutateur emballé et l'opcode Dalvik du commutateur clairsemé

Question

Je veux connaître la différence entre les opcodes de commutateur emballés et les opcodes de commutateur clairsemés dans Dalvik.S'il vous plaît, si vous pouvez fournir des exemples.L'explication fournie par Google n'est pas claire pour moi.

commutateur emballé commutateur clairsemé

Merci.

Answer 1

On dirait que packed-switch est équivalent à celui de Java tableswitch, et sparse-switch à lookupswitch.

UN packed-switch utilise une simple table de sauts, indexée par le formulaire low + n, où low est la valeur de test la plus basse parmi les case les étiquettes, et n est l'entrée du switch.Les valeurs de chaque index représentent les décalages de bytecode pour chaque case.Trouver l'adresse de saut correcte est une opération à temps constant.

UN sparse-switch utilise une liste triée de paires clé-valeur, où chaque clé est une valeur de test provenant d'un case étiquette, et les valeurs sont des décalages de saut.Trouver la bonne cible de saut pour un lookupswitch nécessite une recherche binaire sur la clé, il s'agit donc d'une opération en temps logarithmique.

Le compilateur choisira lequel utiliser.Si les clés ont tendance à être regroupées ou emballé étroitement ensemble, puis un packed-switch (ou, en termes Java, un tableswitch) peuvent être émis efficacement.Mais si les clés sont clairsemé, et la plage de valeurs (high - low + 1) est grande, alors l'utilisation d'une table de sauts nécessiterait un gros bloc de bytecode, car toutes les valeurs de cette plage doivent exister dans la table de sauts, qu'il existe ou non un fichier correspondant. case étiquette.Dans ces scénarios, le compilateur émettra un sparse-switch (lookupswitch).

Il est intéressant de noter que les ingénieurs de Dalvik ont ​​choisi de nommer ces opcodes d'une manière qui décrit les distributions de clés pour lesquelles ils doivent être utilisés, tandis que les ingénieurs Java ont choisi des noms qui décrivent les structures de données conceptuelles auxquelles ressemblent les opérandes du bytecode.

Regardons quelques exemples.Considérons le code Java suivant, qui produira un tableswitch (et, une fois converti en Dalvik, un 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";
    }
}

Conceptuellement, la charge utile du packed-switch L'opcode ressemblerait à ceci :

Comme vous pouvez le constater, c'est assez compact.Trois des cinq emplacements indiquent des valeurs réelles case cibles, les deux autres sautant vers les default cible.Mais et si nos valeurs de test étaient plus étalées ?

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

Si le compilateur essayait d'émettre ceci en tant que packed-switch, la charge utile ressemblerait à ceci :

Remarquez que seuls trois emplacements sur quelques centaines pointent réellement vers case étiquettes du code original.Les autres sont là simplement pour remplir la table de saut.Ce n’est pas très économe en espace, n’est-ce pas ?C'est pourquoi le compilateur émettrait un sparse-switch, qui a une empreinte de bytecode beaucoup plus compacte pour cet exemple particulier :

Maintenant, c'est beaucoup plus raisonnable, vous ne trouvez pas ?L'inconvénient, cependant, est qu'au lieu de savoir exactement à quel index accéder en fonction de l'entrée, nous devons effectuer une recherche binaire sur la table jusqu'à ce que nous trouvions une valeur de test correspondante.Plus le commutateur est grand, plus l'impact sur les performances est important, bien que l'effet ait une courbe logarithmique.