La boucle vide est plus lente qu’une boucle non vide en C

En essayant de savoir combien de temps une ligne de code C exécutait, j’ai remarqué cette chose étrange:

int main (char argc, char * argv[]) { time_t begin, end; uint64_t i; double total_time, free_time; int A = 1; int B = 1; begin = clock(); for (i = 0; i<(1<<31)-1; i++); end = clock(); free_time = (double)(end-begin)/CLOCKS_PER_SEC; printf("%f\n", free_time); begin = clock(); for (i = 0; i<(1<<31)-1; i++) { A += B%2; } end = clock(); free_time = (double)(end-begin)/CLOCKS_PER_SEC; printf("%f\n", free_time); return(0); } 

Qui, lorsqu’il est exécuté, affiche:

 5.873425 4.826874 

Pourquoi la boucle vide utilise-t-elle plus de temps que la seconde qui contient une instruction? Bien sûr, j’ai essayé de nombreuses variantes, mais à chaque fois, une boucle vide prend plus de temps qu’une seule avec une seule instruction à l’intérieur.

Notez que j’ai essayé de permuter l’ordre des boucles et d’append un code de mise en température et que cela n’a pas du tout modifié mon problème.

J’utilise codeblocks comme IDE avec le compilateur GNU gcc, linux ubuntu 14.04 et ai un intel i5 quadcore à 2,3 GHz (j’ai essayé de lancer le programme sur un seul core, cela ne change pas le résultat).

Le fait est que les processeurs modernes sont compliqués. Toutes les instructions exécutées interagiront de manière compliquée et intéressante. Merci pour “cet autre gars” pour avoir posté le code.

Les deux OP et “cet autre gars” ont apparemment constaté que la boucle courte prend 11 cycles, tandis que la boucle longue prend 9 cycles. Pour la boucle longue, 9 cycles sont suffisants même s’il y a beaucoup d’opérations. Pour la boucle courte, il doit y avoir un décrochage causé par sa longueur et l’ajout d’un nop rend la boucle suffisamment longue pour éviter le décrochage.

Une chose qui arrive si on regarde le code:

 0x00000000004005af <+50>: addq $0x1,-0x20(%rbp) 0x00000000004005b4 <+55>: cmpq $0x7fffffff,-0x20(%rbp) 0x00000000004005bc <+63>: jb 0x4005af  

Nous lisons i et l’écrivons ( addq ). Nous le cmpq immédiatement et le comparons ( cmpq ). Et puis on boucle. Mais la boucle utilise la prédiction de twig. Donc, au moment où addq est exécuté, le processeur n’est pas vraiment sûr de pouvoir écrire sur i (car la prédiction de twig peut être fausse).

Ensuite, nous comparons à i . Le processeur essaiera d’éviter de lire la mémoire, car sa lecture prend beaucoup de temps. Au lieu de cela, un morceau de matériel se rappellera que nous venons d’écrire à i en y ajoutant, et au lieu de lire i , l’instruction cmpq obtient les données de l’instruction store. Malheureusement, nous ne sums pas sûrs à ce stade si l’écriture a bien eu lieu ou non! Donc, cela pourrait introduire un stand ici.

Le problème ici est que le saut conditionnel, l’ addq qui mène à un magasin conditionnel, et le cmpq qui ne sait pas où trouver les données, sont tous très proches l’un de l’autre. Ils sont exceptionnellement proches les uns des autres. Il se peut qu’ils soient si proches les uns des autres, le processeur ne peut pas déterminer à ce moment-ci s’il faut prendre les instructions du magasin ou les lire de mémoire. Et le lit depuis la mémoire, ce qui est plus lent car il faut attendre que le magasin se termine. Et append un seul nop donne suffisamment de temps au processeur.

Habituellement, vous pensez qu’il y a de la RAM, et il y a du cache. Sur un processeur Intel moderne, la mémoire de lecture peut lire (du plus lent au plus rapide):

  1. Mémoire (RAM)
  2. Cache L3 (facultatif)
  3. Cache L2
  4. Cache L1
  5. Instruction de magasin précédente qui n’a pas encore été écrite dans le cache L1.

Donc, ce que le processeur fait en interne dans la boucle courte et lente:

  1. Lire i depuis le cache L1
  2. Ajouter 1 à i
  3. Ecrivez i dans le cache L1
  4. Attendez que j’écrive dans le cache L1
  5. Lire i depuis le cache L1
  6. Comparer avec INT_MAX
  7. Branchez à (1) si c’est moins.

Dans le long, rapide, boucle le processeur fait:

  1. Beaucoup de choses
  2. Lire i depuis le cache L1
  3. Ajouter 1 à i
  4. Faites une instruction “store” qui écrira i dans le cache L1
  5. Lire i directement à partir de l’instruction “store” sans toucher au cache L1
  6. Comparer avec INT_MAX
  7. Branchez à (1) si c’est moins.

