Est-ce que “IF” est cher?

Pour ma vie, je ne peux pas me rappeler ce que notre professeur a dit exactement ce jour-là et j’espère que vous le saurez probablement.

Le module est “Structures de données et algorithmes” et il nous a dit quelque chose comme:

La déclaration if est la plus chère [quelque chose]. [quelque chose] enregistre quelque chose.

Oui, j’ai un horrible souvenir et je suis vraiment désolée, mais j’ai fait des recherches 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 en cours à exécuter est stockée dans quelque chose appelé typiquement le pointeur d’instruction (IP) ou le compteur de programme (PC); ces termes sont synonymes, mais des termes différents sont utilisés avec différentes architectures. Pour la plupart des instructions, le PC de l’instruction suivante n’est que le PC actuel plus la longueur de l’instruction en cours. Pour la plupart des architectures RISC, les instructions ont 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 combien de temps l’instruction en cours doit trouver l’emplacement de l’instruction suivante.

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

Conditionnel vs inconditionnel est facile à comprendre – une twig conditionnelle n’est prise que si une certaine condition est vérifiée (comme si un nombre est égal à un autre); Si la twig n’est pas prise, le contrôle passe à l’instruction suivante après la twig, comme d’habitude. Pour les twigs inconditionnelles, la twig est toujours prise. Les twigs conditionnelles apparaissent dans les instructions if et les tests de contrôle des boucles for et while . Les twigs inconditionnelles apparaissent dans les boucles infinies, les appels de fonctions, les retours de fonctions, les instructions de break et de continue , le fameux énoncé goto et bien d’autres encore (ces listes sont loin d’être exhaustives).

La cible de la twig est un autre problème important. La plupart des succursales ont une cible de twig fixe: elles accèdent à un emplacement spécifique dans le code qui est fixé au moment de la compilation. Cela inclut les instructions if , les boucles de toutes sortes, les appels de fonctions standard et bien d’autres. Les twigs calculées calculent la cible de la twig à l’exécution. Cela inclut les instructions de switch (parfois), le retour d’une fonction, les appels de fonction virtuels et les appels de pointeur de fonction.

Alors, qu’est-ce que tout cela signifie pour la performance? Lorsque le processeur voit une instruction de twig apparaître dans son pipeline, il doit déterminer comment continuer à remplir son pipeline. Pour déterminer quelles instructions suivent la twig dans le stream de programme, il faut connaître deux choses: (1) si la twig sera prise et (2) la cible de la twig. Cela s’appelle la prédiction de twig , et c’est un problème difficile. Si le processeur devine correctement, le programme continue à pleine vitesse. Si, au contraire, le processeur devine de manière incorrecte , il a juste passé du temps à calculer la mauvaise chose. Il doit maintenant vider son pipeline et le recharger avec les instructions du chemin d’exécution correct. Bottom line: un grand succès de performance.

Ainsi, la raison pour laquelle les déclarations sont coûteuses est due à des erreurs de Ce n’est qu’au niveau le plus bas. Si vous écrivez du code de haut niveau, vous n’avez pas besoin de vous soucier de ces détails. Vous ne devriez vous en préoccuper que si vous écrivez un code extrêmement critique en C ou en assemblage. Si tel est le cas, l’écriture de code sans succursale peut souvent être supérieure au code de ces twigs, même si plusieurs instructions supplémentaires sont nécessaires. Il existe quelques astuces intéressantes pour calculer des choses telles que abs() , min() et max() sans twigment.

“Cher” est un terme très relatif, en particulier avec une relation avec une déclaration ” if ” 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 firebase database distante.

Je ne m’inquiéterais pas à ce sujet. À moins que vous ne fassiez de la programmation intégrée, vous ne devriez probablement pas vous inquiéter du coût de ” if “. Pour la plupart des programmeurs, cela ne sera jamais le facteur déterminant des performances de votre application.

Les twigs, en particulier sur les microprocesseurs d’architecture RISC, font partie des 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 ensuite ces instructions dans l’exécutable, de sorte qu’elles se trouvent déjà dans le cache du processeur lorsque la twig se produit. Si la twig aille dans l’autre direction, elle doit retourner à la mémoire principale et récupérer les nouvelles instructions, ce qui est assez coûteux. Sur de nombreuses architectures RISC, toutes les instructions sont un cycle sauf pour la twig (qui est souvent 2 cycles). Nous ne parlons pas d’un coût majeur ici, alors ne vous inquiétez pas à ce sujet. De plus, le compilateur s’optimisera mieux que vous dans 99% des cas 🙂 L’une des choses vraiment géniales de l’architecture EPIC (Itanium en est un exemple) est qu’il met en cache (et commence le traitement) les instructions des deux côtés de la twig, puis élimine l’ensemble dont il n’a pas besoin une fois que le résultat de la twig est connu. Cela permet d’économiser l’access à la mémoire supplémentaire d’une architecture classique au cas où celle-ci serait dérivée sur le chemin non prévu.

