L'ordre des cas dans une instruction switch affecte-t-il les performances?

Question

J'ai un switch de cas du programme:

L'ordre croissant de l'interrupteur cas :

int main()
{
        int a, sc = 1;
        switch (sc)
        {
                case 1:
                        a = 1;
                        break;
                case 2:
                        a = 2;
                        break;
        }
}

Assemblée de code:

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 1
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, 1
        je      .L3
        cmp     eax, 2
        je      .L4
        jmp     .L2
.L3:
        mov     DWORD PTR [rbp-8], 1
        jmp     .L2
.L4:
        mov     DWORD PTR [rbp-8], 2
        nop
.L2:
        mov     eax, 0
        pop     rbp
        ret

L'ordre décroissant de l'interrupteur cas:

int main()
{
        int a, sc = 1;
        switch (sc)
        {
                case 2:
                        a = 1;
                        break;
                case 1:
                        a = 2;
                        break;
        }
}

Assemblée de code:

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 1
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, 1
        je      .L3
        cmp     eax, 2
        jne     .L2
        mov     DWORD PTR [rbp-8], 1
        jmp     .L2
.L3:
        mov     DWORD PTR [rbp-8], 2
        nop
.L2:
        mov     eax, 0
        pop     rbp
        ret

Ici, ascendant ordonnance d'affaires généré plus de l'assemblée de descente de l'ordre.

Donc, si j'ai d'autres numéros de commutateur cas, alors l'ordre de cas affecter les performances?

Answer 1

Vous êtes à la recherche à unoptimized code, afin de l'étudier pour la performance n'est pas très significatif. Si vous regardez optimisé le code pour vos exemples, vous trouverez qu'il ne veut pas faire de comparaisons à tous! L'optimiseur d'avis que le commutateur variable sc a toujours la valeur 1, de sorte qu'il supprime l'inaccessible case 2.

L'optimiseur voit également que la variable a n'est pas utilisé après il est affecté, de sorte qu'il supprime le code en case 1 , en laissant main() une fonction vide. Et il supprime la fonction du prologue/épilogue qui manipule rbp depuis que le registre est inutilisé.

Ainsi, le code optimisé finit la même pour les deux versions de votre main() fonction de:

main:
    xor eax, eax
    ret

En bref, pour le code en question, il n'est pas soit l'ordre dans lequel vous mettre la case déclarations, parce que rien de ce code sera généré à tous.

Serait l' case afin de matière dans un exemple où le code est généré et utilisé? Probablement pas. Notez que, même dans votre unoptimized code généré, les deux versions de test pour les deux case valeurs dans l'ordre numérique, de vérifier d'abord pour 1 puis de 2, indépendamment de l'ordre dans le code source. Clairement le compilateur fait certains de tri de même dans le unoptimized code.

Assurez-vous de noter Glenn et Lundin commentaires: l' ordre de l' case sections n'est pas le seul changement entre vos deux exemples, le code est différent aussi. Dans l'un d'eux, le cas valeurs correspondent aux valeurs définies en a, mais pas dans l'autre.

Les compilateurs utilisent diverses stratégies pour switch/case des déclarations selon les valeurs réelles utilisées. Ils peuvent utiliser une série de comparaisons comme dans ces exemples, ou peut-être un saut de la table. Il peut être intéressant d'étudier le code généré, mais comme toujours, si des questions de rendement, de regarder vos paramètres d'optimisation et d'essai dans une situation de vie réelle.

Answer 2

Optimisation du compilateur d' switch des déclarations est délicate. Bien sûr, vous devez activer les optimisations (par exemple, essayez de compiler votre code avec gcc -O2 -fverbose-asm -S avec GCC et de regarder à l'intérieur de la générées .s assembleur fichier). BTW sur vos deux exemples de mon GCC 7 sur Debian/Sid/x86-64 donne simplement:

        .type   main, @function
main:
.LFB0:
        .cfi_startproc
# rsp.c:13: }
        xorl    %eax, %eax      #
        ret
        .cfi_endproc

^{(donc il n'y à aucune trace de l' switch en que le code généré)}

Si vous avez besoin de comprendre comment un compilateur peut optimiser switch, il y a quelques études sur ce sujet, comme ce un.

Si j'ai d'autres numéros de commutateur cas, alors une commande de cas d'effet sur les performances?

Pas en général, si vous utilisez un compilateur optimisant et en demandant à optimiser. Voir aussi cette.

