C言語における変数の値を交換（Swap）する方法と実行速度の比較

C言語では，様々な方法を用いて，変数内の値を交換（Swap）することができます．

今回は，一時変数を用いる方法や排他的論理和を用いる方法，さらにはアセンブラを用いる方法を比較し，その実行速度を調べてみました．

一般的にプログラム中で2変数の値を交換するには，一時変数を用いて交換できます．

一時変数を用いた一般的な値の交換方法は，C言語では次のように書けます．

void swap_tmp(int *a, int *b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

しかし一時変数を使わずとも，ビット演算子 ^（排他的論理和：XOR）を用いることでも
2変数の値を交換することができます．

これは，((a XOR b) XOR a) = a という関係式が成り立つことによります．

この XOR を用いた値の交換方法は，C言語では次のように書けます．

void swap_xor(int *a, int *b) {
	*b ^= *a;
	*a ^= *b;
	*b ^= *a;
}

XOR を用いる方法では，この方法を知らないと何をしているのか理解しにくく，可読性の観点から言えば，明らかに一時変数を用いる方法の方がよさそうです．

ところで，C言語ではインラインアセンブラの機能を用いて，簡単にアセンブラを使用することができます．

アセンブラは，機械語と1対1で対応していますから，適切に使えばC言語の命令よりも少ないクロック数で実行でき，速度向上につなげることができます．

先ほどのC言語の XOR の方法を，アセンブラで書き直せば次のように書けます．

void swap_asm(int *a, int *b) {
	__asm {
		MOV EBX, a
		MOV EDX, b
		MOV EAX, [EBX]
		MOV ECX, [EDX]
		XOR ECX, EAX
		XOR EAX, ECX
		XOR ECX, EAX
		MOV [EBX], EAX
		MOV [EDX], ECX
	}
}

さらに，アセンブラにはレジストリの値を交換する命令 XCHG があります．

XCHG を用いて書き直すと，先ほどのアセンブラの例は次のように書き直せます．

void swap_asm2(int *a, int *b) {
	__asm {
		MOV EBX, a
		MOV EDX, b
		MOV EAX, [EBX]
		MOV ECX, [EDX]
		XCHG EAX, ECX
		MOV [EBX], EAX
		MOV [EDX], ECX
	}
}

さて同じC言語でこのようにざっとあげるだけでも，一般的な一時変数を使う方法，XOR を使う方法，アセンブラの XOR を使う方法，アセンブラの XCHG を使う方法と4種類もの方法が挙げられます．

ここで，これら4種の実行速度を比較してみましょう．試しに，私の環境（Windows 7，Visual Studio C++ 2008 x86，念のためコンパイラオプション /Od）で実行速度を計測してみました．計測プログラムは今までのプログラムを組み合わせ，次のようにしました．

#include <stdio.h>
#include <Windows.h>

#define CNT	400000000	// 繰り返す回数
#define V1	19841		// 初期値1
#define V2	987253		// 初期値2

void swap_xor(int *a, int *b);	// CのXOR演算子を用いる
void swap_tmp(int *a, int *b);	// 一時変数を用いる
void swap_asm(int *a, int *b);	// アセンブラのXORを用いる
void swap_asm2(int *a, int *b);	// アセンブラのXCHGを用いる
int getTime(void);

（※ 何故かこの環境では下の main 関数が syntaxhighlighter でうまく表示されないのですがどうしてでしょう…．）

int main(void) {
int t0, t1, t2, t3, t4;
unsigned int i;
int a, b;

t0 = getTime();
for (i = 0; i < CNT; i++) swap_xor(&a, &b); t1 = getTime(); for (i = 0; i < CNT; i++) swap_tmp(&a, &b); t2 = getTime(); for (i = 0; i < CNT; i++) swap_asm(&a, &b); t3 = getTime(); for (i = 0; i < CNT; i++) swap_asm2(&a, &b); t4 = getTime(); printf("SWAP %d times\n", CNT); printf("SWAP_XOR\t: %d\tms\n", t1 - t0); printf("SWAP_TMP\t: %d\tms\n", t2 - t1); printf("SWAP_ASM\t: %d\tms\n", t3 - t2); printf("SWAP_ASM2\t: %d\tms\n", t4 - t3); }

void swap_xor(int *a, int *b) {
	*b ^= *a;
	*a ^= *b;
	*b ^= *a;
}

void swap_tmp(int *a, int *b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void swap_asm(int *a, int *b) {
	__asm {
		MOV EBX, a
		MOV EDX, b
		MOV EAX, [EBX]
		MOV ECX, [EDX]
		XOR ECX, EAX
		XOR EAX, ECX
		XOR ECX, EAX
		MOV [EBX], EAX
		MOV [EDX], ECX
	}
}

void swap_asm2(int *a, int *b) {
	__asm {
		MOV EBX, a
		MOV EDX, b
		MOV EAX, [EBX]
		MOV ECX, [EDX]
		XCHG EAX, ECX
		MOV [EBX], EAX
		MOV [EDX], ECX
	}
}

int getTime(void) {
	SYSTEMTIME t;
	
	GetLocalTime(&t);
	return ((t.wMinute * 60 + t.wSecond) * 1000) + t.wMilliseconds;
}

実行してみると，私の環境では次のようになりました．

SWAP 400000000 times
SWAP_XOR        : 2420  ms
SWAP_TMP        : 1340  ms
SWAP_ASM        : 1241  ms
SWAP_ASM2       : 1210  ms

はじめにアセンブラを用いない，純粋なC言語のみを用いた方法を比べてみると，XOR を用いる方法は，一時変数を用いる方法のおよそ倍の時間がかかってしまいました．

このことより，可読性の観点からも実行速度の観点からも，一時変数を用いる方法の方が優れていることがわかりました．

XOR の方法が遅い原因としては，一時変数の方法では代入を3回繰り返すだけなのに対し，XOR の方法では，ビット演算3回と代入を3回行っているからだと考えられます．

アセンブラの XOR の方法では，一時変数を用いる方法よりもやや実行速度が優れていました．流石アセンブラというべきでしょうか．

おそらく，一時変数の方法よりもメモリアクセスの回数が減っているからではないでしょうか（あまり確証は持てませんが）．

アセンブラの XCHG を用いる方法では，アセンブラの XOR の方法よりもさらにやや早くなっています．

これは，XOR は 1 クロック命令で3回実行しているので 3 クロック，XCHG 命令は EAX レジスタを用いる場合 2 クロック命令であり，XOR の方法よりも 1 クロック短いことが影響しているのではないかと考えられます．

C言語のみでの XOR による方法では，変数を1つ節約できるものの，組み込み開発などの特殊な環境を除けば変数1つの大きさが問題となることは考えられにくく，実行速度や可読性の観点から言っても XOR による方法を用いる理由はほぼないと考えられます．

アセンブラを用いる方法では，確かにやや実行速度が改善されるものの，可読性が低下され，他の人が読むことになったとき，その人もアセンブラが使えるとは限らないので，よほどの高速化を望まない限りはあまり積極的に採用する理由はなさそうです．

結局，C言語で変数の値を交換（Swap）するには，無難に一時変数を用いるのがよいと思われます．