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

この記事は 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"

ソースファイル "1-1.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