Pourquoi introduire inutile instructions MOV accélérer une boucle en x86_64 assemblée?

Question

Arrière-plan:

Bien que l'optimisation de certaines Pascal le code intégré dans le langage d'assemblage, j'ai remarqué une inutiles MOV instruction, et l'a supprimé.

À ma grande surprise, la suppression de l'onu-les instructions nécessaires, la cause de mon programme à ralentir.

J'ai trouvé que l'ajout d'arbitraire, inutile, MOV instructions de l'augmentation des performances encore plus loin.

L'effet est erratique, et des modifications basées sur l'ordre d'exécution: la même ordure instructions transposée vers le haut ou vers le bas par une ligne unique de produire un ralentissement.

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

Les données:

Une version de mon code conditionnellement compile trois indésirable opérations au moyen d'une boucle qui s'exécute 2**20==1048576 temps. (Environnants programme calcule SHA-256 de hachages).

Les résultats sur ma vieille machine (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 dans une boucle, avec l'ordre d'exécution de changer 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 essayer vous-même.

Mes questions:

• Pourquoi ne pas la copie d'un registre le contenu de la RAM n'augmente les performances?
• Pourquoi serait même inutile instruction fournir une accélération sur certaines lignes, et un ralentissement sur les autres?
• Est-ce le comportement de quelque chose qui pourrait être exploité de façon prévisible par un compilateur?

Answer 1

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

• l'insertion d'une MOV déplace les instructions qui s'affichent à différentes adresses de la mémoire
• l'un de ces déplacés des instructions a été une importante branche conditionnelle
• cette branche était mal prévu en raison de l'aliasing dans la direction de la prévision table
• le déplacement de la branche éliminé l'alias et a permis à la branche de prédire correctement

Votre Core2 ne pas garder un enregistrement de l'historique pour chaque saut conditionnel. Au lieu de cela, il maintient une histoire partagée de tous les sauts conditionnels. Un inconvénient de la mondiale, direction de la prévision , c'est que l'histoire est dilué par de l'information non pertinente si les différents sauts conditionnels ne sont pas corrélées.

Cette petite branche de prédiction tutoriel montre comment la direction de la prévision tampons de travail. La mémoire cache est indexé par la partie inférieure de l'adresse de la direction de l'instruction. Cela fonctionne bien, sauf deux non corrélées branches partagent les mêmes bits de poids faible. Dans ce cas, vous terminez avec de l'aliasing qui provoque de nombreux mispredicted branches (qui stalles de l'instruction pipeline et le ralentissement de votre programme).

Si vous voulez comprendre comment le branche mispredictions affecter les performances, jetez un oeil à cette excellente réponse: http://stackoverflow.com/a/11227902/1001643

Les compilateurs n'ont généralement pas de suffisamment d'informations pour savoir quelles branches d'alias et si les alias seront importants. Toutefois, cette information peut être déterminé au moment de l'exécution avec des outils tels que Cachegrind et VTune.

Answer 2

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

TL;DR: au hasard de l'insertion nop instructions de programmes peuvent facilement augmenter le rendement de 5% ou plus, et non, les compilateurs ne peuvent pas l'exploiter facilement. C'est généralement une combinaison de la branche prédicteur et le cache de comportement, mais il peut tout aussi bien être par exemple une réservation de la station de décrochage (même dans le cas où il n'y a pas de dépendance des chaînes qui sont cassées ou ressource évidente sur-abonnements que ce soit).

Answer 3

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

Les Processeurs modernes sont RISC/CISC hybrides qui traduisent CDCI x86 instructions dans les instructions internes qui sont plus RISC dans le comportement. De plus il y a de l'exécution d'analyseurs, de la direction générale de prédicteurs, Intel "micro-ops fusion" qui tentent de groupe pour des instructions sur les lots plus gros du travail simultané (un peu comme le VLIW/Itanium titanic). Il y a même des cache limites qui pourrait rendre le code de courir plus vite pour dieu sait pourquoi, si c'est plus grand (peut-être le contrôleur de mémoire cache les fentes de manière plus intelligente, ou elle conserve plus longtemps).

Le SCRC a toujours eu une assemblée-à-microcode couche de traduction, mais le point est que, avec les Processeurs modernes, les choses sont beaucoup beaucoup beaucoup plus compliqué. Avec tout le transistor de l'immobilier moderne, les usines de fabrication de semi-conducteurs, Processeurs peuvent probablement s'appliquer à plusieurs approches d'optimisation en parallèle, puis sélectionnez l'une à la fin qui offre la meilleure accélération. Les instructions supplémentaires peuvent influencer le CPU à utiliser une optimisation du chemin qui est meilleur que les autres.

L'effet des instructions supplémentaires dépend probablement sur le modèle de CPU / génération / le fabricant, et n'est pas susceptible d'être prévisible. L'optimisation de l'assemblée de la langue cette façon serait de requérir l'exécution à l'encontre de nombreux architecture du PROCESSEUR générations, peut-être l'aide spécifique au PROCESSEUR de chemins d'exécution, et ne serait souhaitable pour vraiment vraiment important sections de code, mais si vous êtes en train de faire le montage, vous savez probablement déjà que.