Pourquoi un coup conditionnel n'est pas vulgaire

Question

Après avoir lu ce billet (réponse sur StackOverflow) (à la section d'optimisation), je me demandais pourquoi les coups conditionnels ne sont pas vulnérables à l'échec de la prédiction de branche. J'ai trouvé sur un article sur les mouvements de cond ici (PDF par AMD) . Là aussi, ils revendiquent l'avantage de performance des mouvements de cond. Mais pourquoi cela ? Je ne le vois pas. Au moment où cette instruction ASM est évaluée, le résultat de l'instruction CMP précédente n'est pas encore connu.

Answer 1

Il s'agit de la pipeline d'instructions . N'oubliez pas que les CPU modernes exécutent leurs instructions dans un pipeline, ce qui permet d'améliorer considérablement les performances lorsque le flux d'exécution est prévisible par le CPU.

cmov

    add     eax, ebx
    cmp     eax, 0x10
    cmovne  ebx, ecx
    add     eax, ecx

---

Au moment où cette instruction ASM est évaluée, le résultat de l'instruction CMP précédente n'est pas encore connu.

Peut-être, mais le CPU sait toujours que l'instruction qui suit la cmov sera exécuté juste après, quel que soit le résultat de la fonction cmp y cmov l'instruction. L'instruction suivante peut donc être recherchée/décodée à l'avance en toute sécurité, ce qui n'est pas le cas avec les branches.

L'instruction suivante pourrait même être exécutée avant l'instruction cmov fait (dans mon exemple, cela serait sûr)

branche

    add     eax, ebx
    cmp     eax, 0x10
    je      .skip
    mov     ebx, ecx
.skip:
    add     eax, ecx

Dans ce cas, lorsque le décodeur du CPU voit je .skip il devra choisir s'il veut continuer à préextraire/décoder les instructions soit 1) à partir de l'instruction suivante, soit 2) à partir de la cible du saut. Le CPU va supposer que ce branchement conditionnel direct ne se produira pas, donc l'instruction suivante mov ebx, ecx ira dans le pipeline.

Quelques cycles plus tard, le je .skip est exécuté et la branche est prise. Et zut ! Notre pipeline contient maintenant des déchets aléatoires qui ne devraient jamais être exécutés. Le CPU doit vider toutes ses instructions en cache et repartir de zéro. .skip: .

C'est la pénalité de performance des branches mal prédites, ce qui ne peut jamais arriver avec cmov puisqu'il ne modifie pas le flux d'exécution.

Answer 2

En effet, le résultat peut ne pas être encore connu, mais si d'autres circonstances le permettent (en particulier, la chaîne de dépendance), le cpu peut réordonner et exécuter les instructions en suivant la méthode cmov . Comme il n'y a pas de branchement, ces instructions doivent être évaluées dans tous les cas.

Prenons cet exemple :

cmoveq edx, eax
add ecx, ebx
mov eax, [ecx]

Les deux instructions qui suivent le cmov ne dépendent pas du résultat de la cmov afin qu'ils puissent être exécutés même si l cmov lui-même est en attente (c'est ce qu'on appelle exécution hors service ). Même s'ils ne peuvent pas être exécutés, ils peuvent toujours être récupérés et décodés.

Une version ramifiée pourrait être :

    jne skip
    mov edx, eax
skip:
    add ecx, ebx
    mov eax, [ecx]

Le problème ici est que le flux de contrôle change et que le processeur n'est pas assez intelligent pour voir qu'il pourrait simplement "insérer" la partie sautée. mov instruction si la branche a été mal prédite comme prise - au lieu de cela, il jette tout ce qu'il a fait après la branche, et redémarre à partir de zéro. C'est de là que vient la pénalité.

Answer 3

Vous devriez les lire. Avec Fog+Intel, il suffit de chercher CMOV.

La critique de Linus Torvald sur l'OCMV vers 2007
Comparaison des microarchitectures par Agner Fog
Manuel de référence sur l'optimisation des architectures Intel® 64 et IA-32

En bref, les prédictions correctes sont "gratuites" alors que les mauvaises prédictions de branche conditionnelle peuvent coûter 14 à 20 cycles sur Haswell. Cependant, la CMOV n'est jamais gratuite. Pourtant, je pense que CMOV est beaucoup mieux maintenant que lorsque Torvalds a fulminé. Il n'y a pas une seule réponse correcte pour tout le temps sur tous les processeurs jamais.

Answer 4

J'ai cette illustration de la diapositive de [Peter Puschner et al.] qui explique comment il se transforme en code à chemin unique, et accélère l'exécution.