Consultez l’article Meilleures performances grâce à l’élimination des twigs sur la performance des cellules. Un autre amusement est ce post sur les sélections sans twig 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, je voudrais rappeler que même si les déclarations “if” sont considérées comme des opérations de bas niveau coûteuses, essayer d’utiliser des techniques de programmation sans agence dans un environnement de haut niveau. , comme un langage de script ou une couche de logique métier (indépendamment de 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 la performance. Il existe de nombreux domaines problématiques dans lesquels les performances sont primordiales, mais le simple fait est que la plupart des développeurs n’écrivent pas de modules pour une utilisation profonde dans un moteur de rendu ou une simulation de dynamic des fluides haute performance pendant des semaines. Lorsque la priorité absolue est que votre solution “fonctionne”, la dernière chose à laquelle vous devez penser est de savoir si vous pouvez économiser sur la surcharge d’une instruction conditionnelle dans votre code.

Au niveau le plus bas possible if consiste en (après avoir calculé toutes les conditions préalables spécifiques à l’application pour un if particulier):

  • quelques instructions de test
  • passer à un endroit du code si le test réussit, procéder autrement vers l’avant.

Les coûts associés à cela:

  • une comparaison de bas niveau – généralement 1 opération cpu, super pas cher
  • saut potentiel – qui peut être coûteux

Reson pourquoi les sauts sont chers:

  • vous pouvez passer à un code arbitraire qui vit n’importe où dans la 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 avons besoin d’accéder à la mémoire principale, ce qui est plus lent
  • les processeurs modernes font la prédiction de twig. Ils essayent de deviner si réussiront ou non et exécuteront le code en avance dans le pipeline, accélérant ainsi les choses. Si la prédiction échoue, tous les calculs effectués par pipeline doivent être invalidés. C’est aussi une opération coûteuse

Pour résumer:

  • Si cela peut être intéressant, si vous vous souciez vraiment de la performance.
  • Vous devriez vous en soucier si et seulement si vous écrivez en temps réel un raytraceur ou une simulation biologique ou quelque chose de similaire. Il n’y a aucune raison de s’en préoccuper dans la plupart des cas.

Peut-être que le twigment tue le préchargement des instructions du processeur?

Les processeurs modernes ont de longs pipelines d’exécution, ce qui signifie que plusieurs instructions sont exécutées à différents stades à la fois. Ils peuvent ne pas toujours connaître l’issue d’une instruction lorsque la suivante commence à s’exécuter. Lorsqu’ils se heurtent à un saut conditionnel (if), ils doivent parfois attendre que le pipeline soit vide avant de pouvoir savoir dans quel sens le pointeur d’instruction doit être utilisé.

J’y pense comme un long train de marchandises. Il peut transporter beaucoup de fret rapidement en ligne droite, mais il tourne mal.

Le Pentium 4 (Prescott) a connu un long pipeline de 31 étapes.

Plus sur Wikipedia

if en soi n’est pas lent. La lenteur est toujours relative, je parie que pour ma vie, vous n’avez jamais ressenti le “surcoût” d’une déclaration si. Si vous prévoyez de créer un code performant, vous voudrez peut-être éviter les twigs de toute façon. Ce qui rend if lent, c’est que le processeur est en train de précharger le code après le if basé sur des heuristiques et autres. Il empêchera également les pipelines d’exécuter du code directement après l’instruction if branch dans le code machine, car le processeur ne sait pas encore quel chemin sera pris (dans un processeur en pipeline, plusieurs instructions sont entrelacées et exécutées). Le code exécuté peut être exécuté en sens inverse (si l’autre twig a été prise. C’est ce qu’on appelle une branch misprediction ) ou noop être rempli à ces endroits pour que cela ne se produise pas.

Si if est le mal, alors le switch est mauvais aussi, et && , || aussi. Ne t’inquiète pas pour ça.

La seule chose à laquelle je peux imaginer, c’est le fait qu’une instruction if peut généralement aboutir à une twig. Selon les spécificités de l’architecture du processeur, les twigs peuvent provoquer des arrêts de pipeline ou d’autres situations moins qu’optimales.

Cependant, ceci est extrêmement spécifique à la situation – la plupart des processeurs modernes ont des capacités de prédiction de twig qui tentent de minimiser les effets négatifs des twigments. 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 n’entraîne aucune dérivation – les instructions s’exécutent simplement si les conditions ne sont pas remplies.

Tout cela étant dit – corrigez votre logique avant de vous inquiéter de ce genre de choses. Un code incorrect est aussi peu optimisé que possible.

Comme le soulignent de nombreuses personnes, les twigs conditionnelles peuvent être très lentes sur un ordinateur moderne.

Cela étant dit, il y a beaucoup de twigs conditionnelles qui ne vivent pas dans les instructions if, vous ne pouvez pas toujours savoir ce que le compilateur va produire, et se soucier de la durée des instructions de base est presque toujours la mauvaise chose. faire. (Si vous pouvez déterminer ce que le compilateur va générer de manière fiable, vous ne pouvez pas avoir un bon compilateur d’optimisation.)

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

Le processeur cale en attendant de savoir quoi faire ou le processeur prend une décision. Dans le cas d’un processeur plus ancien, ou si la supposition est erronée, vous devrez subir un blocage du pipeline pendant le chargement et charger l’instruction correcte. Selon le processeur, cela peut aller jusqu’à 10-20 instructions de décrochage.

Les processeurs modernes essayent d’éviter ceci en faisant de bonnes prédictions de twig, et en exécutant plusieurs chemins en même temps, en ne gardant que le chemin réel. Cela aide beaucoup, mais ne peut aller que jusqu’à présent.

Bonne chance dans la classe.

De plus, si vous devez vous soucier de cela dans la vraie vie, vous réalisez probablement du design de système d’exploitation, des graphiques en temps réel, du calcul scientifique ou quelque chose de similaire lié au processeur. Profil avant de s’inquiéter.

Notez également que l’intérieur d’une boucle n’est pas nécessairement très coûteux.

Lors de la première visite d’une instruction if, le CPU moderne suppose que le “if-body” doit être pris (ou dit autrement: il suppose également qu’un corps de boucle soit pris plusieurs fois) (*). Lors des deuxièmes visites et des visites ultérieures, il (le processeur) peut peut-être examiner la table d’historique des twigs et voir comment la condition était la dernière fois (était-ce vrai? Était-ce faux?). Si c’était la dernière fois, alors l’exécution spéculative passera à “else” de la boucle if ou after.

(*) La règle est en réalité ” twig avant non prise, twig en arrière prise “. Dans une instruction if, il n’y a qu’un saut [avant] (au point après le corps if) si la condition est fausse (rappelez-vous: le processeur suppose de toute façon qu’il ne faut pas prendre une twig / un saut), mais en boucle , il y a peut-être une twig avant à la position après la boucle (à ne pas prendre), et une twig arrière à la répétition (à prendre).

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

Ecrivez vos programmes de la manière la plus claire, la plus simple et la plus propre qui n’est évidemment pas inefficace. Cela fait la meilleure utilisation de la ressource la plus chère, vous. Qu’il s’agisse d’écrire ou de déboguer plus tard (nécessite une compréhension) du programme. Si les performances ne suffisent pas, mesurez les goulots d’étranglement et voyez comment les atténuer. Ce n’est que dans de très rares cas que vous devrez vous soucier des instructions individuelles (de source). La performance consiste à sélectionner les bons algorithmes et structures de données en première ligne, à programmer soigneusement, à obtenir une machine suffisamment rapide. Utilisez un bon compilateur, vous seriez surpris de voir le type de restructuration de code qu’un compilateur moderne fait. Restructurer le code pour la performance est une sorte de mesure de dernier recours, le code devient plus complexe (donc plus difficile), plus difficile à modifier et donc plus cher.

J’ai eu cette dispute avec un ami à moi une fois. Il utilisait un algorithme de cercle très naïf, mais prétendait être plus rapide que le mien (Le genre qui ne calcule que 1 / 8ème du cercle) car le mien était utilisé si. À la fin, l’instruction if a été remplacée par sqrt et plus rapidement. Peut-être parce que le FPU a été intégré?

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

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

Reportez-vous aux macros probabilité () / improbable () dans le kernel Linux – comment fonctionnent-elles? Quel est leur avantage? .

Le plus cher en termes d’utilisation d’ALU? Il utilise les registres CPU pour stocker les valeurs à comparer et prend le temps de récupérer et de comparer les valeurs chaque fois que l’instruction if est exécutée.

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

Juste essayer d’interpréter vos mots manquants.