http://www.initialt.org/takehiro-switch-case.PDF
いまどきのCPUには漏れなく分岐予測があるので予測が当る可能性が高いものからif文を書くのが良いという話。
gccにはプロファイルをもとに最適化する機能があるので、どこまでやってくれるか試してみた。
// main.c
#include <stdio.h>
#include <stdlib.h>
extern int f(int);
int
main(int ac, char **av)
{
const int x = atoi(av[1]);
printf("%d -> %d\n", x, func(x));
return 0;
}
// func.c
extern int func0(void);
extern int func2(void);
extern int func3(void);
int
func(int x)
{
if (x < 2)
return func0();
if (x == 2)
return func2();
return func3();
}
// impl.c
int func0(void) { return 0; }
int func2(void) { return 2; }
int func3(void) { return 3; }
# Makefile GCC = gcc47 CFLAGS0 = -O2 CFLAGS1 = -O2 -fprofile-generate CFLAGS2 = -O2 -fprofile-use OBJS = main.o func.o impl.o all: $(MAKE) clean $(MAKE) pgo CFLAGS="$(CFLAGS0)" cat func.s >func.s0 $(MAKE) clean $(MAKE) pgo CFLAGS="$(CFLAGS1)" cat func.s >func.s1 $(MAKE) test-run $(MAKE) clean0 $(MAKE) pgo CFLAGS="$(CFLAGS2)" cat func.s >func.s2 pgo: $(OBJS) $(GCC) -o $@ $(CFLAGS) $(OBJS) .c.o: $(GCC) -S $(CFLAGS) $< $(GCC) -c $(CFLAGS) $< test-run: ./pgo 0 ./pgo 1 ./pgo 2 ./pgo 3 clean0: -rm -f pgo *.o clean: clean0 -rm -f *.s *.s? *.gc??
普通にコンパイルしたfuncのアセンブリコード(func.s0)
.file "func.c" .text .p2align 4,,15 .globl func .type func, @function func: .LFB0: .cfi_startproc cmpl $1, %edi jle .L5 cmpl $2, %edi je .L6 jmp func3 .p2align 4,,10 .L6: jmp func2 .p2align 4,,10 .L5: jmp func0 .cfi_endproc .LFE0: .size func, .-func .ident "GCC: (FreeBSD Ports Collection) 4.7.1 20120324 (prerelease)" .section .note.GNU-stack,"",@progbits
ソースコードどおりに生成されているようだ。
PGO付きでコンパイルしたfuncのアセンブリコード(func.s2)
.file "func.c" .text .p2align 4,,15 .globl func .type func, @function func: .LFB0: .cfi_startproc cmpl $1, %edi jg .L2 jmp func0 .L2: cmpl $2, %edi jne .L3 .p2align 4,,5 jmp func2 .L3: .p2align 4,,5 jmp func3 .cfi_endproc .LFE0: .size func, .-func .ident "GCC: (FreeBSD Ports Collection) 4.7.1 20120324 (prerelease)" .section .note.GNU-stack,"",@progbits
逆アセンブルするとこんな感じか?
int func(int x) {
if (x > 1) {
if (x != 2) {
return func3();
}
return func2();
}
return func0();
}
順番はかなり入れ換わっているが、これだと分岐予測が当らないからよくないなぁ。(早い話、分岐予測的にはまったく改善されてない。)
