Différence de vitesse entre les if-Else et opérateur Ternaire dans le C...?

Donc à la suggestion d'un collègue, je viens de tester la différence de vitesse entre l'opérateur ternaire et l'équivalent if-Else bloc... et il semble que l'opérateur ternaire rendements de code qui est entre 1x et 2x plus rapide que if-Else. Mon code est:

  gettimeofday(&tv3, 0);
  for(i = 0; i < N; i++)
  {
     a = i & 1;
     if(a) a = b; else a = c;
  }
  gettimeofday(&tv4, 0);


  gettimeofday(&tv1, 0);
  for(i = 0; i < N; i++)
  {
     a = i & 1;
     a = a ? b : c;
  }
  gettimeofday(&tv2, 0);

(Désolé pour l'utilisation de gettimeofday et pas clock_gettime... je m'efforcerai de m'améliorer.)

J'ai essayé de changer l'ordre dans lequel j'ai programmé les blocs, mais les résultats semblent persister. Ce qui donne? Aussi, l'if-Else montre beaucoup plus de variabilité en termes de vitesse d'exécution. Dois-je être l'examen de l'assemblée généré par gcc?

Par la voie, c'est tout à l'optimisation du niveau zéro (-O0).

Suis-je imaginer cela, ou est-il quelque chose que je ne suis pas prise en compte, ou est-ce un dépendant de la machine, ou quoi? Toute aide est appréciée.

Repères avec les optimisations sont vide de sens...
"Par la voie, c'est tout à l'optimisation du niveau zéro (-O0)." cela signifie Que vous avez dit au compilateur de ne pas optimiser (en gros), c'est donc sans surprise que cela va générer plus de commentaires (et donc plus lent) code pour plus de commentaires de code. Si vous jeter un -O1, je soupçonne que vous ne remarquerez aucune différence. Ne voyant pas beaucoup de point en regardant la distinction de la performance dans unoptimized code.
Remarque: ? est l'opérateur conditionnel, Un opérateur ternaire, pas L'opérateur ternaire.
c'est le seul opérateur ternaire en C++, d'où L'opérateur ternaire.
ouais, et les etats-unis pourraient, à l'avenir passer à un système de d'avoir plusieurs titulaires Présidents, mais jusqu'alors, Obama (ou d'autres titulaires) est LE Président, et Bush est Un Président. Drôle de langue ;-p

OriginalL'auteur Patrick87 | 2011-07-19

c++performance ternary-operator

23

Il ya une bonne chance que l'opérateur ternaire sera compilé dans un cmov tandis que le if/else résultats dans un cmp+jmp. Il suffit de prendre un coup d'oeil à l'assemblée (à l'aide d'-S) pour être sûr. Avec les optimisations activées, il ne sera pas plus d'importance de toute façon, comme tout bon compilateur doit produire le même code dans les deux cas.

Aujourd'hui sur le Cpu, une condition mouvement a une latence fixe tandis qu'un prédit branche conditionnelle est fondamentalement libre. Pour cette raison, vous ne pourriez pas voir d'un compilateur optimisant générer CMOV tout à fait aussi souvent que vous le pensiez.

OriginalL'auteur Anteru
9

C'est une belle explication: http://www.nynaeve.net/?p=178

Fondamentalement, il y a "conditionnel ensemble" instructions du processeur, qui est plus rapide que de branchement et réglage de la notice séparée.

OriginalL'auteur trutheality
9

Vous pouvez aussi aller complètement dépourvu de branches et de mesurer si cela fait une différence:
```
int m = -(i & 1);
a = (b & m) | (c & ~m);
```
Aujourd'hui sur les architectures, ce style de programmation a grandi un peu en dehors de la mode.

Il est toujours utile lorsque vous avez une condition dans une boucle qui exécute un grand nombre (disons milliards de dollars) de fois.

OriginalL'auteur fredoverflow

Si il y a de tout, de changer de compilateur!

