[解決済み】x86_64アセンブリで無駄なMOV命令を導入すると、なぜタイトループが速くなるのでしょうか?
質問
背景は?
を最適化したところ
パスカル
のコードをアセンブリ言語で埋め込んだところ、不要な
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 .
関連
-
[解決済み] なぜベクトル化、ループよりも一般的に速いのですか?
-
[解決済み】2つの範囲が重なっているかどうかをテストする最も効率的な方法は何ですか?
-
[解決済み】JSFがゲッターを複数回呼び出す理由
-
[解決済み】Goはどうしてそんなに早くコンパイルできるのですか?
-
[解決済み】長さnのソートされていない配列の中でk番目に大きい要素をO(n)で見つけるにはどうすればよいですか?)
-
[解決済み】GHCコアの読み込み
-
[解決済み] gccのffast-mathは実際に何をするのですか?
-
[解決済み] Apache Spark: map vs mapPartitions?
-
[解決済み] x86アセンブリでレジスタをゼロに設定するには、xor、mov、andのどれが一番良い方法ですか?
-
[解決済み] TeamViewerはどうしてこんなに速いのですか?
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み] なぜベクトル化、ループよりも一般的に速いのですか?
-
[解決済み] apacheサーバーがMaxClientsの設定に達したので、MaxClientsの設定を上げることを検討してください。
-
[解決済み】-depth 1でcloneを浅くし、コミットを作成し、再び更新をpullするのは安全ですか?
-
[解決済み】x86_64アセンブリで無駄なMOV命令を導入すると、なぜタイトループが速くなるのでしょうか?
-
[解決済み] gccのffast-mathは実際に何をするのですか?
-
[解決済み] 与えられた数の除数の数を計算するアルゴリズム
-
[解決済み] SSLはどれくらいのオーバーヘッドを発生させるのですか?
-
[解決済み] 32ビットレジスタに対するx86-64命令は、なぜフル64ビットレジスタの上部をゼロにするのですか?
-
[解決済み】2次元の点がポリゴン内にあるかどうかを判断するにはどうしたらいいですか?
-
[解決済み] memcachedはRedisに比べれば恐竜のようなもの?[クローズド]