概要

クイックソートは一般に高速なソートアルゴリズムとして知られています。アルゴリズム中にはピボットを選択する部分がありますが、ここでなるべく中央値に近い値を選択すると、総比較回数を少なくすることができます。しかし、最近の高性能プロセッサは投機実行するため、比較回数ではなく分岐予測ミスの回数が性能に大きく影響します。ピボットとして中央値ではなく四分位数を選択する場合、比較回数が23%増加するものの、分岐予測ミス回数を38%削減し、ソートにかかる時間を20%削減できることが分かりました。

はじめに

去年の末、kimiyukiさん（kimiyuki@うさぎ🐇 (@kimiyuki_u) | Twitter）に「クイックソートのピボットとして中央値ではない値を選んだほうが、分岐予測ミス率が減って高速なのでは」という話をいただきました。その時私は、「分岐予測ミス率を減らせても、トータルの仕事量が増えてしまって意味がないのでは」と怪しんでいましたが、実際に実験してみると高速化することがわかりました。

以下では、高速化する原因を、モデルを用いて明らかにします。

実際に計測に用いたコード（ピボットをオラクル的に選択できるように改造したクイックソート）は以下です。

#include <array>
#include <utility>

std::array<double, 10000000> arr;

void q_sort( double* begin, double* end, double begin_v, double end_v ) {
        if( end - begin <= 1 ) { return; }

        const double pivot = begin_v*0.75 + end_v*0.25;

        double* p = begin;
        double* q = end;

        for( ; ; ) {
                while( p < q && *p < pivot ) ++p;
                do --q; while( p < q && *q > pivot );
                if( p >= q ) break;
                std::swap( *p, *q );
                ++p;
        }

        q_sort( begin, p, begin_v, pivot );
        q_sort( p, end, pivot, end_v );
}

#include <random>

int main() {
        std::mt19937 mt;
        std::uniform_real_distribution<double> dist(1.0, 2.0);
        for( auto& e : arr ) {
                e = dist(mt);
        }
        q_sort( arr.begin(), arr.end(), 1.0, 2.0 );
}

モデル化

理論

N要素に対するソートアルゴリズムは、N!通りある入力に対して1通りの出力を返すので、エントロピーを $\log_2(N!)$ ビット下げる必要があります。

クイックソートでは、ピボットとして中央値を選んだ場合、一回の分岐命令で1ビットのエントロピーを下げることができます。一般に、ピボットとしてp:(1-p)に内分する点を選んだ場合、一回の分岐命令で $H(p) = - p\log_2(p) - (1-p)\log_2(1-p)$ ビットのエントロピーを下げることができます。

よって、ピボットとしてp:(1-p)に内分する点を選んだ場合、 $\log_2(N!) / H(p)$ 回の比較が少なくとも必要です*1。

また、ソートを行うためには比較した後に分岐する必要がありますが、この分岐の飛び先には規則性がありません。分岐予測器は、単に確率の高いほうに分岐するだろうと予測するしかなく、実際にそのように動作すると考えてよいです。この場合の分岐予測成功確率は、 $\max(p, 1-p)$ となります。

よって、ピボットとしてp:(1-p)に内分する点を選んだ場合、分岐予測ミスは、 $\max(p, 1-p) \times \log_2(N!) / H(p)$ 回発生することになります。

プロセッサのパラメータ

Intel社のSkylakeマイクロアーキテクチャでは、分岐予測ミスペナルティがおおよそ 20 cycle です。また、このコードの場合、ミスがなかった場合と比べて追加で 9 cycle 損します。これは、パイプラインがフラッシュされ、メモリアクセス（5 cycle）と浮動小数点数比較（4 cycle）がやり直しになるためです。

分岐予測ミスが発生しない場合、比較にかかる時間*2は 1 cycle です。

また、実測値を使うと、end - begin > 1の時の関数呼び出しのオーバーヘッドは、約 50 cycle でした。

クイックソートにかかる時間

ソートが完了するまでにかかる時間は、ピボット選択位置pをパラメータとして、

分岐予測ミスペナルティ 29 cycle × $\max(p, 1-p) \times \log_2(N!) / H(p)$ 回
比較コスト 1 cycle × $\log_2(N!) / H(p)$ 回
関数呼び出しコスト 50 cycle × $\log_2(N) / H(p)$ 回

の和としてモデル化できます。

その結果、p=0.2～0.25付近で最小値を取ることがわかります。

定性的な説明

ピボットとして中央値を選択すると、分岐予測ミス確率は50%です。分岐一回で減らせるエントロピーは、1ビットです。よって、分岐予測ミス一回当たりで減らせるエントロピーは、2ビットです。

一方、ピボットとして四分位数を選択した場合、分岐予測ミス確率は25%です。分岐一回で減らせるエントロピーは、0.811ビットです。よって、分岐予測ミス一回当たりで減らせるエントロピーは、3.2ビットです。

このように、減らせるエントロピーが小さくなる（＝トータルの仕事量が多くなってしまう）効果よりも、分岐予測ミス確率が減る効果のほうがはるかに大きいです。

一般に、偏ったピボットをとるほど、一回の分岐予測ミスで減らせるエントロピーは大きくなります。

比較コストや関数呼び出しコストより分岐予測ミスペナルティのほうが十分大きい領域（0.2<p<0.8）においては、なるべく偏ったピボットを選択したほうが効率的です。

ただし、ピボットとしてあまりに偏った値を選択すると、比較コストや関数呼び出しコストが支配的となり、かえって低速になります。

おわりに

クイックソートのピボットは中央値を選ぶのが、比較回数が最小となるため望ましいというのが定説でした。実際に中央値を選択するのは難しいですが、複数のピボット候補の中央値を選択することでなるべく中央値に近いと思われるピボットを選択する手法が一般に用いられています。

しかし、分岐予測ミスペナルティが非常に大きな近年の高性能プロセッサの場合、中央値に近い値をピボットとして選択するのは、かえって悪手である可能性があることがわかりました。複数のピボット候補からピボットを選択する手法も、今後は見直す必要がありそうです。

*1:再帰呼び出し終端付近では無駄な比較が多発するため、約1.2倍の比較が実行されるようです

*2:正確にはスループット

よーる

クイックソートのピボットは中央値でなく四分位数を選択したほうが高速

概要