Skip to content

Pourquoi ce code est-il 6.5x plus lent avec les optimisations activées ?

Après avoir consulté des spécialistes du domaine, des programmeurs de diverses branches et des enseignants, nous avons trouvé la réponse au dilemme et nous la capturons dans cet article.

Solution :

Le test de votre code sur l'explorateur de compilateurs de Godbolt fournit cette explication :

  • à l'adresse -O0 ou sans optimisations, le code généré appelle la fonction de la bibliothèque C strlen;
  • à -O1 le code généré utilise une simple expansion en ligne utilisant une fonction rep scasb instruction ;
  • à l'adresse -O2 et au-dessus, le code généré utilise une expansion en ligne plus élaborée.

Le benchmarking de votre code à plusieurs reprises montre des variations substantielles d'une exécution à l'autre, mais l'augmentation du nombre d'itérations montre que :

  • le site -O1 code est beaucoup plus lent que l'implémentation de la bibliothèque C : 32240 vs 3090
  • le site -O2 est plus rapide que le code -O1 mais toujours sensiblement plus lent que le code C ibrary : 8570 vs 3090.

Ce comportement est spécifique à gcc et à la libc GNU. Le même test sur OS/X avec clang et la libc d'Apple ne montre pas de différences significatives, ce qui n'est pas une surprise puisque Godbolt montre que clang génère un appel à la bibliothèque C strlen à tous les niveaux d'optimisation.

Cela pourrait être considéré comme un bogue dans gcc/glibc, mais des analyses comparatives plus approfondies pourraient montrer que l'overhead de l'appel de strlen a un impact plus important que le manque de performance du code en ligne pour les petites chaînes de caractères. Les chaînes de caractères dans votre benchmark sont inhabituellement grandes, donc focaliser le benchmark sur des chaînes de caractères ultra-longues pourrait ne pas donner de résultats significatifs.

J'ai amélioré ce benchmark et testé différentes longueurs de chaînes. Il apparaît d'après les benchmarks sur linux avec gcc (Debian 4.7.2-5) 4.7.2 fonctionnant sur un CPU Intel(R) Core(TM) i3-2100 @ 3.10GHz que le code inline généré par -O1 est toujours plus lent, d'un facteur pouvant aller jusqu'à 10 pour les chaînes modérément longues, tandis que -O2 n'est que légèrement plus rapide que la libc strlen pour les chaînes de caractères très courtes et moitié moins rapide pour les chaînes de caractères plus longues. A partir de ces données, la version de la bibliothèque GNU C de strlen est assez efficace pour la plupart des longueurs de chaîne, du moins sur mon matériel spécifique. Gardez également à l'esprit que la mise en cache a un impact majeur sur les mesures du benchmark.

Voici le code mis à jour :

#include 
#include 
#include 

void benchmark(int repeat, int minlen, int maxlen) {
    char *s = malloc(maxlen + 1);
    memset(s, 'A', minlen);
    long long bytes = 0, calls = 0;
    clock_t clk = clock();
    for (int n = 0; n < repeat; n++) {
        for (int i = minlen; i < maxlen; ++i) {
            bytes += i + 1;
            calls += 1;
            s[i] = '';
            s[strlen(s)] = 'A';
        }
    }
    clk = clock() - clk;
    free(s);
    double avglen = (minlen + maxlen - 1) / 2.0;
    double ns = (double)clk * 1e9 / CLOCKS_PER_SEC;
    printf("average length %7.0f -> avg time: %7.3f ns/byte, %7.3f ns/calln",
           avglen, ns / bytes, ns / calls);
}

int main() {
    benchmark(10000000, 0, 1);
    benchmark(1000000, 0, 10);
    benchmark(1000000, 5, 15);
    benchmark(100000, 0, 100);
    benchmark(100000, 50, 150);
    benchmark(10000, 0, 1000);
    benchmark(10000, 500, 1500);
    benchmark(1000, 0, 10000);
    benchmark(1000, 5000, 15000);
    benchmark(100, 1000000 - 50, 1000000 + 50);
    return 0;
}

