J'ai remarqué pour la première fois en 2009 que GCC (au moins sur mes projets et sur mes machines) a tendance à générer un code sensiblement plus rapide si j'optimise pour la taille ( -Os) au lieu de la vitesse ( -O2ou -O3), et je me demande depuis pourquoi.
J'ai réussi à créer (plutôt stupide) du code qui montre ce comportement surprenant et est suffisamment petit pour être publié 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 -O2ou -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'assembly vers GitHub : ils ont gonflé le message et fno-align-*n'ont apparemment ajouté que très peu de valeur aux questions car les indicateurs ont le même effet.)
Voici l'assembly généré avec -Oset -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 -O2et j'ai fusionné toutes ses différences dans l'assemblage, à l' -Os exception des .p2alignlignes, résultat ici . Ce code fonctionne toujours en 0.38s et la seule différence est le .p2align truc.
Si je suppose correctement, ce sont des rembourrages pour l'alignement de la pile. Selon Pourquoi le pad GCC fonctionne-t-il avec les NOP? cela se fait dans l'espoir que le code fonctionnera plus rapidement, mais apparemment cette optimisation s'est retournée contre moi.
Est-ce le rembourrage qui est le coupable dans ce cas? Pourquoi et comment?
Le bruit qu'il fait rend la synchronisation des micro-optimisations impossible.
Comment puis-je m'assurer que ces alignements chanceux / malchanceux accidentels 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 ++?
MISE À JOUR:
Suite à la réponse de Pascal Cuoq, j'ai bricolé un peu les alignements. En passant -O2 -fno-align-functions -fno-align-loopsà gcc, tous .p2alignsont 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 de -O2 [mais] -Os désactive les indicateurs d'optimisation suivants:
-falign-functions -falign-jumps -falign-loops -falign-labels -freorder-blocks -freorder-blocks-and-partition -fprefetch-loop-arrays
Donc, cela ressemble à peu près à un (mauvais) alignement.
Je reste sceptique, -march=nativecomme le suggère la réponse de Marat Dukhan . Je ne suis pas convaincu que cela n'interfère pas seulement avec ce (mauvais) problème d'alignement; cela n'a absolument aucun effet sur ma machine. (Néanmoins, j'ai surévalué sa réponse.)
MISE À JOUR 2:
Nous pouvons retirer -Osde l'image. Les temps suivants sont obtenus en compilant avec
-O2 -fno-omit-frame-pointer0,37 s-O2 -fno-align-functions -fno-align-loops0,37 s-S -O2puis déplacer manuellement l'assemblageadd()aprèswork()0,37 s-O20,44 s
Il me semble que la distance par add()rapport au site d'appel compte beaucoup. J'ai essayé perf, mais la sortie de perf statet perf reportn'a que très peu de sens pour moi. Cependant, je n'ai pu en obtenir qu'un 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 retardions l'appel add()dans le cas lent.
J'ai examiné tout ce qui perf -epeut cracher sur ma machine; pas seulement les statistiques qui sont données ci-dessus.
Pour le même exécutable, la stalled-cycles-frontendmontre une corrélation linéaire avec le temps d'exécution; Je n'ai rien remarqué d'autre qui puisse corréler aussi clairement. (Comparer stalled-cycles-frontendpour différents exécutables n'a pas de sens pour moi.)
J'ai inclus les échecs de cache lors de son premier commentaire. J'ai examiné toutes les erreurs de cache qui peuvent être mesurées sur ma machine perf, pas seulement celles indiquées 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.
Réponses:
Par défaut, les compilateurs optimisent pour le processeur "moyen". Étant donné que différents processeurs favorisent différentes séquences d'instructions, les optimisations du compilateur activées par
-O2peuvent bénéficier au processeur moyen, mais diminuent 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 sur certains d'entre eux en bénéficient-O2alors que d'autres sont plus favorables aux-Osoptimisations.Voici les résultats pour
time ./test 0 0plusieurs processeurs (temps utilisateur rapporté):Dans certains cas, vous pouvez atténuer l'effet des optimisations désavantageuses en demandant
gccd'optimiser pour votre processeur particulier (en utilisant des options-mtune=nativeou-march=native):Mise à jour: sur le Core i3 basé sur Ivy Bridge, trois versions de
gcc(4.6.4,4.7.3et4.8.1) produisent des binaires avec des performances sensiblement différentes, mais le code d'assemblage n'a que de subtiles variations. 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 s):Assemblage à partir de
gcc-4.7.3 -Os(s'exécute en 0,822 s):Assemblage à partir de
gcc-4.8.1 -Os(s'exécute en 0,994 secondes):la source
-O2 -fno-align-functions -fno-align-loops, le temps passe à0.340s, donc cela pourrait être expliqué par l'alignement. Cependant, l'alignement optimal dépend du processeur: certains processeurs préfèrent les boucles et les fonctions alignées.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 renommée).
Réponse courte:
Tout se résume à l'alignement. Les alignements peuvent avoir un impact significatif sur les performances, c'est pourquoi nous avons les
-falign-*drapeaux en premier lieu.J'ai soumis un rapport de bogue (faux?) Aux développeurs de gcc . Il s'avère que le comportement par défaut est "nous alignons les boucles sur 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
-O3fait l'alignement approprié et le code généré ne montre pas ce comportement étrange.Bien sûr, si un alignement inapproprié est effectué, cela empire les choses. Un alignement inutile / mauvais mange juste des octets sans raison et augmente potentiellement les échecs de cache, etc.
Simplement en disant à gcc de faire le bon alignement:
g++ -O2 -falign-functions=16 -falign-loops=16Longue réponse:
Le code s'exécutera plus lentement si:
une
XXlimite d'octet coupeadd()au milieu (XXen fonction de la machine).si l'appel à
add()doit dépasser uneXXlimite d'octets 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):une limite de 256 octets coupe
add()en plein milieu et niadd()ni la boucle n'est alignée. Surprise, surprise, c'est le cas le plus lent!Dans le cas
gcc-4.7.3 -Os(s'exécute en 0,822 s), la limite de 256 octets ne coupe que dans une section froide (mais ni la boucle, ni laadd()coupe):Rien n'est aligné et l'appel à
add()doit dépasser la limite de 256 octets. Ce code est le deuxième plus lent.Dans le cas
gcc-4.6.4 -Os(s'exécute en 0,709 s), bien que rien ne soit aligné, l'appel àadd()ne doit pas franchir la limite de 256 octets et la cible est exactement à 32 octets:C'est le plus rapide des trois. Pourquoi la limite de 256 octets est spéciale sur sa machine, je vais lui laisser le soin de le comprendre. Je n'ai pas un tel processeur.
Maintenant, sur ma machine, je n'obtiens pas cet effet de limite de 256 octets. Seules la fonction et l'alignement de boucle interviennent sur ma machine. Si je passe,
g++ -O2 -falign-functions=16 -falign-loops=16tout redevient normal: j'ai toujours le cas le plus rapide et le temps n'est plus sensible au-fno-omit-frame-pointerdrapeau. Je peux passerg++ -O2 -falign-functions=32 -falign-loops=32ou tout multiple de 16, le code n'y est pas sensible non plus.Une explication probable est que j'avais des hotspots qui étaient sensibles à l'alignement, tout comme celui de cet exemple. En jouant avec les drapeaux (en passant à la
-Osplace de-O2), ces points chauds ont été alignés de manière chanceuse par accident et le code est devenu plus rapide. Cela n'avait rien à voir avec l'optimisation de la taille: c'était par pur accident que les points chauds s'alignaient mieux. Désormais, je vérifierai les effets de l'alignement sur mes projets.Oh, et encore une chose. Comment de tels hotspots peuvent-ils apparaître, comme celui illustré dans l'exemple? Comment l'échec d'une fonction aussi minuscule comme l'
add()échec?Considère ceci:
et dans un fichier séparé:
et compilé comme:
g++ -O2 add.cpp main.cpp.gcc ne sera pas en ligne
add()!C'est tout, c'est aussi simple que cela 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 vous compilez ce qui précède en tant
g++ -O2 -flto add.cpp main.cppque :, c'est-à-dire si j'effectue une optimisation du temps de liaison, le code s'exécute en 0.19s!(L'inline est artificiellement désactivé dans l'OP, par conséquent, le code dans l'OP était 2x plus lent).
la source
inlinedéfinition de la fonction + dans l'en-tête. Je ne sais pas à quel point le lto est mature dans gcc. Mon expérience avec au moins à mingw est un succès.-flto. c'est assez révolutionnaire si vous ne l'avez jamais utilisé auparavant, en parlant d'expérience :)J'ajoute ce post-accept 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 celui-ci est également apparu dans CACM) montre comment les modifications de l'ordre des liens et de la taille de l'environnement du système d'exploitation suffisaient à elles seules à modifier considérablement les performances. Ils attribuent cela à l'alignement des "boucles chaudes".
Ce document, intitulé "Produire des données erronées sans rien faire de mal!" dit qu'un biais expérimental par inadvertance dû à des différences presque incontrôlables dans les environnements d'exécution de programme rend probablement de nombreux résultats de référence dénués de sens.
Je pense que vous rencontrez un angle différent sur la même observation.
Pour le code critique pour les performances, c'est un très 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 différemment optimisées des routines clés.
la source
Je pense que vous pouvez obtenir le même résultat que ce que vous avez fait:
… En utilisant
-O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1. Je compile tout avec ces options, qui étaient plus rapides que tout le temps à-O2chaque fois que je me donnais la peine de mesurer, depuis 15 ans.De plus, pour un contexte complètement différent (y compris un compilateur différent), j'ai remarqué que la situation est similaire : l'option qui est censée «optimiser la taille du code plutôt que la vitesse» optimise la taille et la vitesse du code.
Non, cela n'a rien à voir avec la pile, les NOP générés par défaut et que les options -falign - * = 1 empêchent sont pour l'alignement du code.
Il est très probable que le rembourrage soit le coupable. La raison pour laquelle le remplissage est jugé nécessaire et utile dans certains cas est que le code est généralement récupéré en lignes de 16 octets (voir les ressources d'optimisation d'Agner Fog pour les détails, qui varient selon le modèle de processeur). L'alignement d'une fonction, d'une boucle ou d'une étiquette sur une limite de 16 octets signifie que les chances sont statistiquement augmentées qu'une ligne de moins soit nécessaire pour contenir la fonction ou la boucle. De toute évidence, cela se retourne contre car ces NOP réduisent la densité du code et donc l'efficacité du cache. Dans le cas de boucles et d'étiquettes, les NOP peuvent même devoir être exécutés une fois (lorsque l'exécution arrive normalement à la boucle / étiquette, par opposition à un saut).
la source
-O2 -fno-omit-frame-pointerest tout aussi bon que-Os. Veuillez vérifier la question mise à jour.Si votre programme est limité par le cache CODE L1, l'optimisation de la taille commence soudainement à payer.
Lors de ma dernière vérification, le compilateur n'est pas assez intelligent pour comprendre cela dans tous les cas.
Dans votre cas, -O3 génère probablement suffisamment de code pour deux lignes de cache, mais -O tient dans une seule ligne de cache.
la source
-falign-*=16drapeaux, tout revient à la normale, tout se comporte de façon cohérente. En ce qui me concerne, cette question est résolue.Je ne suis en aucun cas un expert dans ce domaine, mais je semble me souvenir que les processeurs modernes sont assez sensibles en matière de prédiction de branche . Les algorithmes utilisés pour prédire les branches sont (ou du moins étaient à l'époque où j'ai écrit le code assembleur) basés sur 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. Lorsque la branche reculait et que la distance n'était pas trop éloignée, la prédiction de la branche était optimisée pour ce cas car toutes les petites boucles se font de cette façon. Les mêmes règles peuvent entrer en jeu lorsque vous échangez l'emplacement de
addetworkdans le code généré ou lorsque la position des deux change légèrement.Cela dit, je ne sais pas comment vérifier cela et je voulais juste vous faire savoir que cela pourrait être quelque chose que vous souhaitez examiner.
la source
add()etwork()si-O2c'est passé. Dans tous les autres cas, le code ralentit considérablement en échangeant. Au cours du week-end, j'ai également analysé les statistiques de prédiction / mauvaise prédiction de branche avecperfet je n'ai rien remarqué qui pourrait expliquer ce comportement bizarre. Le seul résultat cohérent est que dans le cas lent, ilperfindique 100,0 poucesadd()et une grande valeur sur la ligne juste après l'appel àadd()dans la boucle. Il semble que nous stagnons pour une raison quelconqueadd()dans le cas lent mais pas dans les courses rapides.perfne prend en charge qu'un nombre limité de choses, peut-être que les trucs d'Intel sont un peu plus pratiques sur leur propre processeur.