c++ - software - x86 instruction latency




Code C++ pour tester la conjecture de Collatz plus rapidement qu'un assemblage écrit à la main-pourquoi? (8)

En guise de réponse générique, qui ne vise pas spécifiquement cette tâche: Dans de nombreux cas, vous pouvez accélérer de manière significative tout programme en apportant des améliorations de haut niveau. Par exemple, calculez les données une fois au lieu de plusieurs fois, en évitant complètement le travail inutile, en utilisant au mieux les caches, etc. Ces choses sont beaucoup plus faciles à faire dans une langue de haut niveau.

En écrivant du code assembleur, il est possible d'améliorer le fonctionnement d'un compilateur d'optimisation, mais c'est un travail difficile. Et une fois que c'est fait, votre code est beaucoup plus difficile à modifier, il est donc beaucoup plus difficile d'ajouter des améliorations algorithmiques. Parfois, le processeur dispose de 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 néanmoins d'utiliser un langage de haut niveau.

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

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

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

Le C ++ a été compilé avec

g++ p14.cpp -o p14

Assemblée, p14.asm

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

global main
extern printf

section .text

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

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

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

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

c1:
    inc r10
    cmp rax, 1
    jne l2

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

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C ++, p14.cpp

#include <iostream>

using namespace std;

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

        ++count;
    }

    return count;
}

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

    cout << maxi << endl;
}

Je connais les optimisations du compilateur pour améliorer la vitesse et tout le reste, mais je ne vois pas beaucoup de façons d’optimiser davantage ma solution d’assemblage (parler de manière programmatique et non mathématique).

Le code C ++ a un module à chaque terme et une division à chaque terme pair, où l’assemblage ne représente qu’une division par terme pair.

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

Temps d'exécution

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


La réponse simple:

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

  • ADD 1 est probablement plus rapide que INC ici

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

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

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


Même sans regarder l’assemblage, la raison la plus évidente /= 2 est probablement optimisée étant donné >>=1 que de nombreux processeurs fonctionnent très rapidement. Mais même si un processeur ne subit pas d'opération de décalage, la division entière est plus rapide que la division à virgule flottante.

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

Sur une note non liée , si n est impair, l'expression n*3+1 sera toujours paire. Donc, il n'y a pas besoin de vérifier. Vous pouvez changer cette branche en

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

Donc toute la déclaration serait alors

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

Pour le problème Collatz, vous pouvez augmenter considérablement les performances en mettant en cache les "queues". C'est un compromis temps / mémoire. Voir: memoization ( https://en.wikipedia.org/wiki/Memoization ). Vous pouvez également rechercher des solutions de programmation dynamiques 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))

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

test rax, 1
jpe even

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

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


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

La différence de temps que vous voyez est due au fait que le code d'assemblage de 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 ne peut être optimisée que pour 5 instructions:

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

Le code entier ressemble à:

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

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

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

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

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

        dec     ecx
        jnz     .main_loop

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

        FinalizeAll
        stdcall TerminateAll, 0

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

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

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


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

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

Voici une grande victoire: si vous regardez les 8 bits les plus bas de n, toutes les étapes jusqu’à ce que vous divisiez par 2 huit fois sont 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, les prochaines étapes sont les suivantes:

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

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 créer 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 stade, n peut devenir 1 avec moins de huit divisions sur 2, et effectuer huit étapes ou plus à la fois vous ferait perdre le point où vous atteignez 1 pour la première fois. Continuez ensuite la boucle "normale" - ou préparez un tableau qui vous indique combien d’étapes supplémentaires sont nécessaires pour atteindre 1.

PS Je soupçonne fortement la suggestion de Peter Cordes d'accélérer les choses Il n'y aura aucune branche conditionnelle du tout sauf une, et celle-ci sera prédite correctement sauf lorsque la boucle se termine réellement. Donc, le code serait quelque chose comme

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

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

En pratique, vous évalueriez si le traitement des 9, 10, 11, 12 derniers bits de n à la fois serait plus rapide. Pour chaque bit, le nombre d'entrées dans la table doublerait et j'entraînerais 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 sur deux et un nombre variable d'opérations (3n + 1), de sorte qu'une méthode évidente de décompte des 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: remplacez n par (3n + 1) / 2 si impair, et remplacez par n / 2 si pair. Ensuite, chaque itération fera exactement 8 étapes, mais vous pourriez envisager de tricher :-) Supposons donc qu'il y avait r opérations n <- 3n + 1 et s opérations n <- n / 2. Le résultat sera exactement 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 si nous avons une table précalculée, combien d'itérations sont nécessaires à partir de tout 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 ne soit vraiment grand.


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

