__builtin_expectの効力
RLogをいじってて知った__builtin_expectを試してみた。__builtin_expectはある式がほとんどの場合に決まった定数になる、と言う場合に分岐予測のヒントなどを与えて高速化を計るためのgccディレクティブだそうな。
RLogはdormant(休眠)状態のログファシリティに最適化してあって、プロダクションコードにログコードを残しっぱなしでもさほどデグレしないのが売りなんだけど、そのカラクリがこれ。
で、RLog自身についてはあとで書く。
どうかく？
具体的には
__builtin_expect(A,B)
と書いた場合 Aが定数 Bである事を期待する、というヒント情報になる。
例えば、比較演算子がほとんどの場合成り立たない、と言う場合 __builtin_expect(
#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
