Pourquoi les optimiseurs C ++ ont-ils des problèmes avec ces variables temporaires ou plutôt pourquoi v devrait-il être évité dans les boucles serrées?

Il semble que le compilateur manque de connaissances sur la relation entre std::vector<>::size() et la taille du tampon vectoriel interne. Considérez std::vector comme notre bugged_vector vectoriel personnalisé bugged_vector avec un léger bug – its ::size() peut parfois être un de plus que la taille du tampon interne n , mais seulement alors v[n-2] >= v[n-1] .

Ensuite, deux fragments ont encore une sémantique différente: le premier a un comportement indéfini, car nous v[v.size() - 1] élément v[v.size() - 1] . Le second, cependant, n’a pas: à cause de la nature de court-circuit de && , nous ne lisons jamais v[v.size() - 1] lors de la dernière itération.

Donc, si le compilateur ne peut pas prouver que notre v n’est pas un bugged_vector , il doit court-circuiter, ce qui introduit un saut supplémentaire dans un code machine.

En regardant la sortie de assembly de clang , nous pouvons voir que cela se produit réellement.

Depuis le Godbolt Comstackr Explorer , avec clang 3.7.0 -O2, la boucle dans f0 est:

 ### f0: just the loop .LBB1_2: # =>This Inner Loop Header: Depth=1 mov edi, ecx cmp edx, edi setl r10b mov ecx, dword ptr [r8 + 4*rsi + 4] lea rsi, [rsi + 1] cmp edi, ecx setl dl and dl, r10b movzx edx, dl add eax, edx cmp rsi, r9 mov edx, edi jb .LBB1_2 

Et pour f1 :

 ### f1: just the loop .LBB2_2: # =>This Inner Loop Header: Depth=1 mov esi, r10d mov r10d, dword ptr [r9 + 4*rdi] lea rcx, [rdi + 1] cmp esi, r10d jge .LBB2_4 # <== This is Extra Jump cmp r10d, dword ptr [r9 + 4*rdi + 4] setl dl movzx edx, dl add eax, edx .LBB2_4: # %._crit_edge.3 cmp rcx, r8 mov rdi, rcx jb .LBB2_2 

J'ai souligné le saut supplémentaire dans f1 . Et comme nous le souhaitons (espérons-le), les sauts conditionnels dans les boucles serrées sont mauvais pour la performance. (Voir les guides de performances dans le wiki de balises x86 pour plus de détails.)

GCC et Visual Studio sont conscients que std::vector se comporte bien et produisent un assemblage presque identique pour les deux extraits. Modifier Il s'avère que clang fait un meilleur travail pour optimiser le code. Les trois compilateurs ne peuvent pas prouver qu'il est sûr de lire v[i + 1] avant la comparaison dans le deuxième exemple (ou de ne pas le faire), mais seul clang parvient à optimiser le premier exemple avec les informations supplémentaires v[i + 1] est soit valide soit UB.

Une différence de performance de 2% est négligeable peut être expliquée par un ordre différent ou le choix de certaines instructions.

Voici un aperçu supplémentaire à développer sur la réponse de @deniss, qui a correctement diagnostiqué le problème.

Incidemment, cela est lié au plus populaire des questions-réponses C ++ de tous les temps “Pourquoi le traitement d’un tableau sortingé est-il plus rapide qu’un tableau non sortingé?” .

Le problème principal est que le compilateur doit respecter l’opérateur logique AND (&&) et ne pas charger à partir de v [i + 1] sauf si la première condition est vraie. Ceci est une conséquence de la sémantique de l’opérateur logique ainsi que de la sémantique du modèle de mémoire renforcée introduite avec C ++ 11, les clauses pertinentes du brouillon de la norme sont:

5.14 Opérateur logique AND [expr.log.and]

Contrairement à & , && garantit une évaluation de gauche à droite: le second opérande n’est pas évalué si le premier opérande est faux .
_{Norme ISO C ++ 14 (projet N3797)}

et pour les lectures spéculatives

1.10 Exécutions multithread et courses de données [intro.multithread]

23 [ Remarque: les transformations qui introduisent une lecture spéculative d’un emplacement de mémoire potentiellement partagé peuvent ne pas préserver la sémantique du programme C ++ tel que défini dans la présente norme, car elles introduisent potentiellement une course de données. Cependant, ils sont généralement valides dans le contexte d’un compilateur d’optimisation qui cible une machine spécifique avec une sémantique bien définie pour les courses de données. Ils seraient invalides pour une machine hypothétique qui ne tolère pas les courses ou assure la détection de la course matérielle. – note finale ]
_{Norme ISO C ++ 14 (projet N3797)}