Voici la sortie :

chqrlie> gcc -std=c99 -O0 benchstrlen.c && ./a.out
average length       0 -> avg time:  14.000 ns/byte,  14.000 ns/call
average length       4 -> avg time:   2.364 ns/byte,  13.000 ns/call
average length      10 -> avg time:   1.238 ns/byte,  13.000 ns/call
average length      50 -> avg time:   0.317 ns/byte,  16.000 ns/call
average length     100 -> avg time:   0.169 ns/byte,  17.000 ns/call
average length     500 -> avg time:   0.074 ns/byte,  37.000 ns/call
average length    1000 -> avg time:   0.068 ns/byte,  68.000 ns/call
average length    5000 -> avg time:   0.064 ns/byte, 318.000 ns/call
average length   10000 -> avg time:   0.062 ns/byte, 622.000 ns/call
average length 1000000 -> avg time:   0.062 ns/byte, 62000.000 ns/call
chqrlie> gcc -std=c99 -O1 benchstrlen.c && ./a.out
average length       0 -> avg time:  20.000 ns/byte,  20.000 ns/call
average length       4 -> avg time:   3.818 ns/byte,  21.000 ns/call
average length      10 -> avg time:   2.190 ns/byte,  23.000 ns/call
average length      50 -> avg time:   0.990 ns/byte,  50.000 ns/call
average length     100 -> avg time:   0.816 ns/byte,  82.000 ns/call
average length     500 -> avg time:   0.679 ns/byte, 340.000 ns/call
average length    1000 -> avg time:   0.664 ns/byte, 664.000 ns/call
average length    5000 -> avg time:   0.651 ns/byte, 3254.000 ns/call
average length   10000 -> avg time:   0.649 ns/byte, 6491.000 ns/call
average length 1000000 -> avg time:   0.648 ns/byte, 648000.000 ns/call
chqrlie> gcc -std=c99 -O2 benchstrlen.c && ./a.out
average length       0 -> avg time:  10.000 ns/byte,  10.000 ns/call
average length       4 -> avg time:   2.000 ns/byte,  11.000 ns/call
average length      10 -> avg time:   1.048 ns/byte,  11.000 ns/call
average length      50 -> avg time:   0.337 ns/byte,  17.000 ns/call
average length     100 -> avg time:   0.299 ns/byte,  30.000 ns/call
average length     500 -> avg time:   0.202 ns/byte, 101.000 ns/call
average length    1000 -> avg time:   0.188 ns/byte, 188.000 ns/call
average length    5000 -> avg time:   0.174 ns/byte, 868.000 ns/call
average length   10000 -> avg time:   0.172 ns/byte, 1716.000 ns/call
average length 1000000 -> avg time:   0.172 ns/byte, 172000.000 ns/call

L'inline de GCC strlen sont beaucoup plus lents que ce qu'ils pourraient faire avec SSE2. pcmpeqb / pmovmskbet bsfétant donné l'alignement de 16 octets de calloc. Cette "optimisation" est en fait une pessimisation.

Ma simple boucle écrite à la main qui tire parti de l'alignement sur 16 octets est 5 fois plus rapide que ce que gcc... -O3 inlines pour les grands buffers, et ~2x plus rapide pour les chaînes courtes. (Et plus rapide que d'appeler strlen pour les chaînes courtes). J'ai ajouté un commentaire à https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88809 pour proposer ceci pour ce que gcc devrait mettre en ligne à -O2 / -O3 quand il le peut. (Avec une suggestion pour monter en puissance jusqu'à 16 octets si nous ne connaissons que l'alignement sur 4 octets pour commencer).


Lorsque gcc sait qu'il a un alignement de 4 octets. pour le tampon (garanti par calloc), il choisit de mettre en ligne strlen comme un bithack scalaire de 4 octets à la fois utilisant les registres entiers de GP (-O2 et plus).

