performance - インライン - x86 pushl




無駄なMOV命令を導入すると、x86_64アセンブリのタイトなループが加速するのはなぜですか? (3)

キャッシュの準備

操作をメモリーに移動すると、キャッシュを準備して後続の移動操作を高速化できます。 通常、CPUには2つのロードユニットと1つのストアユニットがあります。 ロードユニットは、メモリからレジスタに読み出すことができ(1サイクル当たり1つの読み取り)、ストアユニットはレジスタからメモリに格納する。 レジスタ間で演算を行う他のユニットもあります。 すべてのユニットが並行して動作します。 したがって、各サイクルで、一度にいくつかの操作を行うことができますが、2つ以下のロード、1つのストア、および複数のレジスタ操作を実行できます。 通常、プレーンレジスタでは最大4回の単純な操作、XMM / YMMレジスタでは最大3回、シンプルな操作でも、あらゆる種類のレジスタでも1〜2回の複雑な操作が可能です。 あなたのコードはレジスタで多くの操作をしていますので、1つのダミーメモリストア操作はフリーです(とにかく4つ以上のレジスタ操作があるため)、後続のストア操作のためにメモリキャッシュを準備します。 メモリストアの仕組みについては、「 インテル64アーキテクチャーとIA-32アーキテクチャー最適化リファレンスマニュアル」を参照してください。

偽の依存関係を壊す

これは厳密にあなたのケースを参照していませんが、64ビットプロセッサの下で32ビットのmovオペレーションを使用することがあります(あなたの場合のように)、上位ビット(32-63)をクリアして依存関係チェインを破ります。

x86-64では、32ビットオペランドを使用すると、64ビットレジスタの上位ビットがクリアされることはよく知られています。 インテル ®64 およびIA-32アーキテクチャー・ソフトウェア開発者マニュアル第1巻

32ビットのオペランドは、デスティネーション汎用レジスタの64ビットの結果にゼロ拡張された32ビットの結果を生成します

したがって、最初の視点では役に立たないように見えるmov命令は、適切なレジスタの上位ビットをクリアします。 それは私たちに何を与えるのでしょうか? それは依存関係チェインを破壊し、1995年のPentium Pro以来、CPUによって内部的に実装されたOut-of-Orderアルゴリズムによって、命令がランダムな順序で並行して実行されるようにします。

インテル ®64 およびIA-32アーキテクチャー最適化リファレンス・マニュアル 、第3.5.1.8項からの引用:

部分的なレジスタを変更するコードシーケンスは、依存関係のチェーンでいくらかの遅延が発生する可能性がありますが、依存関係の破壊のイディオムを使用することで回避できます。 Intel Coreマイクロアーキテクチャに基づくプロセッサでは、ソフトウェアがこれらの命令を使用してレジスタの内容をゼロにクリアすると、多くの命令が実行依存を解消するのに役立ちます。 部分レジスタの代わりに32ビットレジスタを操作することにより、命令間のレジスタの一部の依存関係を解除します。 移動の場合、これは32ビットの移動またはMOVZXを使用して実行できます。

アセンブリ/コンパイラコーディング規則37(M影響、MH一般性) :部分レジスタの代わりに32ビットレジスタ上で動作することにより、命令間のレジスタの部分に対する依存性を解除する。 移動の場合、これは32ビットの移動またはMOVZXを使用して実行できます。

x64の32ビットオペランドを持つMOVZXとMOVは等価です。それらはすべて依存関係のチェーンを壊します。

そのため、コードがより速く実行されます。 依存関係がない場合、CPUはレジスタの名前を内部的に変更することができます。ただし、最初の命令では、2番目の命令が最初の命令で使用されるレジスタを変更し、2つが並列に実行できないように見えます。 しかし、登録名の変更により、名前を変更できます。

レジスタの名前変更は、CPUによって内部的に使用される手法であり、レジスタ間の実際のデータ依存性を持たない連続した命令によるレジスタの再利用に起因する誤ったデータ依存性を排除します。

私はあなたが今それがあまりにも明白だと思うと思う。

バックグラウンド:

組み込みアセンブリ言語を使っていくつかのPascalコードを最適化しながら、私は不要なMOV命令に気づき、それを削除しました。

私の驚いたことに、不要な命令を削除すると、プログラムが遅くなりました

私は、無用なMOV命令追加するとパフォーマンスがさらに向上することを発見しました。

その効果は不安定であり、実行順序に基づいて変化します.1つの行で上下に移動した同じジャンク命令 は、減速を引き起こします。

私はCPUがあらゆる種類の最適化と合理化を行っていることを理解していますが、これは黒い魔法のようです。

データ:

私のコードのバージョンは、 2**20==1048576回実行するループの途中で3つのジャンク操作を条件付きでコンパイルします。 (周囲のプログラムはちょうど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コピーするとパフォーマンスが向上するのでしょうか?
  • 同じ無駄な指示が、いくつかの回線でスピードアップを提供し、他のものでは減速するのはなぜですか?
  • この動作は、コンパイラによって予測可能に悪用される可能性がありますか?

http://research.google.com/pubs/pub37077.htmlを読んでみてくださいhttp://research.google.com/pubs/pub37077.html

TL; DR:プログラムに無作為にnop命令を挿入すると、パフォーマンスが5%以上簡単に向上する可能性があります。コンパイラはこれを簡単に利用できません。 これは、通常、分岐予測とキャッシュ動作の組み合わせですが、たとえば、リザベーションステーションの停止(たとえ壊れている、または明白なリソースの過剰購読であっても依存チェーンがない場合でも)です。


速度改善の最も可能性の高い原因は次のとおりです。

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

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

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

ブランチの誤予測がパフォーマンスにどのように影響するかを理解したい場合は、この優れた答えを見てhttps://.com/a/11227902/1001643 : https://.com/a/11227902/1001643 : https://.com/a/11227902/1001643

コンパイラには、通常、エイリアスとエイリアスが重要であるかどうかを知るための十分な情報がありません。 ただし、その情報は、 CachegrindVTuneなどのツールを使用して実行時に決定することができます。