最強コンパイラを使えばマージソートは遅くない？

# はじめに

現在，筆者はソートアルゴリズムについて勉強中であり，これまで下記の記事で取り上げてきた。

- [uCRT の qsort のソースを読む - Qiita](https://qiita.com/TETSURO1999/items/ff12ba697a1ae79cbf9f)
- [GNU C Libraryのqsortはクイックソートではないの？ - Qiita](https://qiita.com/TETSURO1999/items/3eff3b6a5e3983630f3c)

しかしながら，GNU C Libarary は（当たり前のことながら）GNU C コンパイラ でビルドされることが前提であり，単に Microsoft の Visual C++ では性能が出なかっただけなのかもしれない。とはいえ，今から GNU C コンパイラをインストールするのは気が進まないというか，既に筆者のPCには LLVM の clang-cl と intel C++ コンパイラ がインストールされているのだった[^1][^2]。ということで中立的かつ最強コンパイラの呼び声も高い LLVM の clang-cl と intel C++ コンパイラで再評価を試みた。

結論を先に言うと，マージソートも clang-cl または intel C++ コンパイラを使えばクイックソートに肉薄するレベルまで高速化できる。

# 試験条件

- 要素数 200,000,000 個の`int` 型の配列の昇順ソートを行う。マージソートの場合，同サイズの配列がもう一つ必要になることから，32bit プログラムではほぼ上限値である。
  4×200,000,000 bytes = 0x2FAF0800 bytes
- データの順序は以下の四種類とする。
  - ゼロ
  - 昇順：0 → 199,999,999
  - 降順：199,999,999 → 0
  - 乱数：0～199,999,999 の範囲の一様乱数，乱数発生器は XorShift とした[^3]
- 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

# ソースコード

ソースコードは<b>前回の記事</b>と全く同じであるが，念のため再掲する。

<details><summary><b>ベンチ用メイン</b></summary>

```c++: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
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");
		fprintf(stderr, " data: zero, ascend, descend, random\n");
		fprintf(stderr, " func: " STRINGOF(SORTFUNC) "\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': 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;
	  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;
}
```

</details>

<details><summary><b>uCRT 版 qsort の意訳版</b></summary>

```c++:qsort_ucrt.c
#ifdef	COUNT
#include <stdint.h>
extern	uint64_t	move_count;
#endif
typedef	int		(*COMPARE)(int, int);
#define	STACK_SIZE	30
static	void	swap(int *p, int *q) {
#ifdef	COUNT
	move_count += 2;
#endif
	int	temp = *p;
	*p = *q;
	*q = temp;
}
void	qsort_ucrt(int *a, int len, COMPARE compare) {
	if(len < 2) return;
	int	top_stack[STACK_SIZE];
	int	end_stack[STACK_SIZE];
	int	stack = 0;
	int	top = 0;
	int	end = len - 1;
LOOP:
	int	n = end - top + 1;
	if(n <= 8) {
		for(int e = end; e > top; e--) {
			int	max = top;
			for(int i = top + 1; i <= e; i++)
				if(compare(a[i], a[max]) > 0) max = i;
			swap(&a[max], &a[e]);
		}
	} else {
		int	mid = top + n / 2;
		int	t = top;
		int	e = end;
		if(compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
		if(compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
		if(compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
		for(;;) {
			if(t <  mid) while(++t <  mid && compare(a[t], a[mid]) <= 0);
			if(t >= mid) while(++t <= end && compare(a[t], a[mid]) <= 0);
			while(--e > mid && compare(a[e], a[mid]) > 0);
			if(t > e) break;
			swap(&a[t], &a[e]);
			if(e == mid) mid = t;
		}
		e++;
		if(e >  mid) while(--e > mid && compare(a[e], a[mid]) == 0);
		if(e <= mid) while(--e > top && compare(a[e], a[mid]) == 0);
		if(e - top >= end - t) {
			if(top < e) {
				top_stack[stack] = top;
				end_stack[stack] = e;
				stack++;
			}
			if(t < end) {
				top = t;
				goto LOOP;
			}
		} else {
			if(t < end) {
				top_stack[stack] = t;
				end_stack[stack] = end;
				stack++;
			}
			if(top < e) {
				end = e;
				goto LOOP;
			}
		}
	}
	if(--stack >= 0) {
		top = top_stack[stack];
		end = end_stack[stack];
		goto LOOP;
	}
}
```

</details>

<details><summary><b>GNU C ライブラリ版 qsort の意訳版</b></summary>

```c++:qsort_glibc.c
#ifdef	COUNT
#include <stdint.h>
extern	uint64_t	move_count;
#endif
#include <stdlib.h>
typedef	int		(*COMPARE)(int, int);
#define	TEMP_SIZE	256
static	void	sort(int *buf, int *a, int len, COMPARE compare) {
	if(len < 2) return;
	int	n1 = len / 2;
	int	n2 = len - n1;
	int	*p1 = a;
	int	*p2 = &a[n1];
	sort(buf, p1, n1, compare);
	sort(buf, p2, n2, compare);
	int	*q = buf;
	for(;;) {
#ifdef	COUNT
		move_count++;
#endif
		if(compare(*p1, *p2) <= 0) {
			*q++ = *p1++;
			if(--n1 == 0) break;
		} else {
			*q++ = *p2++;
			if(--n2 == 0) break;
		}
	}
#ifdef	COUNT
	move_count += n1 + len - n2;
#endif
	while(n1 > 0) {
		*q++ = *p1++;
		n1--;
	}
	for(int i = 0; i < len - n2; i++)
		a[i] = buf[i];
}
void	qsort_glibc(int *a, int len, COMPARE compare) {
	if(len < 2) return;
	if(len <= TEMP_SIZE) {
		int	tmp[TEMP_SIZE];
		sort(tmp, a, len, compare);
	} else {
		int	*buf = (int*)malloc(sizeof(int) * len);
		if(buf == (int*)NULL) return;
		sort(buf, a, len, compare);
		free(buf);
	}
}
```

</details>

# メイクファイル

Microsoft Visual C++ 用メイクファイルを以下に示す。32bit（x86）版と64bit（x64）版共用である。オプション `/GL` を指定してプログラム全体の最適化を有効にした。

```:Makefile.vc
OUTDIR=$(VSCMD_ARG_TGT_ARCH)vc
CC=cl
CFLAGS=/c /O2 /W4 /arch:AVX2 /GL /GS-
LFLAGS=/GL
LIBS=
!include "MAKEFILE.INC"
```

LLVM clang-cl 用メイクファイルを以下に示す。32bit（x86）版と64bit（x64）版共用である。オプション `/TC` は C ソースファイルとみなす。Visual C++ では拡張子 `.c` のファイルは C ソースファイルとみなすので指定不要だが，clang-cl ではわざわざ指定する必要がある。オプション `-flto` はリンク時最適化であり，リンカも専用のものを指定する必要がある。

```:Makefile.clang
OUTDIR=$(VSCMD_ARG_TGT_ARCH)clang
CC=clang-cl
CFLAGS=/c /O2 /W4 /arch:AVX2 /TC -flto /GS-
LFLAGS=-flto -fuse-ld=lld
LIBS=
!include "MAKEFILE.inc"
```

intel C++ コンパイラ用メイクファイルを以下に示す。32bit（x86）版と64bit（x64）版共用である。基本的に細かい注意点については clang-cl と同じ。

```:Makefile.intel
OUTDIR=$(VS_TARGET_ARCH)intel
CC=icx-cl
CFLAGS=/c /O2 /W4 /arch:AVX2 /TC -flto /GS-
LFLAGS=-flto -fuse-ld=lld
LIBS=
!include "MAKEFILE.inc"
```

共通部分を以下に示す。

```Makefile.inc
OUTDIRS=$(OUTDIR) \
        $(OUTDIR)\ucrt \
        $(OUTDIR)\glibc

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

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

$(OUTDIR)\ucrt\bench.exe:  $(OUTDIR)\ucrt\bench.obj  $(OUTDIR)\ucrt\qsort_ucrt.obj
$(OUTDIR)\glibc\bench.exe: $(OUTDIR)\glibc\bench.obj $(OUTDIR)\glibc\qsort_glibc.obj

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

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

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

clean:
	if exist $(OUTDIR) rd /s /q $(OUTDIR)
```

上記のメイクファイルを実行すると，`x86vc`, `x64vc`, `x86clang`, `x64clang`, `x86intel`, `x64intel` と６個のフォルダが作られ，各フォルダの下にそれぞれの環境でビルドされた `ucrt\bench.exe` と `glibc\bench.exe` が作られる。

# バイナリサイズの比較

intel C++ コンパイラを使うとバイナリサイズが一気に肥大化するので驚く。おそらくループアンローリングや関数のインライン展開を多用するのだろう。

<table>
<caption>表１　バイナリサイズの比較（単位はバイト）</caption>
<thead>
<tr><th colspan=2 style="text-align:center">コンパイラ</th>
    <th style="text-align:center">qsort_ucrt</th>
    <th style="text-align:center">qsort_glibc</th></tr>
</thead>
<tbody>
<tr></tr>
<tr><th rowspan=3>Visual C++</th><th>32bit</th>
    <td style="text-align:right">118,272</td>
    <td style="text-align:right">117,760</td></tr>
<tr></tr>
<tr><th>64bit</th>
    <td style="text-align:right">142,848</td>
    <td style="text-align:right">142,848</td></tr>
<tr></tr>
<tr><th rowspan=3>LLVM clang-cl</th><th>32bit</th>
    <td style="text-align:right">118,784</td>
    <td style="text-align:right">118,784</td></tr>
<tr></tr>
<tr><th>64bit</th>
    <td style="text-align:right">148,480</td>
    <td style="text-align:right">148,480</td></tr>
<tr></tr>
<tr><th rowspan=3>intel icx-cl</th><th>32bit</th>
    <td style="text-align:right">166,400</td>
    <td style="text-align:right">169,472</td></tr>
<tr></tr>
<tr><th>64bit</th>
    <td style="text-align:right">208,384</td>
    <td style="text-align:right">226,304</td></tr>
</tbody>
</table>

ここで qsort_ucrt と qsort_glibc のファイルサイズに注目する。コンパクトな 32bit 版のサイズに着目すると，

- Visual C++ では qsort_ucrt < qsort_glibc
- LLVM clang-cl では qsort_ucrt = qsort_glibc
- intel icx-cl では qsort_ucrt > qsort_glibc

となっており，強力な最適化を施すことによって，とりわけ qsort_glibc のほうが著しくサイズが増えていることが分かる。

# 試験結果

試験結果を以下に示す。

<table>
<caption>表２　実行時間の比較（単位は秒）</caption>
<thead>
<tr><th style="text-align:center">コンパイラ</th>
    <th style="text-align:center">順序</th>
    <th style="text-align:center">qsort_ucrt</th>
    <th style="text-align:center">qsort_glibc</th></tr>
</thead>
<tbody>
<tr></tr>
<tr><th rowspan=7>Visual C++<br>32bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.090</td>
    <td style="text-align:right">2.660</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.433</td>
    <td style="text-align:right">2.656</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.475</td>
    <td style="text-align:right">3.914</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">15.505</td>
    <td style="text-align:right">17.996</td></tr>
<tr></tr>
<tr><th rowspan=7>Visual C++<br>64bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.093</td>
    <td style="text-align:right">2.470</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.582</td>
    <td style="text-align:right">2.473</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.617</td>
    <td style="text-align:right">3.769</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">15.500</td>
    <td style="text-align:right">21.129</td></tr>
<tr></tr>
<tr><th rowspan=7>LLVM clang-cl<br>32bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.098</td>
    <td style="text-align:right">2.066</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.627</td>
    <td style="text-align:right">2.060</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.688</td>
    <td style="text-align:right">3.642</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">15.636</td>
    <td style="text-align:right">16.487</td></tr>
<tr></tr>
<tr><th rowspan=7>LLVM clang-cl<br>64bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.089</td>
    <td style="text-align:right">1.958</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.460</td>
    <td style="text-align:right">1.997</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.523</td>
    <td style="text-align:right">2.942</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">15.710</td>
    <td style="text-align:right">16.022</td></tr>
<tr></tr>
<tr><th rowspan=7>intel icx-cl<br>32bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.070</td>
    <td style="text-align:right">2.488</td></tr>
<tr></tr><tr><th>昇順</th>
    <td style="text-align:right">1.592</td>
    <td style="text-align:right">2.498</td></tr>
<tr></tr><tr><th>降順</th>
    <td style="text-align:right">1.691</td>
    <td style="text-align:right">3.333</td></tr>
<tr></tr><tr><th>乱数</th>
    <td style="text-align:right">17.120</td>
    <td style="text-align:right">17.809</td></tr>
<tr></tr><tr><th rowspan=7>intel icx-cl<br>64bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.064</td>
    <td style="text-align:right">1.811</td></tr>
<tr></tr><tr><th>昇順</th>
    <td style="text-align:right">1.366</td>
    <td style="text-align:right">1.797</td></tr>
<tr></tr><tr><th>降順</th>
    <td style="text-align:right">1.491</td>
    <td style="text-align:right">2.507</td></tr>
<tr></tr><tr><th>乱数</th>
    <td style="text-align:right">16.584</td>
    <td style="text-align:right">15.969</td></tr>
</tbody>
</table>

こういうのはグラフにした方が分かり易い。

<font color=#5B9BD5>■</font>qsort_ucrt，<font color=#ED7D31>■</font>qsort_glibc

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontstyle normal
  fontsize 16
}
</style>
sprite FIGURE <svg width="320" height="300">
<g fill="lightgray">
<path d="M30 270 h280 v1 h-280">
<path d="M30 220 h280 v1 h-280">
<path d="M30 170 h280 v1 h-280">
<path d="M30 120 h280 v1 h-280">
<path d="M30 70 h280 v1 h-280">
<path d="M30 20 h280 v1 h-280">
</g>
<g fill="#5B9BD5">
<path d="M43 270 h20 v-1 h-20">
<path d="M113 270 h20 v-14 h-20">
<path d="M183 270 h20 v-15 h-20">
<path d="M253 270 h20 v-155 h-20">
</g>
<g fill="#ED7D31">
<path d="M67 270 h20 v-27 h-20">
<path d="M137 270 h20 v-27 h-20">
<path d="M207 270 h20 v-39 h-20">
<path d="M277 270 h20 v-180 h-20">
</g>

<text x="15" y="276" font-size="16" fill="black">0</text>
<text x="15" y="226" font-size="16" fill="black">5</text>
<text x="5" y="176" font-size="16" fill="black">10</text>
<text x="5" y="126" font-size="16" fill="black">15</text>
<text x="5" y="76" font-size="16" fill="black">20</text>
<text x="5" y="26" font-size="16" fill="black">25</text>
<text x="48" y="290" font-size="16" fill="black">ゼロ</text>
<text x="118" y="290" font-size="16" fill="black">昇順</text>
<text x="188" y="290" font-size="16" fill="black">降順</text>
<text x="258" y="290" font-size="16" fill="black">乱数</text>
</svg>
title
<$FIGURE>
図１　Visual C++ 32bit版（単位は秒）
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontstyle normal
  fontsize 16
}
</style>
sprite FIGURE <svg width="320" height="300">
<g fill="lightgray">
<path d="M30 270 h280 v1 h-280">
<path d="M30 220 h280 v1 h-280">
<path d="M30 170 h280 v1 h-280">
<path d="M30 120 h280 v1 h-280">
<path d="M30 70 h280 v1 h-280">
<path d="M30 20 h280 v1 h-280">
</g>
<g fill="#5B9BD5">
<path d="M43 270 h20 v-1 h-20">
<path d="M113 270 h20 v-16 h-20">
<path d="M183 270 h20 v-16 h-20">
<path d="M253 270 h20 v-155 h-20">
</g>
<g fill="#ED7D31">
<path d="M67 270 h20 v-25 h-20">
<path d="M137 270 h20 v-25 h-20">
<path d="M207 270 h20 v-38 h-20">
<path d="M277 270 h20 v-211 h-20">
</g>

