Le «IF» est-il cher?

98

Je ne peux pas, pour la vie de moi, me rappeler ce que notre professeur a dit exactement ce jour-là et j'espère que vous le sauriez probablement.

Le module est "Structures de données et algorithmes" et il nous a dit quelque chose du genre:

La ifdéclaration est le plus cher [quelque chose]. [quelque chose] enregistre [quelque chose].

Oui, j'ai un souvenir horrible et je suis vraiment désolé, mais j'ai cherché sur Google pendant des heures et rien ne s'est passé. Des idées?

pek
la source
29
Est-ce que demander à votre enseignant est une option?
Michael Myers
7
Pourquoi ne pas envoyer un e-mail à votre professeur? Il est peu probable que quelqu'un sur SO sache ce que votre professeur a dit, à moins qu'il ne soit là à ce moment-là (ou que votre professeur lui-même lit SO).
Bill Karwin
11
Et bien sûr un lien vers la réponse ferroviaire
bobobobo
Les instructions If ou en particulier les expressions "?:" Dans les langages à accolades influencés par C peuvent être implémentées par des instructions d'exécution conditionnelles spéciales sur, par exemple, les processeurs x86 et arm. Ce sont des instructions qui font ou ne font pas une opération basée sur un test préalable. L'utilisation de ces excellentes instructions évite le besoin d'instructions conditionnelles jump / branch / 'goto'. Une énorme amélioration des performances dans certaines situations en rendant le déroulement du programme complètement prévisible car il se contente de marcher droit sans (peut-être imprévisible) sauter à différents points du code.
Cecil Ward
Un bon compilateur peut parfois avoir besoin d'un petit coup de pouce dans la bonne direction pour qu'il utilise des instructions conditionnelles au lieu d'être stupide et d'utiliser des sauts conditionnels, en réorganisant le code et éventuellement en utilisant une arithmétique intelligente dans une expression ou un? : expression. Ne jouez pas avec cela à moins de connaître vraiment votre asm et d'avoir lu par exemple les guides d'optimisation d'Agner Fog. Les compilateurs ont parfois raison, que ce soit des déclarations ou : des expressions sont utilisées.
Cecil Ward

Réponses:

185

Au niveau le plus bas (dans le matériel), oui, si les s sont chers. Pour comprendre pourquoi, vous devez comprendre le fonctionnement des pipelines .

L'instruction courante à exécuter est stockée dans quelque chose généralement appelé le pointeur d'instruction (IP) ou le compteur de programme (PC); ces termes sont synonymes, mais différents termes sont utilisés avec différentes architectures. Pour la plupart des instructions, le PC de l'instruction suivante est simplement le PC actuel plus la longueur de l'instruction actuelle. Pour la plupart des architectures RISC, les instructions ont toutes une longueur constante, de sorte que le PC peut être incrémenté d'une quantité constante. Pour les architectures CISC telles que x86, les instructions peuvent être de longueur variable, de sorte que la logique qui décode l'instruction doit déterminer la durée de l'instruction en cours pour trouver l'emplacement de l'instruction suivante.

Pour les instructions de branchement , cependant, la prochaine instruction à exécuter n'est pas l'emplacement suivant après l'instruction en cours. Les branches sont des gotos - elles indiquent au processeur où se trouve la prochaine instruction. Les branches peuvent être conditionnelles ou inconditionnelles, et l'emplacement cible peut être fixe ou calculé.

Conditionnel ou inconditionnel est facile à comprendre - une branche conditionnelle n'est prise que si une certaine condition est satisfaite (par exemple si un nombre en équivaut à un autre); si la branche n'est pas prise, le contrôle passe à l'instruction suivante après la branche comme d'habitude. Pour les branches inconditionnelles, la branche est toujours prise. Les branches conditionnelles apparaissent dans les ifinstructions et les tests de contrôle des boucles foret while. Les branches inconditionnelles apparaissent dans des boucles infinies, des appels de fonction, des retours de fonction breaket des continueinstructions, la tristement célèbre gotoinstruction, et bien d'autres (ces listes sont loin d'être exhaustives).

