wandbox - online compiler c++17




Pourquoi GCC génère-t-il un code de 15 à 20% plus rapide si j'optimise pour la taille au lieu de la vitesse? (4)

J'ajoute cette post-acceptation pour souligner que les effets de l'alignement sur la performance globale des programmes - y compris les grands - ont été étudiés. Par exemple, cet article (et je crois qu'une version de ceci est également apparue dans CACM) montre comment l'ordre de lien et les changements de taille d'environnement d'OS seuls étaient suffisants pour décaler les performances de manière significative. Ils attribuent cela à l'alignement des "boucles chaudes".

Ce document, intitulé "Produire de mauvaises données sans rien faire de toute évidence faux!" dit que le biais expérimental involontaire dû à des différences presque incontrôlables dans les environnements de fonctionnement du programme rend probablement beaucoup de résultats de référence sans signification.

Je pense que vous rencontrez un angle différent sur la même observation.

Pour le code critique en termes de performances, il s'agit d'un bon argument pour les systèmes qui évaluent l'environnement lors de l'installation ou de l'exécution et choisissent le meilleur local parmi les versions optimisées différentes des routines de clé.

J'ai d'abord remarqué en 2009 que GCC (au moins sur mes projets et sur mes machines) a tendance à générer du code sensiblement plus rapide si -Os pour la taille ( -Os ) au lieu de la vitesse ( -O2 ou -O3 ), et j'ai été Je me demandais depuis pourquoi.

J'ai réussi à créer (plutôt bête) un code qui montre ce comportement surprenant et qui est suffisamment petit pour être posté ici.

const int LOOP_BOUND = 200000000;

__attribute__((noinline))
static int add(const int& x, const int& y) {
    return x + y;
}

__attribute__((noinline))
static int work(int xval, int yval) {
    int sum(0);
    for (int i=0; i<LOOP_BOUND; ++i) {
        int x(xval+sum);
        int y(yval+sum);
        int z = add(x, y);
        sum += z;
    }
    return sum;
}

int main(int , char* argv[]) {
    int result = work(*argv[1], *argv[2]);
    return result;
}

Si je le compile avec -Os , il faut 0,38 s pour exécuter ce programme, et 0,44 s s'il est compilé avec -O2 ou -O3 . Ces temps sont obtenus de manière cohérente et pratiquement sans bruit (gcc 4.7.2, x86_64 GNU / Linux, Intel Core i5-3320M).

(Mise à jour: j'ai déplacé tout le code d'assemblage vers GitHub : ils ont rendu le message gonflé et apparemment n'ajoutent que peu de valeur aux questions car les fno-align-* ont le même effet.)

Voici l'assembly généré avec -Os et -O2 .

Malheureusement, ma compréhension de l'assemblage est très limitée, donc je n'ai aucune idée si ce que j'ai fait ensuite était correct: j'ai attrapé l'assemblage pour -O2 et fusionné toutes ses différences dans l'assemblage pour -Os sauf les lignes .p2align , résultat here . Ce code fonctionne toujours en 0.38s et la seule différence est le truc .p2align .

Si je devine correctement, ce sont des paddings pour l'alignement de pile. D'après Pourquoi le pad GCC fonctionne-t-il avec les NOP? c'est fait dans l'espoir que le code fonctionnera plus vite, mais apparemment cette optimisation s'est retournée dans mon cas.

Est-ce le rembourrage qui est le coupable dans ce cas? Pourquoi et comment?

Le bruit qu'il fait à peu près rend les micro-optimisations de synchronisation impossibles.

Comment puis-je m'assurer que de tels alignements accidentels chanceux / malchanceux n'interfèrent pas lorsque je fais des micro-optimisations (sans rapport avec l'alignement de la pile) sur le code source C ou C ++?

METTRE À JOUR:

À la suite de la réponse de Pascal Cuoq, j'ai bricolé un peu avec les alignements. En passant -O2 -fno-align-functions -fno-align-loops à gcc, tous les .p2align sont partis de l'assembly et l'exécutable généré s'exécute en 0.38s. Selon la documentation de gcc :

-Os active toutes les optimisations -O2 [mais] -Os désactive les indicateurs d'optimisation suivants:

  -falign-functions  -falign-jumps  -falign-loops <br/>
  -falign-labels  -freorder-blocks  -freorder-blocks-and-partition <br/>
  -fprefetch-loop-arrays <br/>

Donc, cela ressemble beaucoup à un problème (d'alignement).

Je suis toujours sceptique à propos de -march=native comme suggéré dans la réponse de Marat Dukhan . Je ne suis pas convaincu qu'il ne s'agit pas seulement d'interférer avec ce problème (d'erreur) d'alignement; cela n'a absolument aucun effet sur ma machine. (Néanmoins, j'ai upvoted sa réponse.)

MISE À JOUR 2:

Nous pouvons sortir de l'image. Les temps suivants sont obtenus en compilant avec

  • -O2 -fno-omit-frame-pointer 0.37s

  • -O2 -fno-align-functions -fno-align-loops 0.37s

  • -S -O2 puis en déplaçant manuellement l'assembly de add() après le work() 0.37s

  • -O2 0.44s

Il me semble que la distance de add() du site d'appel est importante. J'ai essayé perf , mais la sortie de perf stat et perf report me fait très peu de sens. Cependant, je n'ai pu obtenir qu'un seul résultat cohérent:

-O2 :

 602,312,864 stalled-cycles-frontend   #    0.00% frontend cycles idle
       3,318 cache-misses
 0.432703993 seconds time elapsed
 [...]
 81.23%  a.out  a.out              [.] work(int, int)
 18.50%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦       return x + y;
100.00 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   }
       ¦   ? retq
[...]
       ¦            int z = add(x, y);
  1.93 ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 79.79 ¦      add    %eax,%ebx

Pour fno-align-* :

 604,072,552 stalled-cycles-frontend   #    0.00% frontend cycles idle
       9,508 cache-misses
 0.375681928 seconds time elapsed
 [...]
 82.58%  a.out  a.out              [.] work(int, int)
 16.83%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦       return x + y;
 51.59 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   }
[...]
       ¦    __attribute__((noinline))
       ¦    static int work(int xval, int yval) {
       ¦        int sum(0);
       ¦        for (int i=0; i<LOOP_BOUND; ++i) {
       ¦            int x(xval+sum);
  8.20 ¦      lea    0x0(%r13,%rbx,1),%edi
       ¦            int y(yval+sum);
       ¦            int z = add(x, y);
 35.34 ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 39.48 ¦      add    %eax,%ebx
       ¦    }

Pour -fno-omit-frame-pointer :

 404,625,639 stalled-cycles-frontend   #    0.00% frontend cycles idle
      10,514 cache-misses
 0.375445137 seconds time elapsed
 [...]
 75.35%  a.out  a.out              [.] add(int const&, int const&) [clone .isra.0]                                                                                     ¦
 24.46%  a.out  a.out              [.] work(int, int)
 [...]
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
 18.67 ¦     push   %rbp
       ¦       return x + y;
 18.49 ¦     lea    (%rdi,%rsi,1),%eax
       ¦   const int LOOP_BOUND = 200000000;
       ¦
       ¦   __attribute__((noinline))
       ¦   static int add(const int& x, const int& y) {
       ¦     mov    %rsp,%rbp
       ¦       return x + y;
       ¦   }
 12.71 ¦     pop    %rbp
       ¦   ? retq
 [...]
       ¦            int z = add(x, y);
       ¦    ? callq  add(int const&, int const&) [clone .isra.0]
       ¦            sum += z;
 29.83 ¦      add    %eax,%ebx

Il semble que nous bloquons l'appel à add() dans le cas lent.

J'ai examiné tout ce que je peux cracher sur ma machine; pas seulement les statistiques qui sont données ci-dessus.

Pour le même exécutable, le stalled-cycles-frontend montre une corrélation linéaire avec le temps d'exécution; Je n'ai rien remarqué d'autre qui puisse corréler si clairement. (La comparaison de stalled-cycles-frontend pour différents exécutables n'a pas de sens pour moi.)

J'ai inclus les échecs de cache comme il est apparu comme le premier commentaire. J'ai examiné tous les échecs de cache qui peuvent être mesurés sur ma machine par perf , pas seulement ceux donnés ci-dessus. Les échecs de cache sont très très bruyants et montrent peu ou pas de corrélation avec les temps d'exécution.


Je ne suis en aucun cas un expert dans ce domaine, mais je crois me souvenir que les processeurs modernes sont très sensibles en matière de prédiction de branchement . Les algorithmes utilisés pour prédire les branches sont (ou au moins étaient de retour dans les jours où j'ai écrit le code assembleur) en fonction de plusieurs propriétés du code, y compris la distance d'une cible et la direction.

Le scénario qui me vient à l'esprit est celui des petites boucles. Quand la branche reculait et que la distance n'était pas trop loin, la prédiction de branche optimisait pour ce cas puisque toutes les petites boucles sont faites de cette façon. Les mêmes règles peuvent entrer en jeu lorsque vous permutez l'emplacement de l' add et du work dans le code généré ou lorsque la position des deux change légèrement.

Cela dit, je n'ai aucune idée de comment vérifier cela et je voulais juste vous faire savoir que c'est quelque chose que vous voulez examiner.


Mon collègue m'a aidé à trouver une réponse plausible à ma question. Il a remarqué l'importance de la limite de 256 octets. Il n'est pas inscrit ici et m'a encouragé à poster la réponse moi-même (et à prendre toute la célébrité).

Réponse courte:

Est-ce le rembourrage qui est le coupable dans ce cas? Pourquoi et comment?

Tout se résume à l'alignement. Les alignements peuvent avoir un impact significatif sur la performance, c'est pourquoi nous avons les -falign-* en premier lieu.

J'ai soumis un rapport de bogue (bidon?) Aux développeurs de gcc . Il s'avère que le comportement par défaut est "nous alignons des boucles à 8 octets par défaut, mais essayons de l'aligner sur 16 octets si nous n'avons pas besoin de remplir plus de 10 octets." Apparemment, ce défaut n'est pas le meilleur choix dans ce cas particulier et sur ma machine. Clang 3.4 (tronc) avec -O3 fait l'alignement approprié et le code généré ne montre pas ce comportement étrange.

Bien sûr, si un alignement inapproprié est fait, cela aggrave les choses. Un alignement inutile / incorrect ne fait qu'alimenter les octets sans raison et augmente potentiellement les échecs de cache, etc.

Le bruit qu'il fait à peu près rend les micro-optimisations de synchronisation impossibles.

Comment puis-je m'assurer que de tels alignements accidentels chanceux / malchanceux n'interfèrent pas lorsque je fais des micro-optimisations (sans rapport avec l'alignement de la pile) sur les codes source C ou C ++?

Simplement en disant à gcc de faire le bon alignement:

g++ -O2 -falign-functions=16 -falign-loops=16

Longue réponse:

Le code sera plus lent si:

  • une limite de XX octets coupe add() au milieu ( XX étant dépendant de la machine).

  • si l'appel à add() doit sauter par-dessus une limite d'octet XX et que la cible n'est pas alignée.

  • si add() n'est pas aligné.

  • si la boucle n'est pas alignée.

Les 2 premiers sont magnifiquement visibles sur les codes et les résultats que Marat Dukhan a gentiment posté . Dans ce cas, gcc-4.8.1 -Os (s'exécute en 0.994 secondes):

00000000004004fd <_ZL3addRKiS0_.isra.0>:
  4004fd:       8d 04 37                lea    eax,[rdi+rsi*1]
  400500:       c3   

une limite de 256 octets coupe add() juste au milieu et ni add() ni la boucle n'est alignée. Surprise, surprise, c'est le cas le plus lent!

Dans le cas où gcc-4.7.3 -Os (s'exécute en 0.822 sec), la limite de 256 octets ne coupe que dans une section froide (mais ni la boucle ni add() sont coupées):

00000000004004fa <_ZL3addRKiS0_.isra.0>:
  4004fa:       8d 04 37                lea    eax,[rdi+rsi*1]
  4004fd:       c3                      ret

[...]

  40051a:       e8 db ff ff ff          call   4004fa <_ZL3addRKiS0_.isra.0>

Rien n'est aligné et l'appel à add() doit sauter par-dessus la limite de 256 octets. Ce code est le deuxième plus lent.

Dans le cas où gcc-4.6.4 -Os (s'exécute en 0.709 sec), bien que rien ne soit aligné, l'appel à add() n'a pas à sauter par-dessus la frontière de 256 octets et la cible est exactement à 32 octets:

  4004f2:       e8 db ff ff ff          call   4004d2 <_ZL3addRKiS0_.isra.0>
  4004f7:       01 c3                   add    ebx,eax
  4004f9:       ff cd                   dec    ebp
  4004fb:       75 ec                   jne    4004e9 <_ZL4workii+0x13>

C'est le plus rapide des trois. Pourquoi la frontière de 256 octets est speacial sur sa machine, je lui laisserai le soin de le comprendre. Je n'ai pas un tel processeur.

Maintenant, sur ma machine, je n'ai pas cet effet de frontière de 256 octets. Seule la fonction et l'alignement de la boucle interviennent sur ma machine. Si je passe g++ -O2 -falign-functions=16 -falign-loops=16 alors tout est de retour à la normale: je reçois toujours le cas le plus rapide et le temps n'est plus sensible au drapeau -fno-omit-frame-pointer . Je peux passer g++ -O2 -falign-functions=32 -falign-loops=32 ou des multiples de 16, le code n'est pas non plus sensible à ça.

J'ai d'abord remarqué en 2009 que gcc (au moins sur mes projets et sur mes machines) a tendance à générer du code notablement plus rapide si j'optimise pour la taille (-Os) au lieu de la vitesse (-O2 ou -O3) et je me demandais depuis quand.

Une explication probable est que j'avais des points chauds qui étaient sensibles à l'alignement, tout comme celui de cet exemple. En jouant avec les drapeaux (en passant -Os au lieu de -O2 ), ces hotspots ont été alignés d'une manière chanceuse par accident et le code est devenu plus rapide. Cela n'avait rien à voir avec l'optimisation de la taille: ce fut par un simple accident que les hotspots s'alignèrent mieux. A partir de maintenant, je vais vérifier les effets de l'alignement sur mes projets.

Oh, et encore une chose. Comment de tels points chauds peuvent-ils apparaître, comme celui montré dans l'exemple? Comment l'inlining d'une fonction aussi minuscule comme add() échouer?

Considère ceci:

// add.cpp
int add(const int& x, const int& y) {
    return x + y;
}

et dans un fichier séparé:

// main.cpp
int add(const int& x, const int& y);

const int LOOP_BOUND = 200000000;

__attribute__((noinline))
static int work(int xval, int yval) {
    int sum(0);
    for (int i=0; i<LOOP_BOUND; ++i) {
        int x(xval+sum);
        int y(yval+sum);
        int z = add(x, y);
        sum += z;
    }
    return sum;
}

int main(int , char* argv[]) {
    int result = work(*argv[1], *argv[2]);
    return result;
}

et compilé comme: g++ -O2 add.cpp main.cpp .

gcc ne va pas add() !

C'est tout, c'est si facile de créer involontairement des hotspots comme celui de l'OP. Bien sûr, c'est en partie de ma faute: gcc est un excellent compilateur. Si compilez ci-dessus comme: g++ -O2 -flto add.cpp main.cpp , c'est-à-dire, si g++ -O2 -flto add.cpp main.cpp optimisation du temps de lien, le code s'exécute en 0.19s!

(Inlining est artificiellement désactivé dans l'OP, par conséquent, le code dans l'OP était 2x plus lent).


Par défaut, les compilateurs optimisent pour le processeur "moyen". Puisque différents processeurs favorisent différentes séquences d'instructions, les optimisations de compilateur activées par -O2 peuvent bénéficier au processeur moyen, mais diminuer les performances sur votre processeur particulier (et la même chose s'applique à -Os ). Si vous essayez le même exemple sur différents processeurs, vous constaterez que certains d'entre eux bénéficient de -O2 alors que d'autres sont plus favorables aux optimisations -Os .

Voici les résultats pour le time ./test 0 0 sur plusieurs processeurs (temps utilisateur signalé):

Processor (System-on-Chip)             Compiler   Time (-O2)  Time (-Os)  Fastest
AMD Opteron 8350                       gcc-4.8.1    0.704s      0.896s      -O2
AMD FX-6300                            gcc-4.8.1    0.392s      0.340s      -Os
AMD E2-1800                            gcc-4.7.2    0.740s      0.832s      -O2
Intel Xeon E5405                       gcc-4.8.1    0.603s      0.804s      -O2
Intel Xeon E5-2603                     gcc-4.4.7    1.121s      1.122s       -
Intel Core i3-3217U                    gcc-4.6.4    0.709s      0.709s       -
Intel Core i3-3217U                    gcc-4.7.3    0.708s      0.822s      -O2
Intel Core i3-3217U                    gcc-4.8.1    0.708s      0.944s      -O2
Intel Core i7-4770K                    gcc-4.8.1    0.296s      0.288s      -Os
Intel Atom 330                         gcc-4.8.1    2.003s      2.007s      -O2
ARM 1176JZF-S (Broadcom BCM2835)       gcc-4.6.3    3.470s      3.480s      -O2
ARM Cortex-A8 (TI OMAP DM3730)         gcc-4.6.3    2.727s      2.727s       -
ARM Cortex-A9 (TI OMAP 4460)           gcc-4.6.3    1.648s      1.648s       -
ARM Cortex-A9 (Samsung Exynos 4412)    gcc-4.6.3    1.250s      1.250s       -
ARM Cortex-A15 (Samsung Exynos 5250)   gcc-4.7.2    0.700s      0.700s       -
Qualcomm Snapdragon APQ8060A           gcc-4.8       1.53s       1.52s      -Os

Dans certains cas, vous pouvez alléger l'effet des optimisations désavantageuses en demandant à gcc d'optimiser pour votre processeur particulier (en utilisant les options -mtune=native ou -march=native ):

Processor            Compiler   Time (-O2 -mtune=native) Time (-Os -mtune=native)
AMD FX-6300          gcc-4.8.1         0.340s                   0.340s
AMD E2-1800          gcc-4.7.2         0.740s                   0.832s
Intel Xeon E5405     gcc-4.8.1         0.603s                   0.803s
Intel Core i7-4770K  gcc-4.8.1         0.296s                   0.288s

Mise à jour: sur Core i3 basé sur Ivy Bridge, trois versions de gcc ( 4.6.4 , 4.7.3 et 4.8.1 ) produisent des binaires avec des performances significativement différentes, mais le code d'assemblage n'a que des variations subtiles. Jusqu'à présent, je n'ai aucune explication de ce fait.

Assemblage à partir de gcc-4.6.4 -Os (s'exécute en 0.709 secondes):

00000000004004d2 <_ZL3addRKiS0_.isra.0>:
  4004d2:       8d 04 37                lea    eax,[rdi+rsi*1]
  4004d5:       c3                      ret

00000000004004d6 <_ZL4workii>:
  4004d6:       41 55                   push   r13
  4004d8:       41 89 fd                mov    r13d,edi
  4004db:       41 54                   push   r12
  4004dd:       41 89 f4                mov    r12d,esi
  4004e0:       55                      push   rbp
  4004e1:       bd 00 c2 eb 0b          mov    ebp,0xbebc200
  4004e6:       53                      push   rbx
  4004e7:       31 db                   xor    ebx,ebx
  4004e9:       41 8d 34 1c             lea    esi,[r12+rbx*1]
  4004ed:       41 8d 7c 1d 00          lea    edi,[r13+rbx*1+0x0]
  4004f2:       e8 db ff ff ff          call   4004d2 <_ZL3addRKiS0_.isra.0>
  4004f7:       01 c3                   add    ebx,eax
  4004f9:       ff cd                   dec    ebp
  4004fb:       75 ec                   jne    4004e9 <_ZL4workii+0x13>
  4004fd:       89 d8                   mov    eax,ebx
  4004ff:       5b                      pop    rbx
  400500:       5d                      pop    rbp
  400501:       41 5c                   pop    r12
  400503:       41 5d                   pop    r13
  400505:       c3                      ret

Assemblage à partir de gcc-4.7.3 -Os (s'exécute en 0.822 secondes):

00000000004004fa <_ZL3addRKiS0_.isra.0>:
  4004fa:       8d 04 37                lea    eax,[rdi+rsi*1]
  4004fd:       c3                      ret

00000000004004fe <_ZL4workii>:
  4004fe:       41 55                   push   r13
  400500:       41 89 f5                mov    r13d,esi
  400503:       41 54                   push   r12
  400505:       41 89 fc                mov    r12d,edi
  400508:       55                      push   rbp
  400509:       bd 00 c2 eb 0b          mov    ebp,0xbebc200
  40050e:       53                      push   rbx
  40050f:       31 db                   xor    ebx,ebx
  400511:       41 8d 74 1d 00          lea    esi,[r13+rbx*1+0x0]
  400516:       41 8d 3c 1c             lea    edi,[r12+rbx*1]
  40051a:       e8 db ff ff ff          call   4004fa <_ZL3addRKiS0_.isra.0>
  40051f:       01 c3                   add    ebx,eax
  400521:       ff cd                   dec    ebp
  400523:       75 ec                   jne    400511 <_ZL4workii+0x13>
  400525:       89 d8                   mov    eax,ebx
  400527:       5b                      pop    rbx
  400528:       5d                      pop    rbp
  400529:       41 5c                   pop    r12
  40052b:       41 5d                   pop    r13
  40052d:       c3                      ret

Assemblage à partir de gcc-4.8.1 -Os (s'exécute en 0.994 secondes):

00000000004004fd <_ZL3addRKiS0_.isra.0>:
  4004fd:       8d 04 37                lea    eax,[rdi+rsi*1]
  400500:       c3                      ret

0000000000400501 <_ZL4workii>:
  400501:       41 55                   push   r13
  400503:       41 89 f5                mov    r13d,esi
  400506:       41 54                   push   r12
  400508:       41 89 fc                mov    r12d,edi
  40050b:       55                      push   rbp
  40050c:       bd 00 c2 eb 0b          mov    ebp,0xbebc200
  400511:       53                      push   rbx
  400512:       31 db                   xor    ebx,ebx
  400514:       41 8d 74 1d 00          lea    esi,[r13+rbx*1+0x0]
  400519:       41 8d 3c 1c             lea    edi,[r12+rbx*1]
  40051d:       e8 db ff ff ff          call   4004fd <_ZL3addRKiS0_.isra.0>
  400522:       01 c3                   add    ebx,eax
  400524:       ff cd                   dec    ebp
  400526:       75 ec                   jne    400514 <_ZL4workii+0x13>
  400528:       89 d8                   mov    eax,ebx
  40052a:       5b                      pop    rbx
  40052b:       5d                      pop    rbp
  40052c:       41 5c                   pop    r12
  40052e:       41 5d                   pop    r13
  400530:       c3                      ret




assembly