Code C++ pour tester la conjecture Collatz plus rapidement que l'assemblage manuel-pourquoi?

j'ai écrit ces deux solutions pour projet Euler Q14 , en assemblage et en C++. Il s'agit de la même approche de force brute identique pour tester la conjecture 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 des compilateurs 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 de façon programmatique pas mathématiquement).

le code C++ a un module chaque terme et une division chaque terme pair, 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 vous demande de principalement curiosité.

délais d'exécution

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

740
demandé sur einpoklum 2016-11-01 09:12:06
la source

11 ответов

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

1761
répondu Peter Cordes 2018-08-08 14:12:23
la source

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'humain peut toujours améliorer le code que le compilateur peut, et cette situation particulière est une bonne illustration de cette revendication.

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

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

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

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

pour compiler ce code, FreshLib est nécessaire.

dans mes tests, (1 GHz AMD A4-1200 processeur), le code ci-dessus est environ quatre fois plus rapide que le code C++ du question (lorsqu'elle est compilée avec -O0 : 430 ms vs. 1900 ms), et plus de deux fois plus rapide (430 ms vs. 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.

92
répondu johnfound 2016-11-01 21:52:54
la source

pour plus de performance: un changement simple est d'observer qu'après n = 3n+1, n sera Pair, donc vous pouvez diviser par 2 immédiatement. Et n NE SERA PAS 1, donc vous n'avez pas besoin de le tester. Vous pouvez donc en sauver quelques unes 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 un grand victoire: si vous regardez les 8 bits les plus bas de n, Toutes les étapes jusqu'à ce que vous divisé par 2 huit fois sont entièrement déterminés par ces huit bits. Par exemple, si les huit derniers bits sont 0x01, qui est en binaire votre numéro ???? 0000 0001 puis les prochaines étapes sont:

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

pour que toutes ces étapes puissent être prédites, et 256k + 1 est remplacé par 81k + 1. Quelque chose de semblable se produira pour toutes les combinaisons. Ainsi, vous pouvez faire une boucle avec une grande déclaration de commutateur:

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écuter la boucle jusqu'à n ≤ 128, parce qu'à ce point n pourrait devenir 1 avec moins de huit divisions par 2, et faire huit pas ou plus à la fois serait faire vous manquez le point où vous atteignez 1 pour la première fois. Ensuite, continuez la boucle "normale" - ou faites préparer une table qui vous indique combien d'étapes supplémentaires sont nécessaires pour atteindre 1.

PS. Je soupçonne fortement la suggestion de Peter Cordes de le rendre encore plus rapide. Il n'y aura aucune branche conditionnelle 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];
}

In pratiquez, vous mesurerez si le traitement des derniers 9, 10, 11, 12 bits de n à la fois serait plus rapide. Pour chaque bit, le nombre d'entrées dans la table doublerait, et je m'aperçois 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 faisons 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 calculez en fait 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 tricherie : -) donc supposons qu'il y a eu des opérations r n <- 3n+1 et des opérations s n <- n/2. Le résultat sera 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 un tableau précalculé combien d'itérations sont nécessaires à partir de n'importe quel point de départ n ≤ 1.000.000, puis le calcul de r comme ci-dessus, arrondi à l'entier le plus proche, donnera le bon résultat à moins que s soit vraiment grand.

20
répondu gnasher729 2017-01-18 14:30:52
la source

sur une note un peu différente: plus de piratages de performance!

  • [la première "conjecture" a finalement été démystifiée par @ShreevatsaR; supprimé]

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

    1. [Pair] [Impair]
    2. [impair] [même]
    3. [pair] [pair]

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

    prouvons que pour les deux cas (1) et (2) Il est possible d'utiliser la première formule, (N >> 1) + N + 1 .

    L'affaire

    (1) est évidente. Le cas (2) implique (N & 1) == 1 , donc si nous supposons (sans perte de généralité) que N est de 2 bits de long et ses bits sont ba de la plus à la moins importante, puis a = 1 , et le suivant dit:

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

    B = !b . Droite-déplacer le premier résultat nous donne exactement ce que nous voulons.

    Q. E. D.: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1 .

    comme prouvé, nous pouvons parcourir la séquence 2 éléments à la fois, en utilisant une seule opération ternaire. Une autre réduction de 2 fois le temps.

le résultat l'algorithme 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;
}

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

[EDIT:]

traduisons ceci en assemblée!

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