(La lecture de 4 octets à la fois n'est sûre que si l'on sait que l'on ne peut pas traverser une page qui ne contient pas d'octets de chaîne, et qui pourrait donc être non mappée. Est-il sûr de lire au-delà de la fin d'un tampon dans la même page sur x86 et x64 ? (TL:DR oui, en asm ça l'est, donc les compilateurs peuvent émettre du code qui fait cela même si le faire dans le source C est UB. libc strlen tirent également avantage de cela. Voir ma réponse là pour les liens vers la glibc. strlen et un résumé de la façon dont elle fonctionne si rapidement pour les grandes chaînes de caractères).

Sur -O1, gcc toujours (même sans alignement connu) choisit de mettre en ligne strlen comme repnz scasbce qui est très lent (environ 1 octet par cycle d'horloge sur les processeurs Intel modernes). Les "chaînes rapides" ne s'appliquent qu'aux rep stos et rep movset non aux repz/repnz malheureusement. Leur microcode est juste simple, 1 octet à la fois, mais ils ont toujours une certaine surcharge de démarrage. (https://agner.org/optimize/)

(Nous pouvons tester cela en "cachant" le pointeur du compilateur en stockant / rechargeant s à un volatile void *tmppar exemple. gcc ne doit faire aucune supposition sur la valeur du pointeur qui est lue à partir d'un volatile.volatileen détruisant toute information d'alignement).


GCC dispose de quelques options de réglage pour x86 comme -mstringop-strategy=libcall vs. unrolled_loop vs. rep_byte pour l'inlining des opérations sur les chaînes en général (pas seulement strlen ; memcmp serait une autre majeure qui peut être faite avec rep ou une boucle). Je n'ai pas vérifié l'effet qu'ils ont ici.

La documentation d'une autre option décrit également le comportement actuel. Nous pouvions obtenir cet inlining (avec du code supplémentaire pour la gestion de l'alignement) même dans les cas où nous le voulions sur des pointeurs non alignés. (C'était une victoire réelle de perf, surtout pour les petites chaînes, sur des cibles où la boucle en ligne n'était pas un déchet par rapport à ce que la machine peut faire).

-minline-all-stringops
Par défaut, GCC inline les opérations de chaînes de caractères uniquement lorsque la destination est connue pour être alignée sur au moins une frontière de 4 octets. Cela permet plus d'inlining et augmente la taille du code, mais peut améliorer les performances du code qui dépend de memcpy rapide, strlen, et memset pour les courtes longueurs.

