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


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

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

Le C ++ a été compilé avec

g++ p14.cpp -o p14

Assemblée, p14.asm

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

global main
extern printf

section .text

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

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

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

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

c1:
    inc r10
    cmp rax, 1
    jne l2

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

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C ++, p14.cpp

#include <iostream>

using namespace std;

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

        ++count;
    }

    return count;
}

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

    cout << maxi << endl;
}

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

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

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

Temps d'exécution

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


737
2017-11-01 06:12


origine


Réponses:


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 manuscrit, même avec -O0 (compilation rapide, 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).

Voir Optimisation du guide d'assemblage d'Agner Fog apprendre à écrire asm efficace. Il a également des tables d'instructions et un guide de microarch pour des détails spécifiques pour des processeurs spécifiques. Voir aussi  tag wiki pour plus de liens perf.

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

Habituellement, vous pouvez laisser le compilateur faire son travail, surtout si vous essayer d'écrire C ++ qui peut compiler efficacement. Regarde aussi est l'assemblage 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 très simples avec des astuces cool.


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

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

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

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


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

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

gcc -Os (optimiser pour la taille) Est-ce que utiliser IDIV pour la division sans pouvoir de 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: utilisation uint64_t n)

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

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

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

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

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

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

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


BTW, GCC optimisé la sortie d'asm semble assez bonne (en utilisant unsigned long n): la boucle interne, il insère dans main() est ce que ca:

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

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

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

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

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

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

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

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

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


Battre le compilateur

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

Il pourrait également enregistrer toutes les instructions MOV, et le test: SHR définit CF = le bit déplacé, 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 une autre astuce intelligente: supprimer le CMP en dérivant sur le résultat du drapeau de SHR et en l'utilisant pour CMOV: zéro seulement si n était 1 (ou 0) pour commencer. (Fait amusant: SHR avec count! = 1 sur Nehalem ou plus tôt provoque un décrochage si vous lisez les résultats du drapeau. C'est comme ça qu'ils l'ont fait en single-uop. L'encodage spécial shift-by-1 est correct, cependant.

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

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

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

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

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


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

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

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


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

Je pense que la meilleure stratégie pour faire la détection d'un 1 "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 ceci avec des intrinsèques, au lieu d'asm écrit à la main.


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

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

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

Donc, la boucle pourrait ressembler à ceci:

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

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

Il place également tzcnt (3c sur Haswell et plus tard) sur le chemin critique, ce qui allonge considérablement la latence totale de la chaîne de dépendances bouclée. Il supprime tout besoin d'un CMOV, ou pour préparer un registre n>>1, bien que. 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 interchangeable, parce que n ne peut jamais être nul à ce moment-là. Le code machine de TZCNT est décodé en tant que BSF sur les CPU qui ne supportent pas BMI1. (Les préfixes sans signification sont ignorés, donc REP BSF s'exécute comme BSF).

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

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

Quoi qu'il en soit, LZCNT / TZCNT sur Haswell ont le même faux dépôt que POPCNT: voir cette Q & A. C'est pourquoi dans la sortie asm de gcc pour le code de @ Veedrac, vous le voyez briser la chaîne de dépôt avec xor-zeroing sur le registre, il est sur le point d'utiliser comme destination TZCNT, quand il n'utilise pas dst = src. Puisque TZCNT / LZCNT / POPCNT ne laissent jamais leur destination indéfinie ou non modifiée, cette fausse dépendance à la sortie sur les processeurs Intel est purement un bug / une limitation de performance. Vraisemblablement, cela vaut la peine de disposer de transistors / puissances pour les faire se comporter comme d'autres uops qui vont à la même unité d'exécution. Le seul avantage visible du logiciel est dans l'interaction avec une autre limitation microarchitecturale: 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é la fausse dépendance pour LZCNT / TZCNT, ils "désassemblent" les modes d'adressage indexés tandis que POPCNT peut toujours faire une micro-fusion de n'importe quel mode addr.


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

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

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

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


Le code de @ Veedrac

