c++ Pourquoi g++ transfère-t-il les calculs dans une boucle chaude?




gcc assembly (3)

J'ai un comportement de compilateur très étrange où G ++ tire les calculs dans une boucle chaude, réduisant considérablement les performances du code résultant. Qu'est-ce qui se passe ici?

Considérons cette fonction:

#include <cstdint>

constexpr bool noLambda = true;

void funnyEval(const uint8_t* columnData, uint64_t dataOffset, uint64_t dictOffset, int32_t iter, int32_t limit, int32_t* writer,const int32_t* dictPtr2){
   // Computation X1
   const int32_t* dictPtr = reinterpret_cast<const int32_t*>(columnData + dictOffset);
   // Computation X2
   const uint16_t* data = (const uint16_t*)(columnData + dataOffset);
   // 1. The less broken solution without lambda
   if (noLambda) {
        for (;iter != limit;++iter){
            int32_t t=dictPtr[data[iter]];
            *writer = t;
            writer++;
        }
   }
   // 2. The totally broken solution with lambda
   else {
        auto loop = [=](auto body) mutable { for (;iter != limit;++iter){ body(iter); } };
        loop([=](unsigned index) mutable {
            int32_t t=dictPtr[data[index]];
            *writer = t;
            writer++;
        });
   }
}

Le problème ici est que G ++ aime en quelque sorte extraire les calculs X1 et X2 dans la boucle principale chaude, ce qui réduit les performances. Voici les détails:

La fonction itère simplement sur les data un tableau, recherche une valeur dans un dictionnaire dictPtr et l'écrit dans un writer emplacement de mémoire cible. data et dictPtr sont calculés au début de la fonction. Pour ce faire, il a deux saveurs: l’une avec un lambda, l’autre sans.

