for (i=0; i<N; i++)
for (j=0; j<N - (i+1); j++)
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
第2の実施形態では、内側のループは配列の別の部分を通過しますが、アルゴリズム的には、このオプションは最初のオプションと同等です（詳細は以下）。
for (i=0; i<N-1; i++)
for (j=i; j>=0; j--)
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
たとえば、intの配列でN = 100,000の場合、実行（ code ）すると、最初のケースで約30秒、2番目で10秒未満、つまり3倍の差が得られます。 では、この違いはどこから来たのでしょうか？
まず、コンパイラーの最適化の問題ではないことを確認します。 これは、どちらの場合でもアセンブラコードを生成および比較することで簡単に検証できます。 または、最適化をオフにすることができます。 または、アセンブラでコードを書き換えることができます（たとえば、アセンブラの挿入を使用）。 いずれにしても、効果は保持されます。
次に、両方のオプションが同等であることを確認する方法は？ たとえば、比較した値a [j]、a [j + 1]および対応する値jを表示し、結果のリストを並べ替えて、行ごとに比較できます（もちろん、小さいNでこれを行うのが妥当です）。 リストは同じであることがわかります。つまり、どちらの場合も同じ比較と同じ割り当てが実行され、違いはこれらの操作が実行される順序のみです。
はい、一部の人は言うでしょうが、時間が操作の順序に依存する場合、他の例を知っています。 たとえば、同じデータを読み取ったとしても、メモリへの順次アクセスとランダムアクセスには違いがあります。 この場合、メモリへのアクセスはかなり長いプロセスであり、プロセッサは数百の命令を実行できる時点でほとんどアイドル状態です。 ただし、シーケンシャルアクセスでは、これらの遅延は、大量のデータがすぐにコピーされるプロセッサキャッシュと、はるかに高速なアクセスにより償却されます。
しかし、私たちの場合、データ量はそれほど大きくないことに注意してください-100'000 intはたった400Kbですが、最新のプロセッサにはメガバイト以上のL2キャッシュがあります。 さらに、どちらの場合も、配列の要素に順番にアクセスするため、メモリアクセス遅延は再び償却されます。 最後に、Nを減らすと、同じ差が3回観測されます。 したがって、キャッシュはここで役割を果たしますが、観察された効果の主な理由ではありません。
何が起こっているのかを理解し、前のステートメントを確認するために、プロセッサカウンターを使用して両方のオプションを分析します。 これらのカウンターは、実行された命令の数、キャッシュアクセス、分岐イベントの数、および他の多くのパラメーターをカウントします。 測定値を取得するために、Intelを使用しました（試用版-はい、無料サービスを待たずに、グーグルで検索しないでください！）VTuneパフォーマンスアナライザーですが、他の方法もあります。 開始して分析し、出力を取得します（P4 Prescott、L1 16Kb、L2 2Mb、最初のオプションと2番目のオプション）：
完了した手順：40対 35（10 9 ）
L2キャッシュミス：1.1 vs. 1.8（10 9 ）
L1キャッシュミス：1.6 vs. 0.4（・10 6 ）
では、ここから何が続くのでしょうか？ 第一に、命令ごとに第1レベルのキャッシュでミスが非常に少ないため、対応する遅延はそれほど重要ではありません。 第二に、2番目のレベルのキャッシュにはまだかなり多くのミスがありますが、2番目のバリアントではミスが最初のキャッシュよりも頻繁に発生することがわかります。 他のプロセッサでの結果はわずかに異なる場合があります（特に、私のプロセッサ上にないL3キャッシュがある場合もあります）が、全体像はほぼ同じままになると思います。
したがって、キャッシュについてではありません。 しかし、追加の分析結果を見てください：
遷移（ブランチ）の数：1.0 vs. 1.0（10 10 ）
分岐予測エラー： 0.16 vs. 0.00009 （10 10 ）
私が最近までそうだったように、 分岐予測子のような興味深いものに慣れていない人のための小さな余談（奇妙なことに、ハブに関するトピックを見つけられませんでした）。
おそらく、最近のプロセッサは、 命令パイプラインのために、1つの命令を連続して実行するのではなく、複数の命令を並列に実行し、結果を結合することを知っています。 ただし、この例のように、命令のシーケンスは条件付き遷移の結果に依存する場合があります。a[j]> a [j + 1]の場合、要素は再配置されます。 ここで、遷移予測子が救助に来て、彼は遷移が完了するかどうかを推測しようとし、これに従って、パイプラインの命令が選択されます。
遷移予測子は静的および動的にすることができます。 ダイナミックは、以前の遷移の履歴に基づいて遷移を予測しようとします。 このストーリーがまだ入力されていない場合は、静的予測子が使用されますが、このケースでは重要ではありません。 静的および動的な予測子のトピックについては、 この記事 （英語）が気に入りましたが、実際には、もちろんすべてがより複雑です。
遷移予測子とそのエラーはどれほど重要ですか？ ウィキペディアによると、最新のプロセッサでは、遅延は数十クロックサイクルであり、それ自体
for (i=0; i<T; i++)
for (j=0; j<M; j++)
if (p[j]) ++;
ここで、p []は条件付きでジャンプするかどうかを決定する配列であり、カウンターは単にこれら2つのイベントを区別する役割を果たします。 すべてのp [j]値が同じ場合、数回の反復後、遷移はすでに十分に予測可能です。 p [j]が何らかの方法で、たとえば周期的に生成される場合、遷移の予測可能性は予測子の実装に依存します。 しかし、誤って配列がいっぱいになると、特定の制限の下で次の遷移を予測することはできません。 配列Mのサイズは重要であることに注意してください-配列が大きすぎる場合、キャッシュが不適切になり、小さすぎる場合、遷移を予測できます。
私のコンピューターでは、このコードの実行時間は、配列を満たすランダム性の度合いに応じて4〜6回変化します。 配列の要素を再配置するなど、カウンタを増やすよりも複雑な操作を実行すると、差は小さくなりますが、それほど大きくはなりません。 したがって、遷移予測エラーの有無によって、実行時間に数倍の差が生じる可能性がありますが、これは元の問題で見られます。
上記の分析結果によると、最初のバージョンのソートでは、予測エラーはケースの16％で発生し、2番目のケースでは-1000倍少ない。 これはなぜですか？ これは、両方のケースでソートがどのように発生するかを考慮することで理解できます。
最初のケースでは、小さいiの場合、jに沿った内部サイクルは、ソートされた「テール」のみに触れることなく、配列のほぼ終わりまで実行されます。 最初、配列のこの部分のデータは乱れているため、条件a [j]> a [j + 1]はほとんど偶然に満たされます。 iが増加すると、順列に起因する要素の順序付けがある程度行われますが、それでもランダム性の大部分が残ります（ アニメーション ）。 したがって、遷移を予測することはかなり困難であり、多くの予測エラーが発生します。
2番目の場合、i = 0の場合、内側のループは[0]と[1]のみをソートし、i = 1の場合は[2]を追加します。 実際、これは挿入 （ただしバイナリではない） によるソートです 。i番目のステップで、要素a [i + 1]が既にソートされたサブ配列a [0..i]（ アニメーション ）に挿入されます。 要素はサブ配列の末尾から挿入されるため、ほとんどの場合、この要素は配列内の必要な位置に順次移動され、条件p [j]> p [j + 1]の値は到達する前に同じになります。 したがって、数回の反復の後、遷移は簡単に予測でき、遷移予測子は非常に満足しているように見えます。
