Une boucle vide est plus lente qu'une boucle non vide en C

Question

En essayant de savoir combien de temps une ligne de code C s'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 boucle contenant une seule instruction.

Notez que j'ai essayé de changer l'ordre des boucles et d'ajouter du code de réchauffement, mais cela n'a rien changé à mon problème.

J'utilise codeblocks comme IDE avec le compilateur GNU gcc, linux ubuntu 14.04 et j'ai un intel i5 quadcore à 2.3GHz (j'ai essayé d'exécuter le programme sur un seul cœur, cela ne change pas le résultat).

Answer 1

En supposant que votre code utilise un entier de 32 bits int (ce que votre système fait probablement), alors rien ne peut être déterminé à partir de votre code. Au contraire, 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 d'arranger ça :

#include <stdint.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>

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<INT_MAX; i++);
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    begin = clock();
    for (i = 0; i<INT_MAX; i++) {
        A += B%2;
    }
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    return(0);
}

Maintenant, regardons la sortie de l'assemblage de ce code. Personnellement, je trouve l'assemblage interne de LLVM très lisible, donc je vais le montrer. Je vais le produire en exécutant :

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 existe pas de entre les appels à clock() para dans les deux cas . Ils sont donc tous deux compilés dans le exactement la même chose .

Answer 2

Le fait est que les processeurs modernes sont compliqués. Toutes les instructions exécutées interagissent les unes avec les autres de manière compliquée et intéressante. Merci pour "l'autre gars" pour avoir posté le code.

Le PO et "l'autre gars" ont apparemment trouvé que la boucle courte prend 11 cycles, tandis que la longue prend 9 cycles. Pour la boucle longue, 9 cycles sont largement suffisants, même s'il y a beaucoup d'opérations. Pour la boucle courte, il doit y avoir un blocage causé par le fait qu'elle est si courte, et le simple fait d'ajouter une touche nop rend la boucle suffisamment longue pour éviter le décrochage.

Une chose qui se passe si on regarde le code :

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

Nous lisons i et le réécrire ( addq ). Nous le relisons immédiatement, et le comparons ( cmpq ). Et ensuite on boucle. Mais la boucle utilise la prédiction de branche. Donc au moment où la addq est exécuté, le processeur n'est pas vraiment sûr d'être autorisé à écrire dans le fichier i (car la prédiction de la branche peut être erronée).

Ensuite, nous comparons à i . Le processeur essaiera d'éviter de lire i de mémoire, car sa lecture prend beaucoup de temps. Au lieu de cela, une partie du matériel se souviendra que nous venons d'écrire dans le fichier i en y ajoutant, et au lieu de lire i El cmpq reçoit les données de l'instruction de stockage. Malheureusement, nous ne sommes pas sûrs à ce stade si l'instruction write to i s'est réellement produit ou non ! Cela pourrait donc introduire un blocage ici.

Le problème ici est que le saut conditionnel, le addq qui mène à un magasin conditionnel, et l'option cmpq qui ne sait pas d'où proviennent les données, sont toutes très très proches les unes des autres. Ils sont inhabituellement proches les uns des autres. Il se peut qu'elles soient si proches les unes des autres que le processeur n'arrive pas à savoir s'il doit prendre i à partir de l'instruction de stockage ou pour le lire depuis la mémoire. Il le lit en mémoire, ce qui est plus lent car il doit attendre la fin de l'enregistrement. Et l'ajout d'un seul nop donne au processeur suffisamment de temps.

En général, on pense qu'il y a la mémoire vive et le cache. Sur un processeur Intel moderne, la mémoire vive peut être lue de (du plus lent au plus rapide) :

1. Mémoire (RAM)
2. Cache L3 (facultatif)
3. Cache L2
4. Cache L1
5. Instruction de stockage 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 à partir du cache L1
2. Ajouter 1 à i
3. Écrire à i vers le cache L1
4. Attendez jusqu'à ce que i est écrit dans le cache L1
5. Lire i à partir du cache L1
6. Comparez i avec INT_MAX
7. Passer à (1) si elle est inférieure.

Dans la boucle longue et rapide, le processeur le fait :

1. Beaucoup de choses
2. Lire i à partir du cache L1
3. Ajouter 1 à i
4. Faites une instruction "store" qui écrira i vers le cache L1
5. Lire i directement à partir de l'instruction "store" sans toucher au cache L1
6. Comparez i avec INT_MAX
7. Passer à (1) si elle est inférieure.

Answer 3

_Cette réponse suppose que vous avez déjà compris et traité les excellents points concernant le comportement indéfini que sharth fait dans sa réponse . Il signale également les astuces que le compilateur peut jouer sur votre code. Vous devez prendre des mesures pour vous assurer que le compilateur ne considère pas la boucle entière comme inutile. Par exemple, en changeant la déclaration de l'itérateur en volatile uint64_t i; empêchera le retrait de la boucle, et volatile int A; permettra de s'assurer que la deuxième boucle fait réellement plus de travail que la première. Mais même si vous faites tout cela, vous pouvez encore découvrir que :_

Le code situé plus loin dans un programme peut très bien s'exécuter plus rapidement que le code antérieur.

En clock() La fonction de la bibliothèque a pu provoquer un échec de la mise en cache après la lecture de la minuterie, et avant le retour. Cela aurait provoqué un temps supplémentaire dans le premier intervalle mesuré. (Pour les appels ultérieurs, le code est déjà dans le cache). Cependant, cet effet sera minuscule, certainement trop petit pour que la fonction clock() à mesurer, même si c'était un défaut de page jusqu'au disque. Les changements de contexte aléatoires peuvent ajouter à l'un ou l'autre intervalle de temps.

Plus important encore, vous avez un processeur i5, qui a une horloge dynamique. Lorsque votre programme commence à s'exécuter, la fréquence d'horloge est très probablement basse, car le CPU est resté inactif. Le simple fait d'exécuter le programme fait que le CPU n'est plus inactif, donc après un court délai, la vitesse d'horloge augmente. Le rapport entre la fréquence d'horloge du CPU inactif et TurboBoosted peut être significatif. (Sur le Haswell i5-4200U de mon ultrabook, le premier multiplicateur est de 8, et le second de 26, ce qui fait que le code de démarrage s'exécute moins de 30% plus rapidement que le code ultérieur ! Les boucles "calibrées" pour implémenter les délais sont une idée terrible sur les ordinateurs modernes).

L'inclusion d'une phase d'échauffement (exécution répétée d'un benchmark et rejet du premier résultat) pour un chronométrage plus précis n'est pas réservée aux cadres gérés avec des compilateurs JIT !

Answer 4

Je suis capable de reproduire ce problème 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 <main+50>

Et voici celle qui n'est pas 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 <main+157>

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 <main+50>

Ils courent maintenant aussi vite l'un que l'autre :

$ ./a.out 
3.846031
3.705035

J'imagine que cela montre l'importance de l'alignement, mais j'ai bien peur de ne pas pouvoir dire précisément comment :-)