.NET (Framework) のArray.Sortのアルゴリズムを探る

はじめに

これまでソート関数について勉強してきた。

• uCRT の qsort のソースを読む - Qiita
• GNU C Libraryのqsortはクイックソートではないの？ - Qiita
• 最強コンパイラを使えばマージソートは遅くない？ - Qiita
• マージソートを非再帰型に書き直す～誰でも思いつくアイディアだが～ - Qiita
• マージソートを非再帰型に書き直す２～さらなる改善を試みる～ - Qiita
• マージソートを非再帰型に書き直す３～もう限界かもしれない～ - Qiita
• マージソートを非再帰型に書き直す４～限界突破のアイディアを思いつく～ - Qiita

しかしながら，そもそもは .NET (Framework) の Array.Sort の謎が発端である。

• 数万個のファイルの重複チェックを行うプログラムをC#でささっと作る２～コメント欄で指導されて作り直す - Qiita
• 数万個のファイルの重複チェックを行うプログラムをC#でささっと作る３～.NETのArray.Sortの謎に挑む - Qiita

本命は .NET (Framework) の Array.Sort でありながら，一見回り道をしてきたのは理由がある。単純に Array.Sort のソースコードが巨大すぎて筆者の理解能力を超えているからだ。

表１　ソート関数のソースコード比較

	ファイル名	ステップ数	ファイルサイズ
uCRT	qsort.cpp	396行	12,904 bytes
GNU C library	qsort.c	407行	10,507 bytes
.NET Framework 4.8	array.cs	3083行	137,701 bytes
.NET	array.cs	2578行	107,786 bytes

各ソースコードは以下を参照した。

• qsort.cpp - uCRT
  Visual Studio 2022 Community Edition をインストールすると下記フォルダにあるはず。
  C:\Program Files (x86)\Windows Kits\10\Source\10.0.26100.0\ucrt\stdlib\qsort.cpp
• GNU C Library 2.41 stdlib/qsort.c - glibc.git
• Array.cs - .NET Framework 4.8
• Array.cs (.NET Platform) - github

テストコード

ということで，まずはソースコードについては触れず，外部からデータを与えて挙動を見ることにした。XorShift による乱数配列を 20～200,000,000 個の範囲で与え，これを昇順ソートさせたときの比較関数の呼び出し回数をカウントする。

比較対象は下記の四つとする。

表２　比較対象

言語	関数	プラットフォーム
C	qsort	uCRT
C#	Array.Sort	.NET Framework 3.5
		.NET Framework 4.8
		.NET 8.0

C言語版テストコード

C 言語版のテストコードを以下に示す。

test.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
uint32_t	xorshift(void) {
static	uint64_t	x = 1;
	x ^= x << 13;
	x ^= x >>  7;
	x ^= x << 17;
	return (uint32_t)x;
}
static	uint64_t	count = 0;
static	int		compare(int *p, int *q) {
	count++;
	return *p - *q;
}
int	main(int argc, char *argv[]) {
	if(argc < 3) {
		fprintf(stderr, "Usage: test(.exe) [z/a/d/r] [size]\n");
		return -1;
	}
	int	size = atoi(argv[2]);
	int	*table = malloc(sizeof(int) * size);
	if(table == (int*)NULL) {
		fprintf(stderr, "cannot allocate size: %d\n", size);
		return -1;
	}
	switch(argv[1][0]) {
	  case 'Z': case 'z':	/* ZERO */
		for(int i = 0; i < size; i++) table[i] = 0;
		break;
	  case 'A': case 'a':	/* ASCEND */
		for(int i = 0; i < size; i++) table[i] = i;
		break;
	  case 'D': case 'd':	/* DESCEND */
		for(int i = 0; i < size; i++) table[i] = size - i - 1;
		break;
	  case 'R': case 'r':	/* RANDOM */
		for(int i = 0; i < size; i++) table[i] = xorshift() % size;
		break;
	  default:
		fprintf(stderr, "illegal command: %s\n", argv[1]);
		return -1;
	}
	qsort(table, size, sizeof(int), (int(*)(const void*, const void*))compare);
	fprintf(stdout, "%lld\n", count);
	return 0;
}