GCC dispose également d'attributs par fonction que vous pouvez apparemment utiliser pour contrôler cela, comme par exemple __attribute__((no-inline-all-stringops)) void foo() { ... }, mais je n'ai pas joué avec. (C'est l'opposé de inline-all. Il ne signifie inline none, cela revient juste à ne mettre en ligne que lorsque l'alignement sur 4 octets est connu).


Les deux inline de gcc strlen de gcc ne parviennent pas à tirer parti de l'alignement sur 16 octets, et sont assez mauvaises pour x86-64.

A moins que le cas de la petite chaîne soit très commun, faire un morceau de 4 octets, puis des morceaux alignés de 8 octets irait environ deux fois plus vite que le 4 octets.

Et la stratégie 4 octets a un nettoyage beaucoup plus lent que nécessaire pour trouver l'octet dans le dword contenant l'octet zéro. Il détecte cela en cherchant un octet avec son bit haut activé, donc il devrait juste masquer les autres bits et utiliser... bsf (balayage des bits en avant). Cela a une latence de 3 cycles sur les CPU modernes (Intel et Ryzen). Ou les compilateurs peuvent utiliser rep bsf de sorte qu'il s'exécute comme tzcnt sur les CPU qui supportent BMI1, ce qui est plus efficace sur AMD. bsf et tzcnt donnent le même résultat pour les entrées non nulles.

La boucle de 4 octets de GCC semble avoir été compilée à partir de C pur, ou d'une certaine logique indépendante de la cible, ne tirant pas avantage du bitscan. gcc utilise bien andn pour l'optimiser lors de la compilation pour x86 avec BMI1, mais c'est toujours moins de 4 octets par cycle.

SSE2 pcmpeqb + bsf est beaucoup beaucoup meilleur pour les entrées courtes et longues. le x86-64 garantit que SSE2 est disponible, et le x86-64 System V dispose de alignof(maxalign_t) = 16 donc calloc retournera toujours des pointeurs alignés sur au moins 16 octets.


J'ai écrit un remplacement pour la fonction strlen pour tester les performances

Comme prévu, c'est environ 4x plus rapide sur Skylake en passant 16 octets à la fois au lieu de 4.

(J'ai compilé la source originale vers asm avec -O3, puis édité l'asm pour voir ce que les performances auraient dû être avec cette stratégie pour l'expansion en ligne de... strlen. Je l'ai également porté en asm inline à l'intérieur du sour C.ce; voir cette version sur Godbolt).

    # at this point gcc has `s` in RDX, `i` in ECX

    pxor       %xmm0, %xmm0         # zeroed vector to compare against
    .p2align 4
.Lstrlen16:                         # do {
#ifdef __AVX__
    vpcmpeqb   (%rdx), %xmm0, %xmm1
#else
    movdqa     (%rdx), %xmm1
    pcmpeqb    %xmm0, %xmm1           # xmm1 = -1 where there was a 0 in memory
#endif

    add         $16, %rdx             # ptr++
    pmovmskb  %xmm1, %eax             # extract high bit of each byte to a 16-bit mask
    test       %eax, %eax
    jz        .Lstrlen16            # }while(mask==0);
    # RDX points at the 16-byte chunk *after* the one containing the terminator
    # EAX = bit-mask of the 0 bytes, and is known to be non-zero
    bsf        %eax, %eax           # EAX = bit-index of the lowest set bit

    movb       $'A', -16(%rdx, %rax)

Notez que j'ai optimisé une partie du nettoyage de strlen dans le mode d'adressage store : Je corrige le dépassement avec le -16 déplacement, et qu'il s'agit juste de trouver la fin de la chaîne de caractères, et non pas de calculer réellement la longueur puis d'indexer comme GCC le faisait déjà après avoir inliné sa boucle de 4 octets à la fois.

Pour obtenir la chaîne de caractères réelle longueur (au lieu du pointeur vers la fin), il faudrait soustraire rdx-start et ensuite ajouter rax-16 (peut-être avec un LEA pour ajouter 2 registres + une constante, mais le LEA à 3 composants a plus de latence).

Avec AVX pour permettre le load+compare en une seule instruction sans détruire le registre mis à zéro, la boucle entière n'est plus que 4 uop, contre 5. (test/jz macro-fuse en une seule uop sur Intel et AMD. vpcmpeqb avec un non-indexé non indexé peut le garder micro-fondu à travers tout le pipeline, donc c'est seulement 1 uop de domaine fusionné pour le front-end).

(Notez que le mélange d'AVX 128-bit avec SSE fait pas causer des décrochages même sur Haswell, tant que vous êtes dans un état propre pour commencer. Je n'ai donc pas pris la peine de changer les autres instructions en AVX, seulement celle qui importait. Il semble y avoir un effet mineur où pxor était en fait légèrement meilleur que vpxor sur mon ordinateur de bureau, cependant, pour un corps de boucle AVX. Cela semblait quelque peu répétable, mais c'est bizarre car il n'y a pas de différence de taille de code et donc pas de différence d'alignement).

pmovmskb est une instruction à une seule opération. Elle a une latence de 3 cycles sur Intel et Ryzen (pire sur la famille Bulldozer). Pour les chaînes courtes, le voyage à travers l'unité SIMD et le retour à l'entier est une partie importante de la chaîne de dépendance du chemin critique pour la latence des octets de mémoire d'entrée à l'adresse de stockage étant prêt. Mais seul SIMD a des comparaisons d'entiers emballés, donc scalaire devrait faire plus de travail.

Pour le cas des très petites chaînes de caractères (comme 0 à 3 octets), il pourrait être possible d'obtenir une latence légèrement inférieure pour ce cas en utilisant du scalaire pur (surtout sur la famille Bulldozer), mais le fait que toutes les chaînes de 0 à 15 octets prennent le même chemin de branchement (la branche de boucle n'est jamais prise) est très bien pour la plupart des cas d'utilisation de chaînes courtes..

Être très bon pour toutes les chaînes jusqu'à 15 octets semble être un bon choix, quand on sait qu'on a un alignement de 16 octets. Un branchement plus prévisible est très bien. (Et notez que lors du bouclage, pmovmskb latence n'affecte que la rapidité avec laquelle nous pouvons détecter les mauvaises prédictions de branche pour sortir de la boucle ; la prédiction de branche + l'exécution spéculative masque la latence du pmovmskb indépendant dans chaque itération.

Si nous nous attendions à ce que des chaînes plus longues soient courantes, nous pourrions dérouler un peu, mais à ce moment-là, vous devriez juste appeler la fonction libc pour qu'elle puisse dispatcher vers AVX2 si elle est disponible au moment de l'exécution. Le déroulage vers plus de 1 vecteur complique le nettoyage, nuisant aux cas simples.


Sur ma machine i7-6700k Skylake à 4,2GHz max turbo (et... energy_performance_preference = performance), avec gcc8.2 sur Arch Linux, j'obtiens un timing de benchmark assez cohérent parce que la vitesse d'horloge de mon CPU monte en régime pendant le memset. Mais peut-être pas toujours à max turbo ; la gestion de l'énergie hw de Skylake downclocks lorsque la mémoire est liée. perf stat a montré que j'ai typiquement obtenu juste autour de 4,0 GHz en exécutant ceci pour faire la moyenne de la sortie stdout et voir le résumé perf sur stderr.

perf stat -r 100 ./a.out | awk '{sum+= $1}  END{print sum/100;}'

J'ai fini par copier mon asm dans une déclaration GNU C inline-asm, afin que je puisse mettre le code sur l'explorateur de compilateur Godbolt.

Pour les grandes chaînes de caractères, même longueur que dans la question : temps sur ~4GHz Skylake.

  • ~62100 clock_t unités de temps : -O1 rep scas : (clock() est un peu obsolète, mais je n'ai pas pris la peine de le modifier).
  • ~15900 clock_t unités de temps : -O3 stratégie de boucle 4 octets de gcc : moyenne de 100 exécutions = . (Ou peut-être ~15800 avec -march=native pour andn)
  • ~1880 clock_t unités de temps : -O3 avec glibc strlen appels de fonctions, avec AVX2
  • ~3190 clock_t unités de temps : (AVX1 128-bit vectors, 4 uop loop) hand-written inline asm that gcc could/should inline.
  • ~3230 clock_t unités de temps : (SSE2 5 uop loop) asm inline écrit à la main que gcc pourrait/devrait inline.

Mon asm écrit à la main devrait être très bon pour les chaînes courtes, aussi, car il n'a pas besoin de se brancher spécialement. L'alignement connu est très bon pour strlen, et libc ne peut pas en tirer avantage.

Si nous nous attendons à ce que les grandes chaînes de caractères soient rares, 1,7x plus lent que libc pour ce cas. La longueur de 1M d'octets signifie qu'elle ne restera pas chaude dans le cache L2 (256k) ou L1d (32k) sur mon CPU, donc même embouteillée sur le cache L3, la version libc était plus rapide. (Probablement qu'une boucle non enroulée et des vecteurs de 256 bits n'encombre pas le ROB avec autant d'uops par octet, donc OoO exec peut voir plus loin et obtenir plus de parallélisme mémoire, en particulier aux frontières de page).

Mais la bande passante du cache L3 est probablement un goulot d'étranglement qui empêche la version à 4 uop de fonctionner à 1 itération par horloge, donc nous voyons moins de bénéfice d'AVX nous épargnant une uop dans la boucle. Avec des données chaudes dans le cache L1d, nous devrions obtenir 1,25 cycles par itération contre 1.

Mais une bonne implémentation d'AVX2 peut lire jusqu'à 64 octets par cycle (2x 32 octets de chargements) en utilisant... vpminub pour combiner les paires avant de vérifier les zéros et de revenir en arrière pour trouver où ils étaient. L'écart entre ceci et la libc s'ouvre plus largement pour les tailles de ~2k à ~30 kiB environ qui restent chaudes dans L1d.

Quelques tests en lecture seule avec length=1000 indiquent que la glibc... strlen est vraiment environ 4x plus rapide que ma boucle pour les chaînes de taille moyenne chaudes dans le cache L1d.. C'est assez grand pour qu'AVX2 puisse monter en puissance jusqu'à la grande boucle déroulée, mais cela tient encore facilement dans le cache L1d. (La lecture seule évite les décrochages de store-forwarding, et donc nous pouvons faire de nombreuses itérations).

Si vos chaînes sont aussi grandes, vous devriez utiliser des chaînes de longueur explicite au lieu d'avoir besoin de... strlen du tout, donc l'inlining d'une simple boucle semble encore être une stratégie raisonnable, tant qu'il s'agit effectivement de... bon pour les chaînes courtes et pas un déchet total pour les chaînes moyennes (comme 300 octets) et très longues (> taille du cache).


Benchmarking de petites chaînes de caractères avec ceci :

J'ai rencontré quelques bizarreries en essayant d'obtenir les résultats que j'attendais :

J'ai essayé s[31] = 0 de tronquer la chaîne avant chaque itération (permettant une longueur constante courte). Mais alors ma version SSE2 avait presque la même vitesse que la version de GCC. Les décrochages de transfert de magasin étaient le goulot d'étranglement ! Un stockage d'octets suivi d'un chargement plus large fait que le store-forwarding prend le chemin lent qui fusionne les octets du tampon de stockage avec les octets du cache L1d. Cette latence supplémentaire fait partie d'une chaîne de dep transportée en boucle à travers le dernier morceau de 4 ou 16 octets de la chaîne, pour calculer l'indice de stockage pour la prochaine itération.

Le code plus lent de GCC, 4 octets à la fois, pourrait suivre en traitant les morceaux de 4 octets précédents dans l'ombre de cette latence. (L'exécution hors ordre est assez fantastique : un code lent peut parfois ne pas affecter la vitesse globale de votre programme).

J'ai finalement résolu le problème en faisant une version en lecture seule, et en utilisant l'asm en ligne pour empêcher le compilateur de hisser... strlen hors de la boucle.

Mais le store-forwarding est un problème potentiel avec l'utilisation de chargements de 16 octets. Si d'autres variables C sont stockées au-delà de la fin du tableau, nous pourrions rencontrer un blocage SF dû au chargement de la fin du tableau plus loin qu'avec des magasins plus étroits. Pour les données récemment copiées, tout va bien si elles ont été copiées avec des magasins alignés sur 16 octets ou plus, mais glibc memcpy pour les petites copies fait deux chargements superposés qui couvrent l'objet entier, du début et de la fin de l'objet. Ensuite, il stocke les deux, toujours en se chevauchant, en gérant gratuitement le cas du memmove src overlaps dst. Ainsi, le second morceau de 16 ou 8 octets d'une courte chaîne de caractères qui vient d'être memcpyée peut nous faire perdre du temps pour lire le dernier morceau. (Celui qui a la dépendance des données pour la sortie).

Juste courir plus lentement pour ne pas arriver à la fin avant qu'elle ne soit prête n'est pas bon en général, donc il n'y a pas de grande solution ici. Je pense la plus du temps vous n'allez pas strlen un buffer que vous venez de écrit, En général, vous allez strlen une entrée que vous ne faites que lire, donc les décrochages de transfert de mémoire ne sont pas un problème.. Si quelque chose d'autre l'a simplement écrit, alors un code efficace n'aurait pas, espérons-le, jeté la longueur et appelé une fonction qui nécessitait de la recalculer.


D'autres bizarreries que je n'ai pas totalement comprises :

L'alignement du code fait une différence d'un facteur 2 pour la lecture seule, size=1000 (s[1000] = 0;). Mais la boucle asm la plus interne elle-même est alignée avec... .p2align 4 ou .p2align 5. Augmenter l'alignement de la boucle peut la ralentir d'un facteur 2 !

# slow version, with *no* extra HIDE_ALIGNMENT function call before the loop.
# using my hand-written asm, AVX version.
  i<1280000 read-only at strlen(s)=1000 so strlen time dominates the total runtime (not startup overhead)
  .p2align 5 in the asm inner loop. (32-byte code alignment with NOP padding)

gcc -DUSE_ASM -DREAD_ONLY -DHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
 time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
 awk '{sum+= $1}  END{print sum/100;}'

 Performance counter stats for './a.out' (100 runs):

             40.92 msec task-clock                #    0.996 CPUs utilized            ( +-  0.20% )
                 2      context-switches          #    0.052 K/sec                    ( +-  3.31% )
                 0      cpu-migrations            #    0.000 K/sec                  
               313      page-faults               #    0.008 M/sec                    ( +-  0.05% )
       168,103,223      cycles                    #    4.108 GHz                      ( +-  0.20% )
        82,293,840      branches                  # 2011.269 M/sec                    ( +-  0.00% )
         1,845,647      branch-misses             #    2.24% of all branches          ( +-  0.74% )
       412,769,788      instructions              #    2.46  insn per cycle           ( +-  0.00% )
       466,515,986      uops_issued.any           # 11401.694 M/sec                   ( +-  0.22% )
       487,011,558      uops_executed.thread      # 11902.607 M/sec                   ( +-  0.13% )

         0.0410624 +- 0.0000837 seconds time elapsed  ( +-  0.20% )

40326.5   (clock_t)

real    0m4.301s
user    0m4.050s
sys     0m0.224s

Notez les ratés de branche définitivement non nuls, contre presque exactement zéro pour la version rapide. Et les uops émises sont beaucoup plus élevées que la version rapide : il se peut qu'elle spécule sur le mauvais chemin pour un... long temps sur chacun de ces ratés de branche.

Probablement que les branches de la boucle intérieure et extérieure s'aliènent l'une l'autre, ou pas.

Le nombre d'instructions est presque identique, juste différent par quelques NOPs dans la boucle externe devant la boucle interne. Mais l'IPC est largement différent : sans problèmes, la version rapide exécute une moyenne de 4,82 instructions par horloge pour l'ensemble du programme. (La plus grande partie de ce chiffre se trouve dans la boucle la plus interne qui exécute 5 instructions par cycle, grâce à un test/jz qui fusionne par macro 2 instructions en 1 uop). Et notez que uops_executed est beaucoup plus élevé que uops_issued : cela signifie que la micro-fusion fonctionne bien pour faire passer plus d'uops par le goulot d'étranglement frontal.

fast version, same read-only strlen(s)=1000 repeated 1280000 times

gcc -DUSE_ASM -DREAD_ONLY -UHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
 time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
 awk '{sum+= $1}  END{print sum/100;}' 

 Performance counter stats for './a.out' (100 runs):

             21.06 msec task-clock                #    0.994 CPUs utilized            ( +-  0.10% )
                 1      context-switches          #    0.056 K/sec                    ( +-  5.30% )
                 0      cpu-migrations            #    0.000 K/sec                  
               313      page-faults               #    0.015 M/sec                    ( +-  0.04% )
        86,239,943      cycles                    #    4.094 GHz                      ( +-  0.02% )
        82,285,261      branches                  # 3906.682 M/sec                    ( +-  0.00% )
            17,645      branch-misses             #    0.02% of all branches          ( +-  0.15% )
       415,286,425      instructions              #    4.82  insn per cycle           ( +-  0.00% )
       335,057,379      uops_issued.any           # 15907.619 M/sec                   ( +-  0.00% )
       409,255,762      uops_executed.thread      # 19430.358 M/sec                   ( +-  0.00% )

         0.0211944 +- 0.0000221 seconds time elapsed  ( +-  0.10% )

20504  (clock_t)

real    0m2.309s
user    0m2.085s
sys     0m0.203s

Je pense que c'est juste la prédiction de branchement, pas d'autres trucs frontaux qui posent problème. Les instructions de test/branchement ne sont pas divisées à travers une frontière qui empêcherait la macro-fusion.

Changement de .p2align 5 en .p2align 4 les inverse : -UHIDE_ALIGNMENT devient lent.

Ce lien binaire Godbolt reproduit le même padding que je vois avec gcc8.2.1 sur Arch Linux pour les deux cas : 2x 11-byte nopw + un 3-octet nop à l'intérieur de la boucle externe pour le cas rapide. Il a également la source exacte que j'utilisais localement.


short strlen micro-benchmarks en lecture seule :

Testé avec des choses choisies pour qu'il ne souffre pas de mauvaises prédictions de branche ou de store-forwarding, et qu'il puisse tester la même longueur courte de façon répétée pour suffisamment d'itérations pour obtenir des données significatives.

strlen=33donc le terminateur est près du début du 3ème vecteur de 16 octets. (Cela fait paraître ma version aussi mauvaise que possible par rapport à la version à 4 octets). -DREAD_ONLYet i<1280000 comme une boucle externe de répétition.

  • 1933 clock_t : mon asm: temps de meilleur cas agréable et cohérent (pas bruyant / rebondissant lors de la réexécution de la moyenne.) Perf équivalente avec/sans -DHIDE_ALIGNMENT, contrairement à la plus longue strlen. La branche de la boucle est beaucoup plus facilement prévisible avec ce motif beaucoup plus court. (strlen=33, pas 1000).
  • 3220 clock_t : gcc -O3 strlen. (-DHIDE_ALIGNMENT)
  • 6100 clock_t : gcc -O3 boucle de 4 octets
  • 37200 clock_t : gcc -O1 repz scasb

Ainsi, pour les chaînes courtes, ma simple boucle en ligne bat un appel de fonction de bibliothèque à strlen qui doit passer par le PLT (appel + jmp [mem]), puis exécuter le surcoût de démarrage de strlen qui ne peut pas dépendre de l'alignement.

Il y avait des prédictions négligeables de branche, comme 0,05% pour toutes les versions avec. strlen(s)=33. La version repz scasb avait 0,46%, mais c'est sur moins de branches totales. Pas de boucle interne pour accumuler de nombreuses branches correctement prédites.

Avec des prédicteurs de branches et un code-cache chaud, repz scasb est plus de 10x pire que d'appeler glibc strlen pour une chaîne de 33 octets. Ce serait moins mauvais dans les cas d'utilisation réels où strlen pourrait manquer de branchement ou même manquer dans le code-cache et caler, mais en ligne droite. repz scasb ne le ferait pas. Mais 10x est énorme, et c'est pour une chaîne assez courte.

notes et commentaires

Si ce post vous a été utile, il serait très utile que vous le partagiez avec plus de juniors, vous contribuerez ainsi à diffuser nos informations.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.