Un saut coûteux avec GCC 5.4.0

J'avais une fonction qui ressemblait à ceci (ne montrant que la partie importante):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) && (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

Écrit comme ça, la fonction a pris environ 34 ms sur ma machine. Après avoir changé la condition en multiplication booléenne (faisant ressembler le code à ceci):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) * (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

le temps d'exécution a diminué à ~ 19 ms.

Le compilateur utilisé était GCC 5.4.0 avec -O3 et après avoir vérifié le code asm généré à l'aide de godbolt.org, j'ai découvert que le premier exemple génère un saut, tandis que le second ne le fait pas. J'ai décidé d'essayer GCC 6.2.0 qui génère également une instruction de saut lors de l'utilisation du premier exemple, mais GCC 7 ne semble plus en générer une.

Découvrir cette façon d'accélérer le code était plutôt horrible et a pris un certain temps. Pourquoi le compilateur se comporte-t-il de cette façon? Est-ce prévu et est-ce quelque chose que les programmeurs devraient rechercher? Y a-t-il d'autres choses similaires à cela?

EDIT: lien vers godbolt https://godbolt.org/g/5lKPF3

L'opérateur logique AND ( &&) utilise une évaluation de court-circuit, ce qui signifie que le deuxième test n'est effectué que si la première comparaison est évaluée à vrai. C'est souvent exactement la sémantique dont vous avez besoin. Par exemple, considérez le code suivant:

if ((p != nullptr) && (p->first > 0))

Vous devez vous assurer que le pointeur n'est pas nul avant de le déréférencer. S'il ne s'agissait pas d' une évaluation de court-circuit, vous auriez un comportement non défini car vous déréférenceriez un pointeur nul.

Il est également possible que l'évaluation des courts-circuits donne un gain de performance dans les cas où l'évaluation des conditions est un processus coûteux. Par exemple:

if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))

En cas d' DoLengthyCheck1échec, il ne sert à rien d'appeler DoLengthyCheck2.

Cependant, dans le binaire résultant, une opération de court-circuit se traduit souvent par deux branches, car c'est le moyen le plus simple pour le compilateur de conserver cette sémantique. (C'est pourquoi, de l'autre côté de la pièce, l'évaluation de court-circuit peut parfois inhiber le potentiel d'optimisation.) Vous pouvez le voir en regardant la partie pertinente du code objet généré pour votre ifdéclaration par GCC 5.4:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L5

    cmp     ax, 478           ; (l[i + shift] < 479)
    ja      .L5

    add     r8d, 1            ; nontopOverlap++

Vous voyez ici les deux comparaisons ( cmpinstructions) ici, chacune suivie d'un saut / branchement conditionnel séparé ( jaou d'un saut si ci-dessus).

