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 batte votre code écrit à la main, même avec -O0 (compiler rapidement, pas d'optimisation supplémentaire, et stocker/recharger en mémoire après/avant chaque instruction C pour qu'un débogueur puisse modifier les variables).

Voir Agner le Brouillard de l'Optimisation de l'Assemblée guide pour apprendre à écrire efficace à l'asm. Il a aussi des tables d'instructions et une microarch guide pour des détails spécifiques pour des CPU spécifiques. Voir aussi le wiki x86 tag pour plus de liens perf.

Voir Aussi cette question plus générale sur le fait 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 le faites mal (comme cette question).

habituellement, vous êtes bien laisser le compilateur faire son truc, surtout si vous essayer de écrire C++ qui peut compiler efficacement . Voir aussi l'assemblage est-il plus rapide que les langages compilés? . Une des réponses liens à ces diapositives soignées montrant comment divers compilateurs C optimiser certaines fonctions vraiment simples avec des trucs cool.

---

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

sur Intel Haswell, div r64 is 36 uops, avec une latence de 32-96 cycles , et un débit d'un cycle par 21-74 cycles. (Plus les 2 uops pour mettre en place RBX et Zero RDX, mais l'exécution hors-ordre peut les exécuter en avance). Haute-uop-comte instructions comme les DIV sont microcoded, qui peut également causer avant la fin de l'étranglement. dans ce cas, la latence est le facteur le plus pertinent parce qu'elle fait partie d'une chaîne de dépendances en boucle.

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

à titre de comparaison, la division en 32 bits est plus rapide, mais tout de même horrible contre les changements. idiv r32 est 9 uops, 22-29C latence, et un pour 8-11c débit sur Haswell.

---

