Pourquoi l'introduction d'instructions MOV inutiles accélérerait-elle une boucle serrée dans un assemblage x86_64?

Contexte:

En optimisant du code Pascal avec un langage d'assemblage intégré, j'ai remarqué une MOVinstruction inutile et je l'ai supprimée.

À ma grande surprise, la suppression des instructions inutiles a entraîné un ralentissement de mon programme .

J'ai trouvé que l' ajout d' MOVinstructions arbitraires et inutiles augmentait encore les performances .

L'effet est erratique et change en fonction de l'ordre d'exécution: les mêmes instructions indésirables transposées vers le haut ou vers le bas par une seule ligne produisent un ralentissement .

Je comprends que le CPU fait toutes sortes d'optimisations et de rationalisation, mais cela ressemble plus à de la magie noire.

Les données:

Une version de mon code compile conditionnellement trois opérations indésirables au milieu d'une boucle qui s'exécute plusieurs 2**20==1048576fois. (Le programme environnant calcule simplement les hachages SHA-256 ).

Les résultats sur ma machine plutôt ancienne (Intel (R) Core (TM) 2 CPU 6400 @ 2,13 GHz):

avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without:        1836.44 ms

Les programmes ont été exécutés 25 fois en boucle, l'ordre d'exécution changeant de façon aléatoire à chaque fois.

Extrait:

{$asmmode intel}
procedure example_junkop_in_sha256;
  var s1, t2 : uint32;
  begin
    // Here are parts of the SHA-256 algorithm, in Pascal:
    // s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
    // s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
    // Here is how I translated them (side by side to show symmetry):
  asm
    MOV r8d, a                 ; MOV r9d, e
    ROR r8d, 2                 ; ROR r9d, 6
    MOV r10d, r8d              ; MOV r11d, r9d
    ROR r8d, 11    {13 total}  ; ROR r9d, 5     {11 total}
    XOR r10d, r8d              ; XOR r11d, r9d
    ROR r8d, 9     {22 total}  ; ROR r9d, 14    {25 total}
    XOR r10d, r8d              ; XOR r11d, r9d

    // Here is the extraneous operation that I removed, causing a speedup
    // s1 is the uint32 variable declared at the start of the Pascal code.
    //
    // I had cleaned up the code, so I no longer needed this variable, and 
    // could just leave the value sitting in the r11d register until I needed
    // it again later.
    //
    // Since copying to RAM seemed like a waste, I removed the instruction, 
    // only to discover that the code ran slower without it.
    {$IFDEF JUNKOPS}
    MOV s1,  r11d
    {$ENDIF}

    // The next part of the code just moves on to another part of SHA-256,
    // maj { r12d } := (a and b) xor (a and c) xor (b and c)
    mov r8d,  a
    mov r9d,  b
    mov r13d, r9d // Set aside a copy of b
    and r9d,  r8d

    mov r12d, c
    and r8d, r12d  { a and c }
    xor r9d, r8d

    and r12d, r13d { c and b }
    xor r12d, r9d

    // Copying the calculated value to the same s1 variable is another speedup.
    // As far as I can tell, it doesn't actually matter what register is copied,
    // but moving this line up or down makes a huge difference.
    {$IFDEF JUNKOPS}
    MOV s1,  r9d // after mov r12d, c
    {$ENDIF}

    // And here is where the two calculated values above are actually used:
    // T2 {r12d} := S0 {r10d} + Maj {r12d};
    ADD r12d, r10d
    MOV T2, r12d

  end
end;

Essayez-le vous-même:

Le code est en ligne sur GitHub si vous voulez l'essayer vous-même.

Mes questions:

• Pourquoi la copie inutile du contenu d'un registre vers la RAM augmenterait-elle les performances?
• Pourquoi la même instruction inutile fournirait-elle une accélération sur certaines lignes et un ralentissement sur d'autres?
• Ce comportement est-il quelque chose qui pourrait être exploité de manière prévisible par un compilateur?

La cause la plus probable de l'amélioration de la vitesse est que:

