はじめに

これまで下記の記事で GNU C ライブラリの qsort について勉強してきた。

GNU C ライブラリの qsort はマージソートであり，再帰関数（トップダウン型）として作られていることから，非再帰型（ボトムアップ型）に書き直すことでパフォーマンスアップを狙ったが，期待したほどの効果（劇的な効果）を得られなかった。

そもそも明確な利点があったら GNU C ライブラリで採用しているだろうから，非再帰型（ボトムアップ型）には他に何か致命的な欠陥？があるのではないかと思うようになったのが前回の記事である。

だがしかし，先日，パフォーマンスアップを期待できるアイディアを思いついたのだ。

改善案

部屋の模様替えを行うとき，部屋が狭いわりに大きな家具や荷物が多いといろいろ悩ましい。まず，移動先の空きスペースを確保しないといけないし，かつての倉庫番ゲームのように動かす順番を考えないといけないからだ。こういうとき隣の部屋が空いていたりするととても便利である。ある日，ふと思いついたのだ。いっそのこと隣の空き部屋に家具を全部持って行ってそこに住んでしまえばいいんじゃねと？

マージソートでも同様だ。マージソートでは基本的にソート対象となる配列と同サイズの作業用エリアを必要とする。二つの区間をマージする際，いったん作業用エリア上でマージして，それから元の配列に書き戻しているのだが，わざわざ書き戻さなくても良くないか？つまり，作業用エリアをそのまま使ってしまい，今度は元の配列の領域を作業用として使おうというアイディアだ。こうして二つのエリアを交互に作業用として使えば，データ転送量を約半分に済ませられるはず。

ちなみにこのアイディアは非再帰型（ボトムアップ型）マージソートでないと成立しない。

実装コード

とても簡単にできたので全容を示そう。

merge4（ボトムアップ型・データ転送節約版）

/* 001 */ #include <stdlib.h>
/* 002 */ typedef int     (*COMPARE)(int, int);
/* 003 */ #define TEMP_SIZE   256
/* 004 */ static  void    swap(int *p, int *q) {
/* 005 */     int temp = *p;
/* 006 */     *p = *q;
/* 007 */     *q = temp;
/* 008 */ }
/* 009 */ static  void    merge(int *buf, int *a, int n1, int n2, COMPARE compare) {
/* 010 */     int *p1 = a;
/* 011 */     int *p2 = a + n1;
/* 012 */     int *q = buf;
/* 013 */     for(;;) {
/* 014 */         if(compare(*p1, *p2) <= 0) {
/* 015 */             *q++ = *p1++; if(--n1 == 0) break;
/* 016 */         } else {
/* 017 */             *q++ = *p2++; if(--n2 == 0) break;
/* 018 */         }
/* 019 */     }
/* 020 */     while(n1 > 0) {
/* 021 */         *q++ = *p1++; n1--;
/* 022 */     }
/* 023 */     while(n2 > 0) {
/* 024 */         *q++ = *p2++; n2--;
/* 025 */     }
/* 026 */ }
/* 027 */ static  void    sort(int *buf, int *a, int len, COMPARE compare) {
/* 028 */     for(int i = 0; i + 1 < len; i += 2)
/* 029 */         if(compare(a[i], a[i + 1]) > 0) swap(&a[i], &a[i + 1]);
/* 030 */     int *x = a;
/* 031 */     int *y = buf;
/* 032 */     for(int s = 2; s < len; s = s * 2) {
/* 033 */         int i, adj;
/* 034 */         for(i = 0; i + s * 2 < len; i += s * 2)
/* 035 */             merge(&y[i], &x[i], s, s, compare);
/* 036 */         if((adj = len - (i + s)) > 0)
/* 037 */             merge(&y[i], &x[i], s, adj, compare);
/* 038 */         else
/* 039 */             for(; i < len; i++) y[i] = x[i];
/* 040 */         int *temp = x; x = y; y = temp;
/* 041 */     }
/* 042 */     if(x != a)
/* 043 */         for(int i = 0; i < len; i++) a[i] = x[i];
/* 044 */ }
/* 045 */ void    msort4(int *a, int len, COMPARE compare) {
/* 046 */     if(len < 2) return;
/* 047 */     if(len <= TEMP_SIZE) {
/* 048 */         int tmp[TEMP_SIZE];
/* 049 */         sort(tmp, a, len, compare);
/* 050 */     } else {
/* 051 */         int *buf = (int*)malloc(sizeof(int) * len);
/* 052 */         if(buf == (int*)NULL) return;
/* 053 */         sort(buf, a, len, compare);
/* 054 */         free(buf);
/* 055 */     }
/* 056 */ }
/* 057 */

アルゴリズム解説

それでは自作コードを頭から解説していきたい。同じ非再帰型（ボトムアップ型）マージソートと比べれば実装の違いがよく分かると思う。

マージソートを非再帰型に書き直す～誰でも思いつくアイディアだが～ - Qiita

1. 交換関数

交換関数 swap は全く同じである。

2. ソート関数本体

