C++でソート済み配列の処理が未ソート配列より速い理由とは？ブランチ予測の仕組みを解説

C++において、ソートされた配列はソートされていない配列よりも高速に処理できます。その理由は「ブランチ予測（分岐予測）」にあります。

コンピュータアーキテクチャにおけるブランチ予測とは、プログラムの命令フロー内にある条件分岐（ジャンプ）が実行されるかどうかを、CPUが事前に推測する仕組みのことです。この予測が当たればパイプライン処理が中断されずに済み、処理速度が大きく向上します。

具体例で見てみよう

以下のようなコードを考えてみます。

if(arr[i] > 50) {
   操作Bを実行
} else {
   操作Aを実行
}

このコードを、ソート済みの配列と未ソートの配列に対してそれぞれ100個の要素で実行すると、次のような違いが現れます。

ソート済み配列の場合

1,2,3,4,5,……50,51………100
A,A,A,A,A A,B B

データが昇順に並んでいるため、最初の50個までは一貫して条件が偽となり操作Aが続きます。CPUはこのパターンを学習し、正しい分岐をパイプラインに読み込み続けることができます。つまり、「A,A,A,…,B,B」という規則性のあるシーケンスになるため、ブランチ予測がほぼ完璧に機能し、高速な処理が可能になります。

未ソート配列の場合

5,51,6,90,4,49,60…
A,B,A,B,A,A,A,B

一方、ソートされていない配列では、条件式の結果が「真・偽」と不規則に入り混じります。操作AとBのどちらが実行されるかを予測することが極めて難しく、ブランチ予測はほとんど役に立ちません。予測が外れるたびにパイプラインのフラッシュが発生し、大幅な性能低下につながります。

まとめ

同じ計算量のコードでも、データの並び順によって実行速度が数倍変わることがあります。これはアルゴリズムの問題ではなく、CPUのハードウェアレベルでの最適化（ブランチ予測）によるものです。条件分岐が多い処理を行う場合は、データを事前にソートしておくことでパフォーマンスを改善できるケースがあることを覚えておきましょう。