__builtin_expectの効力

RLogをいじってて知った__builtin_expectを試してみた。__builtin_expectはある式がほとんどの場合に決まった定数になる、と言う場合に分岐予測のヒントなどを与えて高速化を計るためのgccディレクティブだそうな。
RLogはdormant(休眠)状態のログファシリティに最適化してあって、プロダクションコードにログコードを残しっぱなしでもさほどデグレしないのが売りなんだけど、そのカラクリがこれ。
で、RLog自身についてはあとで書く。

どうかく？

具体的には

__builtin_expect(A,B)

と書いた場合 Aが定数 Bである事を期待する、というヒント情報になる。
例えば、比較演算子がほとんどの場合成り立たない、と言う場合 __builtin_expect(, 0)　となる。

#include <stdio.h>

#ifdef EXPECT
#define EXP(foo, bar)  __builtin_expect((foo), (bar))
#else
#define EXP(foo, bar)  (foo)
#endif

#define  N 0x7fffffff
int foo(int x)
{
    if (EXP((x>N-2), 0) == 1)
      printf("%d\n", x);
    return x+1;
}

main()
{
    int i;
    for (i = 0; i< N; ) {
        i = foo(i);
    }
}

てな感じに書いてみる。
ビルドはこんな感じ。

base_exp: $(SRC)
        $(CC) -O2 -DEXPECT $^ -o $@
base_normal: $(SRC)
        $(CC) -O2 $^ -o $@

実は -freorder-blocksをつけてコードを移動できるようにしておかないと、せっかくのexpect情報もあんまり役に立たないみたいなので -O2にしてある。

結果

で、timeでテスト。

model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz

tkuro@sawshark> time ./base_normal
~/Exp/__builtin_expect
2147483646
./base_normal  7.18s user 0.00s system 99% cpu 7.188 total
tkuro@sawshark> time ./base_exp
~/Exp/__builtin_expect
2147483646
./base_exp  5.39s user 0.00s system 99% cpu 5.397 total

ぬお、確かに速くなっている。
違いと言うのが下のような感じ。左がnormal、右が exp。

        cmpl    $2147483645, %edi                                       cmpl    $2147483645, %edi
        .cfi_offset 3, -16                                              .cfi_offset 3, -16
        jle     .L2                                           |         jg      .L5
                                                              > .L2:
                                                              >         leal    1(%rbx), %eax
                                                              >         popq    %rbx
                                                              >         ret
                                                              > .L5:
        movl    %edi, %edx                                              movl    %edi, %edx
        movl    $.LC0, %esi                                             movl    $.LC0, %esi
        movl    $1, %edi                                                movl    $1, %edi
        xorl    %eax, %eax                                              xorl    %eax, %eax
        call    __printf_chk                                            call    __printf_chk
.L2:                                                          |         jmp     .L2
        leal    1(%rbx), %eax                                 <
        popq    %rbx                                          <
        ret                                                   <
        .cfi_endproc                                                    .cfi_endproc

つまりexpしてると、ほとんどの場合成立する edi < 0x7fffffff-2　の場合に分岐しないようになっている、と。実際には分岐予測によって成立不成立自体はあたるんだろうけど、ギャップ分かな。こんなもんで変わるんだなあー。
ついでなのでIntelからVTuneの評価版を拾ってきて試してみた。

ところ、どうやら例の場所で ちょうど 2Gクロック分normalが余分にかかっている。全部で2Gループなのでつまり1clkペナルティがあるのだね。
IntelにはAMDのAnalystみたいなの無いのかなあ。

ちなみにこれよりもっと凶悪なのがプロファイルを取って、それに応じて最適化を行う方法。profile-based optimization。gccの世界ではfeedback based optimizationと呼ばれているらしい。
具体的にはまず -fprofile-generateで作ったバイナリを実行して、プロファイル情報gcdaファイルを吐いて、-fprofile-use　つきでもう一度コンパイルすると最適化してくれる。
これが恐ろしい。

tkuro@sawshark> time ./base_profile
~/Exp/__builtin_expect
2147483646
./base_profile  1.09s user 0.00s system 98% cpu 1.109 total

にょーーーー。元の7倍近く。

.L7:
        cmpl    $2147483646, %eax
        je      .L27
        cmpl    $2147483645, %eax
        je      .L29
        cmpl    $2147483644, %eax
        je      .L27
        cmpl    $2147483643, %eax
        .p2align 4,,5
        je      .L27
        cmpl    $2147483642, %eax
        .p2align 4,,5
        je      .L27
        cmpl    $2147483641, %eax
        .p2align 4,,5
        je      .L27
        cmpl    $2147483640, %eax
        .p2align 4,,5
        je      .L27
        cmpl    $2147483639, %eax
        .p2align 4,,5
        je      .L27
        addl    $9, %eax
        cmpl    $2147483647, %eax
        .p2align 4,,3
        je      .L27
        cmpl    $2147483646, %eax
        .p2align 4,,3
        jne     .L7
        movl    $2147483646, %edx
        movl    $.LC0, %esi

勝手にアンローリングしよった。

結論

バイナリアンの世界は奥が深い。

おまけ

Makefileつけとこっと。

ALL=base_profile base_profile.s base_exp base_exp.s base_normal base_normal.s
SRC=base.c

all: $(ALL)
base_profile: $(SRC) base.gcda
        $(CC) -fprofile-use $< -O2 -o $@

base_profile.s: $(SRC) base.gcda
        $(CC) -fprofile-use $< -O2 -S -o $@

base.gcda: base_tmp
        ./base_tmp
        rm -f ./base_tmp

base_tmp: $(SRC)
        $(CC) -fprofile-generate $^ -O2 -o base_tmp

base_exp: $(SRC)
        $(CC) -O2 -DEXPECT $^ -o $@

base_exp.s: $(SRC)
        $(CC) -O2 -DEXPECT $^ -o $@ -S

base_normal: $(SRC)
        $(CC) -O2 $^ -o $@

base_normal.s: $(SRC)
        $(CC) -O2 $^ -o $@ -S

clean:
        rm $(ALL) base.gcda