Le «IF» est-il cher?

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?

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.

«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.

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.

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.

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.

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.

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

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

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/ )

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.)

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.

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.

É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.

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? .

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?

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.