C言語で分岐を少なくする最適化を試してみた

この記事は [C言語 Advent Calender 2021](https://qiita.com/advent-calendar/2021/_c) の20日目の記事です（Qiita初投稿です）。

https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E6%9C%80%E9%81%A9%E5%8C%96#%E5%90%84%E7%A8%AE%E6%9C%80%E9%81%A9%E5%8C%96

では、

> **分岐を少なくする**
> なるべく制御構造を単純化する。分岐は命令のプリフェッチを乱すため、性能低下の原因となる。

という最適化が紹介されています。この最適化を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"

疑似乱数を生成しながら、偶数と奇数の出現回数をカウントします。また、この処理の実行時間（秒）を測定します。

```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;
}
```

### 実行結果

```bash
$ gcc -O3 1-1.c
$ ./a.out
sec:  11.656250
even: 500155000
odd:  499845000
```

## プログラム1 最適化後

### ソースファイル "1-2.c"

[ソースファイル "1-1.c"](#ソースファイル-1-1c) の

```c
            if ((r % 2) == 0) {
                even++;
            } else {
                odd++;
            }
```

を

```c
            even += ((r % 2) == 0);
            odd  += ((r % 2) != 0);
```

に置き換えます。

### 実行結果

```bash
$ gcc -O3 1-2.c
$ ./a.out
sec:  6.718750
even: 500155000
odd:  499845000
```

分岐を少なくすることで、実行時間が約42%短くなりました。

```bash
$ gcc -O3 -S -g 1-1.c
$ gcc -O3 -S -g 1-2.c
```

でアセンブラファイルを出力、確認したところ、JE命令が減っていることが確認できました。

実際に採用するかどうかはコードの可読性などとのトレードオフになりますが、このケースでは分岐を少なくする最適化は有効と言えそうです。

また、分岐を少なくすることでループ毎の実行時間が一定に近づき、最悪実行時間を予測しやすくなるので、信号処理などのリアルタイム性が求められる処理（時間制約を満たす必要がある処理）にも効果的だと思います。



## プログラム2 最適化前

### ソースファイル "2-1.c"

時間測定前に、あらかじめ `rand()` の結果を配列に入れておくようにします。

```c
#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;
}
```

### 実行結果

```bash
$ gcc -O3 2-1.c
$ ./a.out
sec:  4.703125
even: 5001550000
odd:  4998450000
```

## プログラム2 最適化後

### ソースファイル "2-2.c"

[ソースファイル "2-1.c"](#ソースファイル-2-1c) に [ソースファイル "1-2.c"](#ソースファイル-1-2c) と同様の変更を加えます。

### 実行結果

```bash
$ gcc -O3 2-2.c
$ ./a.out
sec:  4.000000
even: 5001550000
odd:  4998450000
```

分岐を少なくすることで、実行時間が約15%短くなりました。

アセンブラファイルを出力、確認したところ、最適化前からMOVDQA等のSIMD命令が使われていました。このようなケースでは、分岐を少なくする最適化の効果が小さくなるようです。

ただし、以下のようにGCCの最適化オプションが `-O2` の場合はSIMD命令が使われず、分岐を少なくする最適化の効果が大きく（実行時間が約82%短く）なりました。高速な実行を目指すプログラムでは、このオプションは採用しないと思いますが。

```bash
$ 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
```