こんにちは。42 Tokyo Advent Calendar 2023の21日目を担当致します、42 Tokyo在校生の者です。

Overview

アルゴリズムの異なる3種類のswap関数を比較してみました。
なお今回は、言語はC、データ型は整数型 (int) に限定しています。

TOC

Introduction

swap関数とは、引数に取った2つの変数の値を交換する機能を担っているコードの事です。
本記事の投稿日は12月21日ですが、この日付がちょうど月と日とで十の位と一の位をswapしたような数字になっています。

Environment

OSやCPUアーキテクチャの異なる5つの環境で試しました。

Intel Mac

**hostname**% uname -a
Darwin **hostname** 18.7.0 Darwin Kernel Version 18.7.0: Tue Jun 22 19:37:08 PDT 2021; root:xnu-4903.278.70~1/RELEASE_X86_64 x86_64
**hostname**% cc --version
Apple clang version 11.0.0 (clang-1100.0.33.17)
Target: x86_64-apple-darwin18.7.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

Windows PC

**user@hostname**:~/test/swap$ uname -a
Linux **hostname** 5.15.133.1-microsoft-standard-WSL2 #1 SMP Thu Oct 5 21:02:42 UTC 2023 x86_64 x86_64 x86_64 GNU/Linux
**user@hostname**:~/test/swap$ cc --version
cc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

M1 Mac

**user@hostname** swap % uname -a
Darwin **hostname** 22.6.0 Darwin Kernel Version 22.6.0: Wed Jul  5 22:22:52 PDT 2023; root:xnu-8796.141.3~6/RELEASE_ARM64_T8103 arm64
**user@hostname** swap % cc --version
Apple clang version 14.0.3 (clang-1403.0.22.14.1)
Target: arm64-apple-darwin22.6.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

Raspberry Pi

**user@hostname**:/mnt/usb0/swap$ uname -a
Linux **hostname** 5.4.0-1094-raspi #105-Ubuntu SMP PREEMPT Tue Sep 12 08:48:48 UTC 2023 aarch64 aarch64 aarch64 GNU/Linux
**user@hostname**:/mnt/usb0/swap$ cc --version
cc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Jetson AGX Orin

**user@hostname**:/mnt/usb0/swap$ uname -a
Linux **hostname** 5.10.104-tegra #1 SMP PREEMPT Sun Mar 19 07:55:28 PDT 2023 aarch64 aarch64 aarch64 GNU/Linux
**user@hostname**:/mnt/usb0/swap$ cc --version
cc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Methods

3種類のアルゴリズムで swap関数をコーディングし、
コンパイル時にアセンブルコードも出力するとともに、関数が所定回数実行されるのに掛かる時間を比較しました。

Temporary

最も一般的な実装は、ローカル変数tmpを宣言して、2つの変数のうち一方の値をtmpに一時退避するものです。
(以下「tmp」と略す)

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

	tmp = *a;
	*a = *b;
	*b = tmp;
}

XOR

2つ目は、ローカル変数を追加せず、排他的論理和を取る事で値を交換する方法です。
(以下「xor」と略す)
引数に同じ変数への参照が渡された場合、値の情報は失われます。

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

Difference

3つ目は、2つの引数両方の情報を残しつつ両者間で和差を取る事で値を交換する方法です。
(以下「dif」と略す)
情報落ちする事があるため浮動小数点数型には向かず、
整数型に適用する場合でもオーバーフローが発生する事に留意します。
こちらも、引数に同じ変数への参照が渡された場合には、値の情報が失われます。

void	swap_dif(int *a, int *b)
{
	*a = *a - *b;
	*b = *a + *b;
	*a = *b - *a;
}
/*
	a' = a - b
	b' = a' + b
	   = (a - b) + b
	   = a
	a'' = b' - a'
		= a - (a - b)
		= b
*/

Test_function

clock() を用いて、
CLOCKS_PER_SEC × 1000回繰り返すのに掛かる ~~クロック数~~ プロセッサ時間を計測しました。

static void	test(int *a, int *b, void (*f)(int *, int *))
{
	clock_t	clock_begin;
	clock_t	clock_end;
	time_t	time_begin;
	time_t	time_end;

	for (int i = 0; i < my_sqrt(N_CYCLES); i++)
		f(a, b);
	time_begin = time(NULL);
	clock_begin = clock();
	for (int i = 0; i < N_CYCLES; i++)
		f(a, b);
	clock_end = clock();
	time_end = time(NULL);
	printf("[%p]\t%ld clocks\n", f, clock_end - clock_begin);
	printf("[%p]\t%ld seconds\n", f, time_end - time_begin);
}

