1. ホーム
  2. パフォーマンス

[解決済み】x86_64アセンブリで無駄なMOV命令を導入すると、なぜタイトループが速くなるのでしょうか?

2022-04-07 21:19:35

質問

背景は?

を最適化したところ パスカル のコードをアセンブリ言語で埋め込んだところ、不要な MOV 命令を削除しました。

驚いたことに、不要な命令を削除したことで、私のプログラムは 速度を落とす .

ということがわかりました。 を追加することで、無駄な MOV 命令によってパフォーマンスが向上 をさらに増やしました。

効果は不規則で、実行順序によって変化します。 同じジャンクの命令を入れ替えた場合 上下に1行ずつ スローダウンが発生する .

CPUがあらゆる最適化、効率化を行うことは理解していますが、これはむしろ黒魔術のような気がします。

データです。

私のコードを条件付きでコンパイルしたバージョン 3つのジャンク処理 を実行するループの途中で 2**20==1048576 回です。(周囲のプログラムは、単に SHA-256 がハッシュ化されます)。

私のかなり古いマシン(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

プログラムはループで25回実行され、実行順序は毎回ランダムに変更された。

抜粋

{$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;

自分で試してみてください。

コードはオンラインで GitHubにて を使うことができます。

私の質問

  • なぜ、レジスタの中身を無駄にコピーして RAM は、決してパフォーマンスを向上させないのですか?
  • 同じ無駄な命令でも、ある行では高速化し、ある行では低速化するのはなぜか?
  • この挙動は、コンパイラによって予測可能に悪用されるものなのか?

解決方法は?

速度が向上した原因として考えられるのは

  • MOVを挿入すると、後続の命令が異なるメモリアドレスにシフトする。
  • その移動した命令のうちの1つは、重要な条件分岐である。
  • 分岐予測テーブルのエイリアシングにより、その分岐が正しく予測されていなかった。
  • ブランチを移動させることでエイリアスを排除し、ブランチを正しく予測できるようになりました。

Core2は、条件分岐ごとに個別の履歴を保持しているわけではありません。その代わり、すべての条件分岐の履歴を共有しています。 の欠点のひとつは グローバル分岐予測 は、異なる条件付きジャンプが相関しない場合、履歴が無関係な情報によって希釈されることです。

この小さな 分岐予測チュートリアル は、分岐予測バッファの仕組みを示しています。キャッシュバッファは、分岐命令のアドレスの下位部分によってインデックスされます。 これは、相関のない2つの重要な分岐が同じ下位ビットを共有していない限り、うまく機能します。 この場合、エイリアシングが発生し、多くの予測ミスのある分岐が発生します(これは命令パイプラインを停止させ、プログラムの速度を低下させます)。

分岐予測の誤りがパフォーマンスにどのように影響するかを理解したい場合は、この優れた回答を参照してください。 https://stackoverflow.com/a/11227902/1001643

コンパイラは通常、どのブランチがエイリアスになるのか、またそのエイリアスが重要かどうかを知るための十分な情報を持っていません。 しかし、そのような情報は、次のようなツールを使って実行時に決定することができます。 キャッシュグラインド VTune .