J'ai écrit ces deux solutions pour Project Euler Q14 , en assembleur et en C ++. Il s'agit de 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 à chaque terme et une division à chaque terme pair, où l'assemblage n'est qu'une division par terme pair.

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

Délais d'exécution

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

• g++ (non optimisé): 1272 ms en moyenne

• g++ -O3 moyenne 578 ms

• asm d'origine (div) moy 2650 ms

• Asm (shr) moyenne 679 ms

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

• @hidefromkgb asm avg 200 ms

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

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

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

Consultez le guide d' optimisation d'assemblage d'Agner Fog pour savoir comment écrire un asm efficace. Il a également des tables d'instructions et un guide microarch pour des détails spécifiques pour des CPU spécifiques. Voir aussi lex86 balise wiki pour plus de liens perf.

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

Habituellement, vous pouvez laisser le compilateur faire son travail, surtout si vous essayez d'écrire C ++ qui peut compiler efficacement . Voir aussi l' assemblage est plus rapide que les langages compilés? . L'une des réponses renvoie à ces diapositives soignées montrant comment divers compilateurs C optimisent certaines fonctions vraiment simples avec des astuces intéressantes. CppCon2017 de Matt Godbolt: « Qu'est-ce que mon compilateur a fait pour moi récemment? Déboulonner le couvercle du compilateur »est dans la même veine.

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

Sur Intel Haswell, div r64c'est 36 uops, avec une latence de 32-96 cycles , et un débit d'un par 21-74 cycles. (Plus les 2 uops pour configurer RBX et zéro RDX, mais une exécution dans le désordre peut être exécutée tôt). Les instructions à nombre d'uop élevé 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 pertinent car elle fait partie d'une chaîne de dépendance portée par la boucle.

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

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

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

GCC n'a pas de 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 la division par constante 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_13dans le lien Godbolt ci-dessus).

gcc -Os(pour optimiser la taille) ne utilisation IDIV pour la division non-power-of-2, malheureusement , même dans les cas où le code inverse multiplicatif est légèrement plus grande , mais beaucoup plus rapide.

Aider le compilateur

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

Tout d'abord, il est seulement intéressant de regarder la sortie optimisée du compilateur. ( -O3). -O0la vitesse n'a pratiquement aucun sens.

Regardez votre sortie asm (sur Godbolt, ou consultez Comment supprimer le "bruit" de la sortie de l'assemblage GCC / clang? ). Lorsque le compilateur ne crée pas de code optimal en premier lieu: l' écriture de votre source C / C ++ d'une manière qui guide le compilateur dans la création d'un meilleur code est généralement la meilleure approche . Vous devez connaître asm et savoir ce qui est efficace, mais vous appliquez ces connaissances indirectement. Les compilateurs sont également une bonne source d'idées: parfois clang fera quelque chose de cool, et vous pouvez aider gcc à faire la même chose: voir cette réponse et ce que j'ai fait avec la boucle non déroulée dans le code de @ Veedrac ci-dessous.)

Cette approche est portable, et dans 20 ans, un futur compilateur pourra le compiler en tout ce qui sera efficace sur le futur matériel (x86 ou non), peut-être en utilisant une nouvelle extension ISA ou une vectorisation automatique. Asm x86-64 manuscrite d'il y a 15 ans ne serait généralement pas optimisé pour Skylake. Par exemple, la macro-fusion de comparaison et de branche n'existait pas à l'époque. Ce qui est optimal maintenant pour un asm fabriqué à la main pour une microarchitecture peut ne pas être optimal pour d'autres CPU actuels et futurs. Les commentaires sur la réponse de @ johnfound discutent 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=bdver3et g++ -O3 -march=skylakefera la bonne chose. (Ou -march=native.) Ou -mtune=...simplement régler, sans utiliser d'instructions que d'autres processeurs pourraient ne pas prendre en charge.