J'ai eu une très petite accélération de droite autant que nous connaître doit faire, et en vérifiant de continuer la boucle. De 7.5s pour la limite = 1e8 jusqu'à 7.275s, sur Core2Duo (Merom), avec un facteur de déroulement de 16.

code + commentaires sur Godbolt. N'utilisez pas cette version avec clang; il fait quelque chose de stupide avec la boucle de déferlement. Utiliser un compteur tmp k puis en l'ajoutant à count plus tard, change ce que fait clang, mais que légèrement fait mal gcc.

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


1747
2017-11-01 07:04



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

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

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

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

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

L'ensemble du code ressemble à:

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

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

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

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

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

        dec     ecx
        jnz     .main_loop

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

        FinalizeAll
        stdcall TerminateAll, 0

Pour 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.


93
2017-11-01 08:29



Pour plus de performance: Un simple changement observe 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 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 un gros win: Si vous regardez les 8 bits les plus bas de n, toutes les étapes jusqu'à ce que vous divisiez 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 que votre nombre est ???? 0000 0001 alors 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  -> ???? ???? ????

Donc, 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 grosse 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 point n pourrait devenir 1 avec moins de huit divisions par 2, et faire huit pas ou plus à la fois vous ferait manquer le point où vous atteignez 1 pour la première fois. Ensuite, continuez la boucle "normale" - ou préparez une table qui vous indique combien d'étapes supplémentaires doivent atteindre 1.

PS. Je soupçonne fortement que la suggestion de Peter Cordes le rendrait encore plus rapide. Il n'y aura aucune branche conditionnelle à l'exception d'une seule, et celle-ci sera prédite correctement, sauf si 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 double, et j'excite 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 réellement calculer le nombre d'étapes (en fonction du 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. Alors chaque itération fera exactement 8 pas, mais vous pourriez considérer que tricher :-) Supposons donc qu'il y ait eu r opérations n <- 3n + 1 et s opérations n <- n / 2. Le résultat sera exactement n '= n * 3 ^ r / 2 ^ s, parce que n <- 3n + 1 signifie n <- 3n * (1 + 1 / 3n). En prenant le logarithme, nous trouvons r = (s + log2 (n '/ n)) / log2 (3).

Si on fait la boucle jusqu'à n ≤ 1,000,000 et qu'on a 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 calculer r comme ci-dessus, arrondi à l'entier le plus proche, donnera le bon résultat sauf si s est vraiment grand.


19
2017-11-02 10:04



Sur une note plutôt sans rapport: plus de hacks de performance!

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

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

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

    Passer devant ces 2 é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.

    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 ses bits sont ba du plus au moins significatif, alors a = 1, et ce qui suit:

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

    B = !b. Le décalage à droite du 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 traverser la séquence 2 éléments à la fois, en utilisant une seule opération ternaire. Une autre réduction de 2 fois le 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 > 2 parce que le processus peut s'arrêter à 2 au lieu de 1 si la longueur totale de la séquence est impaire.

[MODIFIER:]

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

Voir le C et une version améliorée / corrigée de l'asm par Peter Cordes sur Godbolt. (Note de l'éditeur: Désolé de mettre mes trucs dans votre réponse, mais ma réponse a atteint la limite de 30 Ko de liens Godbolt + texte!)


17
2017-11-01 19:35



Les programmes C ++ sont traduits en programmes d'assemblage lors de la génération du code machine à partir du code source. Il serait 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. Donc, un compilateur C ++ intelligent mai produire un code binaire plus optimal et efficace que le code d'un assembleur muet.

Cependant, je crois que votre méthodologie de profilage a certains défauts. Voici les 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 en cours (applications) que vous avez démarrés ou qui utilisent le processeur de manière intensive (ou interrogez le réseau).
  2. Votre datasize doit être plus grande.
  3. Votre test doit durer plus de 5-10 secondes.
  4. Ne comptez pas sur un seul échantillon. Effectuez votre test N fois. Collectez les résultats et calculez la moyenne ou la médiane du résultat.

5
2017-11-01 06:26



De commentaires:

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

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

Si ça volonté débordement - pour l'une de ces graines initiales malchanceuses, le nombre survolé convergera très probablement vers 1 sans un autre débordement.

