はじめに
これまで下記の記事で GNU C ライブラリの qsort について勉強してきた。
- GNU C Libraryのqsortはクイックソートではないの？ - Qiita
- 最強コンパイラを使えばマージソートは遅くない？ - Qiita
- マージソートを非再帰型に書き直す～誰でも思いつくアイディアだが～ - Qiita
- マージソートを非再帰型に書き直す２～さらなる改善を試みる～ - Qiita
GNU C ライブラリの qsort はマージソートであり，再帰関数（トップダウン型）として作られていることから，非再帰型（ボトムアップ型）に書き直すことでパフォーマンスアップを狙ったが，期待したほどの効果（劇的な効果）を得られなかった。
そもそも明確な利点があったら GNU C ライブラリで採用しているだろうから，非再帰型（ボトムアップ型）には他に何か致命的な欠陥？があるのではないかと思うようになった。
ボトムアップ型の課題その３
それは配列のサイズ $n$ に対して，計算量（比較回数）が不連続に変化してしまうことだと思われる。glibc のような再帰型（トップダウン型）のマージソートは計算量（比較回数）が綺麗に $O(n \log n)$ の直線上に乗るが，非再帰型（ボトムアップ型）のマージソートは $n$ が２のべき乗数のときのみ直線上に乗り，そこから $n$ が少し増えると直線から外れて急増してしまうのだ。
まずは一例を示そう。乱数データにおいて，再帰型と非再帰型のマージソートの比較関数の呼び出し回数の比較を以下に示す。配列のサイズ $n$ が２のべき乗のとき両者は一致しているが，そこから $n$ が僅かに増加すると非再帰型のほうは急増する。
| サイズ $n$ | ①再帰型 | ②非再帰型 | ②／① |
|---|---|---|---|
| 256 | 1,710 | 1,710 | 1.000 |
| 260 | 1,745 | 1,948 | 1.116 |
| 512 | 3,955 | 3,955 | 1.000 |
| 516 | 3,989 | 4,460 | 1.118 |
| 1,024 | 8,919 | 8,919 | 1.000 |
| 1,028 | 8,969 | 9,347 | 1.042 |
| 2,048 | 19,934 | 19,934 | 1.000 |
| 2,052 | 19,996 | 21,443 | 1.072 |
| 4,096 | 43,949 | 43,949 | 1.000 |
| 4,100 | 43,986 | 47,095 | 1.071 |
| 8,192 | 96,168 | 96,168 | 1.000 |
| 8,196 | 96,298 | 101,899 | 1.058 |
| 16,384 | 208,716 | 208,716 | 1.000 |
| 16,388 | 208,768 | 220,389 | 1.056 |
| 32,768 | 450,090 | 450,090 | 1.000 |
| 32,772 | 450,157 | 468,945 | 1.042 |
| 65,536 | 965,855 | 965,855 | 1.000 |
| 65,540 | 965,664 | 997,836 | 1.033 |
| 131,072 | 2,062,821 | 2,062,821 | 1.000 |
| 131,076 | 2,062,428 | 2,193,463 | 1.064 |
| 262,144 | 4,387,074 | 4,387,074 | 1.000 |
| 262,148 | 4,387,229 | 4,612,494 | 1.051 |
| 524,288 | 9,299,238 | 9,299,238 | 1.000 |
| 524,292 | 9,298,853 | 9,696,633 | 1.043 |
| 1,048,576 | 19,645,708 | 19,645,708 | 1.000 |
| 1,048,580 | 19,646,474 | 20,621,315 | 1.050 |
| 2,097,152 | 41,387,613 | 41,387,613 | 1.000 |
| 2,097,156 | 41,387,497 | 43,459,509 | 1.050 |
| 4,194,304 | 86,970,643 | 86,970,643 | 1.000 |
| 4,194,308 | 86,970,926 | 88,560,546 | 1.018 |
| 8,388,608 | 182,330,408 | 182,330,408 | 1.000 |
| 8,388,612 | 182,329,368 | 187,365,121 | 1.028 |
| 16,777,216 | 381,440,754 | 381,440,754 | 1.000 |
| 16,777,220 | 381,441,160 | 395,497,500 | 1.037 |
| 33,554,432 | 796,435,814 | 796,435,814 | 1.000 |
| 33,554,436 | 796,435,082 | 827,538,527 | 1.039 |
| 67,108,864 | 1,659,965,763 | 1,659,965,763 | 1.000 |
| 67,108,868 | 1,659,973,267 | 1,714,466,532 | 1.033 |
| 134,217,728 | 3,454,152,093 | 3,454,152,093 | 1.000 |
| 134,217,732 | 3,454,152,216 | 3,577,340,295 | 1.036 |
こういうのはグラフにすると分かり易い。※ e は envelope のことね。
◆②／①，■包絡線 $e(n)$
非再帰型と再帰型の呼び出し回数の比（②／①）の包絡線 $e(n)$ は配列のサイズ $n$ に対して
e(n) \approx \frac{\log_2{n} + 1}{\log_2{n}}
になると考えられる。メカニズムは簡単で，配列のサイズ $n$ が２のべき乗数であれば，ボトムアップ型マージソートはちょうど $n$ 個のデータのマージを $\log_2{n}$ 段繰り返せば終わる。計算量が $O(n \log n)$ になるというのも分かり易い。 しかし，$n$ が一つ増えただけでマージする段数は一つ増えてしまうのだ。
一方，トップダウン型の場合，配列のサイズ $n$ が一つ増えてもマージする段数が増えるのは一部の区間のみであり，全体には影響を及ぼさない。
実測するとどうなるか？
試験条件
- int 型の配列の昇順ソートを行う。配列のサイズは① 2²⁷ 個と② 2²⁷ + 2 個，③ 2²⁷ + 2² 個の三種類とし，実行時間の変化率②／①，③／①を比較する。
- 配列は乱数で初期化する。乱数発生器は XorShift とした。
- Cコンパイラは下記の三種類とし，かつターゲットを 32bit (x86)と64bit (x64)の二種類の組み合わせで合計六種類とする。
- Microsoft Visual C++ 2022
- LLVM clang 17.0.3
- intel C++ compiler：oneAPI 2024.2, Compiler Release 2024.2.1
- 評価マシンのスペックは下記の通り。
Windows10 2022H2，Core i7-13700 5.1GHZ，32GB - 対象の比較関数は以下の通り。
- glibc：再帰型（トップダウン型）マージソート，GNU C ライブラリの
qsortの意訳版 - merge：非再帰型（ボトムアップ型）マージソート，
未結合要素は末尾 - merge2：非再帰型（ボトムアップ型）マージソート，
未結合要素は先頭（バックワード型）※今回作成 - merge3：非再帰型（ボトムアップ型）マージソート，
未結合要素は先頭（フォワード型）※今回作成
- glibc：再帰型（トップダウン型）マージソート，GNU C ライブラリの
試験結果
試験結果を以下に示す。なお，測定のたびに実行時間は揺らぐため，同一条件で五回測定し，その最小値を示す。
| コンパイラ | 要素数 | glibc | merge | merge2 | merge3 |
|---|---|---|---|---|---|
| Visual C++ 32bit版 |
① 2²⁷ | 11.859 | 12.808 | 13.143 | 11.462 |
| ② 2²⁷ + 2 | 11.872 | 13.020 | 13.183 | 11.553 | |
| ③ 2²⁷ + 2² | 11.862 | 13.040 | 13.247 | 11.625 | |
| Visual C++ 64bit版 |
① 2²⁷ | 13.943 | 13.268 | 13.316 | 13.255 |
| ② 2²⁷ + 2 | 13.915 | 13.351 | 13.371 | 13.294 | |
| ③ 2²⁷ + 2² | 13.910 | 13.362 | 13.388 | 13.359 | |
| LLVM clang-cl 32bit版 |
① 2²⁷ | 10.764 | 10.554 | 10.721 | 10.498 |
| ② 2²⁷ + 2 | 10.769 | 10.683 | 10.802 | 10.579 | |
| ③ 2²⁷ + 2² | 10.787 | 10.674 | 10.875 | 10.639 | |
| LLVM clang-cl 64bit版 |
① 2²⁷ | 10.487 | 10.471 | 10.529 | 10.247 |
| ② 2²⁷ + 2 | 10.500 | 10.587 | 10.598 | 10.312 | |
| ③ 2²⁷ + 2² | 10.502 | 10.584 | 10.652 | 10.339 | |
| intel icx-cl 32bit版 |
① 2²⁷ | 11.629 | 11.714 | 11.279 | 11.620 |
| ② 2²⁷ + 2 | 11.666 | 11.846 | 11.416 | 11.739 | |
| ③ 2²⁷ + 2² | 11.664 | 11.889 | 11.374 | 11.719 | |
| intel icx-cl 64bit版 |
① 2²⁷ | 10.474 | 10.364 | 10.224 | 10.364 |
| ② 2²⁷ + 2 | 10.483 | 10.417 | 10.278 | 10.434 | |
| ③ 2²⁷ + 2² | 10.506 | 10.440 | 10.311 | 10.437 |
| コンパイラ | 要素数 | glibc | merge | merge2 | merge3 |
|---|---|---|---|---|---|
| Visual C++ 32bit版 |
②／① | 1.0011 | 1.0166 | 1.0030 | 1.0079 |
| ③／① | 1.0003 | 1.0181 | 1.0079 | 1.0142 | |
| Visual C++ 64bit版 |
②／① | 0.9980 | 1.0063 | 1.0041 | 1.0029 |
| ③／① | 0.9976 | 1.0071 | 1.0054 | 1.0078 | |
| LLVM clang-cl 32bit版 |
②／① | 1.0005 | 1.0122 | 1.0076 | 1.0077 |
| ③／① | 1.0021 | 1.0114 | 1.0144 | 1.0134 | |
| LLVM clang-cl 64bit版 |
②／① | 1.0012 | 1.0111 | 1.0066 | 1.0063 |
| ③／① | 1.0014 | 1.0108 | 1.0117 | 1.0090 | |
| intel icx-cl 32bit版 |
②／① | 1.0032 | 1.0113 | 1.0121 | 1.0102 |
| ③／① | 1.0030 | 1.0149 | 1.0084 | 1.0085 | |
| intel icx-cl 64bit版 |
②／① | 1.0009 | 1.0051 | 1.0053 | 1.0068 |
| ③／① | 1.0031 | 1.0073 | 1.0085 | 1.0070 |
こういうのはグラフにすると一目瞭然である。glibc は予想通り，要素数の変化に対して実行時間の変化が最小である。
■glibc，■merge，■merge2，■merge3
結論
理論的と言うか簡易的な見積もり（包絡線）では計算量の増加は 3.9% であったが，非再帰型（ボトムアップ型）マージソートとして実装した三種類のいずれとも実行時間の増加はせいぜい 2% に抑えられている。
とはいえ，これは今回精度よく計億できるように配列の要素数を $2^{27}$ と巨大な値に設定したからであり，実際にはもっと小さなサイズで用いられることが多いだろう。たとえば配列の要素数が $2^{10}$ 程度では，２のべき乗数から外れると 10% を超える計算量の増加が予測されており，実際の実行時間の増加が半分の 5% 程度だとしても，非再帰型による改善効果（関数呼び出しのオーバーヘッド低減）を打ち消してしまうだろう。
以上より，GNU C ライブラリの開発者は qsort の実装として非再帰型（ボトムアップ型）マージソートを採用しないのではないかと考えている。