記事検索
月別アーカイブ
アクセスカウンター

    タグ絞り込み検索

    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
    

    やっぱり二分探索かな。

    koie



    このエントリーをはてなブックマークに追加
    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();
    }
    

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

    koie



    このエントリーをはてなブックマークに追加
    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

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



    このエントリーをはてなブックマークに追加