Considérez les deux programmes suivants qui effectuent les mêmes calculs de deux manières différentes:
// v1.c #include #include int main(void) { int i, j; int nbr_values = 8192; int n_iter = 100000; float x; for (j = 0; j < nbr_values; j++) { x = 1; for (i = 0; i < n_iter; i++) x = sin(x); } printf("%f\n", x); return 0; } et
// v2.c #include #include int main(void) { int i, j; int nbr_values = 8192; int n_iter = 100000; float x[nbr_values]; for (i = 0; i < nbr_values; ++i) { x[i] = 1; } for (i = 0; i < n_iter; i++) { for (j = 0; j < nbr_values; ++j) { x[j] = sin(x[j]); } } printf("%f\n", x[0]); return 0; }
Lorsque je les comstack en utilisant gcc 4.7.2 avec -O3 -ffast-math et que -O3 -ffast-math sur une boîte Sandy Bridge, le deuxième programme est deux fois plus rapide que le premier.
Pourquoi donc?
Un des suspects est la dépendance des données entre les itérations successives de la boucle i dans v1 . Cependant, je ne vois pas très bien quelle pourrait être l’explication complète.
(Question inspirée par Pourquoi mon exemple python / numpy est-il plus rapide que l’implémentation en C pur? )
MODIFIER:
Voici l’assembly généré pour v1 :
movl $8192, %ebp pushq %rbx LCFI1: subq $8, %rsp LCFI2: .align 4 L2: movl $100000, %ebx movss LC0(%rip), %xmm0 jmp L5 .align 4 L3: call _sinf L5: subl $1, %ebx jne L3 subl $1, %ebp .p2align 4,,2 jne L2
et pour v2 :
movl $100000, %r14d .align 4 L8: xorl %ebx, %ebx .align 4 L9: movss (%r12,%rbx), %xmm0 call _sinf movss %xmm0, (%r12,%rbx) addq $4, %rbx cmpq $32768, %rbx jne L9 subl $1, %r14d jne L8
Ignorez la structure de la boucle dans son ensemble et ne pensez qu’à la séquence d’appels au sin . v1 fait ce qui suit:
x <-- sin(x) x <-- sin(x) x <-- sin(x) ...
c'est-à-dire que chaque calcul de sin( ) ne peut pas commencer tant que le résultat de l'appel précédent n'est pas disponible; il doit attendre l'intégralité du calcul précédent. Cela signifie que pour N appels au sin , le temps total requirejs est 819200000 fois le temps de latence d'une évaluation unique du sin .
En v2 , en revanche, vous procédez comme suit:
x[0] <-- sin(x[0]) x[1] <-- sin(x[1]) x[2] <-- sin(x[2]) ...
remarquez que chaque appel au sin ne dépend pas de l'appel précédent. Effectivement, les appels à sin sont tous indépendants et le processeur peut commencer dès que le registre et les ressources ALU nécessaires sont disponibles (sans attendre la fin du calcul précédent). Ainsi, le temps requirejs est fonction du débit de la fonction sin, et non de la latence, de sorte que v2 peut se terminer en beaucoup moins de temps.
Je devrais également noter que DeadMG a raison de dire que les versions v1 et v2 sont formellement équivalentes et que, dans un monde parfait, le compilateur optimiserait les deux en une seule chaîne de 100 000 évaluations sin (ou simplement le résultat au moment de la compilation). Malheureusement, nous vivons dans un monde imparfait.
Dans le premier exemple, il exécute 100 000 boucles de péché, 8192 fois.
Dans le deuxième exemple, il exécute 8192 boucles de péché, 100 000 fois.
À part cela et en stockant le résultat différemment, je ne vois aucune différence.
Cependant, ce qui fait la différence, c’est que l’entrée est modifiée pour chaque boucle dans le second cas. Je suppose donc que ce qui se produit est que la valeur du péché devient beaucoup plus facile à calculer à certains moments de la boucle. Et cela peut faire une grande différence. Le calcul du péché n’est pas tout à fait sortingvial et c’est un calcul en série qui boucle jusqu’à ce que la condition de sortie soit atteinte.