Go to Qiita Advent Calendar Top
LoginSignup
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@TETSURO1999

ついに .NET Framework 4.8 の Array.Sort を解明した

Posted at

はじめに

そもそも筆者の下記記事で .NET Framework の Array.Sort の謎の動作に悩まされたのが発端である。.NET Framework の Array.Sort では差がゼロとなることが分かり切っているにも関わらず，同じ要素同士の比較を行う場合があったのだ。

数万個のファイルの重複チェックを行うプログラムをC#でささっと作る３～.NETのArray.Sortの謎に挑む - Qiita

その後の継続的な調査によって .NET Framework の Array.Sort のアルゴリズムについて把握することができた。

先に結論を述べると，.NET Framework 3.5 の Array.Sort は原始的な Quicksort アルゴリズムを忠実に実装したもので，差がゼロとなることが分かり切っているにも関わらず，同じ要素同士の比較を行う場合がある。下手に同じ要素同士の比較を避けないほうがプログラムはシンプルになり，実行効率が良いからだ。

ただし，クイックソートキラーによって最悪データを与えると計算量が $O(n^2)$ になってしまう弱点がある。.NET Framework 4.8 の Array.Sort は .NET Framework 3.5 をベースにしつつも，この欠陥に対応するため再帰呼び出しの深さが 32 を超えるとヒープソートに切り替える仕組みを持つ。このようなソートをイントロソートと呼ぶ。

コード全容

.NET Framework 4.8 の Array.Sort と同じような動きをするものをC言語で作ってみた。簡単のため int 型のソートに特化したが，ソート関数を指定できるのでそれなりに汎用性はあるとは思う。大して長くはないと思うので全容を紹介する。

