ソートされた配列の処理が、ソートされていない配列の処理よりも速いのはなぜですか？

あなたは分岐予測の失敗の犠牲者です。
分岐予測とは何ですか？
鉄道のジャンクションについて考えてみましょう。
ウィキメディアコモンズ経由のMecanismoによる画像。 CC-By-SA3.0ライセンスの下で使用されます。
議論のために、これが1800年代に戻ったと仮定します-長距離または無線通信の前に。
あなたはジャンクションの運営者であり、電車が来るのが聞こえます。あなたはそれがどちらの方向に進むべきか見当がつかない。あなたは電車を止めて、運転手にどちらの方向を望むか尋ねます。そして、スイッチを適切に設定します。
電車は重くて慣性が大きいです。そのため、起動と速度低下に永遠に時間がかかります。
もっと良い方法はありますか？あなたは電車がどちらの方向に行くかを推測します！
あなたが正しく推測した場合、それは続きます。
あなたが間違っていると推測した場合、船長は停止し、後退し、スイッチを切り替えるようにあなたに怒鳴ります。その後、他のパスから再起動できます。
毎回正しく推測すれば、電車は止まる必要はありません。よく間違えると、列車は停車、バックアップ、再起動に多くの時間を費やします。
ifステートメントについて考えてみます。プロセッサレベルでは、これは分岐命令です。
あなたはプロセッサであり、ブランチが表示されます。あなたはそれがどちらの方向に進むのか分かりません。職業はなんですか？実行を停止し、前の命令が完了するまで待ちます。次に、正しいパスを続行します。
最新のプロセッサは複雑で、パイプラインが長くなっています。したがって、彼らは「ウォームアップ」と「スローダウン」に永遠にかかります。
もっと良い方法はありますか？あなたは枝がどちらの方向に行くかを推測します！
あなたが正しく推測した場合、あなたは実行を続けます。
推測が間違っている場合は、パイプラインをフラッシュしてブランチにロールバックする必要があります。その後、他のパスから再開できます。
毎回正しく推測すれば、実行を停止する必要はありません。推測が多すぎると、ストール、ロールバック、再起動に多くの時間を費やします。
これが分岐予測です。列車は旗で方向を知らせることができるので、それは最良の例えではないことを認めます。しかし、コンピュータでは、プロセッサは最後の瞬間までブランチがどちらの方向に進むかを知りません。
では、列車が後退して他の経路を下る必要がある回数を最小限に抑えるために、どのように戦略的に推測しますか？あなたは過去の歴史を見ます！列車が99％の時間左に行く場合、あなたは左だと思います。それが交互になる場合、あなたはあなたの推測を交互にします。それが3回ごとに一方向に進む場合、あなたは同じことを推測します...
言い換えれば、あなたはパターンを特定し、それに従うことを試みます。これは多かれ少なかれ分岐予測子のしくみです。
ほとんどのアプリケーションには、正常に動作するブランチがあります。したがって、最新の分岐予測子は通常、90％を超えるヒット率を達成します。しかし、認識可能なパターンのない予測不可能な分岐に直面した場合、分岐予測子は事実上役に立ちません。
さらに読む：ウィキペディアの「分岐予測」の記事。
上から示唆されているように、原因は次のifステートメントです。
if（data [c]> = 128）
合計+ =データ[c];
データが0から255の間で均等に分散されていることに注意してください。データが並べ替えられると、反復のほぼ前半はifステートメントに入りません。その後、それらはすべてifステートメントに入ります。
分岐は何度も同じ方向に連続して進むため、これは分岐予測に非常に適しています。単純な飽和カウンターでも、方向を切り替えた後の数回の反復を除いて、ブランチを正しく予測します。
迅速な視覚化：
T =分岐した
N =分岐は行われません
data [] = 0、1、2、3、4、... 126、127、128、129、130、... 250、251、252、..。
ブランチ= N N N N N ... N N T T T ... T T T..。
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT（予測が容易）
ただし、データが完全にランダムである場合、分岐予測子はランダムデータを予測できないため、役に立たなくなります。したがって、おそらく約50％の誤予測があります（ランダムな推測に勝るものはありません）。
data [] = 226、185、125、158、198、144、217、79、202、118、14、150、177、182、133、..。
ブランチ= T、T、N、T、T、T、T、N、T、N、N、T、T、T、N .. ..
= TTNTTTTNTNNTTTN ...（完全にランダム-予測が難しい）
では、何ができるでしょうか？
コンパイラーがブランチを条件付き移動に最適化できない場合、パフォーマンスのために読みやすさを犠牲にしても構わないと思っているなら、いくつかのハックを試すことができます。
交換：
if（data [c]> = 128）
合計+ =データ[c];
と：
int t =（data [c] -128）>> 31;
合計+ = 〜t＆data [c];
これにより、分岐が削除され、ビット単位の演算に置き換えられます。
（このハックは、元のifステートメントと厳密に同等ではないことに注意してください。ただし、この場合、data []のすべての入力値に対して有効です。）
ベンチマーク：Core i7 920 @ 3.5 GHz
C ++-Visual Studio2010-x64リリース
//ブランチ-ランダム
秒= 11.777
//ブランチ-ソート済み
秒= 2.352
//ブランチレス-ランダム
秒= 2.564
//ブランチレス-ソート済み
秒= 2.587
Java-NetBeans 7.1.1 JDK 7-x64
//ブランチ-ランダム
秒= 10.93293813
//ブランチ-ソート済み
秒= 5.643797077
//ブランチレス-ランダム
秒= 3.113581453
//ブランチレス-ソート済み
秒= 3.186068823
観察：
ブランチあり：ソートされたデータとソートされていないデータには大きな違いがあります。
ハックの場合：ソートされたデータとソートされていないデータに違いはありません。
C ++の場合、データがソートされると、ハッキングは実際にはブランチよりも少し遅くなります。
一般的な経験則は、重要なループ（この例のように）でのデータ依存の分岐を回避することです。
更新：
x64で-O3または-ftree-vectorizeを指定したGCC4.6.1は、条件付き移動を生成できます。したがって、ソートされたデータとソートされていないデータの間に違いはありません。どちらも高速です。
（またはやや速い：すでにソートされている場合、特にGCCが単に追加するのではなくクリティカルパスに配置した場合、特にcmovに2サイクルのレイテンシがあるBroadwellより前のIntelでは、cmovが遅くなる可能性があります：gcc最適化フラグ-O3はコードを遅くします-O2より）
VC ++ 2010は、/ Oxの下でも、このブランチの条件付き移動を生成できません。
インテルC ++コンパイラー（ICC）11は、奇跡的なことをします。 2つのループを交換し、予測できない分岐を外側のループに巻き上げます。したがって、予測ミスの影響を受けないだけでなく、VC ++およびGCCが生成できるものの2倍の速度もあります。言い換えれば、ICCはテストループを利用してベンチマークを打ち負かしました...
インテル®コンパイラーにブランチレス・コードを与えると、それは完全にベクトル化されます...そしてブランチと同じくらい高速です（ループ交換あり）。
これは、成熟した最新のコンパイラでさえ、コードを最適化する能力が大きく異なる可能性があることを示しています...
|
分岐予測。
ソートされた配列では、条件data [c]> = 128は、値のストリークに対して最初にfalseになり、その後のすべての値に対してtrueになります。それは簡単に予測できます。ソートされていない配列では、分岐コストを支払います。
|
Mysticialの回答で美しく説明されているように、データを並べ替えるとパフォーマンスが大幅に向上する理由は、分岐予測のペナルティが削除されるためです。
さて、コードを見ると
if（data [c]> = 128）
合計+ =データ[c];
この特定のif ... else ...ブランチの意味は、条件が満たされたときに何かを追加することであることがわかります。このタイプのブランチは、条件付き移動ステートメントに簡単に変換できます。これは、x86システムで条件付き移動命令cmovlにコンパイルされます。分岐、したがって潜在的な分岐予測ペナルティが削除されます。
C、つまりC ++では、x86の条件付き移動命令に（最適化なしで）直接コンパイルされるステートメントは、三項演算子です...？ ...：....したがって、上記のステートメントを同等のステートメントに書き直します。
合計+ = data [c]> = 128？ data [c]：0;
読みやすさを維持しながら、スピードアップファクターを確認できます。
Intel Core i7-2600K @ 3.4GHzおよびVisualStudio 2010リリースモードでは、ベンチマークは次のとおりです（Mysticialからコピーされた形式）。
x86
//ブランチ-ランダム
秒= 8.885
//ブランチ-ソート済み
秒= 1.528
//ブランチレス-ランダム
秒= 3.716
//ブランチレス-ソート済み
秒= 3.71
x64
//ブランチ-ランダム
秒= 11.302
//ブランチ-ソート済み
秒= 1.830
//ブランチレス-ランダム
秒= 2.736
//ブランチレス-ソート済み
秒= 2.737
結果は、複数のテストで堅牢です。分岐の結果が予測できない場合は大幅に高速化されますが、予測可能な場合は少し苦労します。実際、条件付き移動を使用する場合、パフォーマンスはデータパターンに関係なく同じです。
それでは、それらが生成するx86アセンブリを調査して、さらに詳しく見ていきましょう。簡単にするために、2つの関数max1とmax2を使用します。
max1は、次の場合に条件分岐を使用します... else ...：
int max1（int a、int b）{
if（a> b）
を返す;
そうしないと
bを返す;
}
max2は三項演算子を使用しています...？ ...：...：
int max2（int a、int b）{
a> bを返しますか？ a：b;
}
x86-64マシンでは、GCC-Sは以下のアセンブリを生成します。
：max1
movl％edi、-4（％rbp）
movl％esi、-8（％rbp）
movl -4（％rbp）、％eax
cmpl -8（％rbp）、％eax
jle .L2
movl -4（％rbp）、％eax
movl％eax、-12（％rbp）
jmp .L4
.L2：
movl -8（％rbp）、％eax
movl％eax、-12（％rbp）
.L4：
movl -12（％rbp）、％eax
去る
ret
：max2
movl％edi、-4（％rbp）
movl％esi、-8（％rbp）
movl -4（％rbp）、％eax
cmpl％eax、-8（％rbp）
cmovge -8（％rbp）、％eax
去る
ret
max2は、命令cmovgeを使用するため、使用するコードがはるかに少なくなります。ただし、実際の利点は、max2にブランチジャンプjmpが含まれていないことです。これは、予測された結果が正しくない場合、パフォーマンスが大幅に低下します。
では、なぜ条件付き移動のパフォーマンスが向上するのでしょうか。
一般的なx86プロセッサでは、命令の実行はいくつかの段階に分けられます。大まかに言って、さまざまな段階を処理するためのさまざまなハードウェアがあります。したがって、新しい命令を開始するために1つの命令が終了するのを待つ必要はありません。これはパイプラインと呼ばれます。
分岐の場合、次の命令は前の命令によって決定されるため、パイプライン化はできません。待つか予測する必要があります。
条件付き移動の場合、実行条件付き移動命令はいくつかの段階に分かれていますが、フェッチやデコードなどの初期の段階は前の命令の結果に依存しません。後の段階だけが結果を必要とします。したがって、1つの命令の実行時間のほんの一部を待ちます。これが、予測が容易な場合に条件付き移動バージョンがブランチよりも遅い理由です。
『Computer Systems：A Programmer's Perspective』の第2版では、これについて詳しく説明しています。条件付き移動命令についてはセクション3.6.6、プロセッサアーキテクチャについては第4章全体、分岐予測と誤予測のペナルティの特別な扱いについてはセクション5.11.2を確認できます。
最近のコンパイラの中には、コードを最適化してパフォーマンスを向上させることができるものもあれば、できないものもあります（問題のコードはVisual Studioのネイティブコンパイラを使用しています）。予測できない場合のブランチと条件付き移動のパフォーマンスの違いを知ることは、シナリオが非常に複雑になり、コンパイラーがそれらを自動的に最適化できない場合に、パフォーマンスの高いコードを作成するのに役立ちます。
|
このコードに対して実行できるさらに多くの最適化について知りたい場合は、次のことを検討してください。
元のループから開始します。
for（unsigned i = 0; i <100000; ++ i）
{{
for（unsigned j = 0; j  = 128）
合計+ =データ[j];
}
}
ループ交換を使用すると、このループを次のように安全に変更できます。
for（unsigned j = 0; j  = 128）
合計+ =データ[j];
}
}
次に、iループの実行中、if条件が一定であることがわかります。したがって、ifoutを上げることができます。
for（unsigned j = 0; j  = 128）
{{
for（unsigned i = 0; i <100000; ++ i）
{{
合計+ =データ[j];
}
}
}
次に、浮動小数点モデルで許可されていると仮定すると、内側のループを1つの式に折りたたむことができることがわかります（たとえば、/ fp：fastがスローされます）。
for（unsigned j = 0; j  = 128）
{{
合計+ = data [j] * 100000;
}
}
それは以前より10万倍速いです。
|
間違いなく、CPUの分岐予測に問題のあるコードを特定する方法に興味を持つ人もいるでしょう。 Valgrindツールのcachegrindには、-branch-sim = yesフラグを使用して有効化される分岐予測シミュレーターがあります。外側のループの数を10000に減らし、g ++でコンパイルして、この質問の例で実行すると、次の結果が得られます。
並べ替え：
== 32551 ==ブランチ：656,645,130（656,609,208 cond + 35,922 ind）
== 32551 ==誤予測：169,556（169,095 cond + 461 ind）
== 32551 ==誤解率：0.0％（0.0％+ 1.2％）
未分類：
== 32555 ==ブランチ：655,996,082（655,960,160 cond + 35,922 ind）
== 32555 ==誤予測：164,073,152（164,072,692 cond + 460 ind）
== 32555 ==誤解率：25.0％（25.0％+ 1.2％）
問題のループで見られるcg_annotateによって生成された行ごとの出力にドリルダウンします。
並べ替え：
BcBcmビビン
10,001 4 0 0 for（unsigned i = 0; i <10000; ++ i）
。 。 。 。 {{
。 。 。 。 //プライマリループ
327,690,000 10,016 0 0 for（unsigned c = 0; c  = 128）
0 0 00合計+ =データ[c];
。 。 。 。 }
。 。 。 。 }
未分類：
BcBcmビビン
10,001 4 0 0 for（unsigned i = 0; i <10000; ++ i）
。 。 。 。 {{
。 。 。 。 //プライマリループ
327,690,000 10,038 0 0 for（unsigned c = 0; c  = 128）
0 0 00合計+ =データ[c];
。 。 。 。 }
。 。 。 。 }
これにより、問題のある行を簡単に特定できます。並べ替えられていないバージョンでは、if（data [c]> = 128）行がcachegrindの分岐予測モデルで164,050,007の誤って予測された条件分岐（Bcm）を引き起こしていますが、並べ替えられたバージョンでは10,006しか発生していません。 。
または、Linuxでは、パフォーマンスカウンターサブシステムを使用して同じタスクを実行できますが、CPUカウンターを使用したネイティブパフォーマンスを使用します。
perf stat ./sumtest_sorted
並べ替え：
'./sumtest_sorted'のパフォーマンスカウンター統計：
11808.095776タスククロック＃0.998CPU使用率
1,062コンテキストスイッチ＃0.090K /秒
14 CPU移行＃0.001K /秒
337ページフォールト＃0.029K /秒
26,487,882,764サイクル＃2.243 GHz
41,025,654,322命令＃1サイクルあたり1.55イン
6,558,871,379ブランチ＃555.455M /秒
567,204ブランチ-すべてのブランチの＃0.01％が欠落しています
11.827228330秒の経過時間
未分類：
パフォーマンス'./sumtest_unsorted'のカウンター統計：
28877.954344タスククロック＃0.998CPU使用率
2,584コンテキストスイッチ＃0.089K /秒
18 CPU移行＃0.001K /秒
335ページフォールト＃0.012K /秒
65,076,127,595サイクル＃2.253 GHz
41,032,528,741命令＃1サイクルあたり0.63 insns
6,560,579,013ブランチ＃227.183M /秒
1,646,394,749ブランチ-すべてのブランチの＃25.10％が欠落しています
28.935500947秒経過
また、分解してソースコードの注釈を付けることもできます。
perf record -e branch-misss ./sumtest_unsorted
perf annotate -d sumtest_unsorted
パーセント| sumtest_unsortedのソースコードと逆アセンブル
------------------------------------------------
..。
：合計+ =データ[c];
0.00：400a1a：mov -0x14（％rbp）、％eax
39.97：400a1d：mov％eax、％eax
5.31：400a1f：mov -0x20040（％rbp、％rax、4）、％eax
4.60：400a26：cltq
0.00：400a28：％raxを追加、-0x30（％rbp）
..。
詳細については、パフォーマンスチュートリアルを参照してください。
|
この質問とその答えを読んだところ、答えが欠けているように感じます。
マネージド言語で特にうまく機能することがわかった分岐予測を排除する一般的な方法は、分岐を使用する代わりにテーブルルックアップです（この場合はテストしていませんが）。
このアプローチは、一般的に次の場合に機能します。
これは小さなテーブルであり、プロセッサにキャッシュされる可能性があります。
非常にタイトなループで物事を実行しているか、プロセッサがデータをプリロードできます。
背景とその理由
プロセッサの観点からは、メモリは低速です。速度の違いを補うために、いくつかのキャッシュがプロセッサに組み込まれています（L1 / L2キャッシュ）。だから、あなたがあなたの素晴らしい計算をしていると想像して、あなたがメモリの一部を必要としていることを理解してください。プロセッサは「ロード」操作を取得し、メモリの一部をキャッシュにロードします。その後、キャッシュを使用して残りの計算を実行します。メモリは比較的遅いので、この「ロード」はプログラムの速度を低下させます。
分岐予測と同様に、これはPentiumプロセッサで最適化されました。プロセッサは、データの一部をロードする必要があると予測し、操作が実際にキャッシュに到達する前に、それをキャッシュにロードしようとします。すでに見てきたように、分岐予測がひどく間違っていることがあります-最悪のシナリオでは、戻って実際にメモリのロードを待つ必要があります。これには永遠に時間がかかります（言い換えると、分岐予測の失敗は悪いです、メモリ分岐予測が失敗した後のロードはひどいです！）。
幸いなことに、メモリアクセスパターンが予測可能な場合、プロセッサはそれを高速キャッシュにロードし、すべてが順調です。
私たちが最初に知る必要があるのは、何が小さいのかということです。一般的には小さい方が良いですが、経験則では、サイズが4096バイト以下のルックアップテーブルに固執することです。上限として：ルックアップテーブルが64Kより大きい場合は、おそらく再検討する価値があります。
テーブルの作成
これで、小さなテーブルを作成できることがわかりました。次に行うことは、ルックアップ関数を配置することです。ルックアップ関数は通常、いくつかの基本的な整数演算（および、または、xor、shift、add、remove、およびおそらく乗算）を使用する小さな関数です。ルックアップ関数によって入力をテーブル内のある種の「一意のキー」に変換する必要があります。これにより、実行したいすべての作業の答えが得られます。
この場合：> = 128は値を保持できることを意味し、<128は値を削除することを意味します。これを行う最も簡単な方法は、「AND」を使用することです。それを保持する場合は、7FFFFFFFでANDします。それを取り除きたい場合は、0とANDします。128は2の累乗であることに注意してください。つまり、32768/128整数のテーブルを作成し、1つのゼロと多数の整数で埋めることができます。 7FFFFFFFFの。
管理言語
なぜこれが管理された言語でうまく機能するのか不思議に思うかもしれません。結局のところ、マネージド言語は、ブランチを使用して配列の境界をチェックし、混乱しないようにします...
まあ、正確には... :-)
管理言語のこのブランチを削除するためのかなりの作業がありました。例えば：
for（int i = 0; i  = 128）？ c：0;
}
//テスト
DateTime startTime = System.DateTime.Now;
長い合計= 0;
for（int i = 0; i <100000; ++ i）
{{
//プライマリループ
for（int j = 0; j  v（1'000'000）;
iota（v.begin（）、v.end（）、0）;
run（v、 "すでにソートされています"）;
std :: shuffle（v.begin（）、v.end（）、std :: mt19937 {std :: random_device {}（）}）;
run（v、 "シャッフル"）;
}
少なくともこの現象は、このコンパイラ、標準ライブラリ、およびオプティマイザの設定では現実的です。実装が異なれば、答えも異なります。実際、誰かがより体系的な調査を行い（すばやくWeb検索するとそれが見つかります）、ほとんどの実装でその効果が示されています。
理由の1つは、分岐予測です。ソートアルゴリズムの主要な操作は、「if（v [i] > 7）;
a [j] + =データ[c];
}
}
doublelapsedTime = static_cast （clock（）-start）/ CLOCKS_PER_SEC;
合計= a [1];
このコードは追加の半分を無駄にしますが、分岐予測の失敗はありません。ランダムデータでは、実際のifステートメントを使用したバージョンよりも非常に高速です。
しかし、私のテストでは、明示的なルックアップテーブルはこれよりもわずかに高速でした。おそらく、ルックアップテーブルへのインデックス作成がビットシフトよりもわずかに高速だったためです。これは、私のコードがルックアップテーブル（コード内の「ルックアップテーブル」の場合は想像を絶するほどにlutと呼ばれます）を設定して使用する方法を示しています。 C ++コードは次のとおりです。
//ルックアップテーブルを宣言してから入力します
int lut [256];
for（unsigned c = 0; c <256; ++ c）
lut [c] =（c> = 128）？ c：0;
//ビルド後にルックアップテーブルを使用します
for（unsigned i = 0; i <100000; ++ i）
{{
//プライマリループ
for（unsigned c = 0; c  value）
node = node-> pLeft;
そうしないと
node = node-> pRight;
このライブラリは次のようになります。
i =（x <ノード->値）;
node = node-> link [i];
それは素晴らしい解決策であり、多分それはうまくいくでしょう。
|
非常に活発な質問。この質問に答えるために10の評判を獲得してください。レピュテーション要件は、この質問をスパムや無回答のアクティビティから保護するのに役立ちます。
あなたが探している答えではありませんか？ java c ++パフォーマンス最適化分岐予測のタグが付けられた他の質問を参照するか、独自の質問をしてください。