C#版

C# 版のテストコードを以下に示す。.NET Framework 3.5 or 4.8 および .NET 8.0 のソースコードは共通である。

test.cs

using System;
using System.IO;
class XorShift {
	private	ulong	x = 1;
	public	XorShift() {}
	public	XorShift(ulong s) {x = s;}
	public	uint	Next() {
		x ^= x << 13;
		x ^= x >>  7;
		x ^= x << 17;
		return (uint)x;
	}
}
class TEST {
	static	int	Main(string[] args) {
		if(args.Length < 2) {
			Console.Error.WriteLine("Usage: test(.exe) [z/a/d/r] [size]");
			return -1;
		}
		var	size = int.Parse(args[1]);
		var	table = new int[size];
		switch(args[0][0]) {
		  case 'Z': case 'z':	/* ZERO */
			for(int i = 0; i < size; i++) table[i] = 0;
			break;
		  case 'A': case 'a':	/* ASCEND */
			for(int i = 0; i < size; i++) table[i] = i;
			break;
		  case 'D': case 'd':	/* DESCEND */
			for(int i = 0; i < size; i++) table[i] = size - i - 1;
			break;
		  case 'R': case 'r':	/* RANDOM */
			var	r = new XorShift();
			for(int i = 0; i < size; i++) table[i] = (int)(r.Next() % size);
			break;
		  default:
			return -1;
		}
		ulong	count = 0;
		Comparison<int> compare = delegate(int a, int b) {
			count++;
			return a - b;
		};
		Array.Sort(table, compare);
		Console.Out.WriteLine(count);
		return 0;
	}
}

ビルド手順

Visual C++ の場合

Visual Studio 2022 Community Edition だと下記の通り。

cl /O2 /W4 test.c

.NET Framework 3.5 の場合

下記のバッチファイルを実行する。人によっては .NET Framework 3.5 をインストールする必要があるかもしれない。

net35.cmd

@echo off
setlocal
for /F "usebackq tokens=1,2,*" %%I in (
  `reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v3.5" /v InstallPath`
) do (
  if "%%I"=="InstallPath" set "DOTNETPATH=%%K"
)
if "%DOTNETPATH:~-1%"=="\" set "DOTNETPATH=%DOTNETPATH:~0,-1%"
set "PATH=%PATH%;%DOTNETPATH%"
if not exist NET35 mkdir NET35
csc -o -w:4 -out:NET35\test.exe test.cs
endlocal
exit /b

.NET Framework 4.8 の場合

下記のバッチファイルを実行する。

net48.cmd

@echo off
setlocal
for /F "usebackq tokens=1,2,*" %%I in (
  `reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v4\Full" /v InstallPath`
) do (
  if "%%I"=="InstallPath" set "DOTNETPATH=%%K"
)
if "%DOTNETPATH:~-1%"=="\" set "DOTNETPATH=%DOTNETPATH:~0,-1%"
set "PATH=%PATH%;%DOTNETPATH%"
if not exist NET48 mkdir NET48
csc -o -w:4 -out:NET48\test.exe test.cs
endlocal
exit /b

.NET 8.0 の場合

Visual Studio 2022 Community Edition をインストールしている人は .NET 8.0 が使えるはず。コマンドプロンプト（またはターミナル）で下記のコマンドを実行する。

dotnet build -c Release

ソースコード test.cs と同じフォルダに下記のプロジェクトファイル test.csproj を置いておくこと。

test.csproj

<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net8.0</TargetFramework>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
    <EnableDefaultCompileItems>false</EnableDefaultCompileItems>
  </PropertyGroup>
  <ItemGroup>
    <Compile Include="test.cs" />
  </ItemGroup>
</Project>

テスト手順

下記のバッチファイルを実行する。

run.cmd

@echo off
for %%H in (
  test.exe
  NET35\test.exe
  NET48\test.exe
  bin\Release\net8.0\test.exe
) do (
  echo %%H
  for %%I in (
    20 50
    100 200 500
    1000 2000 5000
    10000 20000 50000
    100000 200000 500000
    1000000 2000000 5000000
    10000000 20000000 50000000
    100000000 200000000
  ) do (
    %%H random %%I
  )
)
exit /b

