はじめに
筆者の下記の記事では，.NET Framework の Array.Sort の謎の動作に悩まされた。
.NET Framework の Array.Sort では，差がゼロとなることが分かり切っているにも関わらず，同じ要素同士の比較を行う場合があるのだ。これが .NET Framework の欠陥なのか，あるいはこのほうが効率良いからなのかは分からなかった。
.NET Framework 4.8 の Array.Sort のソースコード
ソースコードは下記のサイトで公開されているので誰でも勉強できる。
Array.cs (.NET Framework 4.8) - microsoft.com
だがしかし，長過ぎて筆者の読解力を超えている。
.NET Framework のアルゴリズムを探る
ということで，ソースコードを読まずに外部入力に対する応答から凡そのアルゴリズムを探ってみたところ，.NET Framework 3.5 時代の Array.Sort は純粋なクイックソートのみで構成され，比較的簡素なつくりをしているものと推察された。
.NET Framework 3.5 の Array.Sort の意訳版を作る
ということで試行錯誤すること数カ月・・・ようやく .NET Framework 3.5 時代の Array.Sort と同じ動きをするものをC言語で作ることができた。非常にコンパクトにまとまっているのでコード全文を紹介しよう。
/* 001 */ typedef int (*COMPARE)(int, int);
/* 002 */ static void swap(int *p, int *q) {
/* 003 */ int temp = *p;
/* 004 */ *p = *q;
/* 005 */ *q = temp;
/* 006 */ }
/* 007 */ static void sort(int *a, int top, int end, COMPARE compare) {
/* 008 */ do {
/* 009 */ int mid = top + (end - top) / 2;
/* 010 */ if(top != mid && compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
/* 011 */ if(top != end && compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
/* 012 */ if(mid != end && compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
/* 013 */ int pivot = a[mid];
/* 014 */ int t = top;
/* 015 */ int e = end;
/* 016 */ do {
/* 017 */ while(compare(a[t], pivot) < 0) t++;
/* 018 */ while(compare(pivot, a[e]) < 0) e--;
/* 019 */ if(t > e) break;
/* 020 */ if(t < e) swap(&a[t], &a[e]);
/* 021 */ t++;
/* 022 */ e--;
/* 023 */ } while(t <= e);
/* 024 */ if(e - top <= end - t) {
/* 025 */ if(top < e) sort(a, top, e, compare);
/* 026 */ top = t;
/* 027 */ } else {
/* 028 */ if(t < end) sort(a, t, end, compare);
/* 029 */ end = e;
/* 030 */ }
/* 031 */ } while(top < end);
/* 032 */ }
/* 033 */ void qsort_net(int *a, int len, COMPARE compare) {
/* 034 */ if(len < 2) return;
/* 035 */ sort(a, 0, len - 1, compare);
/* 036 */ }
アルゴリズム解説
それでは意訳コードを頭から解説していきたい。同じクイックソートである uCRT 版と比べれば実装の違いがよく分かると思う。
1. 交換関数
まずは交換関数 swap() だが，uCRT 版と全く同じである。
2. ソート関数冒頭部
ソート関数本体 qsort_net() である。引数は uCRT 版に合わせた。配列の要素数 len が２個未満のときは何もしないでリターンするところも同じである。
ただし，uCRT 版では再帰呼び出しのオーバーヘッドを嫌い，内部スタックを用意して goto 文によるループ処理で済ませていたが，.NET Framework 3.5 版では普通に再帰関数 sort() を呼び出すように作った。
3. 小型ソート
uCRT 版では分割された区間の要素数が８個以下になるとアルゴリズムを切り換えて選択ソートを実行するが，.NET Framework 3.5 版では切り換えない。
4. ピボット選択
クイックソートではピボットの選択が重要である。たまたま選んだピボット値が最大値または最小値であった場合，クイックソートの効率は最悪になってしまうからだ。これを避けるため先頭と末尾と中間の三点でサンプリングして，その中で最大値でも最小値でもない中央値をピボットに選ぶようにしている。
uCRT 版と .NET Framework 3.5 版では，この中間サンプリングの位置が微妙に異なっている。uCRT 版の場合 n = end - top + 1 であるから，n が偶数のとき，中間サンプリングの位置が一つずれることになる。ただし，性能には全く影響しないだろう。
また，uCRT 版の場合，要素数 n が８個より大きいので，中間サンプリングの位置 mid は先頭 top とも末尾 end とも重なることはないが，.NET Framework 3.5 版の場合，要素数が２個になると重なってしまう。このため同値と比較しないように工夫しているものと考える。
4. ピボットを基準とした交換処理
ピボットを基準として，これより小さな値は配列の先頭へ，大きな値は配列の末尾のほうへ集めていく。クイックソートは外部メモリを必要としない内部ソートであり，配列の先頭からピボットより小さな値を検索する一方，配列の末尾からピボットより大きな検索し，これらを交換することで実現している。ここで uCRT 版と .NET Framework 3.5 版で微妙な差がある。
-
uCRT 版では配列の先頭から検索する
tはピボットの位置midをスキップするようにループが二分割されている。これは同値とわざわざ比較しないような配慮である。一方 .NET Framework 3.5 版ではこのような配慮を行っていないことから，同値と比較してしまうことが避けられない。つまり .NET Framework 3.5 版では比較関数の無駄な呼び出しを行っているが，その分プログラムの構造は少しだけシンプルになっており，これがパフォーマンスにどのような影響を与えるのか興味深いところである。 -
uCRT 版では配列の先頭から検索する変数
tは前置インクリメント演算子があるのでtop + 1から検索を開始する。同様に配列の末尾から検索するeもend - 1から検索を開始する。これは配列の先頭の値a[top]および末尾の値a[end]はピボット選択処理においてピボットの値a[mid]と既に比較が終わっており，比較を省略可能だからだ。一方，.NET Framework 3.5 版では律儀にtはtopから，eはendから検索する。 -
.NET Framework 3.5 版ではピボットの値を変数
pivotにセットすることで，繰り返しピボット値を参照するアクセスを減らしている。そもそも標準ライブラリqsort()の仕様では，比較関数に比較対象となる二つの要素のポインタを与えるため，このようなことは出来ないのだ。逆にこのような実装を可能とするため，今回の一連の記事では比較関数の引数をポインタではなく整数値そのものとした。ここだけは .NET Framework 3.5 版が uCRT 版に対して明らかにパフォーマンス上有利な点である。
6. 三分割処理
三分割処理とは正式な名称ではなく，筆者が独自に呼んでいるものである。uCRT 版ではピボットと隣接して同値が連続している場合，その区間を再帰処理の対象から外す。この結果，同値が多いデータ（極端な例だと全て同じ値）の場合，uCRT 版では極めて高速にソートを完了することができる。.NET Framework 3.5 版には該当する処理はない。
※詳しくは配列のデータがすべてゼロの結果を見て欲しい。
7. 再帰処理
ピボットを基準として [top, e] と [t, end] の区間に分割したが，このうち狭いほうを優先して再帰処理に回す。これは広いほうを優先するとスタックが溢れてしまう危険があるからだ。なお，等号が成立したときの挙動が uCRT 版と異なっている。
uCRT 版では再帰関数の呼び出しを行わず，内部スタックに積んでいる。内部スタックに積むのは後回しにするという意味である。
比較回数・転送回数の比較
それでは uCRT 版と .NET Framework 3.5 版で比較回数・転送回数の比較を行ってみよう。試験条件は下記の通りである。
- 200,000,000 個の 32bit 整数を昇順ソートする。
- データの順序は以下の四種類である。
- ゼロ（すべて同値）
- 昇順：0 → 199,999,999
- 降順：199,999,999 → 0
- 乱数：0～199,999,999 の範囲で一様乱数（重複あり）
- 乱数発生器は XorShift である。
試験結果は下記の通りである。
| 順序 | uCRT | .NET |
|---|---|---|
| ゼロ | 399,999,999 | 5,675,718,141 |
| 昇順 | 5,363,792,412 | 5,730,237,980 |
| 降順 | 5,363,792,412 | 5,730,238,009 |
| 乱数 | 6,400,427,154 | 6,916,900,788 |
| 順序 | uCRT | .NET |
|---|---|---|
| ゼロ | 0 | 5,208,609,280 |
| 昇順 | 265,782,274 | 0 |
| 降順 | 465,782,278 | 200,000,004 |
| 乱数 | 2,736,238,624 | 2,770,781,196 |
こういうのはグラフにすると一目瞭然である。比較関数の呼び出し回数は uCRT 版のほうが全般的に少ないことが分かる。一方，.NET Framework 3.5 版ではゼロのときのデータ転送回数が乱数のときの約２倍になっている。
■uCRT，■.NET
実行時間の比較
試験条件を以下に示す。
- 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 | .NET |
|---|---|---|---|
| Visual C++ 32bit版 |
ゼロ | 0.090 | 1.891 |
| 昇順 | 1.433 | 1.262 | |
| 降順 | 1.475 | 1.275 | |
| 乱数 | 15.505 | 14.986 | |
| LLVM clang-cl 32bit版 |
ゼロ | 0.098 | 2.129 |
| 昇順 | 1.627 | 1.425 | |
| 降順 | 1.688 | 1.461 | |
| 乱数 | 15.636 | 14.389 | |
| intel icx-cl 32bit版 |
ゼロ | 0.070 | 2.255 |
| 昇順 | 1.592 | 1.435 | |
| 降順 | 1.691 | 1.464 | |
| 乱数 | 17.120 | 14.694 |
| コンパイラ | 順序 | uCRT | .NET |
|---|---|---|---|
| Visual C++ 64bit版 |
ゼロ | 0.093 | 2.187 |
| 昇順 | 1.582 | 1.589 | |
| 降順 | 1.617 | 1.607 | |
| 乱数 | 15.500 | 15.562 | |
| LLVM clang-cl 64bit版 |
ゼロ | 0.089 | 2.334 |
| 昇順 | 1.460 | 1.338 | |
| 降順 | 1.523 | 1.381 | |
| 乱数 | 15.710 | 14.703 | |
| intel icx-cl 64bit版 |
ゼロ | 0.064 | 2.388 |
| 昇順 | 1.366 | 1.536 | |
| 降順 | 1.491 | 1.580 | |
| 乱数 | 16.584 | 15.106 |
グラフにすると分かり易い。
■uCRT，■.NET
結論
データが全てゼロのような特殊ケースを除き（これは uCRT 版では専用の処理があるためで仕方ないところであるが）ほぼ全てのコンパイラにおいて .NET Framework 3.5 版は uCRT 版に勝っているのだ。
ということで，筆者の記事「uCRT の qsort のソースを読む - Qiita」において，uCRT 版の qsort() を評して
よく出来ている。芸術品である・・・と，この記事を書いた当時はそう思っていた。
と述べていたが，ようやく今回の記事で伏線を回収できる。uCRT 版の qsort() はあれこれと技巧を凝らしたコードのように見えても，それは開発当時には効果があったのかもしれないが，現代のプロセッサおよびコンパイラにおいてはあまり効果がなくなっていたのだ。