この記事は C言語 Advent Calender 2021 の20日目の記事です（Qiita初投稿です）。
では、
分岐を少なくする
なるべく制御構造を単純化する。分岐は命令のプリフェッチを乱すため、性能低下の原因となる。
という最適化が紹介されています。この最適化をC言語で試してみました。
プログラム実行環境
- CPU: Intel Core i5-10210U
- メモリ: 8.00 GB
- OS: Windows 10、WSL上のUbuntu 20.04.2 LTS
- コンパイラ: GCC 9.3.0
プログラム1 最適化前
ソースファイル "1-1.c"
疑似乱数を生成しながら、偶数と奇数の出現回数をカウントします。また、この処理の実行時間（秒）を測定します。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void)
{
long even = 0;
long odd = 0;
clock_t start = clock();
for (int i = 0; i < 1000; i++) {
srand(0);
for (int j = 0; j < 1000000; j++) {
int r = rand();
if ((r % 2) == 0) {
even++;
} else {
odd++;
}
}
}
clock_t end = clock();
printf("sec: %f\n", (double) (end - start) / CLOCKS_PER_SEC);
printf("even: %ld\n", even);
printf("odd: %ld\n", odd);
return 0;
}
実行結果
$ gcc -O3 1-1.c
$ ./a.out
sec: 11.656250
even: 500155000
odd: 499845000
プログラム1 最適化後
ソースファイル "1-2.c"
if ((r % 2) == 0) {
even++;
} else {
odd++;
}
を
even += ((r % 2) == 0);
odd += ((r % 2) != 0);
に置き換えます。
実行結果
$ gcc -O3 1-2.c
$ ./a.out
sec: 6.718750
even: 500155000
odd: 499845000
分岐を少なくすることで、実行時間が約42%短くなりました。
$ gcc -O3 -S -g 1-1.c
$ gcc -O3 -S -g 1-2.c
でアセンブラファイルを出力、確認したところ、JE命令が減っていることが確認できました。
実際に採用するかどうかはコードの可読性などとのトレードオフになりますが、このケースでは分岐を少なくする最適化は有効と言えそうです。
また、分岐を少なくすることでループ毎の実行時間が一定に近づき、最悪実行時間を予測しやすくなるので、信号処理などのリアルタイム性が求められる処理（時間制約を満たす必要がある処理）にも効果的だと思います。
プログラム2 最適化前
ソースファイル "2-1.c"
時間測定前に、あらかじめ rand() の結果を配列に入れておくようにします。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static int rand_array[1000000];
int main(void)
{
long even = 0;
long odd = 0;
srand(0);
for (int j = 0; j < 1000000; j++) {
rand_array[j] = rand();
}
clock_t start = clock();
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < 1000000; j++) {
int r = rand_array[j];
if ((r % 2) == 0) {
even++;
} else {
odd++;
}
}
}
clock_t end = clock();
printf("sec: %f\n", (double) (end - start) / CLOCKS_PER_SEC);
printf("even: %ld\n", even);
printf("odd: %ld\n", odd);
return 0;
}
実行結果
$ gcc -O3 2-1.c
$ ./a.out
sec: 4.703125
even: 5001550000
odd: 4998450000
プログラム2 最適化後
ソースファイル "2-2.c"
ソースファイル "2-1.c" に ソースファイル "1-2.c" と同様の変更を加えます。
実行結果
$ gcc -O3 2-2.c
$ ./a.out
sec: 4.000000
even: 5001550000
odd: 4998450000
分岐を少なくすることで、実行時間が約15%短くなりました。
アセンブラファイルを出力、確認したところ、最適化前からMOVDQA等のSIMD命令が使われていました。このようなケースでは、分岐を少なくする最適化の効果が小さくなるようです。
ただし、以下のようにGCCの最適化オプションが -O2 の場合はSIMD命令が使われず、分岐を少なくする最適化の効果が大きく（実行時間が約82%短く）なりました。高速な実行を目指すプログラムでは、このオプションは採用しないと思いますが。
$ gcc -O2 2-1.c
$ ./a.out
sec: 34.437500
even: 5001550000
odd: 4998450000
$ gcc -O2 2-2.c
$ ./a.out
sec: 6.250000
even: 5001550000
odd: 4998450000