Aucune réponse à ce jour ont donné une version de f() gcc ou clang peut pleinement optimiser. Ils génèrent de l'asm qui assure à la fois la compare à chaque itération. Voir avec le code de sortie asm sur le Godbolt Compilateur Explorer. (Il est Important de connaissances de base pour la prédiction de la performance de l'asm de sortie: Agner le Brouillard de la microarchitecture du guide, et d'autres liens sur le x86 balise wiki. Comme toujours, il fonctionne généralement mieux pour le profil avec les compteurs de performances pour trouver des étals.)
v[i-1] < v[i] est le travail que nous avons déjà fait la dernière itération, lorsque nous avons évalué v[i] < v[i+1]. En théorie, aider le compilateur connaît que le laisserais mieux optimiser (voir f3()). Dans la pratique, cela finit par vaincre auto-vectorisation dans certains cas, et gcc émet code partielle-s'inscrire dans les stalles, même avec -mtune=core2 où c'est un énorme problème.
Manuellement de levage de l' v.size() - 1 hors de la boucle de la limite supérieure de vérifier semble aider. L'OP f0 et f1 ne fait pas de re-calculer, v.size() depuis le début/la fin des pointeurs en v, mais de toute façon il optimise encore moins bien que pour le calcul de la size_t upper = v.size() - 1 en dehors de la boucle (f2() et f4()).
Une question distincte est que l'utilisation d'un int compteur de boucle avec un size_t limite supérieure signifie que la boucle est potentiellement infinie. Je ne suis pas sûr de l'impact que cela a sur d'autres optimisations.
Bottom line: les compilateurs sont des choses complexes. La prédiction de la version permettra d'optimiser le bien n'est pas du tout évident ou simple.
Les résultats sur 64 bits Ubuntu 15.10, sur Core 2 E6600 (Merom/Conroe microarchitecture).
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 les processeurs Intel de la Bns-quincaillerie familiale, esp. IvyBridge et plus tard, où il n'y aurait pas partielle registre des ralentissements. Core2 est limitée par la lenteur des non alignés charges, et une seule charge par cycle. Les boucles peuvent être assez petit pour décoder n'est pas un problème, cependant.
f0 et f1:
gcc 5.2: L'OP f0 et f1 à la fois de rendre branchu boucles, et ne sont pas auto-vectorisation. f0 seulement utilise une direction générale, cependant, et utilise un étrange setl sil / cmp sil, 1 / sbb eax, -1 pour la deuxième moitié du court-circuit de comparer. C'est donc toujours faire les deux comparaisons à chaque itération.
clang 3.8: f0: une seule charge par itération, mais ne les deux et compare ands ensemble. f1: les deux compare chaque itération, l'un avec une branche de préserver le C de la sémantique. 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: auto-vectorizes, avec trois charges d'obtenir les trois vecteurs de décalage nécessaire pour produire un vecteur de 4 de comparer les résultats. Aussi, après en combinant les résultats de deux pcmpgtd instructions, les compare à l'encontre d'un vecteur de tous les zéro et les masques. Le zéro est déjà l'identité de l'élément de plus, donc, c'est vraiment idiot.
clang 3.8 -O3: déroule: chaque itération n'deux charges, trois cmp/setcc, deux ands, et deux adds.
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: autovectorizes comme f2, mais sans les extra - pcmpeqd.
- gcc 5.2
-O2: ne pas chercher à savoir pourquoi c'est deux fois plus rapide que l' f2.
- clang
-O3: sur le même code que f2.
Tentative de compilateur se tenir par la main
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 typiquement aime se dérouler en 4 quand il n'y a pas de complexe boucle-effectuer les dépendances).
4 cmp/setcc, 4x et/movzx, 4x ajouter. Donc clang a fait exactement ce que j'espérais, et de fait quasi-optimale scalaire code. Ce fut le plus rapide non-vectorisé version, et (sur core2 où movups non alignés charges sont lentes) est aussi rapide que gcc est vectorisé versions.
-
gcc 5.2 -O3: Échec de l'auto-vectorisation. Ma théorie est que l'accès à la matrice de l'extérieur de la boucle confond l'auto-vectorizer. Peut-être parce que nous ne elle avant de vérifier l' v.size(), ou peut-être juste en général.
Compile le scalaire code nous espérer, avec une charge, un cmp/setcc, et un and par itération. Mais gcc crée un partiel-registre de décrochage, même avec -mtune=core2 où c'est un énorme problème (2 à 3 cycle de décrochage pour insérer une fusion uop lors de la lecture d'un large reg après avoir écrit une partie seulement de celui-ci). (setcc est uniquement disponible avec un 8-bit opérande de la taille, de l'OMI est quelque chose d'AMD devrait avoir changé quand ils ont conçu le AMD64 ISA.) C'est la raison principale pourquoi du ccg code s'exécute 2,5 x plus lent que 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