En supposant que votre code utilise un type int entier 32 bits (ce que votre système fait probablement), rien ne peut être déterminé à partir de votre code. Au lieu de cela, il présente un comportement indéfini.

 foo.c:5:5: error: first parameter of 'main' (argument count) must be of type 'int' int main (char argc, char * argv[]) { ^ foo.c:13:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow] for (i = 0; i<(1<<31)-1; i++); ^ foo.c:19:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow] for (i = 0; i<(1<<31)-1; i++) { ^ 

Essayons de corriger cela:

 #include  #include  #include  #include  int main (int argc, char * argv[]) { time_t begin, end; uint64_t i; double total_time, free_time; int A = 1; int B = 1; begin = clock(); for (i = 0; i 

Maintenant, regardons la sortie d'assemblage de ce code. Personnellement, je trouve que l'assemblage interne de LLVM est très lisible, alors je vais le montrer. Je vais le produire en courant:

 clang -O3 foo.c -S -emit-llvm -std=gnu99 

Voici la partie pertinente de la sortie (la fonction principale):

 define i32 @main(i32 %argc, i8** nocapture readnone %argv) #0 { %1 = tail call i64 @"\01_clock"() #3 %2 = tail call i64 @"\01_clock"() #3 %3 = sub nsw i64 %2, %1 %4 = sitofp i64 %3 to double %5 = fdiv double %4, 1.000000e+06 %6 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %5) #3 %7 = tail call i64 @"\01_clock"() #3 %8 = tail call i64 @"\01_clock"() #3 %9 = sub nsw i64 %8, %7 %10 = sitofp i64 %9 to double %11 = fdiv double %10, 1.000000e+06 %12 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %11) #3 ret i32 0 } 

Notez qu'il n'y a pas d' opération entre les appels à clock() pour les deux cas . Donc, ils sont tous les deux compilés pour exactement la même chose .

Cette réponse suppose que vous avez déjà compris et abordé les excellents points concernant le comportement indéfini que la réponse apporte. Il indique également les astuces que le compilateur peut jouer sur votre code. Vous devez prendre des mesures pour vous assurer que le compilateur ne reconnaît pas l’intégralité de la boucle. Par exemple, changer la déclaration de l’iterator en volatile uint64_t i; empêchera la suppression de la boucle, et volatile int A; veillera à ce que la deuxième boucle fasse réellement plus de travail que la première. Mais même si vous faites tout cela, vous pouvez toujours découvrir que:

Code plus tard dans un programme peut bien exécuter plus rapidement que le code précédent.

La fonction de bibliothèque clock() pourrait avoir causé un problème avec icache après avoir lu le minuteur et avant de revenir. Cela provoquerait un délai supplémentaire dans le premier intervalle mesuré. (Pour les appels ultérieurs, le code est déjà en cache). Cependant, cet effet sera minuscule, certainement trop petit pour que clock() puisse mesurer, même si c’était une faute de page jusqu’au disque. Les changements de contexte aléatoires peuvent s’append à l’un ou l’autre des intervalles de temps.

Plus important encore, vous avez un processeur i5, qui a la synchronisation dynamic. Lorsque l’exécution de votre programme commence, le taux d’horloge est probablement faible, car le processeur est inactif. Le simple fait de lancer le programme ne rend plus le processeur inactif, si bien que la fréquence d’horloge augmente après un court délai. Le rapport entre la fréquence d’horloge du processeur en veille et celle du processeur TurboBoosted peut être significatif. (Sur le Haswell i5-4200U de mon ultrabook, l’ancien multiplicateur est de 8 et le second de 26, ce qui fait que le code de démarrage tourne moins de 30% plus rapidement que le code ultérieur! )

L’inclusion d’une phase de réchauffement (exécution répétée d’un benchmark et lancement du premier résultat) pour un timing plus précis ne concerne pas uniquement les frameworks gérés avec les compilateurs JIT!

Je suis capable de le reproduire avec GCC 4.8.2-19ubuntu1 sans optimisation:

 $ ./a.out 4.780179 3.762356 

Voici la boucle vide:

 0x00000000004005af <+50>: addq $0x1,-0x20(%rbp) 0x00000000004005b4 <+55>: cmpq $0x7fffffff,-0x20(%rbp) 0x00000000004005bc <+63>: jb 0x4005af  

Et voici le non-vide:

 0x000000000040061a <+157>: mov -0x24(%rbp),%eax 0x000000000040061d <+160>: cltd 0x000000000040061e <+161>: shr $0x1f,%edx 0x0000000000400621 <+164>: add %edx,%eax 0x0000000000400623 <+166>: and $0x1,%eax 0x0000000000400626 <+169>: sub %edx,%eax 0x0000000000400628 <+171>: add %eax,-0x28(%rbp) 0x000000000040062b <+174>: addq $0x1,-0x20(%rbp) 0x0000000000400630 <+179>: cmpq $0x7fffffff,-0x20(%rbp) 0x0000000000400638 <+187>: jb 0x40061a  

Insérons un nop dans la boucle vide:

 0x00000000004005af <+50>: nop 0x00000000004005b0 <+51>: addq $0x1,-0x20(%rbp) 0x00000000004005b5 <+56>: cmpq $0x7fffffff,-0x20(%rbp) 0x00000000004005bd <+64>: jb 0x4005af  

Ils courent maintenant aussi vite:

 $ ./a.out 3.846031 3.705035 

J’imagine que cela montre l’importance de l’alignement, mais j’ai peur de ne pas pouvoir dire comment: |