テスト結果

テスト結果を以下に示す。

表１　乱数の昇順ソートに費やす比較関数の呼び出し回数

要素数 $N$	qsort(uCRT)	.NET Framework 3.5	.NET Framework 4.8	.NET 8.0
20	84	133	133	56
50	307	396	396	267
100	703	938	938	663
200	1,740	2,227	2,227	1,496
500	5,030	6,388	6,388	4,594
1,000	11,160	14,241	14,241	10,196
2,000	25,238	29,184	29,184	23,226
5,000	76,025	83,449	83,449	67,737
10,000	155,041	177,783	177,783	147,400
20,000	327,934	369,599	369,599	304,244
50,000	897,936	1,043,028	1,043,028	884,113
100,000	1,945,323	2,179,318	2,179,318	1,811,675
200,000	4,169,217	4,486,461	4,486,446	3,833,795
500,000	10,990,027	12,277,948	12,277,110	10,640,989
1,000,000	22,924,973	25,373,361	25,372,150	21,979,476
2,000,000	48,497,868	54,838,178	54,783,339	47,406,196
5,000,000	130,345,910	140,192,513	140,073,583	124,619,124
10,000,000	272,197,148	297,639,739	296,475,127	262,655,755
20,000,000	566,211,699	619,190,596	615,415,448	553,305,269
50,000,000	1,483,365,911	1,601,171,234	1,586,737,108	1,445,233,081
100,000,000	3,066,511,691	3,317,171,348	3,275,574,132	2,972,257,226
200,000,000	6,400,427,154	6,916,900,788	6,804,184,853	6,213,723,201

クイックソートの計算量は $O(N \log{N})$ であるとされているので，その比例係数 $K$ を求めた。配列の要素数 $N$，比較関数の呼び出し回数 $M$ とおくと

K = \frac{M}{N \log_{10}{N}}

とする。グラフにすると分かり易い。.NET Framework 3.5 および 4.8 は qsort (uCRT) と比べて 比較関数の呼び出し回数が多いが，.NET 8.0 になると逆転する。

■qsort (uCRT)，■.NET Framework 3.5，■.NET Framework 4.8，■.NET 8.0

結論

.NET Framework 3.5 と 4.8 は途中まで（$N \le 100000$）は同じであるが，それより $N$ が大きくなると微妙に異なる。.NET Framework 3.5 のソースコードは公開されていないようなので細かい仕様が分からないが，$N$ が小さいときのソートアルゴリズム（クイックソート）は .NET Framework 4.8 と共通なものを使用していると考えらえる。これを仮に quicksort(A) と呼ぶことにする。

.NET Framework 3.5 では，この quicksort(A) を全面的に採用していると思われる。このため平均的には $O(N \log N)$ の計算量で済むが，最悪ケースでは $O(N^2)$ となることを避けられないはずだ。

次に .NET Framework 4.8 では quicksort(A) を用いてソートを開始するが，再帰関数の呼び出し深さ $d > 32$ となるとヒープソートに切り替えることで最悪ケースを回避していると思われる。

一方 .NET 8.0 ではベースとなるクイックソートが改善されており，比較回数が少なくなっている。区別するために quicksort(B) と呼ぼう。再帰関数の呼び出しが深くなるとヒープソートに切り替えるが，切り替えの閾値は固定値ではなく，配列の要素数 $N$ として $d > 2(\log_2{N} + 1)$ としている。また，クイックソートによって分割された区間のサイズ $n \le 16$ になると挿入ソートに切り替わる。

このようにクイックソートでスタートして，再帰関数の呼び出し深さが閾値を超えるとヒープソートに切り替わるようなアルゴリズムをイントロソートと呼ぶ。

なお .NET Framework 4.8 のヒープソートと .NET 8.0 のヒープソートが同じものかどうかは確定していない。確かめようにもヒープソートが必要になる最悪データを作ることが出来ていないからだ。

参考文献

• .NET4.5と.NET4のソートは結果が異なる - Qiita