En règle générale, les branches sont lentes et doivent donc être évitées dans les boucles serrées. Cela a été vrai sur pratiquement tous les processeurs x86, à partir de l'humble 8088 (dont les temps de récupération lents et la file d'attente de prélecture extrêmement petite [comparable à un cache d'instructions], combinés à une absence totale de prédiction de branche, signifiaient que les branches prises nécessitaient le vidage du cache ) aux implémentations modernes (dont les longs pipelines rendent les branches mal prévues tout aussi chères). Notez la petite mise en garde que j'ai glissée là-dedans. Les processeurs modernes depuis le Pentium Pro disposent de moteurs de prédiction de branche avancés conçus pour minimiser le coût des branches. Si la direction de la branche peut être correctement prédite, le coût est minime. La plupart du temps, cela fonctionne bien, mais si vous vous retrouvez dans des cas pathologiques où le prédicteur de branche n'est pas de votre côté,votre code peut devenir extrêmement lent . C'est probablement là que vous êtes ici, puisque vous dites que votre tableau n'est pas trié.

Vous dites que les benchmarks ont confirmé que le remplacement du &&par un *rend le code nettement plus rapide. La raison en est évidente lorsque nous comparons la partie pertinente du code objet:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    xor     r15d, r15d        ; (curr[i] < 479)
    cmp     r13w, 478
    setbe   r15b

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     ax, 478
    setbe   r14b

    imul    r14d, r15d        ; meld results of the two comparisons

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

Il est un peu contre-intuitif que cela puisse être plus rapide, car il y a plus d' instructions ici, mais c'est ainsi que l'optimisation fonctionne parfois. Vous voyez les mêmes comparaisons ( cmp) effectuées ici, mais maintenant, chacune est précédée d'un xoret suivi d'un setbe. Le XOR est juste une astuce standard pour effacer un registre. Il setbes'agit d'une instruction x86 qui définit un bit en fonction de la valeur d'un indicateur et est souvent utilisée pour implémenter du code sans branche. Ici, setbeest l'inverse de ja. Il met son registre de destination à 1 si la comparaison était inférieure ou égale (puisque le registre a été pré-mis à zéro, il sera à 0 dans le cas contraire), tandis que jaramifié si la comparaison était au-dessus. Une fois que ces deux valeurs ont été obtenues en r15betr14bregistres, ils sont multipliés ensemble en utilisant imul. La multiplication était traditionnellement une opération relativement lente, mais elle est sacrément rapide sur les processeurs modernes, et ce sera particulièrement rapide, car elle ne multiplie que deux valeurs de la taille d'un octet.

Vous pourriez tout aussi facilement avoir remplacé la multiplication par l'opérateur binaire AND ( &), qui ne fait pas d'évaluation de court-circuit. Cela rend le code beaucoup plus clair et constitue un modèle que les compilateurs reconnaissent généralement. Mais lorsque vous faites cela avec votre code et que vous le compilez avec GCC 5.4, il continue à émettre la première branche:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L4

    cmp     ax, 478           ; (l[i + shift] < 479)
    setbe   r14b

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

Il n'y a aucune raison technique pour qu'il émette le code de cette façon, mais pour une raison quelconque, ses heuristiques internes lui disent que c'est plus rapide. Ce serait probablement plus rapide si le prédicteur de branche était de votre côté, mais ce sera probablement plus lent si la prédiction de branche échoue plus souvent qu'elle ne réussit.

Les nouvelles générations du compilateur (et d'autres compilateurs, comme Clang) connaissent cette règle et l'utiliseront parfois pour générer le même code que vous auriez recherché en optimisant manuellement. Je vois régulièrement Clang traduire des &&expressions dans le même code qui aurait été émis si j'avais utilisé &. Voici la sortie pertinente de GCC 6.2 avec votre code en utilisant l' &&opérateur normal :

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L7

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r14b

    add     esi, r14d         ; nontopOverlap++

Notez comment intelligent c'est! Il utilise des conditions signées ( et ) par opposition à des conditions non signées ( et ), mais ce n'est pas important. Vous pouvez voir qu'il fait toujours la comparaison et la branche pour la première condition comme l'ancienne version, et utilise la même instruction pour générer du code sans branche pour la deuxième condition, mais il est devenu beaucoup plus efficace dans la façon dont il incrémente . Au lieu de faire une deuxième comparaison redondante pour définir les indicateurs d'une opération, il utilise la connaissance qui sera 1 ou 0 pour simplement ajouter cette valeur sans condition . Si est 0, l'addition est un non-op; sinon, il ajoute 1, exactement comme il est censé le faire.jgsetlejasetbesetCCsbbr14dnontopOverlapr14d

GCC 6.2 produit en fait un code plus efficace lorsque vous utilisez l' &&opérateur de court-circuit que l'opérateur au niveau du bit &:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L6

    cmp     eax, 478          ; (l[i + shift] < 479)
    setle   r14b

    cmp     r14b, 1           ; nontopOverlap++
    sbb     esi, -1

La branche et l'ensemble conditionnel sont toujours là, mais maintenant il revient à la manière moins intelligente d'incrémenter nontopOverlap. C'est une leçon importante sur les raisons pour lesquelles vous devez faire attention lorsque vous essayez de surpasser votre compilateur!

Mais si vous pouvez prouver avec des benchmarks que le code de branchement est en fait plus lent, alors il peut être payant d'essayer de surpasser votre compilateur. Il vous suffit de le faire en inspectant soigneusement le démontage et d'être prêt à réévaluer vos décisions lorsque vous effectuez une mise à niveau vers une version ultérieure du compilateur. Par exemple, le code que vous avez pourrait être réécrit comme suit:

nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));

Il n'y a aucune ifdéclaration ici du tout, et la grande majorité des compilateurs ne penseront jamais à émettre du code de branchement pour cela. GCC ne fait pas exception; toutes les versions génèrent quelque chose qui ressemble à ce qui suit:

    movzx   r14d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r14d, 478         ; (curr[i] < 479)
    setle   r15b

    xor     r13d, r13d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r13b

    and     r13d, r15d        ; meld results of the two comparisons
    add     esi, r13d         ; nontopOverlap++

Si vous avez suivi les exemples précédents, cela devrait vous sembler très familier. Les deux comparaisons sont effectuées sans branche, les résultats intermédiaires sont andédités ensemble, puis ce résultat (qui sera soit 0 soit 1) est addédité à nontopOverlap. Si vous voulez du code sans branche, cela garantira pratiquement que vous l'obteniez.

