software Pourquoi ce code C++ est-il plus rapide que mon assembly manuscrit pour tester la conjecture de Collatz?




x86 instruction latency (9)

J'ai écrit ces deux solutions pour Project Euler Q14 , en assembly et en C ++. Ils sont la même approche de force brute identique pour tester la conjecture de Collatz . La solution d'assemblage a été assemblée avec

nasm -felf64 p14.asm && gcc p14.o -o p14

Le C ++ a été compilé avec

g++ p14.cpp -o p14

Assemblée, p14.asm

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

c1:
    inc r10
    cmp rax, 1
    jne l2

    cmp rdi, r10
    cmovl rdi, r10
    cmovl rsi, rcx

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C ++, p14.cpp

#include <iostream>

using namespace std;

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n*3 + 1;

        ++count;
    }

    return count;
}

int main() {
    int max = 0, maxi;
    for (int i = 999999; i > 0; --i) {
        int s = sequence(i);
        if (s > max) {
            max = s;
            maxi = i;
        }
    }

    cout << maxi << endl;
}

Je connais les optimisations du compilateur pour améliorer la vitesse et tout, mais je ne vois pas beaucoup de façons d'optimiser davantage ma solution d'assemblage (en parlant par programmation et non mathématiquement).

Le code C ++ a un module tous les termes et divisions tous les termes pairs, où l'assemblage est seulement une division par terme pair.

Mais l'assemblage prend en moyenne 1 seconde de plus que la solution C ++. Pourquoi est-ce? Je demande principalement de la curiosité.

Temps d'exécution

Mon système: Linux 64 bits sur Intel Celeron 2955U à 1,4 GHz (microarchitecture Haswell).

  • g++ (non optimisé): moy 1272 ms

  • g++ -O3 moy 578 ms

  • original asm (div) moy. 2650 ms

  • Asm (shr) moy 679 ms

  • @johnfound asm , assemblé avec nasm avg 501 ms

  • @hidefromkgb asm avg 200 ms

  • @hidefromkgb asm optimisé par @Peter Cordes avg 145 ms

  • @Veedrac C ++ moy 81 ms avec -O3 , 305 ms avec -O0


The simple answer:

  • doing a MOV RBX, 3 and MUL RBX is expensive; just ADD RBX, RBX twice

  • ADD 1 is probably faster than INC here

  • MOV 2 and DIV is very expensive; just shift right

  • 64-bit code is usually noticeably slower than 32-bit code and the alignment issues are more complicated; with small programs like this you have to pack them so you are doing parallel computation to have any chance of being faster than 32-bit code

If you generate the assembly listing for your C++ program, you can see how it differs from your assembly.


Even without looking at assembly, the most obvious reason is that /= 2 is probably optimized as >>=1 and many processors have a very quick shift operation. But even if a processor doesn't have a shift operation, the integer division is faster than floating point division.

Edit: your milage may vary on the "integer division is faster than floating point division" statement above. The comments below reveal that the modern processors have prioritized optimizing fp division over integer division. So if someone were looking for the most likely reason for the speedup which this thread's question asks about, then compiler optimizing /=2 as >>=1 would be the best 1st place to look.

On an unrelated note , if n is odd, the expression n*3+1 will always be even. So there is no need to check. You can change that branch to

{
   n = (n*3+1) >> 1;
   count += 2;
}

So the whole statement would then be

if (n & 1)
{
    n = (n*3 + 1) >> 1;
    count += 2;
}
else
{
    n >>= 1;
    ++count;
}