La cible de la branche est un autre problème important. La plupart des branches ont une cible de branche fixe - elles vont à un emplacement spécifique dans le code qui est fixé au moment de la compilation. Cela inclut les ifinstructions, les boucles de toutes sortes, les appels de fonction réguliers et bien d'autres. Les branches calculées calculent la cible de la branche lors de l'exécution. Cela inclut les switchinstructions (parfois), le retour d'une fonction, les appels de fonction virtuelle et les appels de pointeur de fonction.

Alors qu'est-ce que tout cela signifie pour la performance? Lorsque le processeur voit apparaître une instruction de branchement dans son pipeline, il doit déterminer comment continuer à remplir son pipeline. Afin de comprendre quelles instructions viennent après la branche dans le flux de programme, il a besoin de savoir deux choses: (1) si la branche sera prise et (2) la cible de la branche. Comprendre cela s'appelle la prédiction de branche , et c'est un problème difficile. Si le processeur devine correctement, le programme continue à pleine vitesse. Si au contraire le processeur ne devine pas correctement , il a juste passé un certain temps à calculer la mauvaise chose. Il doit maintenant vider son pipeline et le recharger avec des instructions provenant du chemin d'exécution correct. Bottom line: un grand succès en termes de performances.

Ainsi, la raison pour laquelle si les déclarations sont coûteuses est due à des erreurs de prédiction de la branche . Ce n'est qu'au niveau le plus bas. Si vous écrivez du code de haut niveau, vous n'avez pas du tout à vous soucier de ces détails. Vous ne devriez vous en soucier que si vous écrivez du code extrêmement critique en termes de performances en C ou en assembly. Si tel est le cas, l'écriture de code sans succursale peut souvent être supérieure au code qui se branche, même si plusieurs instructions supplémentaires sont nécessaires. Il y a quelques trucs de bit-tripotant cool que vous pouvez faire pour calculer des choses telles que abs(), min()et max()sans ramification.

Adam Rosenfield
la source
20
Ce ne sont pas que des erreurs de prévisions de succursales. Les branches empêchent également la réorganisation des instructions, au niveau du compilateur, et aussi dans une certaine mesure au niveau du processeur (pour un processeur en désordre, bien sûr). Belle réponse détaillée cependant.
jalf
5
Si les langages de haut niveau sont finalement traduits dans des langages de bas niveau et que vous écrivez du code très axé sur les performances, ne gagnez-vous toujours rien à écrire du code qui évite les instructions if? Ce concept ne se retrouve-t-il pas dans les langues de niveau supérieur?
c ..
18

«Cher» est un terme très relatif, en particulier en relation avec un « if» énoncé puisque vous devez également prendre en compte le coût de la condition. Cela peut aller de quelques instructions cpu courtes au test du résultat d'une fonction qui appelle une base de données distante.

Je ne m'en soucierais pas. À moins que vous ne fassiez de la programmation intégrée, vous ne devriez probablement pas du tout vous préoccuper du coût de " if". Pour la plupart des programmeurs, cela ne sera jamais le facteur déterminant des performances de votre application.

Joel Coehoorn
la source
1
Certainement relatif ... cmp / cond jmp est toujours plus rapide qu'un mul sur de nombreux processeurs.
Brian Knoblauch
4
Oui, je suis d'accord que je ne devrais pas m'en préoccuper. Je n'essaye pas d'optimiser quoi que ce soit ici. J'essaie juste de découvrir et d'apprendre. ;)
pek
15

Les branches, en particulier sur les microprocesseurs d'architecture RISC, sont parmi les instructions les plus coûteuses. En effet, sur de nombreuses architectures, le compilateur prédit le chemin d'exécution le plus probable et place ces instructions ensuite dans l'exécutable, de sorte qu'elles seront déjà dans le cache du processeur lorsque la branche se produira. Si la branche va dans l'autre sens, elle doit retourner dans la mémoire principale et récupérer les nouvelles instructions - c'est assez cher. Sur de nombreuses architectures RISC, toutes les instructions sont un cycle sauf pour la branche (qui est souvent 2 cycles). Nous ne parlons pas ici d'un coût majeur, alors ne vous inquiétez pas. De plus, le compilateur optimisera mieux que vous 99% du temps: ) L'une des choses vraiment géniales à propos de l'architecture EPIC (Itanium est un exemple) est qu'elle met en cache (et commence à traiter) les instructions des deux côtés de la branche, puis rejette l'ensemble dont elle n'a pas besoin une fois que le résultat de la branche est connu. Cela économise l'accès à la mémoire supplémentaire d'une architecture typique dans le cas où elle se branche le long du chemin imprévu.