Je suppose que les optimiseurs jouent de manière sûre et choisissent actuellement de ne pas émettre de charges spéculatives sur la mémoire potentiellement partagée plutôt que de créer un cas particulier pour chaque processeur cible, que la charge spéculative puisse introduire une course de données détectable pour cette cible.

Pour implémenter cela, le compilateur génère une twig conditionnelle. Généralement, cela ne se remarque pas, car les processeurs modernes ont une prédiction de twig très sophistiquée et le taux de prédiction est généralement très faible. Cependant, les données ici sont aléatoires – cela tue la prédiction de twig. Le coût d’une erreur de prévision est de 10 à 20 cycles de processeur, étant donné que le processeur retire généralement 2 instructions par cycle, ce qui équivaut à 20 à 40 instructions. Si le taux de prédiction est de 50% (aléatoire), alors chaque itération a une pénalité de prédiction équivalente à 10 à 20 instructions – ÉNORME .

Remarque: Le compilateur pourrait prouver que les éléments v[0] à v[v.size()-2] seront référencés, dans cet ordre, quelles que soient les valeurs qu’ils contiennent. Cela permettrait au compilateur dans ce cas de générer du code qui charge inconditionnellement tous les éléments sauf le dernier du vecteur. Le dernier élément du vecteur, à v [v.size () – 1], ne peut être chargé que dans la dernière itération de la boucle et uniquement si la première condition est vraie. Le compilateur pourrait donc générer du code pour la boucle sans la twig de court-circuit jusqu’à la dernière itération, puis utiliser un code différent avec la twig de court-circuit pour la dernière itération – cela exigerait que le compilateur sache que les données sont aléatoires et la prédiction de twig inutile et par conséquent, cela vaut la peine – les compilateurs ne sont pas si sophistiqués – pour le moment.

