Question

Je ne peux pas, pour ma vie, rappelez-vous 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 dans les lignes de:

  

L'instruction si est la plus chère   [quelque chose]. [quelque chose] enregistre   [quelque chose].

Oui, j'ai une mémoire horrible et je suis vraiment désolée, mais je suis sur Google pendant des heures et rien ne s'est produit. Des idées?

Était-ce utile?

La solution

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

L'instruction en cours à exécuter est stockée dans quelque chose qui s'appelle généralement le pointeur d'instruction (IP) ou le compteur de programme (PC); ces termes sont synonymes, mais des termes différents sont utilisés avec des architectures différentes. Pour la plupart des instructions, le PC de l'instruction suivante est uniquement le PC actuel plus la longueur de l'instruction en cours. 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. Par conséquent, la logique qui décode l’instruction doit déterminer combien de temps l’instruction en cours recherche l’emplacement de la prochaine instruction.

Pour les instructions branch , cependant, l'instruction suivante à exécuter n'est pas l'emplacement suivant après l'instruction en cours. Les branches sont 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é.

Le conditionnel ou l'inconditionnel est facile à comprendre - une branche conditionnelle n'est prise que si une condition donnée est vérifiée (par exemple, 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 les instructions si et les tests de contrôle de pour et pendant que sont bouclés. Les branches inconditionnelles apparaissent dans des boucles infinies, des appels de fonction, des retours de fonction, des instructions break et continue , la fameuse instruction goto , et bien d'autres (ces les 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 instructions si , les boucles de toutes sortes, les appels de fonction normaux, etc. Les branches calculées calculent la cible de la branche au moment de l'exécution. Cela inclut les instructions switch (parfois), le retour d'une fonction, les appels de fonction virtuels et les appels de pointeurs de fonction.

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 trouver un moyen de continuer à remplir son pipeline. Afin de déterminer quelles instructions viennent après la branche dans le flux de programme, il est nécessaire de connaître deux choses: (1) si la branche sera prise et (2) la cible de la branche. La prédiction de branche est un moyen de résoudre ce problème. C'est un problème complexe. Si le processeur devine correctement, le programme continue à pleine vitesse. Si, au lieu de cela, le processeur devine de manière incorrecte , il ne fait que passer du temps à calculer le mauvais résultat. Il doit maintenant vider son pipeline et le recharger avec les instructions du bon chemin d'exécution. En bout de ligne: un énorme succès en termes de performances.

Par conséquent, si les déclarations coûtent cher, cela est dû à des prédictions erronées des branches . Ceci est seulement au plus bas niveau. Si vous écrivez du code de haut niveau, vous n'avez pas du tout à vous soucier de ces détails. Ne vous en préoccupez que si vous écrivez du code extrêmement critique en termes de performances en C ou en assembleur. Si tel est le cas, l'écriture de code sans branche peut souvent être supérieure au code qui branche, même si plusieurs instructions supplémentaires sont nécessaires. Vous pouvez effectuer quelques astuces amusantes pour calculer des éléments tels que abs () , min () et

Autres conseils

" Cher " est un terme très relatif, en particulier en relation avec un " if " déclaration puisque vous devez également prendre en compte le coût de la maladie. Cela peut aller de quelques instructions de l'unité centrale à tester le résultat d'une fonction qui appelle une base de données distante.

Je ne m'inquiéterais pas pour ça. À moins que vous ne fassiez de la programmation intégrée, vous ne devriez probablement pas vous inquiéter du coût du " si " du tout. Pour la plupart des programmeurs, cela ne va tout simplement pas jamais être le facteur déterminant des performances de votre application.

Les branches, en particulier sur les microprocesseurs à architecture RISC, comptent 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 ensuite ces instructions dans l'exécutable, afin qu'elles soient déjà dans le cache du processeur lorsque la branche se produit. Si la branche change de nom, elle doit retourner dans la mémoire principale et récupérer les nouvelles instructions, ce qui est assez coûteux. Sur beaucoup d'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 important ici, alors ne vous inquiétez pas. En outre, le compilateur optimisera mieux que 99% du temps :) L'un des aspects vraiment impressionnants de l'architecture EPIC (Itanium en est un exemple) est qu'il met en cache (et commence à traiter) les instructions des deux côtés de la branche, puis rejette l'ensemble dont il n'a pas besoin une fois que le résultat de la branche est connu. Cela enregistre l’accès mémoire supplémentaire d’une architecture typique au cas où elle se ramifierait 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 branches sur le blog de détection de collisions en temps réel.

En plus des excellentes réponses déjà fournies en réponse à cette question, je voudrais rappeler que "& if" & ";" les instructions 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 niveau supérieur, tel qu'un langage de script ou une couche de logique métier (quel que soit le langage), peut s'avérer ridiculement inapproprié.

La grande majorité du temps, les programmes doivent être écrits pour la clarté en premier et optimisés pour la performance en second lieu. Il existe de nombreux domaines problématiques dans lesquels 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 haute performance en dynamique des fluides pouvant durer des semaines. Lorsque la priorité est donnée à votre solution, il suffit de travailler " La dernière chose qui vous préoccupe devrait être de savoir si vous pouvez ou non économiser sur les frais généraux d’une instruction conditionnelle de votre code.

Au niveau le plus bas possible si consiste en (après le calcul de tous les prérequis spécifiques à l'application pour un particulier ):

  • des instructions de test
  • sautez à un endroit du code si le test réussit, continuez sinon.

Coûts associés à cela:

  • une comparaison de bas niveau - généralement 1 opération de l'unité centrale, super pas cher
  • saut potentiel - ce qui peut coûter cher

Pourquoi les sauts sont-ils chers:

  • vous pouvez passer au code arbitraire qui réside n'importe où dans la mémoire, s'il s'avère que celui-ci n'est pas mis en cache par le processeur - nous avons un problème, car nous devons accéder à la mémoire principale, ce qui est plus lent
  • Les processeurs modernes font la prédition de branche. Ils essaient de deviner si cela va réussir ou non et d'exécuter du code dans le pipeline, accélérez donc les choses. Si la prédiction échoue, tous les calculs effectués à l'avance par pipeline doivent être invalidés. C’est aussi une opération coûteuse

Donc pour résumer:

  • Si peut être coûteux, si vous vous souciez vraiment de la performance.
  • Vous devez vous en préoccuper si et seulement si vous écrivez des simulateurs biologiques ou une simulation biologique en temps réel ou quelque chose de similaire. Il n'y a aucune raison de s'en soucier dans la majeure partie du monde réel.

si en soi n'est pas lent. La lenteur est toujours relative, je parie pour ma vie que vous n’avez jamais ressenti les "frais généraux". d'un if-statement. Si vous voulez créer un code haute performance, vous voudrez peut-être éviter les branches de toute façon. Ce qui rend si lent, c'est que le processeur précharge le code après le if en fonction d'une heuristique et de ce qui ne l'est pas. Cela empêchera également les pipelines d’exécuter du code directement après l’instruction de branche si 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 réalisé). Le code exécuté peut devoir être exécuté en sens inverse (si l'autre branche a été prise. Elle s'appelle mauvaise interprétation de la branche ), ou noop doit être rempli à ces endroits ça n'arrivera pas.

Si si est mauvais, alors switch l'est aussi, et & amp; & amp; , || aussi. Ne t'inquiète pas pour ça.

Peut-être que le branchement tue l'instruction de pré-extraction de la CPU?

Les processeurs modernes disposent de longs pipelines d’exécution, ce qui signifie que plusieurs instructions sont exécutées simultanément à différentes étapes. Ils peuvent ne pas toujours connaître le résultat 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 savoir dans quel sens le pointeur d'instruction doit aller.

Je le considère comme 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 très long de 31 étages.

En savoir plus sur Wikipedia

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

Toutefois, cela dépend extrêmement de la situation - la plupart des processeurs modernes disposent de fonctionnalités de prévision de branche qui tentent de minimiser les effets négatifs de la branche. Un autre exemple serait comment l’architecture ARM (et probablement d’autres) peut gérer la logique conditionnelle - l’ARM a une exécution conditionnelle au niveau instruction, de sorte que la logique conditionnelle simple n’entraîne aucun branchement - les instructions s’exécutent simplement en tant que NOP si les conditions ne sont pas remplies.

Tout ce qui a été dit - corrigez votre logique avant de vous préoccuper de ce genre de choses. Un code incorrect est aussi optimisé que possible.

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 déclarations, vous ne pouvez pas toujours savoir ce que le compilateur proposera et vous inquiétez du temps que prendront les instructions de base. la mauvaise chose à faire. (Si vous savez ce que le compilateur va générer de manière fiable, vous n’avez peut-être pas un compilateur optimiseur performant.)

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

Le processeur s’arrête en attendant de savoir quoi faire ou bien le processeur prend une décision. Dans le cas d'un processeur plus ancien ou si la supposition est fausse, vous devrez subir un blocage du pipeline pendant le chargement et charger l'instruction correcte. Selon le CPU, cela peut aller jusqu'à 10 à 20 instructions.

Les processeurs modernes tentent d’éviter cela en effectuant une bonne prédiction 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 si loin.

Bonne chance en classe.

De plus, si vous devez vous inquiéter à ce sujet dans la vie réelle, vous êtes probablement en train de concevoir des systèmes d’exploitation, des graphiques en temps réel, des calculs scientifiques ou quelque chose de similaire, lié au processeur. Profil avant de s'inquiéter.

Notez également que, dans une boucle, n'est pas nécessairement très coûteux.

L’UC moderne suppose lors de la première visite d’une instruction if que le "if-body" doit être pris (ou dit dans l'autre sens: il suppose également qu'un corps de boucle doit être pris plusieurs fois) (*). Lors de la deuxième visite et lors de visites ultérieures, elle (la CPU) 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?). Si elle était fausse la dernière fois, l'exécution spéculative passe alors à l'option "else". du si, ou au-delà de la boucle.

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

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

Ecrivez vos programmes de la manière la plus claire, la plus simple et la plus propre qui ne soit pas manifestement inefficace. Cela fait le meilleur usage de 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, mesurez l'emplacement des goulots d'étranglement et voyez comment les atténuer. Ce n'est que dans de très rares cas que vous devrez vous préoccuper des instructions individuelles (source). La performance consiste à sélectionner les algorithmes et les structures de données appropriés en première ligne, à programmer soigneusement et à obtenir une machine suffisamment rapide. Utilisez un bon compilateur, vous seriez surpris de voir le type de code restructurant un compilateur moderne. Le code de restructuration pour la performance est une sorte de mesure de dernier recours, le code devient plus complexe (donc buggier), plus difficile à modifier, et donc plus coûteux en général.

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

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

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

Référez-vous aux macros probable () / improbable () dans le noyau Linux - comment est-ce qu'ils travaillent? Quel est leur avantage? .

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

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.

J'essaie simplement d'interpréter vos mots manquants.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top