L'implémentation suivante de square produit une série d'instructions cmp / je comme j'attendrais d'une instruction if chaînée:
int square(int num) {
if (num == 0){
return 0;
} else if (num == 1){
return 1;
} else if (num == 2){
return 4;
} else if (num == 3){
return 9;
} else if (num == 4){
return 16;
} else if (num == 5){
return 25;
} else if (num == 6){
return 36;
} else if (num == 7){
return 49;
} else {
return num * num;
}
}Et ce qui suit produit une table de données pour le retour:
int square_2(int num) {
switch (num){
case 0: return 0;
case 1: return 1;
case 2: return 4;
case 3: return 9;
case 4: return 16;
case 5: return 25;
case 6: return 36;
case 7: return 49;
default: return num * num;
}
}Pourquoi gcc est-il incapable d'optimiser celui du haut dans celui du bas?
Démontage pour référence: https://godbolt.org/z/UP_igi
EDIT: intéressant, MSVC génère une table de saut au lieu d'une table de données pour le boîtier de commutation. Et étonnamment, clang les optimise pour le même résultat.
c++
c
gcc
optimization
compiler-optimization
chacham15
la source
la source
returns; les cas n'ont pasbreaks, donc le commutateur a également un ordre d'exécution spécifique. La chaîne if / else a des retours dans chaque branche, la sémantique dans ce cas est équivalente. L'optimisation n'est pas impossible . Comme contre-exemple icc n'optimise aucune des fonctions.Réponses:
Le code généré pour
switch-caseutilise classiquement une table de saut. Dans ce cas, le retour direct via une table de correspondance semble être une optimisation utilisant le fait que chaque cas implique ici un retour. Bien que la norme ne donne aucune garantie à cet effet, je serais surpris si un compilateur générait une série de comparaisons au lieu d'une table de saut pour un commutateur classique.Maintenant
if-else, c'est exactement le contraire. Tandis qu'ilswitch-cases'exécute en temps constant, quel que soit le nombre de branches,if-elseest optimisé pour un plus petit nombre de branches. Ici, vous vous attendez à ce que le compilateur génère essentiellement une série de comparaisons dans l'ordre où vous les avez écrites.Donc, si je l'avais utilisé
if-elseparce que je m'attends à ce que la plupart des appelssquare()soient pour0ou1et rarement pour d'autres valeurs, alors `` l'optimisation '' en une recherche dans la table pourrait en fait faire fonctionner mon code plus lentement que prévu, ce qui irait à l'encontre de mon objectif d'utiliser un à laifplace d'unswitch. Donc, bien que cela soit discutable, je pense que GCC fait la bonne chose et Clang est trop agressif dans son optimisation.Quelqu'un avait, dans les commentaires, partagé un lien où clang fait cette optimisation et génère également du code basé sur une table de recherche
if-else. Quelque chose de notable se produit lorsque nous réduisons le nombre de cas à seulement deux (et une valeur par défaut) avec clang. Il génère une fois de plus un code identique pour if et switch, mais cette fois, bascule vers compare et se déplace au lieu de l'approche de table de recherche, pour les deux. Cela signifie que même le cliquet favorable aux commutateurs sait que le motif «si» est plus optimal lorsque le nombre de cas est petit!En résumé, une séquence de comparaisons pour
if-elseet une table de saut pourswitch-caseest le modèle standard que les compilateurs ont tendance à suivre et que les développeurs ont tendance à attendre lorsqu'ils écrivent du code. Cependant, dans certains cas particuliers, certains compilateurs peuvent choisir de rompre ce modèle lorsqu'ils estiment qu'il offre une meilleure optimisation. D'autres compilateurs pourraient simplement choisir de s'en tenir au modèle de toute façon, même s'ils ne sont apparemment pas optimaux, en faisant confiance au développeur pour savoir ce qu'il veut. Les deux sont des approches valables avec leurs propres avantages et inconvénients.la source
0et1)?ifest évidemment plus rapide? Maintenant, voici un exemple d'une plate-forme où 0 et 1 seraient plus rapides lors de l'utilisationifque lors de l'utilisation de switch: godbolt.org/z/wcJhvS (Notez qu'il existe également plusieurs autres optimisations en jeu ici)ifinstructions explicites ou automatiquement par le compilateur. Je ne suis pas un expert en ARM, donc je ne suis pas vraiment sûr de savoir si vous prétendezswitchêtre plus rapide que ce quiifest vrai. Cela dépendrait de la pénalité pour les branches mal prédites, et cela dépendrait en fait de quel ARM.Une justification possible est que si des valeurs faibles de
numsont plus probables, par exemple toujours 0, le code généré pour le premier peut être plus rapide. Le code généré pour le commutateur prend un temps égal pour toutes les valeurs.Comparaison des meilleurs cas, selon ce tableau . Voir cette réponse pour l'explication du tableau.
Si
num == 0, pour "si" vous avez xor, test, je (avec saut), ret. Latence: 1 + 1 + saut. Cependant, xor et test sont indépendants de sorte que la vitesse d'exécution réelle serait plus rapide que 1 + 1 cycles.Si
num < 7, pour "switch", vous avez mov, cmp, ja (sans saut), mov, ret. Latence: 2 + 1 + pas de saut + 2.Une instruction de saut qui ne se traduit pas par un saut est plus rapide qu'une instruction qui résulte d'un saut. Cependant, le tableau ne définit pas la latence pour un saut, il n'est donc pas clair pour moi lequel est le meilleur. Il est possible que le dernier soit toujours meilleur et que GCC ne soit tout simplement pas en mesure de l'optimiser.
la source