Pour éviter la twig conditionnelle générée par le AND logique (&&) et éviter de charger les emplacements de mémoire dans des variables locales, nous pouvons changer l’opérateur logique AND en un extrait de code bitwise AND, le résultat est presque 4x plus rapide lorsque les données sont aléatoires

 int f2() { int n = 0; for (int i = 1; i < v.size()-1; ++i) n += (v[i-1] < v[i]) & (v[i] < v[i+1]); // Bitwise AND return n; } 

Sortie

 3.642443ms min 3.779982ms median Result: 166634 3.725968ms min 3.870808ms median Result: 166634 1.052786ms min 1.081085ms median Result: 166634 done 

Le résultat sur gcc 5.3 est 8 fois plus rapide (en live à Coliru ici )

 g++ --version g++ -std=c++14 -O3 -Wall -Wextra -pedantic -pthread -pedantic-errors main.cpp -lm && ./a.out g++ (GCC) 5.3.0 Copyright (C) 2015 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 3.761290ms min 4.025739ms median Result: 166634 3.823133ms min 4.050742ms median Result: 166634 0.459393ms min 0.505011ms median Result: 166634 done 

Vous pourriez vous demander comment le compilateur peut évaluer la comparaison v[i-1] < v[i] sans générer de twig conditionnelle. La réponse dépend de la cible, pour x86 cela est possible grâce à l'instruction SETcc , qui génère un résultat à un octet, 0 ou 1, en fonction d'une condition dans le registre EFLAGS, la même condition pouvant être utilisée dans une twig conditionnelle, mais sans ramification. Dans le code généré par @deniss, vous pouvez voir setl généré, qui définit le résultat à 1 si la condition "inférieur à" est remplie, ce qui est évalué par l'instruction de comparaison précédente:

 cmp edx, edi ; a < b ? setl r10b ; r10b = a < b ? 1 : 0 mov ecx, dword ptr [r8 + 4*rsi + 4] ; c = v[i+1] lea rsi, [rsi + 1] ; ++i cmp edi, ecx ; b < c ? setl dl ; dl = b < c ? 1 : 0 and dl, r10b ; dl &= r10b movzx edx, dl ; edx = zero extended dl add eax, edx ; n += edx 

f0 et f1 sont sémantiquement différents.

x() && y() implique un court-circuit dans le cas où x () est faux, comme nous le soaps. Cela signifie que si x () est faux, alors y () ne doit pas être évalué.

Cela empêche la lecture anticipée des données pour évaluer y () et (au moins sur le clang) provoque l’insertion d’un saut conditionnel, ce qui entraîne des erreurs de prédicteur de twig.

Ajout de 2 autres tests prouve le point.

 #include  #include  #include  #include  #include  #include  using namespace std; using namespace std::chrono; vector v(1'000'000); int f0() { int n = 0; for (int i = 1; i < v.size()-1; ++i) { int a = v[i-1]; int b = v[i]; int c = v[i+1]; if (a < b && b < c) ++n; } return n; } int f1() { int n = 0; auto s = v.size() - 1; for (size_t i = 1; i < s; ++i) if (v[i-1] < v[i] && v[i] < v[i+1]) ++n; return n; } int f2() { int n = 0; auto s = v.size() - 1; for (size_t i = 1; i < s; ++i) { auto t1 = v[i-1] < v[i]; auto t2 = v[i] < v[i+1]; if (t1 && t2) ++n; } return n; } int f3() { int n = 0; auto s = v.size() - 1; for (size_t i = 1; i < s; ++i) { n += 1 * (v[i-1] < v[i]) * (v[i] < v[i+1]); } return n; } int main() { auto benchmark = [](int (*f)()) { const int N = 100; volatile long long result = 0; vector timings(N); for (int i = 0; i < N; ++i) { auto t0 = high_resolution_clock::now(); result += f(); auto t1 = high_resolution_clock::now(); timings[i] = duration_cast(t1-t0).count(); } sort(timings.begin(), timings.end()); cout << fixed << setprecision(6) << timings.front()/1'000'000.0 << "ms min\n"; cout << timings[timings.size()/2]/1'000'000.0 << "ms median\n" << "Result: " << result/N << "\n\n"; }; mt19937 generator (31415); // deterministic seed uniform_int_distribution<> dissortingbution(0, 1023); for (auto& e: v) e = dissortingbution(generator); benchmark(f0); benchmark(f1); benchmark(f2); benchmark(f3); cout << "\ndone\n"; return 0; } 

résultats (pomme clang, -O2):

 1.233948ms min 1.320545ms median Result: 166850 3.366751ms min 3.493069ms median Result: 166850 1.261948ms min 1.361748ms median Result: 166850 1.251434ms min 1.353653ms median Result: 166850 

Aucune des réponses fournies à ce jour n’a donné une version de f() que gcc ou clang peuvent pleinement optimiser. Ils génèrent tous des asm qui comparent les deux itérations. Voir le code avec la sortie asm sur le Godbolt Comstackr Explorer . (Connaissances de base importantes pour prédire la performance à partir de la sortie asm: guide de la microarchitecture d’Agner Fog , et autres liens sur le wiki de la balise x86 .

v[i-1] < v[i] est un travail que nous avons déjà effectué lors de la dernière itération, lorsque nous avons évalué v[i] < v[i+1] . En théorie, aider le compilateur grok à optimiser son fonctionnement (voir f3() ). Dans la pratique, cela finit par aller à l'encontre de l'auto-vectorisation dans certains cas, et gcc émet du code avec un -mtune=core2 registres partiels, même avec -mtune=core2 où c'est un problème énorme.

Le levage manuel de la v.size() - 1 semble aider. Les OP f0 et f1 ne recalculent pas réellement v.size() partir des pointeurs de début / fin de v , mais ils optimisent toujours moins bien que lors du calcul d'un size_t upper = v.size() - 1 dehors de la boucle ( f2() et f4() ).

Un problème distinct est que l'utilisation d'un compteur de boucle int avec une size_t supérieure size_t signifie que la boucle est potentiellement infinie. Je ne suis pas certain de l'impact que cela a sur d'autres optimisations.

Résultat: les compilateurs sont des bêtes complexes . Prédire quelle version sera optimisée n'est pas du tout évident ou simple.

Résultats sur Ubuntu 15.10 64 bits, sur Core2 E6600 (microarchitecture Merom / Conroe).

 clang++-3.8 -O3 -march=core2 | g++ 5.2 -O3 -march=core2 | gcc 5.2 -O2 (default -mtune=generic) f0 1.825ms min(1.858 med) | 5.008ms min(5.048 med) | 5.000 min(5.028 med) f1 4.637ms min(4.673 med) | 4.899ms min(4.952 med) | 4.894 min(4.931 med) f2 1.292ms min(1.323 med) | 1.058ms min(1.088 med) (autovec) | 4.888 min(4.912 med) f3 1.082ms min(1.117 med) | 2.426ms min(2.458 med) | 2.420 min(2.465 med) f4 1.291ms min(1.341 med) | 1.022ms min(1.052 med) (autovec) | 2.529 min(2.560 med) 

Les résultats seraient différents sur le matériel de la famille Intel SnB, en particulier. IvyBridge et plus tard où il n'y aurait aucun ralentissement partiel du registre. Core2 est limité par des charges non alignées lentes et une seule charge par cycle. Les boucles peuvent être assez petites pour que le décodage ne soit pas un problème.

f0 et f1 :

gcc 5.2: Les OP f0 et f1 créent des boucles branchées et ne se vectorisent pas automatiquement. Cependant, f0 n'utilise qu'une seule twig et utilise un setl sil / cmp sil, 1 étrange cmp sil, 1 / sbb eax, -1 pour effectuer la seconde moitié de la comparaison du court-circuit. Donc, il fait toujours les deux comparaisons à chaque itération.

clang 3.8: f0 : une seule charge par itération, mais fait les deux et les compare ensemble. f1 : les deux comparent chaque itération, une avec une twig pour préserver la sémantique C. Deux charges par itération.

 int f2() { int n = 0; size_t upper = v.size()-1; // difference from f0: hoist upper bound and use size_t loop counter for (size_t i = 1; i < upper; ++i) { int a = v[i-1], b = v[i], c = v[i+1]; if (a < b && b < c) ++n; } return n; } 

gcc 5.2 -O3 : vectorise automatiquement, avec trois charges pour obtenir les trois vecteurs de décalage nécessaires pour produire un vecteur de 4 résultats de comparaison. Aussi, après avoir combiné les résultats de deux instructions pcmpgtd , les compare à un vecteur de tout-zéro et masque ensuite cela. Zero est déjà l'élément d'identité pour l'addition, alors c'est vraiment idiot.

clang 3.8 -O3 : unrolls: chaque itération fait deux charges, trois cmp / setcc, deux and s, et deux add s.

 int f4() { int n = 0; size_t upper = v.size()-1; for (size_t i = 1; i < upper; ++i) { int a = v[i-1], b = v[i], c = v[i+1]; bool ab_lt = a < b; bool bc_lt = b < c; n += (ab_lt & bc_lt); // some really minor code-gen differences from f2: auto-vectorizes to better code that runs slightly faster even for this large problem size } return n; } 

• gcc 5.2 -O3 : autovectorise comme f2 , mais sans le pcmpeqd supplémentaire.
• gcc 5.2 -O2 : n'a pas étudié pourquoi c'est deux fois plus rapide que f2 .
• clang -O3 : environ le même code que f2 .

Tentative de compilateur

 int f3() { int n = 0; int a = v[0], b = v[1]; // These happen before checking v.size, defeating the loop vectorizer or something bool ab_lt = a < b; size_t upper = v.size()-1; for (size_t i = 1; i < upper; ++i) { int c = v[i+1]; // only one load and compare inside the loop bool bc_lt = b < c; n += (ab_lt & bc_lt); ab_lt = bc_lt; a = b; // unused inside the loop, only the compare result is needed b = c; } return n; } 

• clang 3.8 -O3 : se déroule avec 4 charges à l'intérieur de la boucle (clang aime généralement se dérouler par 4 lorsqu'il n'y a pas de dépendances complexes en boucle).
  4 cmp / setcc, 4x et / movzx, 4x add. Donc, Clang a fait exactement ce que j'espérais, et a fait un code scalaire presque optimal. C'était la version non vectorisée la plus rapide , et (sur movups où les charges non alignées sont movups ) est aussi rapide que les versions vectorielles de gcc.

• gcc 5.2 -O3 : Échec de la vectorisation automatique. Ma théorie à ce sujet est que l’access au tableau en dehors de la boucle perturbe l’auto-vectoriseur. Peut-être parce que nous le faisons avant de vérifier v.size() , ou peut-être juste en général.

  Comstack le code scalaire que nous espérons, avec un chargement, un cmp / setcc et un and par itération. Mais gcc crée un -mtune=core2 registre partiel , même avec -mtune=core2 où il y a un gros problème (2 ou 3 cycles pour insérer un UOP lors de la lecture d'un reg large après l'écriture d'une partie seulement). ( setcc est uniquement disponible avec une taille d'opérande de 8 bits, ce que AMD devrait avoir changé lorsqu'il a conçu l'ISA AMD64.) C'est la raison principale pour laquelle le code de gcc est 2,5 fois plus lent que celui de clang.

 ## the loop in f3(), from gcc 5.2 -O3 (same code with -O2) .L31: add rcx, 1 # i, mov edi, DWORD PTR [r10+rcx*4] # a, MEM[base: _19, index: i_13, step: 4, offset: 0] cmp edi, r8d # a, a # gcc's verbose-asm comments are a bit bogus here: one of these `a`s is from the last iteration, so this is really comparing c, b mov r8d, edi # a, a setg sil #, tmp124 and edx, esi # D.111089, tmp124 # PARTIAL-REG STALL: reading esi after writing sil movzx edx, dl # using movzx to widen sil to esi would have solved the problem, instead of doing it after the and add eax, edx # n, D.111085 # n += ... cmp r9, rcx # upper, i mov edx, esi # ab_lt, tmp124 jne .L31 #, ret