On a rather unrelated note: more performance hacks!

  • [the first «conjecture» has been finally debunked by @ShreevatsaR; removed]

  • When traversing the sequence, we can only get 3 possible cases in the 2-neighborhood of the current element N (shown first):

    1. [even] [odd]
    2. [odd] [even]
    3. [even] [even]

    To leap past these 2 elements means to compute (N >> 1) + N + 1 , ((N << 1) + N + 1) >> 1 and N >> 2 , respectively.

    Let`s prove that for both cases (1) and (2) it is possible to use the first formula, (N >> 1) + N + 1 .

    Case (1) is obvious. Case (2) implies (N & 1) == 1 , so if we assume (without loss of generality) that N is 2-bit long and its bits are ba from most- to least-significant, then a = 1 , and the following holds:

    (N << 1) + N + 1:     (N >> 1) + N + 1:
    
            b10                    b1
             b1                     b
           +  1                   + 1
           ----                   ---
           bBb0                   bBb
    

    where B = !b . Right-shifting the first result gives us exactly what we want.

    QED: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1 .

    As proven, we can traverse the sequence 2 elements at a time, using a single ternary operation. Another 2× time reduction.

The resulting algorithm looks like this:

uint64_t sequence(uint64_t size, uint64_t *path) {
    uint64_t n, i, c, maxi = 0, maxc = 0;

    for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
        c = 2;
        while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
            c += 2;
        if (n == 2)
            c++;
        if (c > maxc) {
            maxi = i;
            maxc = c;
        }
    }
    *path = maxc;
    return maxi;
}

int main() {
    uint64_t maxi, maxc;

    maxi = sequence(1000000, &maxc);
    printf("%llu, %llu\n", maxi, maxc);
    return 0;
}

Here we compare n > 2 because the process may stop at 2 instead of 1 if the total length of the sequence is odd.

[EDIT:]

Let`s translate this into assembly!

MOV RCX, 1000000;



DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;

@main:
  XOR RSI, RSI;
  LEA RDI, [RCX + 1];

  @loop:
    ADD RSI, 2;
    LEA RDX, [RDI + RDI*2 + 2];
    SHR RDX, 1;
    SHRD RDI, RDI, 2;    ror rdi,2   would do the same thing
    CMOVL RDI, RDX;      Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
    CMOVS RDI, RDX;
    CMP RDI, 2;
  JA @loop;

  LEA RDX, [RSI + 1];
  CMOVE RSI, RDX;

  CMP RAX, RSI;
  CMOVB RAX, RSI;
  CMOVB RBX, RCX;

  SUB RCX, 2;
JA @main;



MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;

@itoa:
  XOR RDX, RDX;
  DIV RCX;
  ADD RDX, '0';
  PUSH RDX;
  TEST RAX, RAX;
JNE @itoa;

  PUSH RCX;
  LEA RAX, [RBX + 1];
  TEST RBX, RBX;
  MOV RBX, RDI;
JNE @itoa;

POP RCX;
INC RDI;
MOV RDX, RDI;

@outp:
  MOV RSI, RSP;
  MOV RAX, RDI;
  SYSCALL;
  POP RAX;
  TEST RAX, RAX;
JNE @outp;

LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;

Use these commands to compile:

nasm -f elf64 file.asm
ld -o file file.o