int	main(int argc, char *argv[])
{
	int	a;
	int	b;

	a = 3;
	b = -4;
	if (argc == 3)
	{
		a = atoi(argv[1]);
		b = atoi(argv[2]);
	}
	test(&a, &b, &swap_tmp);
	test(&a, &b, &swap_tmps);
	test(&a, &b, &swap_xor);
	test(&a, &b, &swap_dif);
	return (0);
}

Results

結論から申し上げると、いずれの環境においても、
xor 及び dif よりも、tmp の方が処理時間が短くなりました。
試しに、ローカル変数を複数個宣言して全てを使用して退避させてみたところ (「tmps」)、
Intel Mac環境ではローカル変数が6個程度で所要時間が同程度となりました。

※GitHubにコード及びログを格納してあります。

各アルゴリズムの所要時間

~~クロック数~~ プロセッサ時間及び現実の経過秒数を、上から tmp, tmps, xor, dif の順に示してあります。

Intel Mac

test_osx.log

[0x10967bbc0]	3047394 clocks
[0x10967bbc0]	3 seconds
[0x10967bbf0]	4923296 clocks
[0x10967bbf0]	5 seconds
[0x10967bc40]	4666046 clocks
[0x10967bc40]	5 seconds
[0x10967bc90]	4683820 clocks
[0x10967bc90]	5 seconds

Windows PC

test_wsl.log

[0x56069cdca1c9]	1909657 clocks
[0x56069cdca1c9]	2 seconds
[0x56069cdca1fa]	2613570 clocks
[0x56069cdca1fa]	3 seconds
[0x56069cdca249]	2956320 clocks
[0x56069cdca249]	3 seconds
[0x56069cdca298]	2929133 clocks
[0x56069cdca298]	3 seconds

M1 Mac

test_m1.log

[0x10089fa8c]	3560843 clocks
[0x10089fa8c]	4 seconds
[0x10089fac8]	8076966 clocks
[0x10089fac8]	8 seconds
[0x10089fb2c]	10057649 clocks
[0x10089fb2c]	10 seconds
[0x10089fb94]	10026761 clocks
[0x10089fb94]	10 seconds

Jetson AGX Orin

test_orin.log

[0xaaaac56e090c]	3845464 clocks
[0xaaaac56e090c]	4 seconds
[0xaaaac56e094c]	9710143 clocks
[0xaaaac56e094c]	10 seconds
[0xaaaac56e09b4]	6949651 clocks
[0xaaaac56e09b4]	7 seconds
[0xaaaac56e0a20]	6911952 clocks
[0xaaaac56e0a20]	7 seconds

Raspberry Pi

test_rpi.log

[0xaaaac353490c]	26269338 clocks
[0xaaaac353490c]	27 seconds
[0xaaaac353494c]	66352269 clocks
[0xaaaac353494c]	66 seconds
[0xaaaac35349b4]	43386985 clocks
[0xaaaac35349b4]	44 seconds
[0xaaaac3534a20]	43401960 clocks
[0xaaaac3534a20]	43 seconds

Discussion

アセンブルコードを参照したところ、
xor や dif よりも tmp の方が行数が少なく、tmps も相応の行数であった事から、
行数と処理時間の間に相関があるように思いました。
しかしRaspberry Pi環境では、tmps が xor や dif と比較して、行数が少ないにもかかわらず時間が大幅に掛かっていました。
調査し切れていないのですが、命令セットやレジスタのサイズ・個数、その他回路設計などのアーキテクチャが関係しているのかも知れません。

各環境のCPUは、以下の通り。

Intel Mac
Intel Core i5-8500, Coffee Lake / 14++nm @ 3.0GHz (6 cores)
Windows PC
Intel Core i5-1235U, Alder Lake / Intel 7 (2 P-cores, 8 E-cores)
M1 Mac
Apple M1 @ 3.2GHz (8 cores)
Jetson AGX Orin
12-core Arm Cortex-A78AE v8.2 64-bit @ 2.2GHz
Raspberry Pi 4B
Broadcom BCM2711, Quad core Cortex-A72 (ARM v8) 64-bit SoC @ 1.8GHz

Editorial_notes

一時変数を使用する一般的な実装が実行速度が速いというのは、意外でした。
一般的に加算・減算よりもビット演算の方が高速と言われますが、。
今後ドヤ顔でswap関数を見せつけてくる人には、「それってどんなメリットがあるの?」と尋ねたいと思います。
他にもswap関数のアルゴリズムをご存知でしたら、コメントでご教示頂けますと幸いです。

References