(Notez que cette fonction est juste un exemple de travail minimal de code beaucoup plus compliqué. Donc, évitez de dire que le lambda est inutile ici. Je suis conscient de ce fait et, malheureusement, dans le code d'origine, il est nécessaire.)

Le problème lors de la compilation avec le dernier g ++ (essayé 8.1 et 7.2, même problème avec les anciens g ++ que vous pouvez voir dans les liens de godbolt fournis) avec un niveau d'optimisation élevé ( -O3 -std=c++14 ) est le suivant :

La solution 2. ( noLambda=false ) génère un très mauvais code pour la boucle, encore pire que la solution "naïve", car elle suppose qu'il est judicieux d'extraire les calculs X1 et X2, qui se trouvent en dehors de la boucle principale super chaude. , dans la boucle principale super chaude, ce qui le rend environ 25% plus lent sur mon processeur.

https://godbolt.org/g/MzbxPN

.L3:
        movl    %ecx, %eax          # unnecessary extra work
        addl    $1, %ecx
        addq    $4, %r9             # separate loop counter (pointer increment)
        leaq    (%rdi,%rax,2), %rax # array indexing with an LEA
        movzwl  (%rax,%rsi), %eax   # rax+rsi is Computation X2, pulled into the loop!
        leaq    (%rdi,%rax,4), %rax # rax+rdx is Computation X1, pulled into the loop!
        movl    (%rax,%rdx), %eax   
        movl    %eax, -4(%r9)
        cmpl    %ecx, %r8d
        jne     .L3

Lorsque vous utilisez une boucle for habituelle ( noLambda=true ), le code est meilleur car X2 n'est plus tiré dans la boucle, mais X1 l'est toujours !:

https://godbolt.org/g/eVG75m

.L3:
        movzwl  (%rsi,%rax,2), %ecx
        leaq    (%rdi,%rcx,4), %rcx
        movl    (%rcx,%rdx), %ecx # This is Computation X1, pulled into the loop!
        movl    %ecx, (%r9,%rax,4)
        addq    $1, %rax
        cmpq    %rax, %r8
        jne     .L3

Vous pouvez essayer qu'il dictPtr vraiment de X1 dans la boucle en remplaçant dictPtr (le calcul X1) dans la boucle par dictPtr2 (un paramètre), l'instruction disparaîtra:

https://godbolt.org/g/nZ7TjJ

.L3:
        movzwl  (%rdi,%rax,2), %ecx
        movl    (%r10,%rcx,4), %ecx
        movl    %ecx, (%r9,%rax,4)
        addq    $1, %rax
        cmpq    %rax, %rdx
        jne     .L3

C'est finalement la boucle que je veux avoir. Une boucle simple qui charge les valeurs et stocke le résultat sans y introduire des calculs aléatoires.

Que se passe-t-il? C'est rarement une bonne idée de tirer un calcul dans une boucle chaude, mais G ++ semble le penser ici. Cela me coûte de vraies performances. Le lambda exacerbe toute la situation; cela amène G ++ à introduire encore plus de calculs dans la boucle.

Ce qui rend ce problème si grave, c'est qu'il s'agit d'un code C ++ vraiment trivial, sans fonctionnalités sophistiquées. Si je ne peux pas compter sur le fait que mon compilateur produise un code parfait pour un exemple aussi trivial, je devrai vérifier l'assemblage de toutes les boucles dynamiques de mon code pour m'assurer que tout est aussi rapide que possible. Cela signifie également qu'il y a probablement un très grand nombre de programmes touchés par cela.


J'ai essayé de lancer votre code et ... surprise: les instructions exécutées lorsque vous êtes dans la boucle ne sont pas celles que vous voyez dans le lien de l'explorateur du compilateur que vous avez posté. Vérifiez ceci (j'ai ajouté une fonction principale) https://godbolt.org/g/PPYtQa Les instructions exécutées pendant que vous êtes dans la boucle sont 162-167, c'est-à-dire

.L15:
        movzwl  25(%rbx,%rdx), %ecx
        movl    5(%rbx,%rcx,4), %ecx
        movl    %ecx, 0(%rbp,%rdx,2)
        addq    $2, %rdx
        cmpq    $180, %rdx
        jne     .L15

Vous pouvez vérifier cela en compilant sur votre machine

g++ test.cpp -std=c++1z -g -O3

et courir avec gdb

> gdb a.out
(gdb) break funnyEval
(gdb) layout split #shows assebly
(gdb) stepi #steps to the next instruction

Le compilateur génère une version différente non en ligne de funnyEval (celle que vous avez vue dans la sortie désassemblée), même si celle qui est réellement utilisée est en ligne. Je ne sais pas (encore) pourquoi les deux sont différents, mais je suppose que si une pénalité de performance vous pénalise, vous pouvez la réparer en vous assurant que funnyEval est en ligne: soit en définissant dans un fichier d'en-tête, soit en compilant et en liant avec optimisation du temps de liaison (-flto). Je vais essayer de voir ce qui se passe quand funnyEval est dans une autre unité de traduction ...


Vous utilisez un type 32 bits non signé pour l'index de tableau (ligne 21). Cela oblige le compilateur à considérer à chaque étape de la boucle si vous avez dépassé sa plage disponible, auquel cas il doit revenir au début du tableau. Le code supplémentaire que vous voyez est lié à cette vérification! Il y a au moins trois façons d'éviter cette approche trop prudente de la part du compilateur:

  1. Utilisez un type 64 bits pour l'index sur la ligne 21. Maintenant, le compilateur sait que vous ne bouclerez jamais le tableau et générerez le même code que celui sans le lambda.
  2. Utilisez un type 32 bits signé pour l'index sur la ligne 21. Désormais, le compilateur ne se préoccupe plus du débordement: le débordement signé est considéré comme un UB et donc ignoré. Je considère cela comme un bug dans l'interprétation de la norme, mais les avis divergent à ce sujet.
  3. Indiquez clairement au compilateur qu'un débordement ne se produira jamais, en ajoutant une ligne 'int32_t iter = 0;' au début de la fonction et en supprimant iter de la déclaration. Clairement, cela ne résout pas votre problème, mais cela montre comment c'est l'analyse de débordement qui génère le code supplémentaire.

Vous ne vous plaignez pas du code avant le début de la boucle, mais le même problème se pose. Faites juste iter et limitez int64_t, et vous verrez que cela devient beaucoup plus court car le compilateur ne considère plus la possibilité de débordement de tableau.

Donc, pour résumer: ce n’est pas le calcul de X1 et X2 qui est déplacé dans la boucle qui provoque la taille de la bulle, mais l’utilisation d’une variable d’index de tableau mal typée.


Félicitations, vous avez trouvé un bogue gcc . La solution principale consiste à le signaler sur le site bugzilla de GCC à l' aide du mot clé "optimisation manquée". Vos MCVE sont déjà d'excellents cas de test pour le bogue, vous ne devriez donc pas en prendre trop de temps pour en écrire un. Copiez / collez le code et une description. Un lien vers ce Q & A, et un lien vers le code sur http://godbolt.org/ , serait également utile.

Parfois, il existe des raisons microarchitecturales subtiles d'utiliser des instructions "extra", telles que xor réinitialiser la destination de popcnt / lzcnt ou bsf pour éviter une fausse dépendance à l'égard des processeurs Intel , mais ce n'est pas le cas ici. C'est juste mauvais; Le movl %ecx, %eax à l'intérieur de la boucle peut résulter de l'utilisation d'un type non signé plus étroit qu'un pointeur, mais même cela pourrait être fait plus efficacement. c'est aussi une optimisation manquée.

Je n'ai pas consulté les images GIMPLE ou RTL (représentations internes) de GCC pour en savoir plus. La seule utilisation des valeurs calculées étant à l'intérieur de la boucle, je peux donc imaginer que la représentation interne de la logique du programme du compilateur a peut-être perdu la différence entre l'intérieur et l'extérieur de la boucle lors de la transformation. Normalement, les objets qui n'ont pas besoin d'être dans la boucle sont hissés ou sortis de la boucle.

Mais malheureusement, il n'est pas rare que gcc laisse une instruction mov supplémentaire dans une boucle afin de configurer le code en dehors de la boucle. Surtout quand il peut prendre plusieurs instructions en dehors de la boucle pour obtenir le même effet. C'est généralement un mauvais compromis lors de l'optimisation des performances plutôt que de la taille du code. Je n'ai pas regardé autant que je le voudrais la sortie de l'optimisation par profil, pour voir le code dans lequel gcc sait quelles boucles sont vraiment chaudes et les a déroulées. Mais la plupart du code est construit sans PGO, malheureusement, donc code-gen sans -fprofile-use est toujours très important.

Cependant, l’essentiel de cette question n’est pas de savoir comment obtenir cet exemple particulier le plus rapidement possible. Au lieu de cela, je suis plutôt confiant sur la façon dont le compilateur peut produire de telles désoptimisations dans un extrait de code aussi simple. Mon problème principal est maintenant: j'ai en quelque sorte perdu confiance en mon compilateur, je veux donc comprendre comment cela peut se produire pour pouvoir le récupérer.

Ne faites pas confiance au gcc! C'est une machine très complexe qui donne souvent de bons résultats, mais produit rarement des résultats optimaux.

Cette affaire est l’un des mauvais choix les plus évidents et les plus simples que j’ai vu son optimiseur faire (et qui soit assez décevant), cependant. Habituellement, les optimisations manquées sont un peu plus subtiles (et reposent sur des détails microarchitecturaux tels que les choix de mode d'adressage et les ports uops / execution), ou du moins, ne sont pas si évidentes à éviter. (Hissez cette instruction sans changer aucune allocation de registre pour la boucle entière.)

Mais de nombreuses boucles goulot d’étranglement sur la mémoire et non sur le débit. Les processeurs modernes sont conçus pour tenir compte des instructions inutiles générées par les compilateurs, en particulier les compilateurs JIT. C’est la raison pour laquelle les optimisations manquées de ce type n’ont généralement pas beaucoup d’impact à l’échelle macro et que les cas dans lesquels elles sont importantes (par exemple, les encodeurs vidéo ou les multiplications matricielles) utilisent encore souvent des blocs d’asm manuscrit.

Il est souvent possible de manipuler gcc pour créer de bons asm en implémentant votre source de manière structurée comme vous le souhaitez. (Comme dans ce cas: quel est le moyen efficace de compter les bits définis à une position ou moins?, Et voir Pourquoi ce code C ++ est-il plus rapide que mon assemblage écrit à la main pour tester la conjecture de Collatz?, Pour une réponse plus générale sur la façon d'aider le compilateur vs battre le compilateur avec asm écrit à la main)

Mais quand votre compilateur est en train de se perdre comme ça, vous ne pouvez rien faire. Eh bien, sauf chercher des solutions de contournement, ou des choses comme éviter les entiers unsigned plus étroits que les pointeurs que d'autres réponses ont souligné comme étant importants.

Fait intéressant, le pire des cas (2 instructions LEA supplémentaires dans la boucle, plus l'utilisation de compteurs de boucles supplémentaires) ne se produit qu'avec votre if (noLambda) .

Si vous créez 2 versions distinctes de la fonction et supprimez le if , la version nolambda crée une belle boucle propre (mais manque la vectorisation automatique de la collecte, ce qui serait un gain si vous -march=skylake avec -march=skylake ).

Je mets votre code sur l'explorateur du compilateur Godbolt . (Également intéressant, utilisez -funroll-loops pour voir quelles parties sont refaites à chaque itération de boucle déroulée, et lesquelles se trouvent simplement une fois dans la boucle.)

# gcc7.2:  the nolamba side of the if, with no actual if()
.L3:
    movzwl  (%rsi,%rax,2), %ecx
    movl    (%rdx,%rcx,4), %ecx
    movl    %ecx, (%r9,%rax,4)   # indexed store: no port 7
    addq    $1, %rax             # gcc8 -O3 -march=skylake uses inc to save a code byte here.
    cmpq    %rax, %r8
    jne     .L3

Sur Intel Sandybridge-famille, cela décode à 5 uops. (La macro-fusion de cmp / jcc transforme cette paire en 1 uop. Les autres instructions sont toutes simples: uppod; movzwl est une charge pure et ne nécessite pas de port ALU).

Le magasin décolle sur SnB / IvB (ce qui représente un coût supplémentaire pour l'étape de développement 4 larges, l'un des principaux goulots d'étranglement de la face avant), mais peut rester fusionné sur HSW / SKL. Toutefois, il ne peut pas utiliser le port 7 (car il est indexé), ce qui signifie que HSW / SKL serait limité à 2 opérations de mémoire par horloge, pas 3.

Goulots d'étranglement:

  • Bande passante d'émission frontale de 4 UOP à domaine fondu par horloge. La boucle est de 5 uops, et peut émettre à près de 1 itération pour 1,25. (Les boucles non-multiples de 4 ne sont pas parfaites, mais 5 oups sont gérées correctement sur Haswell / Skylake au moins . Peut-être pas Sandybridge.)

  • Ports d’exécution de chargement / stockage: Haswell et les versions ultérieures peuvent exécuter 2 charges + 1 magasin par horloge, mais uniquement lorsque le magasin évite un mode d’adressage indexé afin que l’adresse de magasin uop puisse être exécutée sur le port 7.

la version lambda reçoit un compteur de movl %ecx, %eax boucle (incrément de pointeur) et un movl %ecx, %eax stupide movl %ecx, %eax , mais les instructions LEA restent en dehors de la boucle.

Mais ce n'est pas le calcul supplémentaire en soi, c'est le débit total uop qui nuit probablement à votre boucle. Si le dictionnaire reste principalement en cache, un processeur Haswell ou ultérieur

J'allais écrire plus, mais je n'ai pas fini. Publier maintenant parce que la partie générique début / milieu est apparemment l’objet de la question. Ne faites pas aveuglément confiance à gcc.

Et ne vous attendez pas à ce qu’il produise un code optimal la plupart du temps. Vous pouvez souvent gagner 10 ou 20% en modifiant simplement la source C (et parfois beaucoup plus). Parfois, gcc ne semble tout simplement pas avoir la moindre idée, comme utiliser des lea supplémentaires sans aucune raison apparente lors du déroulement, au lieu d’utiliser un déplacement dans un mode d’adressage. Je pense que son modèle de coût en mode d'adressage ne doit pas être précis, du moins pour -march=haswell / -march=skylake .





compiler-optimization