See the C and an improved/bugfixed version of the asm by Peter Cordes on Godbolt . (editor's note: Sorry for putting my stuff in your answer, but my answer hit the 30k char limit from Godbolt links + text!)


Si vous pensez qu'une instruction DIV 64 bits est un bon moyen de diviser par deux, il n'est pas étonnant que la sortie asm du compilateur batte votre code manuscrit, même avec -O0 (compilation rapide, pas d'optimisation supplémentaire et stockage / rechargement en mémoire après / avant chaque instruction C afin qu'un débogueur puisse modifier les variables).

Consultez le guide d' optimisation de l'assemblage Agner Fog pour apprendre comment écrire efficacement asm. Il a également des tables d'instructions et un guide de microarch pour des détails spécifiques pour des processeurs spécifiques. Voir aussi le wiki tag x86 pour plus de liens perf.

Voir aussi cette question plus générale sur la façon de battre le compilateur avec asm écrit à la main: Le langage d'assemblage en ligne est-il plus lent que le code C ++ natif? . TL: DR: oui si vous le faites mal (comme cette question).

Habituellement, vous pouvez laisser le compilateur faire son travail, surtout si vous essayez d'écrire en C ++ qui peut compiler efficacement . Voir aussi l' assemblage plus rapide que les langages compilés? . L'une des réponses renvoie à ces diapositives montrant comment les différents compilateurs C optimisent certaines fonctions très simples avec des astuces sympas.

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

Sur Intel Haswell, div r64 est 36 uops, avec une latence de 32-96 cycles , et un débit de un par 21-74 cycles. (Plus les 2 uops pour mettre en place RBX et zéro RDX, mais l'exécution dans le désordre peut les exécuter tôt). Les instructions de comptage de haut-nombre comme DIV sont microcodées, ce qui peut également provoquer des goulots d'étranglement frontaux. Dans ce cas, la latence est le facteur le plus important car il fait partie d'une chaîne de dépendances bouclée.

shr rax, 1 fait la même division non signée: c'est 1 uop, avec 1c de latence , et peut courir 2 par cycle d'horloge.

A titre de comparaison, la division en 32 bits est plus rapide, mais toujours horrible par rapport aux changements. idiv r32 est 9 uops, 22-29c latence, et un par 8-11c débit sur Haswell.

Comme vous pouvez le voir en regardant la sortie -O0 asm de gcc ( explorateur de compilateur Godbolt ), il n'utilise que des instructions de changement . clang -O0 compile naïvement comme vous le pensiez, même en utilisant IDIV 64 bits deux fois. (Lors de l'optimisation, les compilateurs utilisent les deux sorties de IDIV quand la source fait une division et un module avec les mêmes opérandes, s'ils utilisent IDIV du tout)

GCC n'a pas un mode totalement naïf; il se transforme toujours via GIMPLE, ce qui signifie que certaines "optimisations" ne peuvent pas être désactivées . Cela comprend la reconnaissance de divisions par constantes et l'utilisation de décalages (puissance de 2) ou d' un inverse multiplicatif à virgule fixe (non puissance de 2) pour éviter l'IDIV (voir div_by_13 dans le lien godbolt ci-dessus).

gcc -Os (optimiser pour la taille) utilise IDIV pour la division non-power-of-2, malheureusement même dans les cas où le code inverse multiplicatif n'est que légèrement plus grand mais beaucoup plus lent.

Aider le compilateur

(résumé pour ce cas: utilisez uint64_t n )

Tout d'abord, il est intéressant de regarder la sortie du compilateur optimisé. ( -O3 ). -O0 vitesse est fondamentalement dénuée de sens.

Regardez votre sortie asm (sur Godbolt, ou voir Comment supprimer le "bruit" de la sortie de l'assemblage GCC / clang? ). Quand le compilateur ne fait pas de code optimal en premier lieu: Ecrire votre source C / C ++ de façon à guider le compilateur vers un meilleur code est généralement la meilleure approche . Vous devez connaître l'ASM et savoir ce qui est efficace, mais vous appliquez indirectement cette connaissance. Les compilateurs sont aussi une bonne source d'idées: parfois clang va faire quelque chose de cool, et vous pouvez tenir gcc en faisant la même chose: voir cette réponse et ce que j'ai fait avec la boucle non déroulée dans le code @ Veedrac ci-dessous.

Cette approche est portable et, dans 20 ans, un compilateur à venir peut la compiler pour tout ce qui est efficace sur le futur matériel (x86 ou non), peut-être en utilisant une nouvelle extension ISA ou une auto-vectorisation. L'asm x86-64 écrit à la main il y a 15 ans ne serait généralement pas optimisé pour Skylake. Par exemple, comparez et branchez la macro-fusion n'existait pas à l'époque. Ce qui est optimal maintenant pour une architecture artisanale pour une microarchitecture pourrait ne pas être optimal pour d'autres processeurs actuels et futurs. Commentaires sur la réponse de @ johnfound discuter des différences majeures entre AMD Bulldozer et Intel Haswell, qui ont un grand effet sur ce code. Mais en théorie, g++ -O3 -march=bdver3 et g++ -O3 -march=skylake fera la bonne chose. (Ou -march=native .) Ou -mtune=... juste syntoniser, sans utiliser d'instructions que d'autres processeurs pourraient ne pas supporter.

Mon sentiment est que guider le compilateur vers ASM qui est bon pour un CPU actuel vous intéresse ne devrait pas être un problème pour les compilateurs futurs. Ils sont, espérons-le, meilleurs que les compilateurs actuels pour trouver des moyens de transformer le code, et peuvent trouver un moyen de fonctionner pour les futurs processeurs. Quoi qu'il en soit, le futur x86 ne sera probablement pas terrible à tout ce qui est bon sur le x86 actuel, et le futur compilateur évitera les pièges spécifiques à asm lors de l'implémentation du mouvement de données de votre source C s'il ne voit pas mieux.

Asm écrit à la main est une boîte noire pour l'optimiseur, donc la propagation constante ne fonctionne pas lorsque inlining fait une entrée une constante de compilation. D'autres optimisations sont également affectées. Lisez https://gcc.gnu.org/wiki/DontUseInlineAsm avant d'utiliser asm. (Et évitez les asm inline de type MSVC: les entrées / sorties doivent passer par la mémoire, ce qui ajoute un surcoût .)

Dans ce cas : votre n a un type signé, et gcc utilise la séquence SAR / SHR / ADD qui donne l'arrondi correct. (IDIV et décalage arithmétique "round" différemment pour les entrées négatives, voir l' entrée du manuel de référence d'insn SAR setn ). (IDK si gcc a essayé et n'a pas réussi à prouver que n ne peut pas être négatif, ou quoi.) Signed-overflow est un comportement indéfini, donc il aurait dû pouvoir le faire.)

Vous auriez dû utiliser uint64_t n , donc ça peut juste SHR. Et donc il est portable sur les systèmes où la long est seulement de 32 bits (par exemple x86-64 Windows).

BTW, la sortie asm optimisée de gcc semble assez bonne (en utilisant unsigned long n ) : la boucle interne qu'elle insère dans main() fait:

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

La boucle interne est dépourvue de branchement et le chemin critique de la chaîne de dépendances transportée par boucle est:

  • LEA à 3 composants (3 cycles)
  • cmov (2 cycles sur Haswell, 1c sur Broadwell ou plus tard).

Total: 5 cycles par itération, goulot d'étranglement de latence . L'exécution en désordre s'occupe de tout le reste parallèlement à cela (en théorie: je n'ai pas testé avec les compteurs de perf pour voir si ça fonctionne vraiment en 5c / iter).