Cela pose quand même une question intéressante, y a-t-il un certain nombre de graines de trop-cycle?

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

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

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

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 y faire face 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 tous les non-2 premiers facteurs du nombre original (ou intermédiaire) en une puissance de 2, tôt ou tard . Nous n'avons donc pas besoin de nous inquiéter de la 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 jeté un coup d'oeil sur les nombres tronqués de 8 bits.

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

Mais il n'y a pas de valeur à créer une graine de débordement cyclique.

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

Assez intéressant (pour moi) le nombre 9232 est le maximum pour de nombreux autres numéros de source, qu'est-ce qu'il y a de si spécial? : -O 9232 = 0x2410 ... hmmm .. aucune idée.

Malheureusement, je n'arrive pas à saisir toute cette série, pourquoi converge-t-elle et quelles sont les implications de les tronquer k bits, mais avec cmp number,1 condition de fin, 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ébordement pour un cas de 8 bits est une sorte d'alerte, cela ressemble à si vous comptez le nombre d'étapes pour atteindre la valeur 1, vous obtiendrez un mauvais résultat pour la majorité des nombres de l'ensemble des nombres entiers de k bits. Pour les entiers de 8 bits, les 146 numéros sur 256 ont affecté les séries par troncature (certains d'entre eux peuvent encore heurter le bon nombre de pas par accident peut-être, je suis trop paresseux pour vérifier).


4
2017-11-01 17:18



Vous n'avez pas publié 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:

test rax, 1
jpe even

... a 50% de chance de mal représenter la branche, et cela va coûter cher.

Le compilateur fait presque certainement les deux calculs (ce qui coûte neglegibly plus puisque le div / mod est une latence assez longue, donc le multiply-add est "libre") et suit avec un CMOV. Ce qui, bien sûr, a un zéro Pourcentage de chance d'être mal interprété.


4
2017-11-01 19:50



Même sans regarder l'assemblage, la raison la plus évidente est que /= 2 est probablement optimisé >>=1 et beaucoup de processeurs ont une opération de décalage 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 salaire peut varier selon la déclaration «Division entière est plus rapide que la division à 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 l'accélération que la question de ce fil demande, alors l'optimisation du compilateur /=2 comme >>=1 serait la meilleure 1ère place à regarder.


Sur un note sans rapport, si n est étrange, l'expression n*3+1 sera toujours pair. Donc, il n'y a pas besoin de vérifier. Vous pouvez changer cette branche pour

{
   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
2017-11-01 21:16



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

Ecriture du code assembleur, il est possible pour améliorer ce que fait un compilateur d'optimisation, mais c'est un travail difficile. Et une fois que c'est fait, votre code est beaucoup plus difficile à modifier, donc il est beaucoup plus difficile d'ajouter des améliorations algorithmiques. Parfois, le processeur a des fonctionnalités que vous ne pouvez pas utiliser depuis un langage de haut niveau, l'assemblage en ligne est souvent utile dans ces cas et vous permet quand 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, en trouvant pourquoi c'est lent, en construisant quelque chose de mieux, en trouvant pourquoi c'est lent, et ainsi de suite. C'est très, très dur en utilisant l'assembleur. Un meilleur algorithme à la moitié de la vitesse possible battra généralement un algorithme pire à pleine vitesse, et obtenir la pleine vitesse en assembleur n'est pas trivial.


3
2017-11-04 17:15



Pour le problème Collatz, vous pouvez obtenir une amélioration significative des performances en mettant en cache les "queues". C'est un compromis temps / mémoire. Voir: mémo (https://en.wikipedia.org/wiki/Memoization). Vous pouvez également envisager 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))

3
2017-11-05 18:49



La réponse simple:

  • faire un MOV RBX, 3 et MUL RBX est cher; juste ajouter RBX, RBX deux fois

  • ADD 1 est probablement plus rapide que INC ici

  • MOV 2 et DIV est très cher; juste passer à droite

  • Le code 64 bits est généralement sensiblement 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 empaqueter afin que vous fassiez des calculs parallèles pour avoir une chance d'être plus rapide qu'un code 32 bits

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


-2
2017-11-07 01:03