<text x="15" y="276" font-size="16" fill="black">0</text>
<text x="15" y="226" font-size="16" fill="black">5</text>
<text x="5" y="176" font-size="16" fill="black">10</text>
<text x="5" y="126" font-size="16" fill="black">15</text>
<text x="5" y="76" font-size="16" fill="black">20</text>
<text x="5" y="26" font-size="16" fill="black">25</text>
<text x="48" y="290" font-size="16" fill="black">ゼロ</text>
<text x="118" y="290" font-size="16" fill="black">昇順</text>
<text x="188" y="290" font-size="16" fill="black">降順</text>
<text x="258" y="290" font-size="16" fill="black">乱数</text>
</svg>
title
<$FIGURE>
図２　Visual C++ 64bit版（単位は秒）
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontstyle normal
  fontsize 16
}
</style>
sprite FIGURE <svg width="320" height="300">
<g fill="lightgray">
<path d="M30 270 h280 v1 h-280">
<path d="M30 220 h280 v1 h-280">
<path d="M30 170 h280 v1 h-280">
<path d="M30 120 h280 v1 h-280">
<path d="M30 70 h280 v1 h-280">
<path d="M30 20 h280 v1 h-280">
</g>
<g fill="#5B9BD5">
<path d="M43 270 h20 v-1 h-20">
<path d="M113 270 h20 v-16 h-20">
<path d="M183 270 h20 v-17 h-20">
<path d="M253 270 h20 v-156 h-20">
</g>
<g fill="#ED7D31">
<path d="M67 270 h20 v-21 h-20">
<path d="M137 270 h20 v-21 h-20">
<path d="M207 270 h20 v-36 h-20">
<path d="M277 270 h20 v-165 h-20">
</g>
<text x="15" y="276" font-size="16" fill="black">0</text>
<text x="15" y="226" font-size="16" fill="black">5</text>
<text x="5" y="176" font-size="16" fill="black">10</text>
<text x="5" y="126" font-size="16" fill="black">15</text>
<text x="5" y="76" font-size="16" fill="black">20</text>
<text x="5" y="26" font-size="16" fill="black">25</text>
<text x="48" y="290" font-size="16" fill="black">ゼロ</text>
<text x="118" y="290" font-size="16" fill="black">昇順</text>
<text x="188" y="290" font-size="16" fill="black">降順</text>
<text x="258" y="290" font-size="16" fill="black">乱数</text>
</svg>
title
<$FIGURE>
図３　LLVM clang-cl 32bit版（単位は秒）
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontstyle normal
  fontsize 16
}
</style>
sprite FIGURE <svg width="320" height="300">
<g fill="lightgray">
<path d="M30 270 h280 v1 h-280">
<path d="M30 220 h280 v1 h-280">
<path d="M30 170 h280 v1 h-280">
<path d="M30 120 h280 v1 h-280">
<path d="M30 70 h280 v1 h-280">
<path d="M30 20 h280 v1 h-280">
</g>
<g fill="#5B9BD5">
<path d="M43 270 h20 v-1 h-20">
<path d="M113 270 h20 v-15 h-20">
<path d="M183 270 h20 v-15 h-20">
<path d="M253 270 h20 v-157 h-20">
</g>
<g fill="#ED7D31">
<path d="M67 270 h20 v-20 h-20">
<path d="M137 270 h20 v-20 h-20">
<path d="M207 270 h20 v-29 h-20">
<path d="M277 270 h20 v-160 h-20">
</g>
<text x="15" y="276" font-size="16" fill="black">0</text>
<text x="15" y="226" font-size="16" fill="black">5</text>
<text x="5" y="176" font-size="16" fill="black">10</text>
<text x="5" y="126" font-size="16" fill="black">15</text>
<text x="5" y="76" font-size="16" fill="black">20</text>
<text x="5" y="26" font-size="16" fill="black">25</text>
<text x="48" y="290" font-size="16" fill="black">ゼロ</text>
<text x="118" y="290" font-size="16" fill="black">昇順</text>
<text x="188" y="290" font-size="16" fill="black">降順</text>
<text x="258" y="290" font-size="16" fill="black">乱数</text>
</svg>
title
<$FIGURE>
図４　LLVM clang-cl 64bit版（単位は秒）
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontstyle normal
  fontsize 16
}
</style>
sprite FIGURE <svg width="320" height="300">
<g fill="lightgray">
<path d="M30 270 h280 v1 h-280">
<path d="M30 220 h280 v1 h-280">
<path d="M30 170 h280 v1 h-280">
<path d="M30 120 h280 v1 h-280">
<path d="M30 70 h280 v1 h-280">
<path d="M30 20 h280 v1 h-280">
</g>
<g fill="#5B9BD5">
<path d="M43 270 h20 v-1 h-20">
<path d="M113 270 h20 v-16 h-20">
<path d="M183 270 h20 v-17 h-20">
<path d="M253 270 h20 v-171 h-20">
</g>
<g fill="#ED7D31">
<path d="M67 270 h20 v-25 h-20">
<path d="M137 270 h20 v-25 h-20">
<path d="M207 270 h20 v-33 h-20">
<path d="M277 270 h20 v-178 h-20">
</g>
<text x="15" y="276" font-size="16" fill="black">0</text>
<text x="15" y="226" font-size="16" fill="black">5</text>
<text x="5" y="176" font-size="16" fill="black">10</text>
<text x="5" y="126" font-size="16" fill="black">15</text>
<text x="5" y="76" font-size="16" fill="black">20</text>
<text x="5" y="26" font-size="16" fill="black">25</text>
<text x="48" y="290" font-size="16" fill="black">ゼロ</text>
<text x="118" y="290" font-size="16" fill="black">昇順</text>
<text x="188" y="290" font-size="16" fill="black">降順</text>
<text x="258" y="290" font-size="16" fill="black">乱数</text>
</svg>
title
<$FIGURE>
図５　intel icx-cl 32bit版（単位は秒）
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontstyle normal
  fontsize 16
}
</style>
sprite FIGURE <svg width="320" height="300">
<g fill="lightgray">
<path d="M30 270 h280 v1 h-280">
<path d="M30 220 h280 v1 h-280">
<path d="M30 170 h280 v1 h-280">
<path d="M30 120 h280 v1 h-280">
<path d="M30 70 h280 v1 h-280">
<path d="M30 20 h280 v1 h-280">
</g>
<g fill="#5B9BD5">
<path d="M43 270 h20 v-1 h-20">
<path d="M113 270 h20 v-14 h-20">
<path d="M183 270 h20 v-15 h-20">
<path d="M253 270 h20 v-166 h-20">
</g>
<g fill="#ED7D31">
<path d="M67 270 h20 v-18 h-20">
<path d="M137 270 h20 v-18 h-20">
<path d="M207 270 h20 v-25 h-20">
<path d="M277 270 h20 v-160 h-20">
</g>
<text x="15" y="276" font-size="16" fill="black">0</text>
<text x="15" y="226" font-size="16" fill="black">5</text>
<text x="5" y="176" font-size="16" fill="black">10</text>
<text x="5" y="126" font-size="16" fill="black">15</text>
<text x="5" y="76" font-size="16" fill="black">20</text>
<text x="5" y="26" font-size="16" fill="black">25</text>
<text x="48" y="290" font-size="16" fill="black">ゼロ</text>
<text x="118" y="290" font-size="16" fill="black">昇順</text>
<text x="188" y="290" font-size="16" fill="black">降順</text>
<text x="258" y="290" font-size="16" fill="black">乱数</text>
</svg>
title
<$FIGURE>
図６　intel icx-cl 64bit版（単位は秒）
end title
@enduml
```

# 結論

三種類のコンパイラ×ターゲット32bit(x86) or 64bit(x64) の合計六種類の実行ファイルを作成した。

ゼロ・昇順・降順のような特殊なデータ順序については，qsort_glibc（マージソート）の全敗であるのは仕方ないだろう。だがしかし，intel C++ コンパイラを使えばその差が圧縮される。Visual C++ と intel C++ コンパイラの結果を見比べると，qsort_ucrt（クイックソート）のほうはあまり変わらないが，qsort_glibc（マージソート）のほうは大きく改善されている。バイナリサイズも qsort_glibc（マージソート）のほうが増えていることから，おそらくループアンローリング等の最適化技術を多用しており，そのせいでバイナリサイズも増えていると思われる。

乱数データについては，Visual C++ だと 16～36% の差があるが，LLVM clang や intel C++ コンパイラではその差が 5% 以下に縮まり，一部逆転もしている。

qsort_glibc（マージソート）は LLVM clang や intel C++ コンパイラなどの優れたCコンパイラを用いることで性能が伸びているが，qsort_ucrt（クイックソート）のほうは Visual C++ とあまり変わらないというか，むしろ Visual C++ が最速である。もともとマイクロソフト謹製の uCRT で用いられているものなので，Visual C++ で性能が伸びるように作られているのだろう。逆説的に言えば，uCRT の作りは Visual C++ に特化し過ぎていて，先進的なCコンパイラにとって最適化の障害になっているようにも思える。glibc の作りはシンプルであるがゆえにCコンパイラにとって見通しが良く，最適化し易いのかもしれない。

# 次回

次回に続く。

- [マージソートを非再帰型に書き直す～誰でも思いつくアイディアだが～ - Qiita](https://qiita.com/TETSURO1999/items/23bdd493975cbd8a5085)
- [マージソートを非再帰型に書き直す２～さらなる改善を試みる～ - Qiita](https://qiita.com/TETSURO1999/items/783aa5732b9f19a615ca)
- [マージソートを非再帰型に書き直す３～もう限界かもしれない～ - Qiita](https://qiita.com/TETSURO1999/items/5aa007604198b2ff7b06)
- [マージソートを非再帰型に書き直す４～限界突破のアイディアを思いつく～ - Qiita](https://qiita.com/TETSURO1999/items/17d751555fcf9b275518)

<!--
# 参考文献
-->

[^1]: [自炊の画像形式をPNGからWebPに移行する２～WebPユーティリティを評判のClangでビルドする - Qiita](https://qiita.com/TETSURO1999/items/239a359f337b2211ac04)

[^2]: [自炊の画像形式をPNGからWebPに移行する３～WebPユーティリティを最強Intel C++コンパイラでビルドする - Qiita](https://qiita.com/TETSURO1999/items/2f9a2e2f6a732cdb25d9)

[^3]: [C++とC#で各種乱数発生器を実装してみる（勉強用）- Qiita](https://qiita.com/TETSURO1999/items/7ff6f892ae5a9e46ddd9)