qsort_net2.c（.NET Framework 4.8 版）
/* 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    heap(int *a, int len, int parent, COMPARE compare) {
/* 008 */     int d = a[parent];
/* 009 */     int child;
/* 010 */     while((child = 2 * parent + 1) < len) {
/* 011 */         if(child + 1 < len && compare(a[child], a[child + 1]) < 0)
/* 012 */             child++;
/* 013 */         if(compare(d, a[child]) >= 0) break;
/* 014 */         a[parent] = a[child];
/* 015 */         parent = child;
/* 016 */     }
/* 017 */     a[parent] = d;
/* 018 */ }
/* 019 */ static  void    hsort(int *a, int len, COMPARE compare) {
/* 020 */     for(int i = len / 2 - 1; i >= 0; i--)
/* 021 */         heap(a, len, i, compare);
/* 022 */     for(int i = len - 1; i > 0; i--) {
/* 023 */         swap(&a[0], &a[i]);
/* 024 */         heap(a, i, 0, compare);
/* 025 */     }
/* 026 */ }
/* 027 */ static  void    sort(int *a, int top, int end, int depth, COMPARE compare) {
/* 028 */     do {
/* 029 */         if(depth == 0) {
/* 030 */             hsort(&a[top], end - top + 1, compare);
/* 031 */             return;
/* 032 */         }
/* 033 */         int mid = top + (end - top) / 2;
/* 034 */         if(top != mid && compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
/* 035 */         if(top != end && compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
/* 036 */         if(mid != end && compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
/* 037 */         int t = top;
/* 038 */         int e = end;
/* 039 */         int pivot = a[mid];
/* 040 */         do {
/* 041 */             while(compare(a[t], pivot) < 0) t++;
/* 042 */             while(compare(pivot, a[e]) < 0) e--;
/* 043 */             if(t > e) break;
/* 044 */             if(t < e) swap(&a[t], &a[e]);
/* 045 */             t++;
/* 046 */             e--;
/* 047 */         } while(t <= e);
/* 048 */         depth--;
/* 049 */         if(e - top <= end - t) {
/* 050 */             if(top < e) sort(a, top, e, depth, compare);
/* 051 */             top = t;
/* 052 */         } else {
/* 053 */             if(t < end) sort(a, t, end, depth, compare);
/* 054 */             end = e;
/* 055 */         }
/* 056 */     } while(top < end);
/* 057 */ }
/* 058 */ void    qsort_net2(int *a, int len, COMPARE compare) {
/* 059 */     if(len < 2) return;
/* 060 */     int depth = 32;
/* 061 */     sort(a, 0, len - 1, depth, compare);
/* 062 */ }

コード解説

それでは意訳したC言語版コードを頭から解説していきたい。.NET Framework 3.5 版と比べれば違いがよく分かると思う。

1. 交換関数

まずは交換関数 swap() だが，全く同じである。

2. ソート関数

ソート関数本体 qsort_net2() である。配列の要素数 len が２個未満のときは何もしないでリターンするところも同じである。再帰関数の呼び出し深さの初期値として depth = 32 を与える。

3. ソートエンジン本体

再帰関数の呼び出し深さ depth が与えられており，呼び出すごとにデクリメントしていき，ゼロになるとヒープソート heap() を呼び出す。それ以外は全く同じである。

4. ヒープソート

ヒープソートである。ここは全く新たに追加された部分である。

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

比較回数・転送回数の比較を行ってみよう。試験条件は下記の通りである。

  • 200,000,000 個の 32bit 整数を昇順ソートする。
  • データの順序は以下の四種類である。
    • ゼロ（すべて同値）
    • 昇順：0 → 199,999,999
    • 降順：199,999,999 → 0
    • 乱数：0～199,999,999 の範囲で一様乱数（重複あり）
  • 乱数発生器は XorShift である。

試験結果は下記の通りである。

表１　比較回数の比較（単位は回）
順序 uCRT .NET .NET2
ゼロ 399,999,999 5,675,718,141 5,675,718,141
昇順 5,363,792,412 5,730,237,980 5,730,237,980
降順 5,363,792,412 5,730,238,009 5,730,238,009
乱数 6,400,427,154 6,916,900,788 6,804,184,853
表２　転送回数の比較（単位は回）
順序 uCRT .NET .NET2
ゼロ 0 5,208,609,280 5,208,609,280
昇順 265,782,274 0 0
降順 465,782,278 200,000,004 200,000,004
乱数 2,736,238,624 2,770,781,196 2,998,522,286

こういうのはグラフにすると一目瞭然である。乱数を除けば，.NET (.NET Framework 3.5) と .NET2 (.NET Framework 4.8) の比較回数・転送回数に違いはない。乱数のときのみ異なるのは，.NET2 (.NET Framework 4.8) は途中でヒープソートに切り替わっているからだと考えられる。

■ uCRT，■ .NET，■ .NET2

実行時間の比較

試験条件を以下に示す。

  • 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 .NET2
Visual C++
32bit版		 ゼロ 0.090 1.891 1.838
昇順 1.433 1.262 1.351
降順 1.475 1.275 1.369
乱数 15.505 14.986 15.301
Visual C++
64bit版		 ゼロ 0.093 2.187 2.162
昇順 1.582 1.589 1.567
降順 1.617 1.607 1.576
乱数 15.500 15.562 14.913
LLVM clang-cl
32bit版		 ゼロ 0.098 2.129 2.160
昇順 1.627 1.425 1.460
降順 1.688 1.461 1.509
乱数 15.636 14.389 14.998
LLVM clang-cl
64bit版		 ゼロ 0.089 2.334 2.290
昇順 1.460 1.338 1.357
降順 1.523 1.381 1.394
乱数 15.710 14.703 14.780
intel icx-cl
32bit版		 ゼロ 0.070 2.255 2.136
昇順 1.592 1.435 1.282
降順 1.691 1.464 1.309
乱数 17.120 14.694 14.686
intel icx-cl
64bit版		 ゼロ 0.064 2.388 2.310
昇順 1.366 1.536 1.583
降順 1.491 1.580 1.623
乱数 16.584 15.106 15.053

グラフにすると分かり易い。.NET2 (.NET Framework 4.8) では再帰関数の引数が一つ増えたこと，ヒープソートの呼び出しチェックの処理が増えたこと，そして乱数では計算時間のかかるヒープソートの呼び出しが行われていることから .NET2 は .NET よりも実行時間は増えるはずだ。実際に Visual C++ および clang-cl の 32bit 版では増えている。しかし，64bit 版および intel C++ Compiler ではほぼ同じに見える。64bit 版コンパイラでは使用できるレジスタ増加していることから，優秀なコンパイラであれば隠蔽できてしまう程度の差なのであろう。

■ uCRT，■ .NET，■ .NET2

クイックソートキラーへの耐性

通常のデータを与えただけでは面白くない。.NET Framework 4.8 の真価が問われるのはクイックソートキラーに対する耐性である。

検証用ソフト

検証用ソフトとメイクファイル，およびバッチファイルを以下に示す。

検証用ソフト
bench.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#define	MACROOF(arg)	#arg
#define	STRINGOF(macro)	MACROOF(macro)
typedef	int		(*COMPARE)(int, int);
extern	void	SORTFUNC(int *a, int len, COMPARE compare);
uint32_t	xorshift( void ) {
static	uint64_t	x = 1;
	x ^= x << 13;
	x ^= x >>  7;
	x ^= x << 17;
	return (uint32_t)x;
}
#ifdef	COUNT
static	int		index = 0;
static	int		*pivot = (int*)NULL;
static	int		killer(int p, int q) {
	if(pivot[p] < 0 && pivot[q] < 0) {
		pivot[p] = index++;
		pivot[q] = index++;
		return -1;
	}
	if(pivot[p] < 0) return  1;
	if(pivot[q] < 0) return -1;
	return pivot[p] - pivot[q];
}
uint64_t	move_count = 0;
uint64_t	comp_count = 0;
#endif
static	int		compare(int p, int q) {
#ifdef	COUNT
	comp_count++;
#endif
	return p - q;
}
int	main(int argc, char *argv[]) {
	if(argc < 3) {
		fprintf(stderr, "Usage: bench(.exe) [data] [size] (debug)\n");
#ifdef	COUNT
		fprintf(stderr, " data: zero, ascend, descend, random, killer\n");
#else
		fprintf(stderr, " data: zero, ascend, descend, random\n");
#endif
		fprintf(stderr, " func: " STRINGOF(SORTFUNC) "\n");
		return -1;
	}
	int	size = atoi(argv[2]);
	int	*table = (int*)malloc(sizeof(int) * size);
	if(table == (int*)NULL) {
		fprintf(stderr, "cannot allocate size: %d\n", size);
		return -1;
	}
	switch(argv[1][0]) {
	  case 'z': for(int i = 0; i < size; i++) table[i] = 0;					break;
	  case 'a':	for(int i = 0; i < size; i++) table[i] = i;					break;
	  case 'd':	for(int i = 0; i < size; i++) table[i] = size - i - 1;		break;
	  case 'r':	for(int i = 0; i < size; i++) table[i] = xorshift() % size;	break;
#ifdef	COUNT
	  case 'k':
		int		*dummy = (int*)malloc(sizeof(int) * size);
		if(dummy == (int*)NULL) {
			fprintf(stderr, "cannot allocate size: %d\n", size);
			return -1;
		}
		pivot = (int*)malloc(sizeof(int) * size);
		if(pivot == (int*)NULL) {
			fprintf(stderr, "cannot allocate size: %d\n", size);
			return -1;
		}
		for(int i = 0; i < size; i++) dummy[i] = i;
		for(int i = 0; i < size; i++) pivot[i] = -1;
		SORTFUNC(dummy, size, killer);
		for(int i = 0; i < size; i++) table[dummy[i]] = i;
		free(dummy);
		free(pivot);
		break;
#endif
	  default:
		fprintf(stderr, "illegal data: %s\n", argv[1]);
		return -1;
	}
#ifdef	COUNT
	SORTFUNC(table, size, compare);
	fprintf(stdout, "comp_count: %lld\n", comp_count);
	fprintf(stdout, "move_count: %lld\n", move_count);
#else
	clock_t	t1 = clock();
	SORTFUNC(table, size, compare);
	clock_t	t2 = clock();
	fprintf(stdout, "time: %.3f\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
#endif
	if(argc >= 4 && argv[3][0] == 'd')
		for(int i = 0; i < size; i++) fprintf(stdout, "%d\n", table[i]);
	return 0;
}
メイクファイル
Makefile.count
OUTDIR=count
CC=cl
CFLAGS=/c /O2 /W4 /arch:AVX2 /GL /GS- /DCOUNT
LFLAGS=/GL
LIBS=
!include "MAKEFILE.INC"
Makefile.inc
OUTDIRS=$(OUTDIR) \
        $(OUTDIR)\ucrt \
        $(OUTDIR)\net \
        $(OUTDIR)\net2 

target: $(OUTDIRS) \
        $(OUTDIR)\ucrt\bench.exe \
        $(OUTDIR)\net\bench.exe \
        $(OUTDIR)\net2\bench.exe

$(OUTDIRS):
	@if not exist $@ mkdir $@

$(OUTDIR)\ucrt\bench.exe: $(OUTDIR)\ucrt\bench.obj $(OUTDIR)\ucrt\qsort_net.obj
$(OUTDIR)\net\bench.exe:  $(OUTDIR)\net\bench.obj  $(OUTDIR)\net\qsort_net.obj
$(OUTDIR)\net2\bench.exe: $(OUTDIR)\net2\bench.obj $(OUTDIR)\net2\qsort_net2.obj

$(OUTDIR)\ucrt\bench.exe \
$(OUTDIR)\net\bench.exe \
$(OUTDIR)\net2\bench.exe:
	$(CC) $** /Fe$* $(LFLAGS) $(LIBS)

.c{$(OUTDIR)\ucrt}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\ucrt\ /DSORTFUNC=qsort_ucrt

.c{$(OUTDIR)\net}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\net\  /DSORTFUNC=qsort_net

.c{$(OUTDIR)\net2}.obj::
	$(CC) $(CFLAGS) $< /Fo$(OUTDIR)\net2\ /DSORTFUNC=qsort_net2

clean:
	if exist $(OUTDIR) rd /s /q $(OUTDIR)
バッチファイル 
@echo off
for %%H in (ucrt net net2) do (
  for %%I in (
    10 20 50
    100 200 500
    1000 2000 5000
    10000 20000 50000
    100000 200000 500000
    1000000
  ) do (
    echo %%H %%I
    count\%%H\bench killer %%I
  )
)

検証結果

検証結果を以下に示す。

表４　クイックソートキラーに対する比較回数
要素数 uCRT .NET .NET2
10 39 65 65
20 124 195 195
50 679 885 885
100 2,604 3,035 2,769
200 10,204 11,085 7,137
500 63,004 65,235 21,266
1,000 251,004 255,485 46,197
2,000 1,002,004 1,010,985 97,951
5,000 6,255,004 6,277,485 261,268
10,000 25,010,004 25,054,985 544,536
20,000 100,020,004 100,109,985 1,130,597
50,000 625,050,004 625,274,985 2,960,700
100,000 2,500,100,004 2,500,549,985 6,125,482
200,000 10,000,200,004 10,001,099,985 12,661,996
500,000 62,500,500,004 62,502,749,985 32,968,189
1,000,000 250,001,000,004 250,005,499,985 67,979,733

こういうのは両対数グラフにすると分かり易い。uCRT も .NET (.NET Framework 3.5) も $O(n^2)$ でデータ量が10倍になると比較回数が100倍になっているが，.NET2 (.NET Framework 4.8) では途中でヒープソートに切り替わって傾きが緩やかになり，$O(n \log n)$ になっていることが分かる。

■ uCRT，■ .NET，■ .NET2

次回予告

.NET Core の Array.Sort はもっと凄い。

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?