Question Est-ce que "IF" est cher?


Je ne peux pas, pour la vie de moi, me souvenir de 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 été googler pendant des heures et rien ne s'est passé. Des idées?


68
2017-11-24 20:18


origine


Réponses:


Au niveau le plus bas (dans le matériel), oui, sis sont chers. Pour comprendre pourquoi, vous devez comprendre comment pipelines travail.

L'instruction en cours à exécuter est stockée dans quelque chose appelé généralement le pointeur d'instruction (IP) ou 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 branche instructions, 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 soit fixe, soit calculé.

Conditionnel vs inconditionnel est facile à comprendre - une branche conditionnelle n'est prise que si une certaine condition est vérifiée (comme si un nombre est égal à 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 if déclarations et les tests de contrôle de for et while boucles. Les branches inconditionnelles apparaissent dans les boucles infinies, les appels de fonction, les retours de fonction, break et continue déclarations, le tristement célèbre goto déclaration, et beaucoup plus (ces listes sont loin d'être exhaustives).

La cible de la branche est un autre problème important. La plupart des succursales ont une cible de branche fixe: elles accèdent à un emplacement spécifique dans le code qui est fixé au moment de la compilation. Ceci comprend if des déclarations, des boucles de toutes sortes, des appels de fonctions réguliers, et bien plus encore. Calculé Les branches calculent la cible de la branche à l'exécution. Ceci comprend switch instructions (parfois), renvoyant d'une fonction, appels de fonctions virtuelles et appels de pointeurs de fonctions.

Alors, qu'est-ce que tout cela signifie pour la performance? Lorsque le processeur voit une instruction de branche apparaître dans son pipeline, il doit déterminer comment continuer à remplir son pipeline. Pour déterminer quelles instructions suivent la branche dans le flux de programme, il faut connaître deux choses: (1) si la branche sera prise et (2) la cible de la branche. On appelle cela 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 devine incorrectement, 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 si les déclarations sont coûteuses est due à imprécisions de branche. 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 soucier 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 branches, même si plusieurs instructions supplémentaires sont nécessaires. Il y a quelques astuces géniales que vous pouvez faire pour calculer des choses telles que abs(), min(), et max() sans ramification.


148
2017-11-24 20:38



"Cher" est un terme très relatif, surtout avec une relation à un "if"déclaration car 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'inquiéterais pas à ce sujet. À moins que vous ne fassiez de la programmation embarquée, vous ne devriez probablement pas vous inquiéter du coût de "if"du tout. Pour la plupart des programmeurs, il ne va tout simplement pas déjà être le facteur déterminant dans la performance de votre application.


13
2017-11-24 20:25



Les branches, 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 branche se produit. Si la branche va dans l'autre sens, 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 branche (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 branche, rejette ensuite l'ensemble dont il n'a plus besoin une fois que le résultat de la branche est connu. Cela permet d’économiser l’accès à la mémoire supplémentaire d’une architecture classique au cas où celle-ci serait dérivée sur le chemin non prévu.


13
2017-11-24 20:27



Découvrez l'article Meilleure performance grâce à l'élimination des succursales sur la performance des cellules. Un autre amusant est ce post sur les sélections sans branche sur le blog de détection des collisions en temps réel.

En plus des excellentes réponses déjà publiées en réponse à cette question, je voudrais vous 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 branche 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 dynamique 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.


8
2017-11-24 21:01



Au plus bas niveau possible if se compose de (après avoir calculé tous les prérequis spécifiques à l'application pour if):

  • 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 branche. 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.

6
2017-11-24 20:28



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 Wikipédia


6
2017-11-24 20:36



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


5
2017-11-24 20:22



La seule chose que je puisse imaginer, c'est le fait qu'un if déclaration peut généralement aboutir à une branche. Selon les spécificités de l'architecture du processeur, les branches 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 branche qui tentent de minimiser les effets négatifs des branchements. 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 pas de branchement.

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.


3
2017-11-24 20:26



if en soi est ne 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 branches de toute façon. Ce qui rend if lent est que le processeur est le code de préchargement après le if basé sur de l'heuristique et autres joyeusetés. Il empêchera également les pipelines d’exécuter du code directement après le if instruction de branchement dans le code machine, puisque 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é doit être exécuté en sens inverse (si l’autre branche a été prise, elle est appelée branch misprediction), ou noopêtre rempli à ces endroits afin que cela ne se produise pas.

Si if est mal, alors switch est mal aussi, et &&, || aussi. Ne vous inquiétez pas à ce sujet.


3
2017-11-24 20:36