Un saut coûteux avec GCC 5.4.0

Question

J'avais une fonction qui ressemblait à ça (montrant seulement 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 cela, la fonction a pris ~34ms sur ma machine. Après l'évolution de la condition de bool multiplication (faire le code ressemble à 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é de ~19ms.

Le compilateur utilisé est GCC 5.4.0 avec-O3 et après vérification de l'asm généré le code à l'aide godbolt.org j'ai trouvé que le premier exemple génère un saut, tandis que le second ne l'est pas. J'ai décidé d'essayer de GCC 6.2.0 qui génère également une instruction de saut lorsque vous utilisez le premier exemple, mais GCC 7 semble pas générer un plus.

Trouver de cette façon à accélérer le code a été plutôt macabre et a pris un certain temps. Pourquoi le compilateur se comporter de cette façon? Est-il prévu et est-ce quelque chose que les programmeurs devraient regarder dehors pour? Sont plus là des choses semblables à cela?

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

Answer 1

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

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

Vous devez vous assurer que le pointeur n'est pas null avant de déréférencement. Si ce n'était pas un court-circuit d'évaluation, vous auriez du avoir un comportement indéfini, parce que vous seriez un déréférencement d'un pointeur null.

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

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

Si DoLengthyCheck1 d'échec, il n'y a aucun point en appelant DoLengthyCheck2.

Toutefois, dans le binaire résultant, d'un court-circuit opération souvent des résultats en deux branches, car c'est le moyen le plus facile pour le compilateur afin de préserver ces sémantique. (C'est pourquoi, de l'autre côté de la pièce, de court-circuit d'évaluation peut parfois inhiber le potentiel d'optimisation.) Vous pouvez le voir en regardant la partie pertinente de l'objet code généré pour votre if énoncé 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 (cmp instructions) ici, chacun suivi par un saut conditionnel/branche (ja, ou de sauter si ci-dessus).

C'est une règle générale que les branches sont lents et sont donc à éviter dans les boucles serrées. Cela a été le cas sur presque tous les processeurs x86, de l'humble 8088 (dont la lente extraction fois et extrêmement petites prefetch de file d'attente [comparable à un cache d'instructions], combinée à l'absence totale de direction de la prévision, signifiait que les prises branches requis le cache à être sous-évaluées) pour les implémentations modernes (dont le long des pipelines faire mispredicted branches de même cher). Remarque le petit bémol que j'ai glissé dans. Les processeurs modernes depuis le Pentium Pro ont avancé de la direction de la prévision moteurs sont conçus pour réduire le coût de branches. Si la direction de la branche peuvent être correctement prédit, le coût est minime. La plupart du temps, cela fonctionne bien, mais si vous obtenez dans les cas pathologiques où la branche prédicteur n'est pas de votre côté, votre code peut être extrêmement lente. C'est sans doute où vous êtes, puisque vous dites que votre tableau est trié.

Vous dites que les points de référence a confirmé que le remplacement de l' && avec un * rend le code beaucoup plus rapidement. La raison pour cela est évident lorsque l'on compare la partie pertinente de l'objet code:

    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

C'est un peu contre-intuitif que cela pourrait être plus rapide, car il y a plus d' instructions ici, mais c'est ainsi que l'optimisation des œuvres parfois. Vous voyez la même comparaison (cmp) se fait ici, mais maintenant, chacun est précédé par un xor et suivie par un setbe. Le XOR est juste un truc standard pour la compensation d'un registre. L' setbe est une instruction x86 qui définit un peu en fonction de la valeur d'un indicateur, et est souvent utilisé pour mettre en œuvre sans branches code. Ici, setbe est l'inverse de la ja. Il définit son registre de destination à 1 si la comparaison était inférieur ou égal (depuis le registre a été pré-remise à zéro, il sera de 0 autrement), alors que l' ja ramifiée si la comparaison a été ci-dessus. Une fois ces deux valeurs ont été obtenues dans l' r15b et r14b registres, ils sont multipliées à l'aide de imul. La Multiplication a été traditionnellement relativement lent, mais c'est sacrément rapide sur les processeurs modernes, et ce sera particulièrement rapide, parce que c'est seulement la multiplication de deux octets de taille de valeurs.

Vous pourriez tout aussi bien avoir remplacé la multiplication avec le bit à bit ET de l'opérateur (&), qui ne fait pas de court-circuit de l'évaluation. Cela rend le code beaucoup plus clair, et est un motif que les compilateurs reconnaissent en général. Mais quand vous faites cela avec votre code et le compiler avec GCC 5.4, il continue à émettre de 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 pas de raison technique, il a eu à émettre le code de cette façon, mais pour une raison quelconque, son interne de l'heuristique dire que c'est plus rapide. Il serait probablement plus rapide si la branche prédicteur était de votre côté, mais il devrait être plus lente si la branche de prédiction échoue le plus souvent il réussit.

Les nouvelles générations de le compilateur (et d'autres compilateurs, comme Clang) connaître cette règle et parfois l'utiliser pour générer le même code que vous avez cherché par la main de l'optimisation. Je vais régulièrement voir Clang traduire && expressions du même code, qui auraient été émises si j'avais utilisé &. Ce qui suit est la sortie de GCC 6.2 avec votre code à l'aide de la normale && opérateur:

    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 est signé à l'aide de conditions (jg et setle) plutôt non signés conditions (ja et setbe), mais ce n'est pas important. Vous pouvez voir qu'il fait toujours les comparer-et-branche pour la première condition, comme l'ancienne version, et utilise le même setCC instructions pour générer dépourvu de branches de code pour la deuxième condition, mais il a obtenu beaucoup plus efficace dans la façon dont il fait l'incrément. Au lieu de faire un deuxième, redondant de comparaison pour définir les indicateurs pour un sbb de l'opération, il utilise les connaissances qu' r14d sera 1 ou 0 pour tout simplement sans condition d'ajouter cette valeur à nontopOverlap. Si r14d est égal à 0, la plus est un no-op; sinon, il ajoute 1, exactement comme il est censé le faire.

GCC 6.2 produit plus efficace du code lorsque vous utilisez le court-circuit && de l'opérateur de la bit-à-bit & opérateur:

    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 direction générale et les conditions à définir sont toujours là, mais maintenant il revient à la moins intelligente de l'incrémentation nontopOverlap. C'est une leçon importante dans pourquoi vous devez être prudent lors de la tentative de hors-intelligente votre compilateur!

Mais si vous pouvez prouver par des repères que la ramification code est en fait plus lentement, alors il peut payer pour essayer et intelligent de votre compilateur. Vous avez juste à le faire avec une inspection minutieuse de l'démontage et être prêt à ré-évaluer vos décisions lors de la mise à niveau vers une version ultérieure à la version 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 pas d' if déclaration ici, et la grande majorité des compilateurs ne pense jamais à en émettant de la ramification de code pour cela. GCC n'est pas une exception; toutes les versions de générer quelque chose de semblable à la suivante:

    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 le long avec les exemples précédents, ce devrait être très familier pour vous. Les deux comparaisons sont effectuées dans un dépourvu de branches manière, les résultats intermédiaires sont anded ensemble, et puis ce résultat (qui est soit 0 ou 1) est - added nontopOverlap. Si vous voulez dépourvu de branches de code, ce sera presque garantir que vous obtenez.

GCC 7 a obtenu encore plus intelligent. Il génère maintenant pratiquement identiques code (à l'exception d'un léger réaménagement des instructions) pour l'astuce ci-dessus que le code d'origine. Donc, la réponse à votre question, "Pourquoi le compilateur se comporter de cette façon?", est probablement parce qu'ils ne sont pas parfaits! Ils essaient d'utiliser des heuristiques pour générer le meilleur code possible, mais ils ne sont pas toujours prendre les meilleures décisions. Mais au moins, ils peuvent devenir plus intelligent avec le temps!

Une façon de voir cette situation est que la ramification code a le mieux dans le meilleur des cas de la performance. Si la branche de prédiction est couronnée de succès, de sauter des opérations inutiles aura pour résultat un peu plus vite de temps de fonctionnement. Cependant, sans branches code a le meilleur des cas les pires performances. Si la branche de prédiction de l'échec, de l'exécution de quelques instructions supplémentaires que nécessaire pour éviter une branche va certainement être plus rapide qu'une mispredicted branche. Même les plus intelligents et les plus intelligents de compilateurs ont du mal à faire ce choix.

Et pour votre question de savoir si c'est quelque chose que les programmeurs ont besoin pour regarder dehors pour, la réponse est presque certainement pas, sauf dans certaines chaude boucles que vous essayez d'accélérer par l'intermédiaire de micro-optimisations. Ensuite, vous vous asseyez avec le démontage et de trouver des moyens de le tordre. Et, comme je l'ai dit avant, être préparé à revenir sur ces décisions lorsque vous mettez à jour vers une nouvelle version du compilateur, car il peut faire quelque chose de stupide avec votre délicat code, ou elle peut avoir changé d'optimisation heuristique assez que vous pouvez revenir en arrière à l'aide de votre code d'origine. Commentaires à fond!

Answer 2

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 équivalentes! En particulier, si jamais vous avez la situation où:

• 0 <= i et i < curr.size() sont à la fois vrai
• curr[i] < 479 est faux
• i + shift < 0 ou i + shift >= l.size() est vrai

puis l'expression (curr[i] < 479) && (l[i + shift] < 479) est garanti pour être bien définir la valeur booléenne. Par exemple, il 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 autorisé à provoquer une erreur de segmentation.

Cela signifie que pour l'original de l'extrait de code, par exemple, le compilateur ne peut pas simplement écrire une boucle qui effectue à la fois des comparaisons et un and de l'opération, à moins que le compilateur peut également prouver qu' l[i + shift] ne sera jamais la cause d'une erreur de segmentation dans une situation, il est nécessaire de ne pas.

En bref, l'original de ce morceau de code offre moins de possibilités pour l'optimisation de ce dernier. (bien sûr, si oui ou non le compilateur reconnaît l'occasion est une question entièrement différente)

Vous pouvez corriger la version originale en au lieu de faire

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

Answer 3

L' && de l'opérateur met en œuvre évaluation de court-circuit. Cela signifie que le deuxième opérande n'est évaluée que si le premier évalue true. Il y a certainement des résultats dans 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";
  }
}

L'assembleur de sortie peut être trouvé ici.

Vous pouvez voir le code généré premiers appels f(x), puis vérifie la sortie et les sauts à l'évaluation de l' g(x) lorsqu'il s'agissait d' true. Sinon, il quitte la fonction.

À l'aide de "boolean" la multiplication à la place des forces de l'évaluation des deux opérandes à chaque fois et n'a donc pas besoin d'un saut.

Selon les données, le saut peut provoquer un ralentissement, car il perturbe le pipeline du PROCESSEUR et d'autres choses comme spéculative de l'exécution. Normalement, direction de la prévision aide, mais si vos données est aléatoire, il n'y a pas beaucoup qui peut être prédit.

Answer 4

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, étant donné que vous convertissez implicitement une valeur int en une valeur booléenne, le compilateur émet certaines hypothèses en fonction des types et des valeurs transmis, ainsi que d'une éventuelle condition de saut. Il est également possible que le compilateur optimise complètement les jmps avec des décalages de bits.