Peter Cordes sur Godbolt . (note de l'éditeur: désolé de mettre mes affaires dans votre réponse, mais ma réponse a atteint la limite de 30k char des liens Godbolt + texte!)

17
répondu hidefromkgb 2016-11-04 09:42:08
la source

les programmes C++ sont traduits en programmes d'assemblage pendant la génération du 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 du compilateur au compilateur. Ainsi, un compilateur C++ intelligent peut produire un code binaire plus optimal et efficace qu'un code d'assembleur muet.

cependant je crois que votre méthode de profilage a certains défauts. Les éléments suivants sont lignes directrices 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) que vous avez lancés ou qui utilisent le CPU de manière intensive (ou poll sur 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 s'appuie pas sur un seul échantillon. Effectuez votre test N fois. Recueillir les résultats et calculer la moyenne et la médiane du résultat.
5
répondu Mangu Singh Rajpurohit 2016-11-01 16:45:19
la source

des commentaires:

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

pour de nombreux nombres il sera pas débordement.

si elle va débordement - pour une de ces graines initiales malchanceuses, le nombre débordé convergera très probablement vers 1 sans un autre débordement.

Still cela pose une question intéressante, y a-t-il un certain nombre de graines cycliques de débordement?

N'importe quelle série finale convergente simple commence avec une puissance de deux valeurs (assez évident?).

2^64 va déborder à zéro, qui est boucle infinie non définie selon l'algorithme (se termine seulement avec 1), mais la solution la plus optimale dans la réponse se terminera en raison de shr rax produisant 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 l'état non défini de l'algorithme, mais la réponse optimisée de johnfound récupérera en sortant sur ZF=1. Le cmp rax,1 de Peter Cordes se terminera en boucle infinie (variante QED 1," cheapo "à travers le numéro Non défini 0 ).

Que Diriez-vous d'un nombre plus complexe, qui créera un cycle sans 0 ? Franchement, je ne suis pas bien sûr, ma théorie mathématique est trop floue pour avoir une idée sérieuse, comment la gérer de manière sérieuse. Mais intuitivement, je dirais que la série va converger à 1 pour chaque nombre : 0 < Nombre, car la formule 3n+1 va lentement transformer chaque Non-2 premier facteur du nombre original (ou intermédiaire) en une certaine puissance de 2, tôt ou tard. Donc nous n'avons pas besoin de nous soucier de boucle infinie pour les séries originales, seul le débordement peut nous gêner.

donc j'ai juste mis quelques chiffres dans la feuille et j'ai regardé sur des nombres tronqués de 8 bits.

il y a trois valeurs qui débordent 0 : 227 , 170 et 85 ( 85 allant directement à 0 , les deux autres progressant vers 85 ).

mais il n'y a pas de valeur créant des graines de débordement cyclique.

assez curieusement j'ai fait un contrôle, qui est le premier nombre à souffrir de 8 bits troncature, et déjà 27 est affecté! Il atteint la valeur 9232 dans la série non tronquée appropriée (la première valeur tronquée est 322 dans la 12ème étape), et la valeur maximale atteinte pour l'un des 2-255 nombres d'entrée dans la manière non tronquée est 13120 (pour le 255 elle-même), le nombre maximum d'étapes pour converger à 1 est d'environ 128 (+-2, pas sûr si" 1 " doit compter, etc...).

assez intéressant (pour moi) le nombre 9232 est maximum pour beaucoup d'autres source les numéros, ce qui est si spécial à ce sujet? :- O 9232 = 0x2410 ... hmmm.. aucune idée.

malheureusement, Je ne peux pas obtenir une compréhension profonde de cette série, pourquoi il converge et quelles sont les implications de les tronquer à k bits, mais avec cmp number,1 condition finale il est certainement possible de mettre l'algorithme en boucle infinie avec une valeur d'Entrée particulière se terminant par 0 après la troncature.

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

4
répondu Ped7g 2016-11-01 20:18:35
la source

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

test rax, 1
jpe even

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

il est presque certain que le compilateur effectue les deux calculs (ce qui coûte d'autant plus cher que la latence div/mod est assez longue, de sorte que le multiply-add est" gratuit") et qu'il suit avec une CMOV. Qui, de bien sûr, a un zéro pourcentage de chance d'être mal interprété.

4
répondu Damon 2016-11-01 22:50:03
la source

même sans regarder l'assemblage, la raison la plus évidente est que /= 2 est probablement optimisé comme >>=1 et de nombreux processeurs ont une opération de changement 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 flottante.

Edit: votre kilométrage peut varier sur la "division entière est plus rapide qu'en virgule flottante de la division de la" déclaration ci-dessus. Les commentaires ci-dessous révèlent que les processeurs modernes ont donné la priorité à l'optimisation de fp division division entière. Donc, si quelqu'un cherchait la raison la plus probable de l'accélération que la question de ce fil pose, alors compilateur optimisant /=2 comme >>=1 serait le meilleur premier endroit pour regarder.


sur une note sans rapport , si n est impair, l'expression n*3+1 sera toujours égale. Donc, il n'est pas nécessaire pour 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;
}
4
répondu Dmitry Rubanovich 2016-11-29 20:35:03
la source

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

Writing assembler code, il est possible pour améliorer ce qu'une optimisation compilateur Oui, mais c'est un travail difficile. Et une fois que c'est fait, votre code est beaucoup plus difficile à modifier, il est beaucoup plus difficile d'ajouter des améliorations algorithmiques. Parfois le processeur a 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 tout de même d'utiliser un langage de haut niveau.

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

3
répondu gnasher729 2016-11-04 20:15:18
la source

pour le problème Collatz, vous pouvez obtenir une augmentation significative de la performance en cachant les "queues". C'est un temps de la mémoire et du compromis. Voir: memoization ( 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 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))
3
répondu Emanuel Landeholm 2016-11-05 22:00:35
la source

la réponse simple:

  • faire un MOV RBX, 3 et MUL RBX est cher; il suffit d'AJOUTER RBX, RBX deux fois

  • AJOUTER 1 est probablement plus rapide que INC ici

  • MOV 2 et DIV est très cher; il suffit de décalage à droite

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

si vous générez le listing d'assemblage pour votre programme C++, vous pouvez voir en quoi il diffère de votre assemblage.

-2
répondu Tyler Durden 2016-11-07 20:36:19
la source

Autres questions sur c++ performance optimization assembly x86