Consultez le guide d’Assemblage optimisé d’Agner Fog pour savoir comment écrire un asm efficace. Il dispose également de tables d'instructions et d'un guide microarch pour des détails spécifiques sur des processeurs spécifiques. Voir aussi le wiki des balises x86 pour plus de liens parfaits.

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

En général, vous pouvez laisser le compilateur agir, en particulier si vous essayez d’écrire en C ++ pour compiler efficacement . Vous voyez également que l' assemblage est plus rapide que les langages compilés . L’une des réponses est liée à ces diapositives montrant comment divers compilateurs C optimisent des fonctions très simples avec des astuces géniales.

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

Sur Intel Haswell, div r64 est de 36 UPS, avec une latence de 32 à 96 cycles et un débit d’un à 21-74 cycles. (En plus des 2 uops pour configurer RBX et zéro RDX, mais une exécution dans le désordre peut s'exécuter plus tôt). Les instructions à comptage élevé, telles que DIV, sont microcodées, ce qui peut également causer des goulots d'étranglement frontaux. Dans ce cas, la latence est le facteur le plus pertinent, car elle fait partie d'une chaîne de dépendance en boucle.

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

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

Comme vous pouvez le constater en regardant la sortie -O0 asm de gcc (l' explorateur du compilateur Godbolt ), il utilise uniquement des instructions de décalage . clang -O0 compile naïvement comme vous le pensiez, même en utilisant deux fois l’IDIV 64 bits. (Lors de l'optimisation, les compilateurs utilisent les deux sorties de IDIV lorsque la source effectue 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 inclut la reconnaissance de division par constante et l’utilisation de décalages (puissance de 2) ou d’ un inverse multiplicatif à point fixe (non puissance de 2) pour éviter IDIV (voir div_by_13 dans le lien ci-dessus de godbolt).

gcc -Os (optimiser pour la taille) utilise IDIV pour la division non-puissance-2, malheureusement même dans les cas où le code inverse multiplicatif est à peine plus grand mais beaucoup plus rapide.

Aider le compilateur

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

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

Regardez votre sortie asm (sur Godbolt, ou voir Comment supprimer le "bruit" de la sortie de l'assemblage GCC / clang? ). Lorsque le compilateur ne crée pas un code optimal au départ: Écrire votre source C / C ++ de manière à guider le compilateur pour améliorer le code est généralement la meilleure approche . Vous devez connaître 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 sympa, et vous pouvez utiliser gcc pour faire la même chose: voyez 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 futur pourra la compiler selon ce qui sera efficace sur le matériel futur (x86 ou non), en utilisant éventuellement une nouvelle extension ISA ou une vectorisation automatique. Les x86-64 asm manuscrites d'il y a 15 ans ne sont généralement pas optimisées pour Skylake. par exemple, la macro-fusion de comparaison et de branche n'existait pas à l'époque. Ce qui est optimal maintenant pour un ASM fabriqué à la main pour une microarchitecture peut ne pas être optimal pour d'autres processeurs actuels et futurs. Les commentaires sur la réponse de @ johnfound discutent des différences majeures entre AMD Bulldozer et Intel Haswell, qui ont un impact considérable sur ce code. Mais en théorie, g++ -O3 -march=bdver3 et g++ -O3 -march=skylake fera le bon choix. (Ou -march=native .) Ou -mtune=... pour régler, sans utiliser d'instructions que d'autres processeurs pourraient ne pas prendre en charge.

Mon sentiment est que guider le compilateur pour qu'il soit bon pour un processeur actuel qui vous tient à cœur ne devrait pas être un problème pour les futurs compilateurs. Nous espérons qu'ils sont meilleurs que les compilateurs actuels pour trouver des moyens de transformer le code, et peuvent trouver un moyen qui fonctionne pour les futurs processeurs. Quoi qu'il en soit, le futur x86 ne sera probablement pas terrible pour tout ce qui est bon sur le x86 actuel, et le futur compilateur évitera les pièges spécifiques à asm tout en implémentant quelque chose comme le 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. Par conséquent, la propagation constante ne fonctionne pas lorsque l'inline fait en sorte qu'une entrée soit une constante de compilation. D'autres optimisations sont également affectées. Lisez https://gcc.gnu.org/wiki/DontUseInlineAsm avant d'utiliser asm. (Et évitez les ASM en ligne de style MSVC: les entrées / sorties doivent passer par la mémoire, ce qui augmente la surcharge .)

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

Vous auriez dû utiliser uint64_t n pour pouvoir simplement SHR. Et donc, il est portable pour les systèmes où la long n’est que de 32 bits (par exemple Windows x86-64).

Au fait, la sortie asm optimisée de gcc semble plutôt bonne (avec unsigned long n ) : la boucle interne qu’elle insère dans main() fait ceci:

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

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

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

La boucle interne n'a pas de branche et le chemin critique de la chaîne de dépendance véhiculée par la boucle est le suivant:

  • 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 hors service s’occupe de tout le reste en parallèle (en théorie: je n’ai pas testé avec des compteurs de performances pour voir s’il fonctionne vraiment à 5c / iter).

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

De même, le MOV-> SHR qui produit l'entrée RDI de CMOV est en dehors du chemin critique, car il est également plus rapide que le LEA. MOV sur IvyBridge et versions ultérieures a une latence nulle (gérée au moment de la modification du registre). (Il faut tout de même un uop et un créneau dans le pipeline, donc ce n’est pas gratuit, mais une latence nulle). Le MOV supplémentaire dans la chaîne LEA Dep fait partie du goulot d'étranglement des autres processeurs.

Le cmp / jne ne fait pas non plus partie du chemin critique: il n'est pas acheminé en boucle, 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 un très bon travail ici. Il pourrait économiser un octet de code en utilisant inc edx au lieu de add edx, 1 , car personne ne se soucie de P4 et de ses fausses dépendances pour les instructions de modification partielle du drapeau.

Cela pourrait aussi sauvegarder toutes les instructions MOV, et le TEST: SHR définit CF = le bit décalé, afin que nous puissions 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: supprimez le CMP en créant une branche sur le résultat du drapeau de SHR et en l'utilisant pour CMOV: zéro uniquement si n était égal à 1 (ou 0). (Fait amusant: SHR avec compte! = 1 sur Nehalem ou avant provoque un blocage si vous lisez les résultats du drapeau . C'est comme cela qu'ils l'ont fait en mode simple. Le codage spécial décalage par 1 est cependant correct.)

Eviter MOV n'aide pas du tout avec la latence sur Haswell ( le MOV de x86 peut-il vraiment être "gratuit"? Pourquoi ne puis-je pas le reproduire du tout? ). Cela aide beaucoup sur les processeurs comme Intel pré-IvB et la famille de bulldozers AMD, où MOV n’est pas à latence nulle. Les instructions MOV gâchées par le compilateur affectent le chemin critique. Les complexes LEA et CMOV de BD ont tous deux une latence inférieure (2c et 1c respectivement), ce qui en fait une fraction plus importante de la latence. En outre, les goulots d'étranglement de débit deviennent un problème, car il ne comporte que deux canaux ALU entiers. Voir la réponse de @ johnfound , où il dispose des résultats de synchronisation d'un processeur AMD.

Même sur Haswell, cette version peut aider un peu en évitant certains retards occasionnels dans lesquels un utilisateur non critique vole un port d’exécution à un port situé sur le chemin critique, retardant ainsi l’exécution de 1 cycle. (Cela s'appelle un conflit de ressources). Il enregistre également un registre, ce qui peut être utile lors de la création de n valeurs en parallèle dans une boucle entrelacée (voir ci-dessous).

La latence de LEA dépend du mode d'adressage , des processeurs de la famille Intel SnB. 3c pour 3 composants ( [base+idx+const] , qui prend deux additions distinctes), mais seulement 1c avec 2 composants ou moins (un add). Certains processeurs (comme Core2) font même un LEA à 3 composants en un seul cycle, mais la famille SnB ne le fait pas. Pire encore, la famille Intel SnB normalise les latences de sorte qu'il n'y ait pas d'uops 2c , sinon le LEA à 3 composants ne serait que 2c comme Bulldozer. (Le LEA à 3 composants ralentit également la DMLA, mais pas autant).

Donc lea rcx, [rax + rax*2] / inc rcx n’est que de latence 2c, plus rapide que lea rcx, [rax + rax*2 + 1] , sur les processeurs de la famille Intel SnB comme Haswell. Rentabilité sur BD et pire sur Core2. Cela coûte un uop supplémentaire, ce qui n'est normalement pas la peine d'économiser du temps de latence, mais le temps d'attente est le principal goulot d'étranglement et Haswell dispose d'un pipeline suffisamment 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 un TEST . Compilateurs stupides. : P Ce sont d'excellentes pièces de machinerie complexe, mais un humain intelligent peut souvent les vaincre pour des problèmes mineurs. (Bien entendu, des milliers, des millions de fois plus de temps à y penser! Les compilateurs n'utilisent pas des algorithmes exhaustifs pour rechercher toutes les méthodes possibles, car cela prendrait trop de temps pour optimiser beaucoup de code en ligne. Ils ne modélisent pas non plus le pipeline dans la microarchitecture cible, du moins pas avec les mêmes détails que IACA ou d’autres outils d’analyse statique; ils utilisent simplement des méthodes heuristiques.)

Un simple déroulement de boucle ne va pas aider ; ces goulots d'étranglement de boucle sur la latence d'une chaîne de dépendance véhiculée par la boucle, et non sur le temps système de traitement / le débit de la boucle. Cela signifie que cela fonctionnerait bien avec l'hyperthreading (ou tout autre type de SMT), car le processeur dispose de beaucoup de temps pour entrelacer les instructions de deux threads. Cela impliquerait de paralléliser la boucle dans main , mais c'est correct, car chaque thread peut simplement vérifier une plage de n valeurs et produire une paire d'entiers en conséquence.

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

L’astuce consiste à décider s’il faut attendre que toutes les n valeurs atteignent 1 avant d’obtenir une autre paire de n valeurs de départ, ou s’ouvrir et obtenir un nouveau point de départ pour un seul qui a atteint la condition de fin, sans toucher aux registres de la 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 d'éléments vectoriels où n n'avait pas encore atteint 1 . Ensuite, pour masquer la latence encore plus longue d'une implémentation à incrémentation conditionnelle SIMD, vous devez conserver davantage de vecteurs de n valeurs dans les airs. Peut-être ne vaut-il que la peine avec le vecteur 256b (4x uint64_t ).

Je pense que la meilleure stratégie pour détecter un 1 "collant" est de masquer le vecteur de tout-un que vous ajoutez pour incrémenter le compteur. Donc, après avoir vu un 1 dans un élément, le vecteur d'incrémentation aura un zéro et + = 0 est un non-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 implémenter cela avec des éléments intrinsèques, au lieu d’asm écrit à la main.

Amélioration algorithmique / implémentation:

En plus d’implémenter la même logique avec un asm plus efficace, cherchez des moyens de la simplifier ou d’éviter les tâches redondantes. Par exemple, mémoize pour détecter les fins communes des séquences. Ou même mieux, regardez 8 bits de fuite à la fois (la réponse de gnasher)

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

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 décalages à compte variable 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 drapeaux ne sont pas modifiés. Ils la traitent comme une dépendance de données et prennent plusieurs uops car un uop ne peut avoir que 2 entrées (pré-HSW / BDW de toute façon)). C’est le genre auquel font référence les personnes qui se plaignent de la conception folle-CISC de x86. Cela rend les processeurs x86 plus lents qu’ils ne le seraient si l’ISA était conçu de toutes pièces aujourd’hui, même de manière presque similaire. (c’est-à-dire que cela fait partie de la "taxe x86" qui coûte rapidité / puissance.) SHRX / SHLX / SARX (BMI2) est une grande 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épendance acheminée par la boucle. Cela supprime toutefois la nécessité d'une CMOV ou de la préparation d'un registre contenant n>>1 . @ La réponse de Veedrac surmonte tout cela en différant le tzcnt / shift pour plusieurs itérations, ce qui est très efficace (voir ci-dessous).

Nous pouvons utiliser BSF ou TZCNT manière interchangeable, car n ne peut jamais être zéro à ce stade. Le code machine de TZCNT se décode en tant que BSF sur les CPU ne prenant pas en charge BMI1. (Les préfixes sans signification sont ignorés, REP BSF est donc exécuté en tant que BSF).

TZCNT fonctionne beaucoup mieux que BSF sur les processeurs AMD qui le supportent. Il peut donc être judicieux 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 lorsque vous utilisez __builtin_ctzll même avec -mno-bmi .

Ils fonctionnent de la même manière sur les processeurs Intel. Enregistrez donc simplement l’octet si c’est tout ce qui compte. TZCNT sur Intel (avant Skylake) a toujours une fausse dépendance sur l'opérande de sortie supposé en écriture seule, tout comme BSF, pour prendre en charge le comportement non documenté selon lequel BSF avec input = 0 laisse sa destination non modifiée. Vous devez donc contourner ce problème, à moins d’optimiser uniquement pour Skylake. Il n’ya donc rien à gagner de l’octet REP supplémentaire. (Intel va souvent au-delà des exigences du manuel ISA x86, pour éviter de casser du code largement utilisé qui dépend de quelque chose qu’il ne devrait pas ou qui est rétroactivement interdit. lorsque le code a été écrit, avant qu'Intel ne mette à jour les règles de gestion TLB .)

Quoi qu'il en soit, LZCNT / TZCNT sur Haswell ont le même faux dépôt que POPCNT: voir le présent Q & A. C'est pourquoi dans la sortie asm de gcc pour le code de @ Veedrac, vous voyez qu'il casse la chaîne dep avec xor-zeroing sur le registre qu'il est sur le point d'utiliser comme destination de TZCNT, lorsqu'il n'utilise pas dst = src. Etant donné que TZCNT / LZCNT / POPCNT ne laisse jamais leur destination indéfinie ou modifiée, cette fausse dépendance de la sortie sur les processeurs Intel est purement un bug de performance. Vraisemblablement, certains transistors / puissances valent la peine de les faire se comporter comme d’autres uops qui vont à la même unité d’exécution. Le seul logiciel visible par le logiciel réside dans l'interaction avec une autre limitation microarchitecturale: ils peuvent 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 qu'ils "annelent" modes d’adressage indexés alors que POPCNT peut encore fusionner tout mode addr.

Améliorations apportées aux idées / codes à partir d'autres réponses:

La réponse de @ hidefromkgb donne à penser que vous serez assuré de pouvoir effectuer un changement de rapport après un 3n + 1. Vous pouvez calculer cela encore plus efficacement que de simplement laisser de côté les vérifications entre les étapes. L'implémentation asm de cette réponse est cependant cassée (elle dépend de OF, qui n'est pas défini après SHRD avec un nombre> 1) et lent: ROR rdi,2 est plus rapide que SHRD rdi,rdi,2 et utilise deux instructions CMOV. sur le chemin critique est plus lent qu'un TEST supplémentaire pouvant s'exécuter en parallèle.

Je mets C bien rangé / amélioré (ce qui guide le compilateur pour produire un meilleur asm), et je teste + travaille plus vite (dans les commentaires sous le C) jusqu'à Godbolt: voir le lien dans la réponse de @ hidefromkgb . (Cette réponse a atteint la limite de 30 000 caractères des grandes URL Godbolt, mais les liens courts peuvent pourrir et étaient trop longs pour goo.gl de toute façon.)

Également amélioré l'impression de sortie pour convertir en chaîne et créer un write() au lieu d'écrire un caractère à la fois. Cela minimise l’impact sur le chronométrage de tout le programme avec perf stat ./collatz (pour enregistrer les compteurs de performance), et perf stat ./collatz partie de l’asm non critique.

@ Code de Veedrac

J'ai très peu accéléré depuis le passage à droite autant que nous le savons nécessaires, et en vérifiant de continuer la boucle. De 7,5s pour limit = 1e8 à 7.275s, sur Core2Duo (Merom), avec un facteur de déroulement de 16.

code + commentaires sur Godbolt . N'utilisez pas cette version avec clang; cela fait quelque chose d'idiot avec la boucle différée. Utiliser un compteur tmp k puis l'ajouter pour count plus tard change le comportement de clang, mais cela blesse légèrement gcc.

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





x86