• l'insertion d'un MOV décale les instructions suivantes vers différentes adresses mémoire
• l'une de ces instructions déplacées était une branche conditionnelle importante
• cette branche était incorrectement prédite en raison d'un alias dans la table de prédiction de branche
• le déplacement de la branche a éliminé l'alias et a permis de prédire correctement la branche

Votre Core2 ne conserve pas d'enregistrement historique distinct pour chaque saut conditionnel. Au lieu de cela, il conserve un historique partagé de tous les sauts conditionnels. Un inconvénient de la prédiction de branche globale est que l'historique est dilué par des informations non pertinentes si les différents sauts conditionnels ne sont pas corrélés.

Ce petit tutoriel de prédiction de branche montre comment fonctionnent les tampons de prédiction de branche. Le tampon de cache est indexé par la partie inférieure de l'adresse de l'instruction de branchement. Cela fonctionne bien à moins que deux branches importantes non corrélées partagent les mêmes bits inférieurs. Dans ce cas, vous vous retrouvez avec un alias qui provoque de nombreuses branches mal prédites (ce qui bloque le pipeline d'instructions et ralentit votre programme).

Si vous voulez comprendre comment les erreurs de prédiction des branches affectent les performances, jetez un œil à cette excellente réponse: https://stackoverflow.com/a/11227902/1001643

Les compilateurs n'ont généralement pas suffisamment d'informations pour savoir quelles branches seront alias et si ces alias seront significatifs. Cependant, ces informations peuvent être déterminées lors de l'exécution avec des outils tels que Cachegrind et VTune .

Vous voudrez peut-être lire http://research.google.com/pubs/pub37077.html

TL; DR: l'insertion aléatoire d'instructions nop dans les programmes peut facilement augmenter les performances de 5% ou plus, et non, les compilateurs ne peuvent pas facilement l'exploiter. C'est généralement une combinaison de prédicteur de branche et de comportement de cache, mais il peut tout aussi bien s'agir, par exemple, d'un blocage de station de réservation (même s'il n'y a pas de chaînes de dépendance rompues ou de surabonnements de ressources évidents).

Je crois que dans les processeurs modernes, les instructions d'assemblage, tout en étant la dernière couche visible pour un programmeur pour fournir des instructions d'exécution à un processeur, sont en réalité plusieurs couches de l'exécution réelle par le processeur.

Les processeurs modernes sont des hybrides RISC / CISC qui traduisent les instructions CISC x86 en instructions internes dont le comportement est plus RISC. De plus, il existe des analyseurs d'exécution hors ordre, des prédicteurs de branche, la «fusion micro-op» d'Intel qui essaient de regrouper les instructions en lots plus importants de travaux simultanés (un peu comme le titanic VLIW / Itanium ). Il existe même des limites de cache qui pourraient accélérer le code pour Dieu sait pourquoi s'il est plus grand (peut-être que le contrôleur de cache le positionne plus intelligemment ou le conserve plus longtemps).

Le CISC a toujours eu une couche de conversion assemblage-microcode, mais le fait est qu'avec les processeurs modernes, les choses sont beaucoup plus compliquées. Avec tout l'immobilier supplémentaire de transistors dans les usines de fabrication de semi-conducteurs modernes, les processeurs peuvent probablement appliquer plusieurs approches d'optimisation en parallèle, puis sélectionner celle à la fin qui offre la meilleure accélération. Les instructions supplémentaires peuvent biaiser le CPU pour utiliser un chemin d'optimisation meilleur que les autres.

L'effet des instructions supplémentaires dépend probablement du modèle / de la génération / du fabricant du processeur et n'est pas susceptible d'être prévisible. L'optimisation du langage d'assemblage de cette façon nécessiterait une exécution sur de nombreuses générations d'architecture de processeur, peut-être en utilisant des chemins d'exécution spécifiques au processeur, et ne serait souhaitable que pour des sections de code vraiment très importantes, bien que si vous faites un assemblage, vous le savez probablement déjà.

Préparation du cache

Les opérations de déplacement vers la mémoire peuvent préparer le cache et accélérer les opérations de déplacement suivantes. Un CPU a généralement deux unités de charge et une unité de stockage. Une unité de chargement peut lire de la mémoire dans un registre (une lecture par cycle), une unité de stockage stocke du registre dans la mémoire. Il existe également d'autres unités qui effectuent des opérations entre les registres. Toutes les unités fonctionnent en parallèle. Ainsi, à chaque cycle, nous pouvons effectuer plusieurs opérations à la fois, mais pas plus de deux chargements, un magasin et plusieurs opérations de registre. Habituellement, il s'agit de jusqu'à 4 opérations simples avec des registres simples, jusqu'à 3 opérations simples avec des registres XMM / YMM et 1-2 opérations complexes avec tout type de registres. Votre code a beaucoup d'opérations avec des registres, donc une opération de stockage de mémoire factice est gratuite (car il y a plus de 4 opérations de registre de toute façon), mais il prépare le cache mémoire pour l'opération de stockage suivante. Pour savoir comment fonctionnent les magasins de mémoire, reportez-vous auManuel de référence de l'optimisation des architectures Intel 64 et IA-32 .

Briser les fausses dépendances

Bien que cela ne fasse pas exactement référence à votre cas, mais parfois, l'utilisation d'opérations mov 32 bits sous le processeur 64 bits (comme dans votre cas) est utilisée pour effacer les bits supérieurs (32-63) et rompre les chaînes de dépendance.

Il est bien connu que sous x86-64, l'utilisation d'opérandes 32 bits efface les bits supérieurs du registre 64 bits. Veuillez lire la section pertinente - 3.4.1.1 - du Manuel du développeur du logiciel des architectures Intel® 64 et IA-32 Volume 1 :

Les opérandes 32 bits génèrent un résultat 32 bits, étendu de zéro à un résultat 64 bits dans le registre à usage général de destination

Ainsi, les instructions mov, qui peuvent sembler inutiles à première vue, effacent les bits supérieurs des registres appropriés. Qu'est-ce que cela nous donne? Il rompt les chaînes de dépendances et permet aux instructions de s'exécuter en parallèle, dans un ordre aléatoire, par l' algorithme Out-of-Order implémenté en interne par les CPU depuis Pentium Pro en 1995.

Une citation du manuel de référence sur l'optimisation des architectures Intel® 64 et IA-32 , section 3.5.1.8:

Les séquences de code qui modifient le registre partiel peuvent subir un certain retard dans sa chaîne de dépendance, mais peuvent être évitées en utilisant des idiomes de rupture de dépendance. Dans les processeurs basés sur la micro-architecture Intel Core, un certain nombre d'instructions peuvent aider à éliminer la dépendance d'exécution lorsque le logiciel utilise ces instructions pour effacer le contenu du registre à zéro. Brisez les dépendances sur des parties de registres entre les instructions en opérant sur des registres 32 bits au lieu de registres partiels. Pour les déplacements, cela peut être accompli avec des déplacements 32 bits ou en utilisant MOVZX.

Règle de codage assembleur / compilateur 37. (impact M, généralité MH) : rompre les dépendances sur des parties de registres entre les instructions en opérant sur des registres 32 bits au lieu de registres partiels. Pour les déplacements, cela peut être accompli avec des déplacements 32 bits ou en utilisant MOVZX.

Le MOVZX et le MOV avec des opérandes 32 bits pour x64 sont équivalents - ils rompent tous les chaînes de dépendance.

C'est pourquoi votre code s'exécute plus rapidement. S'il n'y a pas de dépendances, le CPU peut renommer en interne les registres, même si à première vue il peut sembler que la deuxième instruction modifie un registre utilisé par la première instruction et que les deux ne peuvent pas s'exécuter en parallèle. Mais en raison de l'enregistrement, ils peuvent le renommer.

Le renommage de registre est une technique utilisée en interne par une CPU qui élimine les fausses dépendances de données résultant de la réutilisation des registres par des instructions successives qui n'ont pas de véritables dépendances de données entre elles.

Je pense que vous voyez maintenant que c'est trop évident.