GCC 7 est devenu encore plus intelligent. Il génère maintenant un code pratiquement identique (à l'exception d'un léger réarrangement des instructions) pour l'astuce ci-dessus que le code d'origine. Donc, la réponse à votre question, "Pourquoi le compilateur se comporte-t-il de cette façon?" , c'est probablement parce qu'ils ne sont pas parfaits! Ils essaient d'utiliser l'heuristique pour générer le code le plus optimal possible, mais ils ne prennent pas toujours les meilleures décisions. Mais au moins, ils peuvent devenir plus intelligents avec le temps!

Une façon de regarder cette situation est que le code de branchement a le meilleur meilleur cas la performance. Si la prédiction de branche réussit, le fait de sauter des opérations inutiles entraînera une durée d'exécution légèrement plus rapide. Cependant, le code sans branche a les meilleures performances dans le pire des cas . Si la prédiction de branche échoue, exécuter quelques instructions supplémentaires nécessaires pour éviter une branche sera certainement plus rapide qu'une branche mal prédite. Même les compilateurs les plus intelligents et les plus intelligents auront du mal à faire ce choix.

Et pour votre question de savoir si c'est quelque chose que les programmeurs doivent surveiller, la réponse est presque certainement non, sauf dans certaines boucles chaudes que vous essayez d'accélérer via des micro-optimisations. Ensuite, vous vous asseyez avec le démontage et trouvez des moyens de le peaufiner. Et, comme je l'ai déjà dit, soyez prêt à revoir ces décisions lorsque vous mettez à jour vers une version plus récente du compilateur, car il peut soit faire quelque chose de stupide avec votre code délicat, soit avoir suffisamment changé son heuristique d'optimisation pour que vous puissiez revenir en arrière à utiliser votre code d'origine. Commentez attentivement!

Une chose importante à noter est que

(curr[i] < 479) && (l[i + shift] < 479)

et

(curr[i] < 479) * (l[i + shift] < 479)

ne sont pas sémantiquement équivalents! En particulier, le cas échéant, la situation où:

• 0 <= iet i < curr.size()sont tous les deux vrais
• curr[i] < 479 c'est faux
• i + shift < 0ou i + shift >= l.size()est vrai

alors l'expression (curr[i] < 479) && (l[i + shift] < 479)est garantie comme étant une valeur booléenne bien définie. Par exemple, cela ne provoque pas d'erreur de segmentation.

Cependant, dans ces circonstances, l'expression (curr[i] < 479) * (l[i + shift] < 479)est un comportement indéfini ; il est permis de provoquer un défaut de segmentation.

Cela signifie que pour l'extrait de code d'origine, par exemple, le compilateur ne peut pas simplement écrire une boucle qui effectue les deux comparaisons et effectue une andopération, à moins que le compilateur ne puisse également prouver que l[i + shift]cela ne provoquera jamais une erreur de segmentation dans une situation où il est obligé de ne pas le faire.

Bref, le morceau de code original offre moins de possibilités d'optimisation que ce dernier. (bien sûr, que le compilateur reconnaisse ou non l'opportunité est une question entièrement différente)

Vous pouvez corriger la version originale en faisant plutôt

bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
    // ...

L' &&opérateur met en œuvre une évaluation des courts-circuits. Cela signifie que le deuxième opérande n'est évalué que si le premier est évalué à true. Cela entraîne certainement un saut dans ce cas.

Vous pouvez créer un petit exemple pour montrer ceci:

#include <iostream>

bool f(int);
bool g(int);

void test(int x, int y)
{
  if ( f(x) && g(x)  )
  {
    std::cout << "ok";
  }
}

La sortie de l'assembleur peut être trouvée ici .

Vous pouvez voir le code généré pour les premiers appels f(x), puis vérifier la sortie et passer à l'évaluation du g(x)moment true. Sinon, il quitte la fonction.

L'utilisation de la multiplication "booléenne" force à la place l'évaluation des deux opérandes à chaque fois et ne nécessite donc pas de saut.

Selon les données, le saut peut provoquer un ralentissement car il perturbe le pipeline du CPU et d'autres choses comme l'exécution spéculative. Normalement, la prédiction de branche est utile, mais si vos données sont aléatoires, il n'y a pas grand-chose à prévoir.

Cela peut être dû au fait que lorsque vous utilisez l'opérateur logique, &&le compilateur doit vérifier deux conditions pour que l'instruction if réussisse. Cependant, dans le second cas, puisque vous convertissez implicitement une valeur int en booléen, le compilateur fait des hypothèses basées sur les types et les valeurs transmis, avec (éventuellement) une seule condition de saut. Il est également possible que le compilateur optimise complètement le jmps avec des décalages de bits.