Pour ce genre de questions que j'ai utiliser le Essayer de LLVM page. C'est une ancienne version de LLVM (toujours à l'aide de la gcc front-end), mais ce sont des vieux trucs.

Voici mon petit programme d'exemple (version simplifiée de la vôtre):

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

int main (int argc, char* argv[]) {
  int N = atoi(argv[0]);

  int a = 0, d = 0, b = atoi(argv[1]), c = atoi(argv[2]);

  int i;
  for(i = 0; i < N; i++)
  {
     a = i & 1;
     if(a) a = b+i; else a = c+i;
  }

  for(i = 0; i < N; i++)
  {
     d = i & 1;
     d = d ? b+i : c+i;
  }

  printf("%d %d", a, d);

  return 0;
}

Et il est le correspondant IR LLVM généré:

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind {
entry:
%0 = load i8** %argv, align 8                   ; <i8*> [#uses=1]
%N = tail call i32 @atoi(i8* %0) nounwind readonly ; <i32> [#uses=5]
%2 = getelementptr inbounds i8** %argv, i64 1   ; <i8**> [#uses=1]
%3 = load i8** %2, align 8                      ; <i8*> [#uses=1]
%b = tail call i32 @atoi(i8* %3) nounwind readonly ; <i32> [#uses=2]
%5 = getelementptr inbounds i8** %argv, i64 2   ; <i8**> [#uses=1]
%6 = load i8** %5, align 8                      ; <i8*> [#uses=1]
%c = tail call i32 @atoi(i8* %6) nounwind readonly ; <i32> [#uses=2]
%8 = icmp sgt i32 %N, 0                         ; <i1> [#uses=2]
br i1 %8, label %bb, label %bb11
bb:                                               ; preds = %bb, %entry
%9 = phi i32 [ %10, %bb ], [ 0, %entry ]        ; <i32> [#uses=2]
%10 = add nsw i32 %9, 1                         ; <i32> [#uses=2]
%exitcond22 = icmp eq i32 %10, %N               ; <i1> [#uses=1]
br i1 %exitcond22, label %bb10.preheader, label %bb
bb10.preheader:                                   ; preds = %bb
%11 = and i32 %9, 1                             ; <i32> [#uses=1]
%12 = icmp eq i32 %11, 0                        ; <i1> [#uses=1]
%.pn13 = select i1 %12, i32 %c, i32 %b          ; <i32> [#uses=1]
%tmp21 = add i32 %N, -1                         ; <i32> [#uses=1]
%a.1 = add i32 %.pn13, %tmp21                   ; <i32> [#uses=2]
br i1 %8, label %bb6, label %bb11
bb6:                                              ; preds = %bb6, %bb10.preheader
%13 = phi i32 [ %14, %bb6 ], [ 0, %bb10.preheader ] ; <i32> [#uses=2]
%14 = add nsw i32 %13, 1                        ; <i32> [#uses=2]
%exitcond = icmp eq i32 %14, %N                 ; <i1> [#uses=1]
br i1 %exitcond, label %bb10.bb11_crit_edge, label %bb6
bb10.bb11_crit_edge:                              ; preds = %bb6
%15 = and i32 %13, 1                            ; <i32> [#uses=1]
%16 = icmp eq i32 %15, 0                        ; <i1> [#uses=1]
%.pn = select i1 %16, i32 %c, i32 %b            ; <i32> [#uses=1]
%tmp = add i32 %N, -1                           ; <i32> [#uses=1]
%d.1 = add i32 %.pn, %tmp                       ; <i32> [#uses=1]
br label %bb11
bb11:                                             ; preds = %bb10.bb11_crit_edge, %bb10.preheader, %entry
%a.0 = phi i32 [ %a.1, %bb10.bb11_crit_edge ], [ %a.1, %bb10.preheader ], [ 0, %entry ] ; <i32> [#uses=1]
%d.0 = phi i32 [ %d.1, %bb10.bb11_crit_edge ], [ 0, %bb10.preheader ], [ 0, %entry ] ; <i32> [#uses=1]
%17 = tail call i32 (i8*, ...)* @printf(i8* noalias getelementptr inbounds ([6 x i8]* @.str, i64 0, i64 0), i32 %a.0, i32 %d.0) nounwind ; <i32> [#uses=0]
ret i32 0
}

Ok, donc il est susceptible d'être chinois, même si je suis allé de l'avant et de renommage de certaines variables pour le rendre un peu plus facile à lire.

Les choses importantes sont ces deux blocs:

  %.pn13 = select i1 %12, i32 %c, i32 %b          ; <i32> [#uses=1]
%tmp21 = add i32 %N, -1                         ; <i32> [#uses=1]
%a.1 = add i32 %.pn13, %tmp21                   ; <i32> [#uses=2]
%.pn = select i1 %16, i32 %c, i32 %b            ; <i32> [#uses=1]
%tmp = add i32 %N, -1                           ; <i32> [#uses=1]
%d.1 = add i32 %.pn, %tmp                       ; <i32> [#uses=1]

Qui définissent respectivement a et d.

Et la conclusion est: Pas de différence

Remarque: dans un exemple plus simple, les deux variables effectivement fusionné, il semble ici que l'optimiseur n'a pas de détecter la similarité...

OriginalL'auteur Matthieu M.

0

Tout bon compilateur doit générer le même code pour ces derniers si l'optimisation est activée.

OMI cela devrait également être un commentaire, en considérant les 2 réponses qui sont en fait des réponses
vous avez raison, mais... l'un d'eux, bien que la réponse à la question au sérieux, il oublie de mentionner que ce n'est qu'un problème avec -O0. les compilateurs font un très bon travail d'optimisation et les gens ne devraient pas faire de micro-optimisations comme celles-ci. off.

OriginalL'auteur Karoly Horvath
0

Comprendre que c'est tout à fait au compilateur comment il interprète l'expression ternaire (sauf si vous avez fait la force de ne pas (inline) asm). Il pourrait tout aussi facilement comprendre ternaire expression comme "if..else" dans sa Représentation Interne de la langue, et en fonction de la cible en arrière-plan, il peut choisir de générer conditionnelle déplacer instruction (sur x86, CMOVcc est un. Il devrait aussi être ceux pour min/max, abs, etc). La principale motivation de l'aide conditionnelle est de transférer le risque de branche mispredict d'un mémoire/register opération de déplacement. L'inconvénient de cette instruction est presque tout le temps, l'opérande de registre qui sera conditionnelle de chargement devront être évalués en bas de formulaire d'inscription pour profiter de la cmov instruction.

Cela signifie que l'inconditionnel processus d'évaluation doit être inconditionnel, et il apparaîtra à l'augmentation de la longueur de l'inconditionnel chemin d'accès du programme. Mais ils savent que la direction de la mispredict est le plus souvent résolu comme "rinçage" le pipeline, ce qui signifie que les instructions qui aurait fini de s'exécuter sont ignorés (tourné à Pas les instructions de Fonctionnement). Cela signifie que le nombre d'instructions exécutées est plus élevé en raison de la stalles ou des Opr, et de l'effet écailles avec la profondeur du pipeline du processeur et les erreurs de prédiction de taux.

Cela apporte un dilemme intéressant dans la détermination de la droite de l'heuristique. Tout d'abord, nous savons pour sûr que si le pipeline est trop faible ou la direction de la prévision est pleinement en mesure d'apprendre de modèle à partir de l'histoire de la branche, puis cmov n'est pas la peine de le faire. C'est pas la peine de le faire si le coût de l'évaluation du conditionnel argument est plus grand que le coût d'erreurs de prédiction sur la moyenne.

Ce sont peut-être les raisons essentielles pourquoi les compilateurs ont de la difficulté à exploiter cmov enseignement, depuis l'heuristique de la détermination dépend en grande partie de l'exécution d'informations de profilage. Il est plus logique de l'utiliser sur compilateur JIT, car il peut fournir de l'exécution de l'instrumentation de la rétroaction et de construire une meilleure heuristique pour l'utilisation de ce ("Est la branche vraiment imprévisible?"). Sur le statique compilateur côté sans formation ou d'un profileur de données, il est plus difficile à assumer quand ce sera utile. Toutefois, une simple heuristique négative est, comme mentionné ci-dessus, si le compilateur sait que le jeu de données est complètement aléatoire ou en forçant le cond. pour uncond. l'évaluation est coûteuse (peut-être dû à titre irréductible, les opérations coûteuses comme les divise fp), il serait bon de l'heuristique de ne pas le faire.

Un compilateur qui vaut son sel fera tout ce qu'. La Question est, que faut-il faire après tout fiable heuristiques ont été utilisés...

OriginalL'auteur kchoi

Vous devez vous connecter pour publier un commentaire.