comme vous pouvez le voir en regardant gcc -O0 sortie asm ( Godbolt compiler explorer ), il utilise seulement les instructions de changement . clang -O0 ne compilent naïvement comme vous le pensiez, même en utilisant 64-bit IDIV deux fois. (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 un mode totalement naïf; il se transforme toujours par GIMPLE, ce qui signifie que certaines" optimisations "ne peuvent pas être désactivées . Ceci inclut la reconnaissance de division par constante et l'utilisation de déplacements (puissance de 2) ou un point fixe inverse multiplicatif (non puissance de 2) pour éviter les IDIV (voir div_by_13 godbolt lien).

gcc -Os (optimiser en fonction de la taille) does utiliser 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 rapide.

---

Aider le compilateur

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

tout d'Abord, il est intéressant de regarder optimisé sortie du compilateur. ( -O3 ). -O0 la vitesse n'a pas de sens.

regardez votre sortie asm (sur Godbolt, ou voir comment supprimer le "bruit" de la sortie D'assemblage GCC/clang? ). Quand le compilateur ne fait pas le code optimal en premier lieu: écrire votre source C / C++ d'une manière qui guide le compilateur à faire 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 cette connaissance indirectement. Les compilateurs sont aussi une bonne source d'idées: parfois clang fera quelque chose de cool, et vous pouvez tenir gcc dans la main pour 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 à tout ce qui est efficace sur le futur matériel (x86 ou non), en utilisant peut-être une nouvelle extension ISA ou en auto-vectorisant. Écrit à la main x86-64 asm d'il y a 15 ans ne serait généralement pas accordé de manière optimale pour Skylake. par exemple, la macro-fusion de comparaison et de branche n'existait pas à l'époque. Ce qui est optimal maintenant pour fabriqués à la main à l'asm pour une microarchitecture pourrait ne pas être optimal pour d'autres actuels et futurs Processeurs. commentaires sur la réponse de @johnfound discutez 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 feront la bonne chose. (Ou -march=native .) Ou -mtune=... pour juste syntoniser, sans utiliser d'instructions que d'autres CPU pourraient ne pas supporter.

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

écrit à la main asm 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 de temps de compilation. D'autres optimisations sont également touchés. Lire https://gcc.gnu.org/wiki/DontUseInlineAsm avant d ' utiliser asm. (Et éviter de MSVC style inline asm: entrées/sorties d'avoir à passer par la mémoire qui ajoute de la surcharge .)

dans ce cas : votre n a un type signé, et gcc utilise le SAR/SHR/AJOUTER séquence qui donne de l'arrondi correct. (IDIV et de l'arithmétique-shift "ronde" différemment pour les entrées, voir la section SAR insn set ref saisie manuelle ). (IDK si gcc a essayé et n'a pas réussi à prouver que n ne peut pas être négatif, ou quoi. Signé-débordement est un comportement indéterminé, donc ça devrait pouvoir le faire.)

Vous devriez avoir utilisé uint64_t n , de sorte qu'il peut juste SHR. Et donc portable pour les systèmes où long est seulement 32 bits (par exemple Windows x86-64).

---

BTW, gcc optimisé sortie asm semble assez bonne (à l'aide de unsigned long n ) : la boucle interne il inlines dans main() est-ce:

 # 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 branchages, et le chemin critique de la chaîne de dépendance portée par la boucle est:

• 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 hors-ordre s'occupe de tout le reste en parallèle avec ceci (en théorie: je n'ai pas testé avec des compteurs de perf pour voir si elle tourne vraiment à 5c/iter).

le signal D'entrée de cmov (produit par TEST) est plus rapide à produire que le signal D'entrée RAX (à partir de LEA - > MOV), donc il n'est pas sur le chemin critique.

de même, le MOV->SHR qui produit L'entrée RDI de CMOV est hors de la trajectoire critique, parce qu'il est aussi plus rapide que le LEA. MOV sur IvyBridge et plus tard a la latence zéro (manipulé à l'Heure de registre-renommer). (Il faut toujours un uop, et une fente dans le pipeline, donc ce n'est pas gratuit, juste une latence zéro). Le MOV supplémentaire dans la chaîne LEA dep fait partie du goulot d'étranglement sur les autres CPU.

le cmp/jne ne fait pas non plus partie du chemin critique: il n'est pas porté en boucle, parce que 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 bon travail ici. Il pourrait sauver un byte de code en utilisant inc edx au lieu de add edx, 1 , parce que personne ne se soucie de P4 et de ses fausses dépendances pour instructions de modification partielle du drapeau.

il pourrait également enregistrer toutes les instructions MOV, et le TEST: SHR ensembles CF= le bit décalé, de sorte que 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 un autre truc astucieux: supprimer le CMP en branchant sur le résultat du drapeau de SHR ainsi que l'utiliser pour CMOV: zéro seulement si n était 1 (ou 0) pour commencer. (Fait amusant: SHR avec le compte != 1 sur Nehalem ou plus tôt provoque un décrochage si vous lisez les résultats du drapeau . C'est la façon dont ils l'ont fait unique uop. Le codage spécial shift-by-1 est très bien.)

Eviter le MOV n'aide pas du tout avec la latence sur Haswell ( le MOV De x86 peut-il vraiment être "libre"? Pourquoi je ne peux pas reproduire ce tout? ). Il ne AIDE de manière significative sur les CPU comme Intel pré-IvB, et AMD Bulldozer-famille, où MOV n'est pas zéro-latence. Les instructions de MOV gaspillées par le compilateur affectent le chemin critique. Le complexe de BD-LEA et CMOV sont tous deux une latence plus faible (2C et 1C respectivement), donc c'est une plus grande fraction de la latence. En outre, les goulots d'étranglement de débit deviennent un problème, parce qu'il n'a que deux entiers alu pipes. Voir @johnfound la réponse de , où il a calendrier résultats à partir d'un CPU AMD.

même sur Haswell, cette version peut aider un peu en évitant quelques occasionnelles retards où un uop non critique vole un port d'exécution à un autre 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 aider lors de la réalisation de plusieurs valeurs n en parallèle dans une boucle entrelacée (voir ci-dessous).

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

Donc lea rcx, [rax + rax*2] / inc rcx est seulement 2c temps de latence, plus rapide que le lea rcx, [rax + rax*2 + 1] , sur Intel banque nationale, de la famille des Processeurs comme Haswell. Rentabilité sur BD, et pire sur Core2. Il ne coûte un uop supplémentaire, qui normalement n'est pas la peine d'économiser la latence 1c, mais la latence est le principal goulot d'étranglement ici et Haswell a un pipeline assez large pour gérer le débit uop supplémentaire.

ni gcc, ni icc, ni clang (sur godbolt) n'ont utilisé la sortie CF de SHR, toujours en utilisant un et ou TEST . Stupides compilateurs. : P Ce sont de grands morceaux de machinerie complexe, mais un humain intelligent peut souvent battre les problèmes à petite échelle. (Donné des milliers à des millions de fois plus de temps pour y réfléchir, bien sûr! Les compilateurs n'utilisent pas d'algorithmes exhaustifs pour rechercher toutes les façons possibles de faire les choses, parce que cela prendrait trop de temps lors de l'optimisation de beaucoup de code inlined, ce qui est ce qu'ils font le mieux. 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 juste quelques heuristiques.)

---

le déroulage simple de boucle n'aidera pas ; ce goulot d'étranglement de boucle sur la latence d'une chaîne de dépendance portée par boucle, et non sur le débit de boucle. Cela signifie qu'il ferait bien avec l'hyperthreading (ou tout autre type de SMT), puisque le CPU a beaucoup de temps pour intercaler des instructions à partir de deux threads. Cela signifierait paralléliser la boucle dans main , mais c'est bien parce que chaque thread peut juste vérifier une gamme de n valeurs et produire une paire d'entiers en conséquence.

L'entrelacement manuel à l'intérieur d'un seul fil pourrait être viable, aussi . Peut-être calculer la séquence pour une paire de nombres en parallèle, puisque chacun prend seulement un couple registres, et ils peuvent tous mettre à jour le même max / maxi . Cela crée plus de parallélisme d'instruction .

l'astuce est de décider que ce soit pour attendre que toutes les valeurs n aient atteint 1 avant d'obtenir une autre paire de valeurs de départ n , ou si pour se détacher et obtenir un nouveau point de départ pour un seul qui a atteint la condition de fin, sans toucher les registres pour l'autre séquence. Probablement, il est préférable de garder chaque chaîne de travail sur les données utiles, sinon vous devriez conditionnellement incrémenter son compteur.

---

vous pourriez peut-être même faire cela avec SSE emballé-comparer des choses à augmenter 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 de l'incrément conditionnel SIMD, vous aurez besoin de garder plus de vecteurs de valeurs n dans les airs. Ne vaut peut-être 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 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 cela avec intrinsics, au lieu de main-écrit asm.

---

Algorithmique de la mise en œuvre d'amélioration:

D'ailleurs juste mettre en œuvre la même logique avec un asm plus efficace, chercher des moyens de simplifier la logique, ou éviter le travail redondant. par exemple memoize pour détecter les terminaisons communes aux séquences. Ou encore mieux, regarder 8 de fuite bits à la fois (gnasher de réponse)

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

ainsi 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 variables sont lents sur les CPU de la famille SNB Intel sans BMI2. 3 uop, 2c temps de latence. (Ils ont une dépendance d'entrée sur les FLAGS parce que count=0 signifie que les flags ne sont pas modifiés. Ils traitent cela comme une dépendance de données, et prennent uops multiples car un uop ne peut avoir que 2 entrées (pré-HSW/BDW de toute façon). C'est de ce genre que les gens se plaignent du design fou de x86-CISC font référence. Cela rend les CPU x86 plus lents qu'ils ne le seraient si L'ISA avait été conçu à partir de rien aujourd'hui, même de manière similaire. (c'est-à-dire que cela fait partie de la "taxe x86" qui coûte vitesse / puissance.) SHRX / SHLX / SARX (BMI2) are a big win (1 uop / 1C latency).

il met également tzcnt (3c sur Haswell et plus tard) sur le critique le chemin, donc il allonge significativement la latence totale de la chaîne de dépendance en boucle. Il ne supprime tout besoin D'une CMOV, ou pour la préparation d'un registre tenant 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 en toute sécurité BSF ou TZCNT de façon interchangeable, car n ne peut jamais être zéro à ce point. Le code machine de TZCNT décode en tant que BSF sur les CPU qui ne supportent pas BMI1. (Les préfixes qui n'ont pas de sens sont ignorés, donc REP BSF fonctionne comme BSF).

tzcnt fonctionne beaucoup mieux que BSF sur les processeurs AMD qui le supportent, donc il peut être une bonne idée d'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 font cela quand vous utilisez __builtin_ctzll même avec -mno-bmi .

ils font la même chose sur les processeurs Intel, donc sauvez le byte si c'est tout ce qui compte. TZCNT sur Intel (pre-Skylake) a toujours une fausse dépendance sur l'opérande de sortie en écriture, tout comme BSF, pour supporter le comportement non documenté que BSF avec input = 0 laisse sa destination non modifiée. Donc, vous devez travailler autour de cela à moins d'optimiser seulement pour Skylake, donc il n'y a rien à gagner de la réputation supplémentaire. (Intel va souvent au-delà de ce que le x86 ISA manuel exige, pour éviter de casser le code largement utilisé qui dépend de quelque chose qu'il ne devrait pas, ou qui est rejeté rétroactivement. par exemple, Windows 9x ne suppose aucun préfet spéculatif des entrées TLB , qui était sûr lorsque le code a été écrit, avant Intel a mis à jour les règles de gestion TLB .)

quoi qu'il en soit, Lzcnt/TZCNT sur Haswell ont le même faux dep que POPCNT: voir this Q&A . C'est pourquoi dans la sortie ASM de gcc pour le code de @Veedrac, vous voyez casser la chaîne dep avec xor-zeroing sur le registre il est sur le point d'utiliser comme destination de TZCNT, quand il n'utilise pas dst=src. Puisque TZCNT/LZCNT / POPCNT ne quittent jamais leur destination non définie ou non modifiée, cette fausse dépendance sur la sortie sur les CPUs Intel est purement un bug / limitation de performance. Il est probable que cela vaut la peine d'avoir certains transistors / puissance pour les faire se comporter comme d'autres uops qui vont à la même exécution unité. Le seul logiciel-visible à l'envers est dans l'interaction avec une autre limitation microarchitecturale: ils peuvent micro-fusionner un operand mémoire avec un mode d'adressage indexé sur Haswell, mais sur Skylake où Intel a supprimé la fausse dépendance pour LZCNT/TZCNT ils "non-stratifié" modes d'adressage indexé tandis que POPCNT peut micro-fusionner n'importe quel mode addr.

---

amélioration des idées / code à partir d'autres réponses:

la réponse de @hidefromkgb a une belle observation que vous êtes garanti de pouvoir faire un quart de travail à droite après un 3n+1. Vous pouvez calculer cela encore plus efficacement que de simplement laisser les contrôles entre les étapes. L'implémentation asm dans cette réponse est cassée, cependant (cela dépend de, qui n'est pas défini après SHRD avec un nombre > 1), et lente: ROR rdi,2 est plus rapide que SHRD rdi,rdi,2 , et en utilisant deux instructions CMOV sur la critique le chemin est plus lent qu'un TEST supplémentaire qui peut être exécuté en parallèle.

j'ai mis tidied / improved C (qui guide le compilateur pour produire de meilleurs asm), et testé+travail plus rapide asm (dans les commentaires ci-dessous le C) sur Godbolt: voir le lien dans @hidefromkgb'S réponse . (Cette réponse a atteint la limite de 30k char des grandes URLs Godbolt, mais shortlinks can rot et étaient trop long pour goo.gl quand même.)

aussi amélioré l'impression de sortie pour passer à une chaîne et faire un write() au lieu d'écrire un char à 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ésamorcé certains asm non critiques.

---

@code de Veedrac

j'ai eu une très petite accélération de la droite-déplacement autant que nous savoir besoin de faire, et de vérifier, 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 on Godbolt . Ne pas utiliser cette version avec clang; il fait quelque chose de stupide avec la défér-boucle. L'utilisation d'un compteur tmp k et son ajout à count change plus tard ce que fait clang, mais que légèrement blesse gcc.

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