Si ce qui compte pour vous (mais il ne faut pas laisser les micro-optimisations du compilateur!), vous avez besoin de référence, de profil et peut-être à étudier le code assembleur généré. BTW, le cache et l'allocation de registres peut importe beaucoup plus que de l'ordre de case-s donc je pense que vous ne devriez pas déranger du tout. Gardez à l'esprit la taille approximative des estimations de durées de les ordinateurs récents. Mettre la cases dans la plus lisible de commande (pour le prochain développeur travaillant sur le même code source). Lire aussi à propos de threaded code. Si vous avez de l'objectif liées à la performance) des raisons de ré-ordonner l' case-s (ce qui est très peu probable et devrait arriver au plus une fois dans votre vie), écrire un bon commentaire expliquant ces raisons.

Si vous avez beaucoup de performances, assurez-vous de référence et de profil, et de choisir un bon compilateur et de l'utiliser avec les options d'optimisation. Peut-être expérimenter différentes optimisation des paramètres (et peut-être plusieurs compilateurs). Vous pouvez ajouter de l' -march=native (en plus de -O2 ou -O3). Vous pourriez envisager de la compilation et la liaison avec -flto -O2 pour activer le lien-le temps des optimisations, etc. Vous souhaitez peut-être également sur le profil des optimisations.

BTW, beaucoup de compilateurs sont énormes logiciel libre projets (en particulier GCC et Clang). Si vous tenez tant que ça sur les performances, vous pouvez patcher le compilateur, l'étendre en ajoutant des supplémentaires de l'optimisation passer ( un fork du code source, en ajoutant un plugin pour GCC ou certains GCC MELT extensions). Qui nécessite des mois ou des années de travail (notamment pour comprendre les représentations internes et de l'organisation de ce compilateur).

^{(N'oubliez pas de prendre les coûts de développement en considération; dans la plupart des cas, ils coûtent beaucoup plus)}

Answer 3

Les performances dépendraient principalement du nombre de ratés de branche pour un ensemble de données donné, pas tellement du nombre total de cas. Et cela dépend à son tour fortement des données réelles et de la façon dont le compilateur a choisi d'implémenter le commutateur (table de répartition, conditions chaînées, arbre de conditions - je ne sais pas si vous pouvez même contrôler cela à partir de C).

Answer 4

L'instruction switch est généralement compilé via sauter tables de pas par de simples comparaisons.

Donc, il n'y a aucune perte de performances si vous permuter les cas relevés.

Cependant, il est parfois utile de garder le plus de cas dans l'ordre consécutif et n'utilisez pas de pause/retour dans certaines écritures, pour que le flux d'exécution d'aller à la prochaine affaire et d'éviter la duplication du code.

Lorsque les différences de chiffres entre le boîtier number sont de gros d'un cas à l'autre, notamment en case 10: et case 200000: le compilateur ne manquera pas de générer sauter les tables, comme il se doit remplir à propos de 200K, les entrées de presque tous avec un pointeur vers l' default: des cas, et dans ce cas, il va utiliser des comparaisons.

Answer 5

Dans les cas où la plupart des cas, les étiquettes sont consécutifs, compilateurs souvent processus de commutateur états sauter tables plutôt que de comparaisons. Les moyens exacts par lesquels les compilateurs de décider de la forme que de la sauter à utiliser (le cas échéant) varient entre les différentes implémentations. Parfois, l'ajout de cas d'une instruction switch peut améliorer les performances en simplifiant un compilateur de code généré (par exemple, si le code utilise des cas, 4-11, tandis que les cas de 0 à 3 sont manipulés par défaut de la mode, l'ajout explicite case 0:; case 1:; case 2:; case 3:; avant l' default: peut entraîner le compilateur comparant l'opérande contre 12 et, si c'est moins, à l'aide d'un 12-point de sauter de la table. En omettant ces cas peut provoquer le compilateur à soustraire 4 avant de comparer la différence contre 8, et ensuite utiliser un 8-tableau des éléments.

Une des difficultés en essayant d'optimiser les instructions switch est que les compilateurs savent généralement mieux que les programmeurs comment les performances des différentes approches varient lorsque, compte tenu de certaines entrées, mais les programmeurs peuvent savoir mieux que les compilateurs de ce que la distribution des intrants d'un programme ferait l'objet. Étant donné quelque chose comme:

if (x==0)
  y++;
else switch(x)
{
  ...
}

un "smart" compilateur peut reconnaître que le fait de changer le code pour:

switch(x)
{
  case 0:
    y++;
    break;
  ...
}

pourrait éliminer une comparaison dans tous les cas où l' x est non-nul, le coût d'un calculées sauter en x est égal à zéro. Si x est non-nul, la plupart du temps, que serait un bon métier. Si x est égal à zéro 99,9% du temps, toutefois, que peut-être un mauvais commerce. Compilation différents auteurs divergent quant à l'ampleur de la qui ils vont essayer d'optimiser les constructions, comme l'ancien dans le second.