gcc
2014年12月05日18:11gccのswitch文最適化
gccはswitch文でcaseが連続してると表を牽くようになるってきいたことがあったので確かめてみた。
int
foo(int x)
{
//値が連続している
switch (x) {
case 10: return 0;
case 11: return 1;
case 12: return 2;
case 13: return 3;
case 14: return 4;
case 15: return 5;
}
return -1;
}
int
bar(int x)
{
//値が10step
switch (x) {
case 100: return 0;
case 110: return 1;
case 120: return 2;
case 130: return 3;
case 140: return 4;
case 150: return 5;
}
return -1;
}
int
buz(int x)
{
//値が100step
switch (x) {
case 1000: return 0;
case 1100: return 1;
case 1200: return 2;
case 1300: return 3;
case 1400: return 4;
case 1500: return 5;
}
return -1;
}
gcc47 -O9 -Sでコンパイルしてみると、10飛びくらいなら表にしてしまうが100飛びだとさすがにそれはしなくて素直に条件分岐、とおもったら全然素直じゃねぇ。
.file "foo.c" .text .p2align 4,,15 .globl foo .type foo, @function foo: .LFB0: .cfi_startproc subl $10, %edi movl $-1, %eax cmpl $5, %edi ja .L2 movl CSWTCH.2(,%rdi,4), %eax .L2: rep ret .cfi_endproc .LFE0: .size foo, .-foo .p2align 4,,15 .globl bar .type bar, @function bar: .LFB1: .cfi_startproc subl $100, %edi movl $-1, %eax cmpl $50, %edi ja .L6 movsbl CSWTCH.5(%rdi), %eax .L6: rep ret .cfi_endproc .LFE1: .size bar, .-bar .p2align 4,,15 .globl buz .type buz, @function buz: .LFB2: .cfi_startproc cmpl $1200, %edi movl $2, %eax je .L11 jle .L24 cmpl $1400, %edi movl $4, %eax je .L11 cmpl $1500, %edi movb $5, %al je .L11 cmpl $1300, %edi movb $3, %al je .L11 .L9: movl $-1, %eax .p2align 4,,10 .L11: rep ret .p2align 4,,10 .L24: xorb %al, %al cmpl $1000, %edi je .L11 cmpl $1100, %edi movb $1, %al jne .L9 rep ret .cfi_endproc .LFE2: .size buz, .-buz .section .rodata .align 16 .type CSWTCH.2, @object .size CSWTCH.2, 24 CSWTCH.2: .long 0 .long 1 .long 2 .long 3 .long 4 .long 5 .align 32 .type CSWTCH.5, @object .size CSWTCH.5, 51 CSWTCH.5: .byte 0 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte 1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte 2 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte 3 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte 4 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte -1 .byte 5 .ident "GCC: (FreeBSD Ports Collection) 4.7.1 20120324 (prerelease)" .section .note.GNU-stack,"",@progbits
二分探索してるんかとおもったら、そうでもなさそう。疑似コードにしてみたらこんな感じ
int
buz(int x)
{
cmp(x, 1200);
r = 2;
if (==)
retun r;
if (<=) {
r = 0;
cmp(x, 1000);
if (==)
return r;
cmp(x, 1100);
r = 1;
if (!=)
return -1;
return r;
}
cmp(x, 1400);
r = 4;
if (==)
return r;
cmp(x, 1500);
r = 5;
if (==)
return r;
cmp(x, 1300);
r = 3;
if (==)
return r;
return -1;
}
もうチョイ複雑でありがちなケースで、即値リターンじゃなくて関数末尾呼び出しだとこうなった。
extern int unko(int);
int
foo(int x)
{
//値が連続している
switch (x) {
case 10: return bar(1);
case 11: return bar(1);
case 12: return bar(2);
case 13: return bar(3);
case 14: return bar(4);
case 15: return bar(5);
}
return -1;
}
int
bux(int x)
{
//値が100step
switch (x) {
case 1000: return bar(1);
case 1100: return bar(1);
case 1200: return bar(2);
case 1300: return bar(3);
case 1400: return bar(4);
case 1500: return bar(5);
}
return -1;
}
これがこうなる
.file "boke.c" .text .p2align 4,,15 .globl foo .type foo, @function foo: .LFB0: .cfi_startproc subl $10, %edi cmpl $5, %edi jbe .L11 movl $-1, %eax ret .p2align 4,,10 .L11: jmp *.L9(,%rdi,8) .section .rodata .align 8 .align 4 .L9: .quad .L4 .quad .L4 .quad .L5 .quad .L6 .quad .L7 .quad .L8 .text .p2align 4,,10 .L4: movl $1, %edi xorl %eax, %eax jmp bar .p2align 4,,10 .L7: movl $4, %edi xorl %eax, %eax jmp bar .p2align 4,,10 .L5: movl $2, %edi xorl %eax, %eax jmp bar .p2align 4,,10 .L6: movl $3, %edi xorl %eax, %eax jmp bar .p2align 4,,10 .L8: movl $5, %edi xorl %eax, %eax jmp bar .cfi_endproc .LFE0: .size foo, .-foo .p2align 4,,15 .globl bux .type bux, @function bux: .LFB1: .cfi_startproc cmpl $1200, %edi je .L16 jle .L21 cmpl $1400, %edi je .L18 cmpl $1500, %edi je .L19 cmpl $1300, %edi je .L22 .L13: movl $-1, %eax ret .p2align 4,,10 .L21: cmpl $1000, %edi je .L15 cmpl $1100, %edi jne .L13 .L15: movl $1, %edi xorl %eax, %eax jmp bar .p2align 4,,10 .L19: movl $5, %edi xorl %eax, %eax jmp bar .p2align 4,,10 .L18: movl $4, %edi xorl %eax, %eax jmp bar .p2align 4,,10 .L16: movl $2, %edi xorl %eax, %eax jmp bar .p2align 4,,10 .L22: movl $3, %edi xorl %eax, %eax jmp bar .cfi_endproc .LFE1: .size bux, .-bux .ident "GCC: (FreeBSD Ports Collection) 4.7.1 20120324 (prerelease)" .section .note.GNU-stack,"",@progbits
疑似コードにするとこんなかんじ。
int
bux(int x)
{
cmp(x, 1200);
if (==)
return bar(2);
if (<=) {
cmp(x, 1000);
if (==)
return bar(1);
cmp(x, 1100);
if (!=)
return -1;
return bar(1);
}
cmp(x, 1400);
if (==)
return bar(4);
cmp(x, 1500);
if (==)
return bar(5);
cmp(x, 1300);
if (==)
return bar(3);
return -1;
}
二分探索と線形探索を組み合わせた感じか？caseを9個に増やしてみる。
1400
/ \
/ \
1100 1700
/ \ / \
1000 1200 1500 1800
| | |
1300 1600 1900
やっぱり二分探索かな。
2012年04月25日15:02PGO: Profile Guided Optimizationをためしてみた
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();
}
順番はかなり入れ換わっているが、これだと分岐予測が当らないからよくないなぁ。(早い話、分岐予測的にはまったく改善されてない。)
2011年12月15日17:55printers.py： gdbでlibstdc++のコンテナをきれいに表示
最近のgcc+gdbはstd::mapをprintすると
(gdb) p m
$1 = std::map with 3 elements = {[1] = 1, [2] = 4, [3] = 9}
というふうにプリティプリントしてくれる。これまではメンバ変数が丸見えになるだけで、内容はわからなかった。
(gdb) p m
$1 = {_M_t = {
_M_impl = {<std::allocator<std::_Rb_tree_node<std::pair<const int, int> > >> = {<__gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<const int, int> > >> = {<No data fields>}, <No data fields>},
_M_key_compare = {<std::binary_function<int, int, bool>> = {<No data fields>}, <No data fields>}, _M_header = {
_M_color = std::_S_red, _M_parent = 0x801407070, _M_left = 0x801407040, _M_right = 0x8014070a0}, _M_node_count = 3}}}
gdbをpythonありでコンパイルすると有効になり、本体は私の環境だと/usr/local/share/gcc-4.7.0/python/libstdcxx/v6/printers.pyにあった。適当に中身を見ると以下のクラスをサポートしているようだ。
__gnu_cxx::_Slist_iterator __gnu_cxx::__normal_iterator __gnu_cxx::slist __gnu_debug::_Safe_iterator std::_Deque_const_iterator std::_Deque_iterator std::_List_const_iterator std::_List_iterator std::_Rb_tree_const_iterator std::_Rb_tree_iterator std::__debug::bitset std::__debug::deque std::__debug::list std::__debug::map std::__debug::multimap std::__debug::multiset std::__debug::priority_queue std::__debug::queue std::__debug::set std::__debug::stack std::__debug::unique_ptr std::__debug::unordered_map std::__debug::unordered_multimap std::__debug::unordered_multiset std::__debug::unordered_set std::__debug::vector std::__norm::_Deque_const_iterator std::__norm::_Deque_iterator std::__norm::_List_const_iterator std::__norm::_List_iterator std::basic_string std::bitset std::deque std::list std::map std::multimap std::multiset std::priority_queue std::queue std::set std::shared_ptr std::stack std::tr1::shared_ptr std::tr1::unordered_map std::tr1::unordered_multimap std::tr1::unordered_multiset std::tr1::unordered_set std::tr1::weak_ptr std::tuple std::unique_ptr std::unordered_map std::unordered_multimap std::unordered_multiset std::unordered_set std::vector std::weak_ptr
2011年12月08日14:23gcc -std=
gcc -std=でどの規格にあわせるか指定できるが、さて何が違うのか細いところはわからないので調べてみたが、やっぱりわからなかった。
gcc47 (FreeBSD Ports Collection) 4.7.0 20111015 (experimental)
| -std= | flag_iso | flag_no_asm | flag_no_gnu_keywords | flag_no_nonansi_builtin | flag_isoc94 | flag_isoc99 | flag_isoc1x |
| -ansi | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| c90 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| iso9899:199409 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| gnu90 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| c99 | 1 | 1 | -1 | 1 | 1 | 1 | 0 |
| gnu99 | 0 | 0 | -1 | 0 | 1 | 1 | 0 |
| c1x | 1 | 1 | -1 | 1 | 1 | 1 | 1 |
| gnu1x | 0 | 0 | -1 | 0 | 1 | 1 | 1 |
| gnu89 = gnu90 | |||||||
| c89 = c90 | |||||||
| iso9899:1990 = c90 | |||||||
| iso9899:1999 = c99 |
表の展開してもその先も調べないとわからんなぁ。そもそも展開したこと自体失敗だった。
