Programmation adaptée aux succursales

Question

Je suis en train de lire partout que les erreurs de prédiction de branche peut être chaude, d'un goulot d'étranglement pour les performances d'une application. Comme je peux voir, les gens montrent souvent de l'assemblée de code qui dévoilent le problème et de l'état que les programmeurs peuvent généralement prédire où une succursale peut aller la plupart du temps et éviter de branche mispredictons.

Mes questions sont les suivantes:

1 - Est-il possible d' éviter branche mispredictions à l'aide de certains de haut niveau technique de programmation (c'est à dire pas de montage)?

2 - Que dois-je garder à l'esprit pour produire de la branche sympathique du code dans un langage de programmation de haut niveau (je suis surtout intéressé par le C et le C++)?

Des exemples de Code et de points de référence sont les bienvenus!

Answer 1

souvent, les gens ... et de l'état que les programmeurs peuvent généralement prédire où une branche pourrait aller

Les programmeurs expérimentés souvent de rappeler que les programmeurs humains sont très mauvais pour prédire que. (*)

1 - Est-il possible d'éviter branche mispredictions à l'aide de certains de haut niveau technique de programmation (pas de montage)?

Pas dans la norme c++ ou c. Du moins, pas pour une seule branche. Ce que vous pouvez faire est de minimiser la profondeur de votre dépendance des chaînes de sorte que la direction de la mauvaise prédiction n'aurait aucun effet. Les processeurs modernes exécutera les deux chemins de code de la branche et les déposer celui qui n'a pas été choisie. Il y a une limite à cela, cependant, qui est pourquoi la direction de la prévision seules les questions en profondeur de la dépendance des chaînes.

Certains compilateurs fournit une extension pour suggérer la prédiction manuellement comme l' __builtin_attendent dans gcc. Voici une stackoverflow question à ce sujet. Mieux encore, certains compilateurs (comme gcc) soutien profilage du code et de détecter automatiquement les prédictions optimales. Il est intelligent d'utiliser le profilage plutôt que de travail manuel à cause de (*).

2 - Que dois-je garder à l'esprit pour produire de la branche sympathique du code dans un langage de programmation de haut niveau (je suis surtout intéressé par le C et le C++)?

Principalement, vous devez garder à l'esprit que la direction de la mauvaise prédiction est seulement va vous affecter dans les plus critiques pour les performances de la partie de votre programme et ne vous inquiétez pas à ce sujet jusqu'à ce que vous avez mesuré et a trouvé un problème.

Mais que puis-je faire lorsque certains profils (valgrind, VTune, ...) indique que sur la ligne n de foo.cpp j'ai eu une branche de prédiction de la peine?

Lundin a donné de très judicieux conseils

1. Mesurer fo savoir si elle compte.
2. Si c'est important, alors
   • Minimiser la profondeur de la dépendance des chaînes de vos calculs. Comment faire qui peut être assez compliqué et au-delà de mes compétences, et il n'y a pas beaucoup que vous pouvez faire sans plonger dans l'assemblée. Ce que vous pouvez faire dans un langage de haut niveau est de minimiser le nombre de la réserve de vérifications (**). Sinon, vous êtes à la merci d'optimisation du compilateur. Évitant profond de la dépendance des chaînes permet également une utilisation plus efficace de l'out-of-order superscalar processeurs.
   • Faire vos branches constamment prévisible. L'effet de ce que peut être vu dans cette stackoverflow question. Dans la question, il y a une boucle sur un tableau. La boucle contient une branche. La direction dépend de la taille de l'élément courant. Lorsque les données ont été triées, la boucle peut être démontré d'être beaucoup plus rapide lorsqu'il est compilé avec un compilateur et de l'exécuter sur un processeur en particulier. Bien sûr, toutes vos données triées sera également le coût des temps cpu, peut-être plus que la direction de la mis-prédictions ne sont, donc, mesure.
3. Si c'est encore un problème, utilisez le profil guidée de l'optimisation (si disponible).

De l'ordre de 2. et 3. peut être activé. L'optimisation de votre code à la main, c'est beaucoup de travail. D'autre part, la collecte de données de profilage peut être difficile pour certains programmes.

(**) Une façon de le faire est de transformer vos boucles, par exemple, en les déroulant. Vous pouvez aussi laisser l'optimiseur de le faire automatiquement. Vous devez mesurer si, en raison de dérouler va affecter la façon dont vous interagissez avec le cache et peut très bien finir par être un pessimization.

Answer 2

Le noyau Linux définit les macros likely et unlikely basées sur les commandes internes __builtin_expect gcc:

     #define likely(x)   __builtin_expect(!!(x), 1)
    #define unlikely(x) __builtin_expect(!!(x), 0)
 

(Voir ici pour les définitions de macros en include/linux/compiler.h )

Vous pouvez les utiliser comme:

 if (likely(a > 42)) {
    /* ... */
} 
 

ou

 if (unlikely(ret_value < 0)) {
    /* ... */
}
 

Answer 3

La technique la plus courante est peut-être d'utiliser des méthodes distinctes pour les retours normaux et les retours d'erreur. C n'a pas le choix, mais C ++ a des exceptions. Les compilateurs savent que les branches d'exception sont exceptionnelles et donc inattendues.

Cela signifie que les branches d'exception sont en effet lentes, car elles ne sont pas prévues, mais la branche sans erreur est rendue plus rapide. En moyenne, c'est une victoire nette.

Answer 4

En général c'est une bonne idée pour garder les boucles internes bien proportionné à la taille de cache le plus fréquemment rencontré. C'est, si votre programme traite les données dans des morceaux de, disons, moins de 32kbytes à un moment et à un montant décent de travail, alors vous êtes à la bonne utilisation du cache L1.

En revanche, si votre intérieur chaud en boucle à mâcher à travers 100MByte de données et effectue une seule opération sur chaque élément de données, puis le CPU va passer la plupart du temps, de l'extraction de données à partir de la mémoire DRAM.

Ceci est important car une partie de la raison Processeurs direction de la prévision, en premier lieu, pour être en mesure de pré-extraction des opérandes de l'instruction suivante. Les conséquences des performances d'une branche mal de prédiction peut être réduit par l'organisation de votre code pour qu'il y ait une bonne chance que la prochaine proviennent les données de cache L1 n'importe quelle branche est prise. Bien que n'étant pas une stratégie parfaite, le cache L1 tailles semblent être universellement coincé sur 32 ou 64 KO; c'est presque une constante chose dans l'industrie. Certes, le codage de cette façon n'est pas souvent simple, et en s'appuyant sur le profil de conduit d'optimisation, etc. comme recommandé par les autres, est probablement la façon la plus simple de l'avant.

Indépendamment de toute autre chose, que ce soit ou pas un problème avec la direction de la mauvaise prédiction va se produire varie en fonction de la cache du CPU tailles, quoi d'autre est en cours d'exécution sur la machine, ce que la mémoire principale de la bande passante et la latence, etc.

Answer 5

1 - Est-il possible d'éviter branche mispredictions à l'aide de certains de haut niveau technique de programmation (pas de montage)?

Éviter? Peut-être pas. Réduire? Certainement...

2 - Que dois-je garder à l'esprit pour produire de la branche sympathique du code dans un langage de programmation de haut niveau (je suis surtout intéressé par le C et le C++)?

Il est intéressant de noter que l'optimisation pour une machine qui n'est pas forcément d'optimisation pour l'autre. Avec cela à l'esprit, profil guidée d'optimisation est assez bonne à réorganiser les branches, basée sur le test d'entrée vous la donner. Cela signifie que vous n'avez pas besoin de faire toute la programmation pour effectuer cette optimisation, et il devrait être relativement adapté à n'importe quelle machine vous êtes profilage sur. Évidemment, les meilleurs résultats seront obtenus lors de votre entrée de test et la machine vous profil correspond plus ou moins à ce que les attentes communes... mais ce sont aussi des considérations pour tous les autres optimisations, direction de la prévision du lié.