L'entrée FLAGS de cmov (produite par TEST) est plus rapide à produire que l'entrée RAX (de LEA-> MOV), donc elle n'est pas sur le chemin critique.

De même, le MOV-> SHR qui produit l'entrée RDI de CMOV est hors du chemin critique, car il est également plus rapide que le LEA. MOV sur IvyBridge et plus tard a latence nulle (manipulé à l'heure de registre-renommer). (Il faut encore un uop, et un slot dans le pipeline, donc ce n'est pas gratuit, juste une latence nulle). Le MOV supplémentaire dans la chaîne de dépôt LEA fait partie du goulot d'étranglement sur les autres processeurs.

Le cmp / jne ne fait pas non plus partie du chemin critique: il n'est pas bouclé, car les dépendances de contrôle sont gérées avec une prédiction de branche + une exécution spéculative, contrairement aux dépendances de données sur le chemin critique.

Battre le compilateur

GCC a fait du bon travail ici. Il pourrait sauver un octet de code en utilisant inc edx au lieu d' add edx, 1 , parce que personne ne se soucie de P4 et de ses fausses dépendances pour les instructions de modification de drapeau partiel.

Il pourrait également enregistrer toutes les instructions MOV, et le TEST: SHR place CF = le bit déplacé, donc nous pouvons utiliser cmovc au lieu de test / cmovz .

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

Voir la réponse de @ johnfound pour une autre astuce intelligente: supprimer le CMP en dérivant sur le résultat du drapeau de SHR et en l'utilisant pour CMOV: zéro seulement si n était 1 (ou 0) pour commencer. (Fait amusant: SHR avec count! = 1 sur Nehalem ou plus tôt provoque un décrochage si vous lisez les résultats du drapeau, c'est comme ça qu'ils l'ont fait en single-uop, mais l'encodage spécial shift-by-1 est bien.)

Éviter MOV n'aide pas du tout à la latence sur Haswell ( le MOV de Can x86 peut-il vraiment être "libre"? Pourquoi ne puis-je pas le reproduire du tout? ). Il aide de manière significative sur les processeurs comme Intel pré-IvB, et la famille AMD Bulldozer, où MOV n'est pas à latence nulle. Les instructions MOV gaspillées du compilateur affectent le chemin critique. Les complexes LEA et CMOV de BD sont tous les deux moins latents (respectivement 2c et 1c), ce qui représente une plus grande fraction de la latence. De plus, les goulots d'étranglement du débit deviennent un problème, car il ne comporte que deux canaux ALU entiers. Voir la réponse @ johnfound , où il a des résultats de synchronisation d'un processeur AMD.

Même sur Haswell, cette version peut aider un peu en évitant certains retards occasionnels où un uop non critique vole un port d'exécution de l'un sur le chemin critique, retardant l'exécution d'un cycle. (Ceci est appelé un conflit de ressources). Il enregistre également un registre, ce qui peut aider lors de l'exécution de plusieurs valeurs n en parallèle dans une boucle entrelacée (voir ci-dessous).

La latence de LEA dépend du mode d'adressage , sur les processeurs Intel SnB. 3c pour 3 composants ( [base+idx+const] , qui prend deux additions séparées), mais seulement 1c avec 2 composants ou moins (un ajout). Certains processeurs (comme Core2) font même un LEA à trois composants en un seul cycle, mais pas la famille SnB. Pire, la famille Intel SnB standardise les latences, donc il n'y a pas de 2c uops , sinon le LEA à 3 composants serait seulement 2c comme Bulldozer. (LEA à 3 composants est également plus lent sur AMD, mais pas autant).

Donc lea rcx, [rax + rax*2] / inc rcx est seulement 2c de latence, plus rapide que lea rcx, [rax + rax*2 + 1] , sur les processeurs Intel SnB comme Haswell. Break-even sur BD, et pire sur Core2. Cela coûte un coût supplémentaire, ce qui normalement ne vaut pas la peine d'économiser 1c de latence, mais la latence est le principal goulot d'étranglement ici et Haswell a un pipeline assez large pour gérer le débit supplémentaire.

Ni gcc, icc, ni clang (sur godbolt) n'utilisaient la sortie CF de SHR, toujours en utilisant un AND ou TEST . Compilateurs stupides. : P Ils sont de superbes machines complexes, mais un humain intelligent peut souvent les battre sur des problèmes de petite taille. (Etant donné des milliers et des millions de fois plus longs à y penser, les compilateurs n'utilisent pas d'algorithmes exhaustifs pour chercher toutes les manières possibles de faire les choses, car cela prendrait trop de temps pour optimiser beaucoup de code en ligne, ils font mieux, ils ne modélisent pas non plus le pipeline dans la microarchitecture cible, ils utilisent simplement des heuristiques.)

Le déroulement simple de la boucle n'aidera pas ; cette boucle goulot d'étranglement sur la latence d'une chaîne de dépendances transportée en boucle, et non sur la surcharge / le débit de la boucle. Cela signifie qu'il ferait bien avec hyperthreading (ou tout autre type de SMT), car le CPU a beaucoup de temps pour entrelacer les instructions de deux threads. Cela signifierait paralléliser la boucle dans main , mais c'est bien parce que chaque thread peut simplement vérifier une plage de n valeurs et produire une paire d'entiers en conséquence.

Entrelacement à la main dans un seul fil pourrait être viable, aussi . Peut-être calculer la séquence pour une paire de nombres en parallèle, puisque chacun ne prend que quelques registres, et ils peuvent tous mettre à jour le même max / maxi . Cela crée plus de parallélisme au niveau de l'instruction .

L'astuce est de décider si attendre que toutes les n valeurs aient atteint 1 avant d'avoir une autre paire de valeurs de départ n , ou si on doit sortir et obtenir un nouveau point de départ pour une seule qui a atteint la condition finale, sans toucher aux registres pour autre séquence. Il est probablement préférable de laisser chaque chaîne travailler sur des données utiles, sinon vous devrez incrémenter son compteur de manière conditionnelle.

Vous pourriez peut-être même le faire avec SSE packed-compare stuff pour incrémenter conditionnellement le compteur pour les éléments vectoriels où n n'avait pas encore atteint 1 . Et puis, pour masquer la latence encore plus longue d'une implémentation d'incréments conditionnels SIMD, vous devez conserver plus de vecteurs de n valeurs dans l'air. Peut-être seulement la valeur avec le vecteur 256b (4x uint64_t ).

Je pense que la meilleure stratégie pour faire la détection d'un 1 "sticky" est de masquer le vecteur de tous ceux que vous ajoutez pour incrémenter le compteur. Donc, après avoir vu un 1 dans un élément, le vecteur d'incrément aura un zéro, et + = 0 est un no-op.

Idée non testée pour la vectorisation manuelle

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vprllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure.  Probably worth it
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

Vous pouvez et devez mettre en œuvre ceci avec des intrinsèques, au lieu d'asm écrit à la main.

Algorithmique / amélioration de la mise en œuvre:

En plus d'implémenter la même logique avec un ASM plus efficace, cherchez des moyens de simplifier la logique, ou évitez le travail redondant. ex. mémoize pour détecter les fins communes aux séquences. Ou encore mieux, regardez 8 bits de fuite à la fois (réponse gnasher)

@EOF souligne que tzcnt (ou bsf ) pourrait être utilisé pour faire plusieurs n/=2 itérations en une seule étape. C'est probablement mieux que la vectorisation SIMD, car aucune instruction SSE ou AVX ne peut le faire. Cependant, il est toujours compatible avec plusieurs n scalaires parallèles dans différents registres entiers.

Donc, la boucle pourrait ressembler à ceci:

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

Cela peut faire beaucoup moins d'itérations, mais les changements de nombre de variables sont lents sur les processeurs de la famille Intel SnB sans BMI2. 3 uops, 2c de latence. (Ils ont une dépendance d'entrée sur les FLAGS car count = 0 signifie que les flags ne sont pas modifiés, ils gèrent cela comme une dépendance aux données, et prennent plusieurs Uops parce qu'un uop ne peut avoir que 2 entrées (pré-HSW / BDW)). C'est le genre auquel se réfèrent les gens qui se plaignent du design fou de CISC de x86. Il rend les processeurs x86 plus lents qu'ils ne le seraient si l'ISA était conçue à partir de zéro aujourd'hui, même de manière quasi-similaire. (c'est-à-dire que cela fait partie de la "taxe x86" qui coûte de la vitesse / puissance.) SHRX / SHLX / SARX (BMI2) sont une grosse victoire (1 uop / 1c de latence).