Mon sentiment est que guider le compilateur vers asm qui est bon pour un processeur actuel dont vous vous souciez ne devrait pas être un problème pour les futurs compilateurs. Nous espérons qu'ils sont meilleurs que les compilateurs actuels pour trouver des moyens de transformer le code, et peuvent trouver un moyen qui fonctionne pour les futurs processeurs. Quoi qu'il en soit, le futur x86 ne sera probablement pas terrible pour tout ce qui est bon sur le x86 actuel, et le futur compilateur évitera tous les pièges spécifiques à asm tout en implémentant quelque chose comme le mouvement de données depuis votre source C, s'il ne voit pas mieux.

L'asm manuscrit est une boîte noire pour l'optimiseur, donc la propagation constante ne fonctionne pas lorsque l'inlining fait d'une entrée une constante au moment de la compilation. D'autres optimisations sont également affectées. Lisez https://gcc.gnu.org/wiki/DontUseInlineAsm avant d'utiliser asm. (Et évitez l'asm en ligne de style MSVC: les entrées / sorties doivent passer par la mémoire, ce qui ajoute de la surcharge .)

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

Vous auriez dû utiliser uint64_t n, donc il peut simplement SHR. Et donc il est portable pour les systèmes où il longn'y a que 32 bits (par exemple Windows x86-64).

BTW, la sortie asm optimisée de gcc semble assez bonne (en utilisant unsigned long n) : la boucle interne dans laquelle elle est insérée main()fait ceci:

 # 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 sans branche, et le chemin critique de la chaîne de dépendance portée par la 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 dans le désordre s'occupe de tout le reste en parallèle avec cela (en théorie: je n'ai pas testé avec des compteurs de performances pour voir s'il fonctionne vraiment à 5c / iter).

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

De même, le MOV-> SHR qui produit l'entrée RDI du CMOV est hors du chemin critique, car il est également plus rapide que le LEA. MOV sur IvyBridge et plus tard n'a aucune latence (géré au moment du changement de nom de registre). (Il faut toujours 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épose LEA fait partie du goulot d'étranglement des autres processeurs.

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

Battre le compilateur

GCC a fait du très bon travail ici. Il pourrait enregistrer un octet de code en utilisant à la inc edxplace deadd edx, 1 , car 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 définit CF = le bit décalé, afin que nous puissions utiliser à la cmovcplace 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: supprimez le CMP en vous ramifiant sur le résultat du drapeau de SHR ainsi qu'en l'utilisant pour CMOV: zéro uniquement si n était 1 (ou 0) pour commencer. (Fait amusant: SHR avec count! = 1 sur Nehalem ou une version antérieure provoque un blocage si vous lisez les résultats de l'indicateur .

Éviter le MOV n'aide pas du tout avec la latence sur Haswell ( le MOV de x86 peut-il vraiment être "gratuit"? Pourquoi ne puis-je pas le reproduire du tout? ). Cela aide considérablement sur les processeurs comme Intel pré-IvB et AMD Bulldozer-family, où MOV n'est pas à latence nulle. Les instructions MOV perdues du compilateur affectent le chemin critique. Le LEA complexe et le CMOV de BD ont tous deux une latence plus faible (2c et 1c respectivement), c'est donc une plus grande fraction de la latence. De plus, les goulots d'étranglement du débit deviennent un problème, car il ne possède que deux canaux ALU entiers. Voir la réponse de @ johnfound , où il a les résultats de synchronisation d'un processeur AMD.

Même sur Haswell, cette version peut aider un peu en évitant certains retards occasionnels où une uop non critique vole un port d'exécution à l'un sur le chemin critique, retardant l'exécution d'un cycle. (Cela s'appelle un conflit de ressources). Il enregistre également un registre, ce qui peut être utile lorsque vous effectuez plusieurs nvaleurs en parallèle dans une boucle entrelacée (voir ci-dessous).

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

Donc lea rcx, [rax + rax*2]/ inc rcxest que la latence 2c, plus rapide que lea rcx, [rax + rax*2 + 1]sur les processeurs Intel SNB-famille comme Haswell. Le seuil de rentabilité sur BD, et pire sur Core2. Cela coûte un uop supplémentaire, ce qui ne vaut généralement pas la peine d'économiser la latence 1c, mais la latence est le principal goulot d'étranglement ici et Haswell dispose d'un pipeline suffisamment large pour gérer le débit d'uop supplémentaire.

Ni gcc, icc, ni clang (sur godbolt) n'utilisaient la sortie CF de SHR, utilisant toujours un AND ou TEST . Compilateurs stupides. : P Ce sont d'excellentes pièces de machines complexes, mais un humain intelligent peut souvent les battre sur des problèmes à petite échelle. (Étant donné des milliers à des millions de fois plus de temps pour y penser, bien sûr! Les compilateurs n'utilisent pas d'algorithmes exhaustifs pour rechercher toutes les façons possibles de faire les choses, car cela prendrait trop de temps lors de l'optimisation de beaucoup de code en ligne, ce qui est ce que Ils ne modélisent pas non plus le pipeline dans la microarchitecture cible, du moins pas dans les mêmes détails que IACA ou d'autres outils d'analyse statique; ils utilisent simplement quelques heuristiques.)

Le simple déroulement de la boucle n'aidera pas ; ce goulot d'étranglement de boucle sur la latence d'une chaîne de dépendance portée par la boucle, pas sur la surcharge / le débit de la boucle. Cela signifie qu'il ferait bien avec l'hyperthreading (ou tout autre type de SMT), car le processeur a beaucoup de temps pour entrelacer les instructions de deux threads. Cela signifierait paralléliser la boucle main, mais c'est très bien car chaque thread peut simplement vérifier une plage de nvaleurs et produire une paire d'entiers en conséquence.

L'entrelacement à la main dans un seul thread peut également être viable . Peut-être calculer la séquence pour une paire de nombres en parallèle, car 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 consiste à décider d'attendre jusqu'à ce que toutes les nvaleurs soient atteintes 1avant d'obtenir une autre paire de nvaleurs de départ , ou de sortir et d'obtenir un nouveau point de départ pour une seule qui a atteint la condition de fin, sans toucher aux registres de l'autre séquence. Il est probablement préférable de garder chaque chaîne travaillant sur des données utiles, sinon vous devrez incrémenter conditionnellement son compteur.

Vous pourriez peut-être même le faire avec des éléments de comparaison compressés SSE pour incrémenter conditionnellement le compteur des éléments vectoriels qui nn'avaient pas 1encore atteint . Et puis, pour masquer la latence encore plus longue d'une implémentation d'incrément conditionnelle SIMD, vous devez garder plus de vecteurs de nvaleurs en l'air. Peut-être ne vaut-il qu'avec le vecteur 256b (4x uint64_t).

Je pense que la meilleure stratégie pour faire la détection d'un 1"collant" est de masquer le vecteur de tout-ce que vous ajoutez pour incrémenter le compteur. Donc, après avoir vu un 1dans un élément, le vecteur d'incrémentation 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

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    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 implémenter cela avec des éléments intrinsèques au lieu d'un asm manuscrit.

Amélioration algorithmique / implémentation:

Outre l'implémentation de la même logique avec un asm plus efficace, recherchez des moyens de simplifier la logique ou d'éviter les travaux redondants. par exemple mémoriser pour détecter les terminaisons communes aux séquences. Ou encore mieux, regardez 8 bits de fin à la fois (réponse de gnasher)

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

La boucle pourrait donc 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 décalages de nombre variable sont lents sur les processeurs de la famille Intel SnB sans BMI2. 3 uops, latence 2c. (Ils ont une dépendance d'entrée sur les FLAGS car count = 0 signifie que les drapeaux ne sont pas modifiés. Ils gèrent cela comme une dépendance de données et prennent plusieurs uops car un uop ne peut avoir que 2 entrées (pré-HSW / BDW de toute façon)). C'est le genre auquel les gens se plaignant du design fou-CISC de x86 font référence. Cela rend les processeurs x86 plus lents qu'ils ne le seraient si l'ISA était conçu à partir de zéro aujourd'hui, même d'une manière presque similaire. (c'est-à-dire que cela fait partie de la "taxe x86" qui coûte vitesse / puissance.) SHRX / SHLX / SARX (BMI2) sont une grosse victoire (1 uop / 1c de latence).

Il place également tzcnt (3c sur Haswell et versions ultérieures) sur le chemin critique, de sorte qu'il allonge considérablement la latence totale de la chaîne de dépendance portée par la boucle. Cela supprime toutefois le besoin d'un CMOV ou de la préparation d'un registre n>>1. La réponse de @ Veedrac surmonte tout cela en différant le tzcnt / shift pour plusieurs itérations, ce qui est très efficace (voir ci-dessous).

Nous pouvons utiliser en toute sécurité BSF ou TZCNT de manière interchangeable, car nil ne peut jamais être nul à ce stade. Le code machine de TZCNT se décode en BSF sur les processeurs qui ne prennent pas en charge BMI1. (Les préfixes sans signification sont ignorés, donc REP BSF s'exécute en tant que BSF).

TZCNT fonctionne beaucoup mieux que BSF sur les processeurs AMD qui le prennent en charge, il peut donc être une bonne idée à utiliser REP BSF, même si vous ne vous souciez pas de définir ZF si l'entrée est zéro plutôt que la sortie. Certains compilateurs le font lorsque vous utilisez __builtin_ctzllmême avec -mno-bmi.

Ils fonctionnent de la même manière sur les processeurs Intel, alors enregistrez simplement l'octet si c'est tout ce qui compte. TZCNT sur Intel (pré-Skylake) a toujours une fausse dépendance sur l'opérande de sortie soi-disant en écriture, tout comme BSF, pour prendre en charge le comportement non documenté selon lequel BSF avec entrée = 0 laisse sa destination non modifiée. Vous devez donc contourner cela à moins d'optimiser 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 du code largement utilisé qui dépend de quelque chose qu'il ne devrait pas, ou qui est rétroactivement interdit. Par exemple, Windows 9x ne suppose aucune prélecture spéculative des entrées TLB , ce qui était sûr lors de l'écriture du code, avant qu'Intel ne mette à jour les règles de gestion TLB .)

Quoi qu'il en soit, LZCNT / TZCNT sur Haswell ont le même faux dépôt que POPCNT: voir ce Q&R . C'est pourquoi dans la sortie asm de gcc pour le code de @ Veedrac, vous le voyez briser la chaîne dep avec la mise à zéro xor sur le registre qu'il est sur le point d'utiliser comme destination de TZCNT quand il n'utilise pas dst = src. Étant donné que 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 un bug / limitation de performances. Vraisemblablement, cela vaut certains transistors / puissance pour qu'ils se comportent comme les autres uops qui vont à la même unité d'exécution. Le seul avantage positif est l'interaction avec une autre limitation d'uarch: ils peuvent micro-fusionner un opérande de mémoire avec un mode d'adressage indexé sur Haswell, mais sur Skylake où Intel a supprimé le faux dépôt pour LZCNT / TZCNT, ils "décollent" les modes d'adressage indexés tandis que POPCNT peut toujours micro-fusionner n'importe quel mode addr.

Améliorations des idées / du code à partir d'autres réponses:

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

J'ai mis du C rangé / amélioré (qui guide le compilateur pour produire un meilleur asm), et testé + travaillant plus rapidement asm (dans les commentaires ci-dessous le C) sur Godbolt: voir le lien dans la réponse de @ hidefromkgb . (Cette réponse a atteint la limite de 30k caractères des grandes URL Godbolt, mais les liens courts peuvent pourrir et étaient trop longs pour goo.gl de toute façon.)

Amélioration de l'impression de sortie pour convertir en chaîne et en créer une write()au lieu d'écrire un caractère à la fois. Cela minimise l'impact sur la synchronisation de l'ensemble du programme avec perf stat ./collatz(pour enregistrer les compteurs de performance), et j'ai désobscurci une partie de l'asm non critique.

@ Le code de Veedrac

J'ai obtenu une accélération mineure en déplaçant à droite autant que nous le savons , et en vérifiant pour continuer la boucle. De 7,5 s pour limite = 1e8 à 7,275 s, 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 report. Utiliser un compteur tmp ket l'ajouter ensuite pour countchanger plus tard ce que fait clang, mais cela blesse légèrement gcc.

Voir la discussion dans les commentaires: Le code de Veedrac est excellent sur les CPU avec BMI1 (c'est-à-dire pas Celeron / Pentium)

Prétendre que le compilateur C ++ peut produire un code plus optimal qu'un programmeur de langage d'assemblage compétent est une très mauvaise erreur. Et surtout dans ce cas. L'homme peut toujours rendre le code meilleur que le compilateur, et cette situation particulière est une bonne illustration de cette affirmation.

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

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

Par exemple, la fonction de séquence peut être optimisée en 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

Le code entier 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 (lorsqu'il est compilé avec -O0: 430 ms contre 1900 ms), et plus de deux fois plus rapide (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.

Pour plus de performances: Un simple changement consiste à observer qu'après n = 3n + 1, n sera pair, vous pouvez donc diviser par 2 immédiatement. Et n ne sera pas égal à 1, vous n'avez donc pas besoin de le tester. Vous pouvez donc enregistrer quelques instructions if et écrire:

while (n % 2 == 0) n /= 2;
if (n > 1) for (;;) {
    n = (3*n + 1) / 2;
    if (n % 2 == 0) {
        do n /= 2; while (n % 2 == 0);
        if (n == 1) break;
    }
}

Voici une grande victoire: si vous regardez les 8 bits de n les plus bas, toutes les étapes jusqu'à ce que vous divisez par 2 huit fois soient complètement déterminées par ces huit bits. Par exemple, si les huit derniers bits sont 0x01, c'est en binaire votre numéro est ???? 0000 0001, les étapes suivantes sont les suivantes:

3n+1 -> ???? 0000 0100
/ 2  -> ???? ?000 0010
/ 2  -> ???? ??00 0001
3n+1 -> ???? ??00 0100
/ 2  -> ???? ???0 0010
/ 2  -> ???? ???? 0001
3n+1 -> ???? ???? 0100
/ 2  -> ???? ???? ?010
/ 2  -> ???? ???? ??01
3n+1 -> ???? ???? ??00
/ 2  -> ???? ???? ???0
/ 2  -> ???? ???? ????

Ainsi, toutes ces étapes peuvent être prédites, et 256k + 1 est remplacé par 81k + 1. Quelque chose de similaire se produira pour toutes les combinaisons. Vous pouvez donc faire une boucle avec une grande instruction switch:

k = n / 256;
m = n % 256;

switch (m) {
    case 0: n = 1 * k + 0; break;
    case 1: n = 81 * k + 1; break; 
    case 2: n = 81 * k + 1; break; 
    ...
    case 155: n = 729 * k + 425; break;
    ...
}

Exécutez la boucle jusqu'à n ≤ 128, car à ce stade, n pourrait devenir 1 avec moins de huit divisions par 2, et faire huit étapes ou plus à la fois vous ferait manquer le point où vous atteignez 1 pour la première fois. Continuez ensuite la boucle "normale" - ou préparez un tableau qui vous indique le nombre d'étapes supplémentaires nécessaires pour atteindre 1.

PS. Je soupçonne fortement que la suggestion de Peter Cordes le rendrait encore plus rapide. Il n'y aura pas de branches conditionnelles du tout, sauf une, et celle-ci sera prédite correctement, sauf lorsque la boucle se termine réellement. Donc, le code serait quelque chose comme

static const unsigned int multipliers [256] = { ... }
static const unsigned int adders [256] = { ... }

while (n > 128) {
    size_t lastBits = n % 256;
    n = (n >> 8) * multipliers [lastBits] + adders [lastBits];
}

En pratique, vous mesureriez si le traitement des 9, 10, 11, 12 derniers bits de n à la fois serait plus rapide. Pour chaque bit, le nombre d'entrées dans la table doublerait, et j'excepte un ralentissement lorsque les tables ne rentrent plus dans le cache L1.

PPS. Si vous avez besoin du nombre d'opérations: dans chaque itération, nous effectuons exactement huit divisions par deux, et un nombre variable d'opérations (3n + 1), donc une méthode évidente pour compter les opérations serait un autre tableau. Mais nous pouvons réellement calculer le nombre d'étapes (basé sur le nombre d'itérations de la boucle).

Nous pourrions redéfinir légèrement le problème: remplacer n par (3n + 1) / 2 si impair, et remplacer n par n / 2 si pair. Ensuite, chaque itération fera exactement 8 étapes, mais vous pourriez considérer que la triche :-) Supposons donc qu'il y avait r opérations n <- 3n + 1 et s opérations n <- n / 2. Le résultat sera tout à fait exactement n '= n * 3 ^ r / 2 ^ s, car n <- 3n + 1 signifie n <- 3n * (1 + 1 / 3n). En prenant le logarithme, nous trouvons r = (s + log2 (n '/ n)) / log2 (3).

Si nous faisons la boucle jusqu'à n ≤ 1 000 000 et avons une table précalculée combien d'itérations sont nécessaires à partir de n'importe quel point de départ n ≤ 1 000 000, alors le calcul de r comme ci-dessus, arrondi à l'entier le plus proche, donnera le bon résultat à moins que s ne soit vraiment grand.

Sur une note plutôt indépendante: plus de hacks de performances!

• [la première «conjecture» a finalement été démontée par @ShreevatsaR; supprimé]

• Lors de la traversée de la séquence, nous ne pouvons obtenir que 3 cas possibles dans le voisinage à 2 de l'élément courant N(montré en premier):

  1. [même bizarre]
  2. [impair] [pair]
  3. [même] [même]

  Sauter au-delà de ces 2 éléments signifie calculer (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1et N >> 2, respectivement.

  Let`s montrent que dans les deux cas (1) et (2) il est possible d'utiliser la première formule, (N >> 1) + N + 1.

  Le cas (1) est évident. Le cas (2) implique (N & 1) == 1, donc si nous supposons (sans perte de généralité) que N est long de 2 bits et que ses bits sont badu plus grand au moins significatif, alors a = 1, et ce qui suit est vrai:

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

  où B = !b. Décaler à droite le premier résultat nous donne exactement ce que nous voulons.

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

  Comme prouvé, nous pouvons parcourir les éléments de la séquence 2 à la fois, en utilisant une seule opération ternaire. Encore 2 fois moins de temps.

L'algorithme résultant ressemble à ceci:

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;
}

Ici, nous comparons n > 2car le processus peut s'arrêter à 2 au lieu de 1 si la longueur totale de la séquence est impaire.

[ÉDITER:]

Traduisons cela en assemblage!

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;

Utilisez ces commandes pour compiler:

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

Voir le C et une version améliorée / corrigée d'un bug de l'asm par Peter Cordes sur Godbolt . (NDLR: Désolé d'avoir mis mes trucs dans votre réponse, mais ma réponse a atteint la limite de 30k caractères des liens Godbolt + texte!)

Les programmes C ++ sont traduits en programmes d'assemblage lors de la génération de code machine à partir du code source. Il serait pratiquement faux de dire que l'assemblage est plus lent que C ++. De plus, le code binaire généré diffère d'un compilateur à l'autre. Ainsi, un compilateur C ++ intelligent peut produire du code binaire plus optimal et efficace qu'un code d'assembleur stupide.

Cependant, je crois que votre méthodologie de profilage présente certains défauts. Voici les directives générales pour le profilage:

1. Assurez-vous que votre système est dans son état normal / inactif. Arrêtez tous les processus (applications) en cours que vous avez démarrés ou qui utilisent le processeur de manière intensive (ou interrogez le réseau).
2. Votre taille de données doit être plus grande.
3. Votre test doit durer plus de 5 à 10 secondes.
4. Ne vous fiez pas à un seul échantillon. Effectuez votre test N fois. Recueillez les résultats et calculez la moyenne ou la médiane du résultat.

Pour le problème Collatz, vous pouvez obtenir une amélioration significative des performances en mettant en cache les «queues». Il s'agit d'un compromis temps / mémoire. Voir: mémorisation ( https://en.wikipedia.org/wiki/Memoization ). Vous pouvez également rechercher des solutions de programmation dynamique pour d'autres compromis temps / mémoire.

Exemple d'implémentation de python:

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))

Des commentaires:

Mais, ce code ne s'arrête jamais (à cause d'un débordement d'entier)!?! Yves Daoust

Pour de nombreux numéros, il ne débordera pas .

Si elle va déborder - un de ces graines initiales malchanceux, le nombre survolée convergera très probablement vers 1 sans autre débordement.

Cela pose toujours une question intéressante, y a-t-il un nombre de graines cyclique de débordement?

Toute série convergente finale simple commence par une puissance de deux valeurs (assez évident?).

2 ^ 64 débordera à zéro, ce qui est une boucle infinie indéfinie selon l'algorithme (se termine uniquement par 1), mais la solution la plus optimale en réponse se terminera en raison de la shr raxproduction de ZF = 1.

Pouvons-nous produire 2 ^ 64? Si le nombre de départ est 0x5555555555555555, c'est un nombre impair, le nombre suivant est alors 3n + 1, qui est 0xFFFFFFFFFFFFFFFF + 1= 0. Théoriquement dans un état d'algorithme indéfini, mais la réponse optimisée de johnfound récupérera en sortant sur ZF = 1. Le cmp rax,1de Peter Cordes se terminera en boucle infinie (QED variante 1, "cheapo" par un 0nombre indéfini ).

Que diriez-vous d'un nombre plus complexe, qui créera un cycle sans 0? Franchement, je ne suis pas sûr, ma théorie mathématique est trop floue pour avoir une idée sérieuse, comment la traiter sérieusement. Mais intuitivement, je dirais que la série convergera vers 1 pour chaque nombre: 0 <nombre, car la formule 3n + 1 transformera lentement chaque facteur premier non-2 du nombre d'origine (ou intermédiaire) en une puissance de 2, tôt ou tard . Nous n'avons donc pas à nous soucier de la boucle infinie pour les séries originales, seul le débordement peut nous gêner.

J'ai donc mis quelques chiffres dans la feuille et jeté un coup d'œil aux nombres tronqués 8 bits.

Il y a trois valeurs débordantes à 0: 227, 170et 85( 85aller directement 0, deux autres progresser vers 85).

Mais il n'y a pas de valeur créatrice de débordement cyclique.

Curieusement, j'ai fait une vérification, qui est le premier numéro à souffrir de troncature 8 bits, et 27est déjà affecté! Il atteint la valeur 9232dans une série non tronquée appropriée (la première valeur tronquée est 322à la 12ème étape), et la valeur maximale atteinte pour l'un des 2 à 255 numéros d'entrée de manière non tronquée est 13120(pour 255lui - même), nombre maximal d'étapes vers lequel converger 1est d'environ 128(+ -2, je ne sais pas si "1" doit compter, etc ...).

Chose intéressante (pour moi), le nombre 9232est maximum pour de nombreux autres numéros de source, qu'est-ce qui est si spécial à ce sujet? : -O 9232= 0x2410... hmmm .. aucune idée.

Malheureusement, je ne peux pas saisir complètement cette série, pourquoi converge-t-elle et quelles sont les implications de les tronquer en k bits, mais avec une cmp number,1condition de fin, il est certainement possible de mettre l'algorithme en boucle infinie avec une valeur d'entrée particulière se terminant comme 0après troncature.

Mais la valeur 27débordante pour le cas 8 bits est une sorte d'alerte, cela ressemble à si vous comptez le nombre d'étapes pour atteindre la valeur 1, vous obtiendrez un résultat incorrect pour la majorité des nombres de l'ensemble total de k bits. Pour les entiers 8 bits, les 146 nombres sur 256 ont affecté la série par troncature (certains d'entre eux peuvent toujours atteindre le nombre correct d'étapes par accident peut-être, je suis trop paresseux pour vérifier).

Vous n'avez pas posté le code généré par le compilateur, donc il y a quelques hypothèses ici, mais même sans l'avoir vu, on peut dire que ceci:

test rax, 1
jpe even

... a 50% de chances de mal interpréter la succursale, et cela coûtera cher.

Le compilateur effectue presque certainement les deux calculs (ce qui coûte énormément plus cher puisque le div / mod est une latence assez longue, donc le multiply-add est "gratuit") et fait un suivi avec un CMOV. Ce qui, bien sûr, a zéro pour cent de chances d'être mal prédit.

Même sans regarder l'assemblage, la raison la plus évidente est qu'elle /= 2est probablement optimisée car de >>=1nombreux processeurs ont une opération de changement de vitesse très rapide. Mais même si un processeur n'a pas d'opération de décalage, la division entière est plus rapide que la division en virgule flottante.

Modifier: votre kilométrage peut varier sur la déclaration "division entière est plus rapide que la division en virgule flottante" ci-dessus. Les commentaires ci-dessous révèlent que les processeurs modernes ont priorisé l'optimisation de la division fp sur la division entière. Donc , si quelqu'un cherchait la raison la plus probable pour la question qui speedup de cette discussion au sujet demande, alors compilateur optimisé /=2comme >>=1serait le meilleur endroit pour regarder 1er.

Sur une note indépendante , si elle nest impaire, l'expression n*3+1sera toujours paire. Il n'est donc pas nécessaire de vérifier. Vous pouvez changer cette branche en

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

Donc, toute la déclaration serait alors

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

En tant que réponse générique, non spécifiquement dirigée vers cette tâche: dans de nombreux cas, vous pouvez accélérer considérablement n'importe quel programme en apportant des améliorations à un niveau élevé. Comme calculer les données une fois au lieu de plusieurs fois, éviter complètement le travail inutile, utiliser les caches de la meilleure façon, etc. Ces choses sont beaucoup plus faciles à faire dans une langue de haut niveau.

En écrivant du code assembleur, il est possible d'améliorer ce que fait un compilateur d'optimisation, mais c'est un travail difficile. Et une fois cela fait, votre code est beaucoup plus difficile à modifier, il est donc beaucoup plus difficile d'ajouter des améliorations algorithmiques. Parfois, le processeur possède des fonctionnalités que vous ne pouvez pas utiliser à partir d'un langage de haut niveau, l'assemblage en ligne est souvent utile dans ces cas et vous permet toujours d'utiliser un langage de haut niveau.

Dans les problèmes d'Euler, la plupart du temps, vous réussissez en construisant quelque chose, en trouvant pourquoi il est lent, en construisant quelque chose de mieux, en trouvant pourquoi il est lent, et ainsi de suite. C'est très, très difficile d'utiliser l'assembleur. Un meilleur algorithme à la moitié de la vitesse possible battra généralement un pire algorithme à pleine vitesse, et obtenir la pleine vitesse dans l'assembleur n'est pas anodin.

La réponse simple:

• faire un MOV RBX, 3 et MUL RBX coûte cher; AJOUTER simplement RBX, RBX deux fois

• ADD 1 est probablement plus rapide qu'INC ici

• MOV 2 et DIV sont très chers; juste déplacer à droite

• Le code 64 bits est généralement beaucoup plus lent que le code 32 bits et les problèmes d'alignement sont plus compliqués; avec de petits programmes comme celui-ci, vous devez les emballer afin que vous effectuiez un calcul parallèle pour avoir une chance d'être plus rapide que le code 32 bits

Si vous générez la liste d'assembly pour votre programme C ++, vous pouvez voir en quoi elle diffère de votre assembly.