rmeador
la source
13

Consultez l'article Meilleures performances grâce à l'élimination des branches sur les performances des cellules. Un autre article amusant est cet article sur les sélections sans succursales sur le blog de détection de collision en temps réel.

En plus des excellentes réponses déjà publiées en réponse à cette question, j'aimerais rappeler que bien que les instructions «si» soient considérées comme des opérations de bas niveau coûteuses, essayer d'utiliser des techniques de programmation sans succursales dans un environnement de niveau supérieur , comme un langage de script ou une couche de logique métier (quelle que soit la langue), peut être ridiculement inapproprié.

La grande majorité du temps, les programmes doivent d'abord être écrits pour plus de clarté et ensuite optimisés pour les performances. Il existe de nombreux domaines problématiques où les performances sont primordiales, mais le fait est que la plupart des développeurs n'écrivent pas de modules destinés à être utilisés au cœur d'un moteur de rendu ou d'une simulation de dynamique des fluides haute performance qui dure des semaines. Lorsque la priorité absolue est que votre solution "fonctionne simplement", la dernière chose à laquelle vous pensez devrait être de savoir si vous pouvez ou non économiser sur la surcharge d'une instruction conditionnelle dans votre code.

Parappa
la source
En effet! On pourrait également ajouter que, lors du codage dans un langage qui encourage les appels (essentiellement, autre chose que l'assembleur ou C sans stdlib), les interférences de pipeline provenant de techniques de programmation normales submergeront toutes les questions sur le branchement conditionnel.
Ross Patterson
10

ifen soi n'est pas lent. La lenteur est toujours relative, je parie pour ma vie que vous n'avez jamais ressenti le "surcoût" d'une déclaration if. Si vous comptez créer un code performant, vous voudrez peut-être quand même éviter les branches. Ce qui ifralentit, c'est que le processeur précharge le code après le ifsur la base d'une heuristique et ainsi de suite. Cela empêchera également les pipelines d'exécuter du code directement après l' ifinstruction de branchement dans le code machine, car le processeur ne sait pas encore quel chemin sera emprunté (dans un processeur en pipeline, plusieurs instructions sont entrelacées et exécutées). Le code exécuté pourrait devoir être exécuté à l'envers (si l'autre branche a été prise. Elle est appelée branch misprediction), ou doit noopêtre rempli à ces endroits pour que cela ne se produise pas.

Si ifle mal, alors switchle mal aussi, et &&, ||aussi. Ne t'inquiète pas.

Johannes Schaub - litb
la source
7

Le niveau le plus bas possible ifcomprend (après avoir calculé tous les prérequis spécifiques à l'application pour un particulier if):

  • quelques instructions de test
  • sauter à un endroit dans le code si le test réussit, continuer dans le cas contraire.

Coûts associés à cela:

  • une comparaison de bas niveau - généralement 1 opération CPU, super bon marché
  • saut potentiel - qui peut être coûteux

Découvrez pourquoi les sauts sont chers:

  • vous pouvez passer au code arbitraire qui vit n'importe où en mémoire, s'il s'avère qu'il n'est pas mis en cache par le processeur - nous avons un problème, car nous devons accéder à la mémoire principale, qui est plus lente
  • les processeurs modernes font la prédition de branche. Ils essaient de deviner si cela réussira ou non et d'exécuter le code à l'avance dans le pipeline, alors accélérez les choses. Si la prédiction échoue, tout le calcul effectué à l'avance par pipeline doit être invalidé. C'est aussi une opération coûteuse

Pour résumer:

  • Cela peut être cher, si vous vous souciez vraiment de la performance.
  • Vous devriez vous en soucier si et seulement si vous écrivez un raytracer en temps réel ou une simulation biologique ou quelque chose de similaire. Il n'y a aucune raison de s'en soucier dans la majeure partie du monde réel.
Marcin
la source
Passez au niveau supérieur: qu'en est-il des instructions if imbriquées et / ou composées? La dépense peut devenir assez perceptible rapidement si quelqu'un écrit beaucoup de déclarations comme celle-ci. Et puisque pour la plupart des développeurs, si les instructions semblent être une opération aussi fondamentale, éviter le branchement conditionnel alambiqué est souvent relégué à une préoccupation stylistique. Les préoccupations stylistiques sont toujours importantes, mais souvent dans le feu de l'action, elles peuvent être la première préoccupation à ignorer.
jaydel
7

Les processeurs modernes ont de longs pipelines d'exécution, ce qui signifie que plusieurs instructions sont exécutées à différentes étapes en même temps. Ils peuvent ne pas toujours connaître le résultat d'une instruction lorsque la suivante commence à s'exécuter. Quand ils rencontrent un saut conditionnel (if), ils doivent parfois attendre que le pipeline soit vide avant de savoir dans quelle direction le pointeur d'instruction doit aller.

Je pense que c'est un long train de marchandises. Il peut transporter beaucoup de marchandises rapidement en ligne droite, mais il tourne mal.

Le Pentium 4 (Prescott) avait un pipeline réputé long de 31 étages.

En savoir plus sur Wikipedia

Guge
la source
3
+1 pour la métaphore du train de marchandises - je me souviendrai que pour la prochaine fois, je devrai expliquer les pipelines de transformation.
Daniel Pryden
6

Peut-être que le branchement tue la prélecture des instructions CPU?

activout.se
la source
Lors de mes ... "recherches", j'ai appris les tables de sauts et le branchement des instructions switch mais rien des instructions if. Pourriez-vous nous en dire un peu plus?
pek
IIRC, le CPU prélève généralement les instructions le long d'un seul chemin d'exécution probable, mais une instruction 'if' qui provoque une branche à partir du chemin d'exécution prédit invalidera les instructions préchargées et le préteching devra redémarrer.
activout.se
Tout processeur décent devrait avoir des capacités de prédiction de branche qui tenteront de deviner si une branche sera prise ou non, et une instruction de prélecture basée sur la prédiction (ce qui est généralement assez bon). GCC a même des extensions C qui permettent à un programmeur de fournir des conseils pour les prédicteurs de branche.
mipadi
2
De plus, le processeur anticipe généralement pour commencer à exécuter les instructions à venir tôt (pas seulement les prérécupérer), et le compilateur essaie de réorganiser les instructions, et cela devient dangereux entre les branches, vous pouvez donc vraiment tuer la planification des instructions avec trop de branches. Ce qui nuit aux performances.
jalf
6

Sachez également que l'intérieur d'une boucle n'est pas forcément très cher.

Le CPU moderne suppose lors de la première visite d'une instruction if, que le "if-body" doit être pris (ou dit l'inverse: il suppose également qu'un corps de boucle doit être pris plusieurs fois) (*). Lors de la deuxième visite et d'autres visites, il (le processeur) peut peut-être consulter la table d'historique des branches et voir comment la condition était la dernière fois (était-ce vrai? Était-ce faux?). S'il était faux la dernière fois, alors l'exécution spéculative passera à "else" du if, ou au-delà de la boucle.

(*) La règle est en fait " branche avant non prise, branche arrière prise ". Dans une instruction if, il n'y a qu'un saut [en avant] (jusqu'au point après le corps if) si la condition est évaluée à false (rappelez-vous: le CPU suppose de toute façon de ne pas prendre de branche / saut), mais dans une boucle , il y a peut-être une branche avant vers la position après la boucle (à ne pas prendre), et une branche arrière lors de la répétition (à prendre).

C'est aussi l'une des raisons pour lesquelles un appel à une fonction virtuelle ou un appel à un pointeur de fonction n'est pas si pire que beaucoup le supposent ( http://phresnel.org/blog/ )

Sébastien Mach
la source
5

Comme beaucoup l'ont souligné, les branches conditionnelles peuvent être très lentes sur un ordinateur moderne.

Cela étant dit, il y a beaucoup de branches conditionnelles qui ne vivent pas dans les instructions if, vous ne pouvez pas toujours dire ce que le compilateur va proposer, et s'inquiéter du temps que prendront les instructions de base est pratiquement toujours la mauvaise chose faire. (Si vous pouvez dire ce que le compilateur générera de manière fiable, vous n'aurez peut-être pas un bon compilateur d'optimisation.)

David Thornley
la source
4

La seule chose à laquelle je peux imaginer que cela pourrait faire référence est le fait qu'une ifdéclaration peut généralement aboutir à une branche. Selon les spécificités de l'architecture du processeur, les branches peuvent provoquer des blocages de pipeline ou d'autres situations moins qu'optimales.

Cependant, cela est extrêmement spécifique à la situation - la plupart des processeurs modernes ont des capacités de prédiction de branchement qui tentent de minimiser les effets négatifs du branchement. Un autre exemple serait la façon dont l'architecture ARM (et probablement d'autres) peut gérer la logique conditionnelle - l'ARM a une exécution conditionnelle au niveau des instructions, de sorte qu'une logique conditionnelle simple entraîne l'absence de branchement - les instructions s'exécutent simplement en tant que NOP si les conditions ne sont pas remplies.

Cela dit, corrigez votre logique avant de vous soucier de tout cela. Un code incorrect est aussi non optimisé que possible.

Michael Burr
la source
J'ai entendu dire que les instructions conditionnelles d'ARM inhibent l'ILP, alors elles pourraient simplement pousser le problème.
JD
3

Les processeurs sont profondément pipelined. Toute instruction de branchement (if / for / while / switch / etc) signifie que le CPU ne sait pas vraiment quelle instruction charger et exécuter ensuite.

Le CPU se bloque en attendant de savoir quoi faire, ou le CPU prend une estimation. Dans le cas d'un processeur plus ancien, ou si la supposition est fausse, vous devrez subir un blocage du pipeline pendant qu'il charge l'instruction correcte. En fonction du processeur, cela peut atteindre 10 à 20 instructions de décrochage.

Les processeurs modernes essaient d'éviter cela en faisant de bonnes prédictions de branche, en exécutant plusieurs chemins en même temps et en ne conservant que le chemin réel. Cela aide beaucoup, mais ne peut aller plus loin.

Bonne chance dans la classe.

De plus, si vous devez vous en soucier dans la vraie vie, vous faites probablement de la conception de système d'exploitation, des graphiques en temps réel, de l'informatique scientifique ou quelque chose de similaire lié au processeur. Profil avant de s'inquiéter.

tfinniga
la source
2

Écrivez vos programmes de la manière la plus claire, la plus simple et la plus propre qui n'est manifestement pas inefficace. Cela permet d'utiliser au mieux la ressource la plus chère, vous. Que ce soit l'écriture ou le débogage ultérieur (nécessite une compréhension) du programme. Si les performances ne suffisent pas, mesurezoù se trouvent les goulots d'étranglement et voyez comment les atténuer. Ce n'est qu'en de très rares occasions que vous devrez vous soucier des instructions individuelles (source). La performance consiste à sélectionner les bons algorithmes et structures de données dès la première ligne, à programmer soigneusement, à obtenir une machine suffisamment rapide. Utilisez un bon compilateur, vous seriez surpris de voir le type de code qui restructure un compilateur moderne. La restructuration du code pour la performance est une sorte de mesure de dernier recours, le code devient plus complexe (donc plus buggué), plus difficile à modifier et donc plus cher.

vonbrand
la source
1

Certains processeurs (comme X86) fournissent une prédiction de branche au niveau de programmation pour éviter une telle latence de prédiction de branche.

Certains compilateurs les exposent (comme GCC) comme une extension aux langages de programmation de niveau supérieur (comme C / C ++).

Reportez-vous aux macros probables () / improbables () dans le noyau Linux - comment fonctionnent-elles? Quel est leur avantage? .

Arunprasad Rajkumar
la source
0

J'ai eu cette dispute avec un de mes amis une fois. Il utilisait un algorithme de cercle très naïf, mais prétendait que le sien était plus rapide que le mien (le genre qui ne calcule que 1 / 8ème du cercle) parce que le mien l'utilisait. En fin de compte, l'instruction if a été remplacée par sqrt et c'était plus rapide. Peut-être parce que le FPU a intégré sqrt?

Demur Rumed
la source
-1

Le plus cher en termes d'utilisation d'ALU? Il utilise des registres de CPU pour stocker les valeurs à comparer et prend du temps pour récupérer et comparer les valeurs à chaque exécution de l'instruction if.

Par conséquent, une optimisation de cela consiste à faire une comparaison et à stocker le résultat sous forme de variable avant l'exécution de la boucle.

J'essaye juste d'interpréter tes mots manquants.


la source