Il place également tzcnt (3c sur Haswell et plus tard) sur le chemin critique, ce qui allonge considérablement la latence totale de la chaîne de dépendances bouclée. Il supprime tout besoin d'un CMOV, ou pour préparer un registre contenant n>>1 , cependant. La réponse de Veedrac surmonte tout cela en reportant le tzcnt / shift pour des itérations multiples, ce qui est très efficace (voir ci-dessous).

Nous pouvons utiliser BSF ou TZCNT façon interchangeable, car n ne peut jamais être nul à ce moment-là. Le code machine de TZCNT est décodé en tant que BSF sur les CPU qui ne supportent pas BMI1. (Les préfixes sans signification sont ignorés, donc REP BSF s'exécute comme BSF).

TZCNT fonctionne beaucoup mieux que BSF sur les CPU AMD qui le supportent, donc ce peut être une bonne idée d'utiliser REP BSF , même si vous ne vous souciez pas de la configuration de ZF si l'entrée est zéro plutôt que la sortie. Certains compilateurs le font quand vous utilisez __builtin_ctzll même avec -mno-bmi .

Ils effectuent la même chose sur les processeurs Intel, il suffit donc de sauvegarder l'octet si c'est tout ce qui compte. TZCNT sur Intel (pré-Skylake) a encore une fausse dépendance sur l'opérande de sortie censé être en écriture seule, tout comme BSF, pour supporter le comportement non documenté que BSF avec input = 0 laisse sa destination non modifiée. Vous avez donc besoin de contourner ce problème, sauf si vous optimisez uniquement pour Skylake, donc il n'y a rien à gagner de l'octet REP supplémentaire. (Intel va souvent au-delà de ce qu'exige le manuel x86 ISA, pour éviter de casser un code largement utilisé qui dépend de quelque chose qu'il ne devrait pas ou qui est rétroactivement interdit. lorsque le code a été écrit, avant qu'Intel ne mette à jour les règles de gestion TLB .)

