koie blog

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

やっぱり二分探索かな。

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();
}

順番はかなり入れ換わっているが、これだと分岐予測が当らないからよくないなぁ。(早い話、分岐予測的にはまったく改善されてない。)

最近の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

• http://gcc.gnu.org/onlinedocs/libstdc++/manual/debug.html#debug.gdb

gcc -std=でどの規格にあわせるか指定できるが、さて何が違うのか細いところはわからないので調べてみたが、やっぱりわからなかった。

gcc47 (FreeBSD Ports Collection) 4.7.0 20111015 (experimental)

表の展開してもその先も調べないとわからんなぁ。そもそも展開したこと自体失敗だった。