ソート関数本体である。関数名のみ異なり，あとは全く同じである。

3. マージソートエンジン

マージソートエンジンである。領域の大きさが１の場合の処理は同じである。隣接する要素の大小を比較して入れ替えれば良いので，交換関数 swap の呼び出しで済ませている。

領域の大きさ s が２以上になると本実装の特徴が表れる。元の配列 a[] と作業用エリア buf[] を直接参照せず，読出し側が x，書き込み側が y とポインタによる間接参照にして，マージを一段実行する毎にポインタ x と y を交換しているのだ。

他に注意事項としては以下の二つ。

末尾にある未結合要素も忘れずにコピーする必要がある
最後に元の配列 a[] に書き戻すことを忘れないこと

4. マージ関数

マージ関数も少し違う。作業用エリア buf[] に書き込むのみで元の配列 a[] に書き戻さない。

比較回数・転送回数の比較

試験条件は下記の通りである。

200,000,000 個の 32bit 整数を昇順ソートする。
データの順序は以下の四種類である。
- ゼロ（すべて同値）
- 昇順：0 → 199,999,999
- 降順：199,999,999 → 0
- 乱数：0～199,999,999 の範囲で一様乱数（重複あり）
乱数発生器は XorShift である。
比較対象のソートアルゴリズムは以下の四つとする。
- uCRT：クイックソート
- glibc：再帰型マージソート
- merge：非再帰型マージソート
- merge4：非再帰型マージソート・データ転送節約版　※今回作成したもの

表１　比較回数の比較（単位は回）
順序	uCRT	glibc	merge	merge4
ゼロ	399,999,999	2,728,894,208	2,804,304,128	2,804,304,128
昇順	5,363,792,412	2,728,894,208	2,804,304,128	2,804,304,128
降順	5,363,792,412	2,802,670,336	2,728,894,208	2,728,894,208
乱数	6,400,427,154	5,265,836,886	5,280,310,523	5,280,310,523

表２　転送回数の比較（単位は回）
順序	uCRT	glibc	merge	merge4
ゼロ	0	5,457,788,416	5,408,608,256	5,600,000,000
昇順	265,782,274	5,457,788,416	5,408,608,256	5,600,000,000
降順	465,782,278	11,063,129,088	10,866,396,672	5,800,000,000
乱数	2,736,238,624	10,752,119,342	10,613,478,548	5,700,000,344

今回作成した merge4 について，比較回数は merge（非再帰型マージソート）と全く変わらない。一方，データ転送回数について，ゼロや昇順などソートする必要がないデータについては微増となっているが，降順と乱数についてはほぼ半減していることが分かる。これは実行時間に期待できそうだ。

■uCRT，■glibc，■merge，■merge4

実行時間の比較

試験条件を以下に示す。

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

試験結果を以下に示す。

表３　実行時間の比較（単位は秒）
コンパイラ	順序	uCRT	glibc	merge	merge4
Visual C++ 32bit版	ゼロ	0.090	2.660	2.835	3.796

	昇順	1.433	2.656	2.848	3.797

	降順	1.475	3.914	4.668	3.752

	乱数	15.505	17.996	19.431	17.495
Visual C++ 64bit版	ゼロ	0.093	2.470	2.158	2.984

	昇順	1.582	2.473	2.148	2.961

	降順	1.617	3.769	3.370	2.927

	乱数	15.500	21.129	20.050	18.346
LLVM clang-cl 32bit版	ゼロ	0.098	2.066	2.095	3.729

	昇順	1.627	2.060	2.109	3.415

	降順	1.688	3.642	3.015	3.393

	乱数	15.636	16.487	15.981	17.146
LLVM clang-cl 64bit版	ゼロ	0.089	1.958	1.679	2.259

	昇順	1.460	1.997	1.663	2.262

	降順	1.523	2.942	2.456	2.240

	乱数	15.710	16.022	15.853	15.296
intel icx-cl 32bit版	ゼロ	0.070	2.488	2.038	2.971

	昇順	1.592	2.498	2.050	2.973

	降順	1.691	3.333	2.877	2.643

	乱数	17.120	17.809	17.767	16.481
intel icx-cl 64bit版	ゼロ	0.064	1.811	1.621	2.049

	昇順	1.366	1.797	1.608	2.046

	降順	1.491	2.507	2.418	2.074

	乱数	16.584	15.969	15.682	15.010

グラフにすると分かり易い。

■uCRT，■glibc，■merge，■merge4

結論

配列のデータが全てゼロや昇順のようなソート済みの特殊データについては比較回数・転送回数ともにほとんど変わらないにも関わらず，実行時間は微増となっている。
降順や乱数のようにデータを入れ替える必要があるものについては，ほとんどのコンパイラで（LLVM clang-cl 32bit 版を除いて）高速化を実現できている。
LLVM clang-cl 32bit 版でパフォーマンスが上がらなかった点については謎である。おそらくループアンローリングや関数のインライン展開などの最適化を積極的に行ったが，汎用レジスタの少ない x86 アーキテクチャでは逆効果だったと推察している。