Quoi qu'il en soit, LZCNT / TZCNT sur Haswell ont la même fausse note que POPCNT: voir ce Q & A. C'est pourquoi dans la sortie asm de gcc pour le code de @ Veedrac, vous voyez qu'il casse la chaîne dep avec xor-zeroing sur le registre qu'il est sur le point d'utiliser comme destination de TZCNT, quand il n'utilise pas dst = src. Puisque TZCNT / LZCNT / POPCNT ne laissent jamais leur destination indéfinie ou non modifiée, cette fausse dépendance à la sortie sur les processeurs Intel est purement un bug / une limitation de performance. Vraisemblablement, cela vaut la peine de disposer de transistors / puissances pour les faire se comporter comme d'autres uops qui vont à la même unité d'exécution. Le seul avantage visible du logiciel est dans l'interaction avec une autre limitation microarchitectural: ils peuvent micro-fusionner un opérande de mémoire avec un mode d'adressage indexé sur Haswell, mais sur Skylake où Intel a enlevé la fausse dépendance pour LZCNT / TZCNT ils "non-stratifient" modes d'adressage indexés tandis que POPCNT peut toujours micro-fusionner n'importe quel mode addr.

Améliorations apportées aux idées / code provenant d'autres réponses:

La réponse de @ hidefromkgb a une bonne observation que vous êtes assuré de pouvoir faire un bon décalage après un 3n + 1. Vous pouvez calculer cela plus encore plus efficacement que simplement laisser de côté les contrôles entre les étapes. L'implémentation d'asm dans cette réponse est cependant cassée (elle dépend de OF, qui est indéfinie après SHRD avec un nombre> 1), et lente: ROR rdi,2 est plus rapide que SHRD rdi,rdi,2 , et utilise deux instructions CMOV sur le chemin critique est plus lent qu'un TEST supplémentaire qui peut fonctionner en parallèle.

