Vous avez choisi un produit de la plus lente possible façons de vérifier
c*c == a*a + b*b // assuming c is non-negative
Qui compile à trois multiplications d'entiers (dont l'une peut être tiré hors de la boucle). Même sans pow(), vous êtes toujours à la conversion à l' double et en prenant la racine carrée, ce qui est terrible pour le débit. (Et aussi de la latence, mais la direction de la prévision + spéculative d'exécution sur les Processeurs modernes signifie que le temps de latence n'est pas un facteur ici).
Intel Haswell de SQRTSD instruction a un débit de un pour 8 à 14 cycles (source: Agner le Brouillard de l'instruction tables), de sorte que même si votre sqrt() version conserve la FP sqrt unité d'exécution saturé, il reste environ 4 fois plus lent que ce que j'ai gcc à émettre (ci-dessous).
Vous pouvez également optimiser la condition de la boucle de sortir de la boucle lorsque l' b < c de la partie de la condition devient fausse, de sorte que le compilateur n'a qu'à faire une version de cette vérification.
void foo_optimized()
{
for (int a = 1; a <= SUMTOTAL; a++) {
for (int b = a+1; b < SUMTOTAL-a-b; b++) {
// int c = SUMTOTAL-(a+b); // gcc won't always transform signed-integer math, so this prevents hoisting (SUMTOTAL-a) :(
int c = (SUMTOTAL-a) - b;
// if (b >= c) break; // just changed the loop condition instead
// the compiler can hoist a*a out of the loop for us
if (/* b < c && */ c*c == a*a + b*b) {
// Just print a newline. std::endl also flushes, which bloats the asm
std::cout << "a: " << a << " b: " << b << " c: "<< c << '\n';
std::cout << a * b * c << '\n';
}
}
}
}
Cette compile (avec gcc6.2 -O3 -mtune=haswell) à code avec cette boucle interne. Voir le code complet sur le Godbolt compilateur explorer.
# a*a is hoisted out of the loop. It's in r15d
.L6:
add ebp, 1 # b++
sub ebx, 1 # c--
add r12d, r14d # ivtmp.36, ivtmp.43 # not sure what this is or why it's in the loop, would have to look again at the asm outside
cmp ebp, ebx # b, _39
jg .L13 ## This is the loop-exit branch, not-taken until the end
## .L13 is the rest of the outer loop.
## It sets up for the next entry to this inner loop.
.L8:
mov eax, ebp # multiply a copy of the counters
mov edx, ebx
imul eax, ebp # b*b
imul edx, ebx # c*c
add eax, r15d # a*a + b*b
cmp edx, eax # tmp137, tmp139
jne .L6
## Fall-through into the cout print code when we find a match
## extremely rare, so should predict near-perfectly
Sur les processeurs Intel Haswell, toutes ces instructions sont 1 uop chaque. (Et la cmp/ccc paires de macro-fusible en comparer-et-branche uop.) Donc, c'est 10 fusionnée de domaine uop, qui peut délivrer à une itération par 2,5 cycles.
Haswell s'exécute imul r32, r32 avec un débit d'une itération par cycle d'horloge, de sorte que les deux se multiplie à l'intérieur de la boucle interne ne sont pas saturer le port 1 à deux multiplie par 2,5 c. Cela laisse de la marge pour absorber les inévitables conflits de ressources à partir d'AJOUTER et de SOUS-vol port 1.
Nous ne sommes même pas proche de toute autre exécution-port d'étranglement, si le front-end goulot d'étranglement est la seule question, et cela devrait fonctionner à une itération par 2,5 cycles sur les processeurs Intel Haswell et plus tard.
Boucle-déroulage pourrait aider ici afin de réduire le nombre de uop par chèque. par exemple, utiliser lea ecx, [rbx+1] pour calculer b+1 pour la prochaine itération, afin que nous puissions imul ebx, ebx sans l'aide d'un MOV pour le rendre non-destructive.
Une force-la réduction est également possible: compte tenu de b*b on pourrait essayer de calculer (b-1) * (b-1) sans IMUL. (b-1) * (b-1) = b*b - 2*b + 1, alors peut-être que nous pouvons faire une lea ecx, [rbx*2 - 1] , puis de déduire de b*b. (Il n'y a pas à aborder-modes de soustraire au lieu d'ajouter. Hmm, peut-être que nous pourrions conserver -b dans un registre, et de compter jusqu'à zéro, de sorte que nous pourrions utiliser lea ecx, [rcx + rbx*2 - 1] mettre à jour b*b dans ECX, compte tenu de -b dans EBX).
Sauf si vous avez réellement un goulot d'étranglement sur IMUL débit, cela pourrait finir par prendre plus de uops et ne pas être une victoire. Il peut être amusant de voir comment un compilateur pourrait faire avec cette force-la réduction à la source C++.
Vous pourriez probablement aussi vectoriser ce avec l'ESS ou AVX, la vérification de 4 ou 8 consécutifs b valeurs en parallèle. Depuis hits sont vraiment rares, que vous venez de vérifier si l'un des 8 a eu un coup et puis trier dans lequel il a été dans les rares cas où il y avait un match.
Voir aussi le x86 balise wiki pour plus d'optimisation des trucs.
