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
やっぱり二分探索かな。