J'ai mis en ordre / amélioré C (qui guide le compilateur pour produire mieux asm), et testé + travaillant plus vite asm (dans les commentaires ci-dessous le C) sur Godbolt: voir le lien dans la réponse @ hidefromkgb . (Cette réponse atteint la limite de 30 Ko des grandes URL Godbolt, mais les liens courts peuvent pourrir et sont trop longs pour goo.gl de toute façon.)

Amélioré également l'impression de sortie pour convertir en une chaîne et faire un write() au lieu d'écrire un char à la fois. Cela minimise l'impact sur le chronométrage de l'ensemble du programme avec perf stat ./collatz (pour enregistrer les compteurs de performance), et je de-obfuscated une partie de l' perf stat ./collatz non critique.

Le code de @ Veedrac

J'ai reçu une très petite accélération de la part de droite autant que nous le sachions , et j'ai vérifié pour continuer la boucle. De 7.5s pour la limite = 1e8 jusqu'à 7.275s, sur Core2Duo (Merom), avec un facteur de déroulement de 16.

code + commentaires sur Godbolt . N'utilisez pas cette version avec clang; il fait quelque chose de stupide avec la boucle de déferlement. Utiliser un compteur tmp k et ensuite l'ajouter pour count plus tard change ce que fait le clang, mais cela blesse légèrement gcc.

Voir la discussion dans les commentaires: le code de Veedrac est excellent sur les processeurs avec BMI1 (c.-à-d. Pas Celeron / Pentium)


You did not post the code generated by the compiler, so there' some guesswork here, but even without having seen it, one can say that this:

test rax, 1
jpe even

... has a 50% chance of mispredicting the branch, and that will come expensive.

The compiler almost certainly does both computations (which costs neglegibly more since the div/mod is quite long latency, so the multiply-add is "free") and follows up with a CMOV. Which, of course, has a zero percent chance of being mispredicted.


C++ programs are translated to assembly programs during the generation of machine code from the source code. It would be virtually wrong to say assembly is slower than C++. Moreover, the binary code generated differs from compiler to compiler. So a smart C++ compiler may produce binary code more optimal and efficient than a dumb assembler's code.

However I believe your profiling methodology has certain flaws. The following are general guidelines for profiling:

  1. Make sure your system is in its normal/idle state. Stop all running processes (applications) that you started or that use CPU intensively (or poll over the network).
  2. Your datasize must be greater in size.
  3. Your test must run for something more than 5-10 seconds.
  4. Do not rely on just one sample. Perform your test N times. Collect results and calculate the mean or median of the result.

As a generic answer, not specifically directed at this task: In many cases, you can significantly speed up any program by making improvements at a high level. Like calculating data once instead of multiple times, avoiding unnecessary work completely, using caches in the best way, and so on. These things are much easier to do in a high level language.

Writing assembler code, it is possible to improve on what an optimising compiler does, but it is hard work. And once it's done, your code is much harder to modify, so it is much more difficult to add algorithmic improvements. Sometimes the processor has functionality that you cannot use from a high level language, inline assembly is often useful in these cases and still lets you use a high level language.

In the Euler problems, most of the time you succeed by building something, finding why it is slow, building something better, finding why it is slow, and so on and so on. That is very, very hard using assembler. A better algorithm at half the possible speed will usually beat a worse algorithm at full speed, and getting the full speed in assembler isn't trivial.


Affirmer que le compilateur C ++ peut produire un code plus optimal qu'un programmeur de langage assembleur compétent est une très mauvaise erreur. Et surtout dans ce cas. L'humain peut toujours améliorer le code que le compilateur peut, et cette situation particulière illustre bien cette affirmation.

La différence de synchronisation que vous voyez est parce que le code d'assemblage dans la question est très loin d'être optimal dans les boucles internes.

(Le code ci-dessous est 32 bits, mais peut être facilement converti en 64 bits)

Par exemple, la fonction de séquence peut être optimisée pour seulement 5 instructions:

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

L'ensemble du code ressemble à:

include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"

start:
        InitializeAll
        mov ecx, 999999
        xor edi, edi        ; max
        xor ebx, ebx        ; max i

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

        cmp     edi, esi
        cmovb   edi, esi
        cmovb   ebx, ecx

        dec     ecx
        jnz     .main_loop

        OutputValue "Max sequence: ", edi, 10, -1
        OutputValue "Max index: ", ebx, 10, -1

        FinalizeAll
        stdcall TerminateAll, 0

Afin de compiler ce code, FreshLib est nécessaire.

Dans mes tests, (processeur AMD A4-1200 1 GHz), le code ci-dessus est environ quatre fois plus rapide que le code C ++ de la question (compilé avec -O0 : 430 ms contre 1900 ms), et plus de deux fois plus vite (430 ms contre 830 ms) lorsque le code C ++ est compilé avec -O3 .

La sortie des deux programmes est la même: séquence max = 525 sur i = 837799.


For the Collatz problem, you can get a significant boost in performance by caching the "tails". This is a time/memory trade-off. See: memoization ( https://en.wikipedia.org/wiki/Memoization ). You could also look into dynamic programming solutions for other time/memory trade-offs.

Example python implementation:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))






x86