switch为何高效率

来源:互联网 时间:1970-01-01

在用switch的同时,为何能高效,又如何避免编译退化?

arm-linux-objdump的一个基础实验,你懂得。

int main(void){ 834c: e24dd008 sub sp, sp, #8 ; 0x8 int a = 4; 8350: e3a03004 mov r3, #4 ; 0x4 8354: e58d3004 str r3, [sp, #4] switch(a) 8358: e59d3004 ldr r3, [sp, #4] 835c: e3530005 cmp r3, #5 ; 0x5 8360: 908ff103 addls pc, pc, r3, lsl #2 8364: ea00001c b 83dc <main+0x90> 8368: ea000004 b 8380 <main+0x34> 836c: ea000007 b 8390 <main+0x44> 8370: ea00000a b 83a0 <main+0x54> 8374: ea00000d b 83b0 <main+0x64> 8378: ea000010 b 83c0 <main+0x74> //通过跳转的方式,空间换时间 837c: ea000013 b 83d0 <main+0x84> { case 0: a++; break; 8380: e59d3004 ldr r3, [sp, #4] 8384: e2833001 add r3, r3, #1 ; 0x1 8388: e58d3004 str r3, [sp, #4] 838c: ea000012 b 83dc <main+0x90> case 1: a++; break; 8390: e59d3004 ldr r3, [sp, #4] 8394: e2833001 add r3, r3, #1 ; 0x1 8398: e58d3004 str r3, [sp, #4] 839c: ea00000e b 83dc <main+0x90> case 2: a++; break; 83a0: e59d3004 ldr r3, [sp, #4] 83a4: e2833001 add r3, r3, #1 ; 0x1 83a8: e58d3004 str r3, [sp, #4] 83ac: ea00000a b 83dc <main+0x90> case 3: a++; break; 83b0: e59d3004 ldr r3, [sp, #4] 83b4: e2833001 add r3, r3, #1 ; 0x1 83b8: e58d3004 str r3, [sp, #4] 83bc: ea000006 b 83dc <main+0x90> case 4: a++; break; 83c0: e59d3004 ldr r3, [sp, #4] 83c4: e2833001 add r3, r3, #1 ; 0x1 83c8: e58d3004 str r3, [sp, #4] 83cc: ea000002 b 83dc <main+0x90> case 5: a++; break; 83d0: e59d3004 ldr r3, [sp, #4] 83d4: e2833001 add r3, r3, #1 ; 0x1 83d8: e58d3004 str r3, [sp, #4] default: break; } return 0; 83dc: e3a03000 mov r3, #0 ; 0x0}

再来试一些不规则的case。

int main(void){ 834c: e24dd008 sub sp, sp, #8 ; 0x8 int a = 9; 8350: e3a03009 mov r3, #9 ; 0x9 8354: e58d3004 str r3, [sp, #4] switch(a) 8358: e59d3004 ldr r3, [sp, #4] 835c: e3530009 cmp r3, #9 ; 0x9 8360: 908ff103 addls pc, pc, r3, lsl #2 8364: ea000020 b 83ec <main+0xa0> 8368: ea000008 b 8390 <main+0x44> 836c: ea00000b b 83a0 <main+0x54> 8370: ea00000e b 83b0 <main+0x64> 8374: ea00001c b 83ec <main+0xa0> 8378: ea000018 b 83e0 <main+0x94> 837c: ea00001a b 83ec <main+0xa0> 8380: ea000012 b 83d0 <main+0x84> 8384: ea000018 b 83ec <main+0xa0> 8388: ea000017 b 83ec <main+0xa0> 838c: ea00000b b 83c0 <main+0x74> //发生了看似不规则的变化,跳转未按地址顺序排列 { case 0: a++; break; 8390: e59d3004 ldr r3, [sp, #4] 8394: e2833001 add r3, r3, #1 ; 0x1 8398: e58d3004 str r3, [sp, #4] 839c: ea000012 b 83ec <main+0xa0> case 1: a++; break; 83a0: e59d3004 ldr r3, [sp, #4] 83a4: e2833001 add r3, r3, #1 ; 0x1 83a8: e58d3004 str r3, [sp, #4] 83ac: ea00000e b 83ec <main+0xa0> case 2: a++; break; 83b0: e59d3004 ldr r3, [sp, #4] 83b4: e2833001 add r3, r3, #1 ; 0x1 83b8: e58d3004 str r3, [sp, #4] 83bc: ea00000a b 83ec <main+0xa0> case 9: a++; break; 83c0: e59d3004 ldr r3, [sp, #4] 83c4: e2833001 add r3, r3, #1 ; 0x1 83c8: e58d3004 str r3, [sp, #4] 83cc: ea000006 b 83ec <main+0xa0> case 6: a++; break; 83d0: e59d3004 ldr r3, [sp, #4] 83d4: e2833001 add r3, r3, #1 ; 0x1 83d8: e58d3004 str r3, [sp, #4] 83dc: ea000002 b 83ec <main+0xa0> case 4: a++; break; 83e0: e59d3004 ldr r3, [sp, #4] 83e4: e2833001 add r3, r3, #1 ; 0x1 83e8: e58d3004 str r3, [sp, #4] default: break; } return 0; 83ec: e3a03000 mov r3, #0 ; 0x0}
事物总不是绝对的,switch也是如此。
int main(void){ 834c: e24dd010 sub sp, sp, #16 ; 0x10 int a = 90; 8350: e3a0305a mov r3, #90 ; 0x5a 8354: e58d300c str r3, [sp, #12] switch(a) 8358: e59d300c ldr r3, [sp, #12] 835c: e58d3004 str r3, [sp, #4] 8360: e59d3004 ldr r3, [sp, #4] 8364: e3530002 cmp r3, #2 ; 0x2 8368: 0a00001b beq 83dc <main+0x90> //退化成了 if ! 836c: e59d3004 ldr r3, [sp, #4] 8370: e3530002 cmp r3, #2 ; 0x2 8374: ca000006 bgt 8394 <main+0x48> 8378: e59d3004 ldr r3, [sp, #4] 837c: e3530000 cmp r3, #0 ; 0x0 8380: 0a00000d beq 83bc <main+0x70> 8384: e59d3004 ldr r3, [sp, #4] 8388: e3530001 cmp r3, #1 ; 0x1 838c: 0a00000e beq 83cc <main+0x80> 8390: ea000020 b 8418 <main+0xcc> 8394: e59d3004 ldr r3, [sp, #4] 8398: e3530006 cmp r3, #6 ; 0x6 839c: 0a000016 beq 83fc <main+0xb0> 83a0: e59d3004 ldr r3, [sp, #4] 83a4: e353005a cmp r3, #90 ; 0x5a 83a8: 0a00000f beq 83ec <main+0xa0> 83ac: e59d3004 ldr r3, [sp, #4] 83b0: e3530004 cmp r3, #4 ; 0x4 83b4: 0a000014 beq 840c <main+0xc0> 83b8: ea000016 b 8418 <main+0xcc> { case 0: a++; break; 83bc: e59d300c ldr r3, [sp, #12] 83c0: e2833001 add r3, r3, #1 ; 0x1 83c4: e58d300c str r3, [sp, #12] 83c8: ea000012 b 8418 <main+0xcc> case 1: a++; break; 83cc: e59d300c ldr r3, [sp, #12] 83d0: e2833001 add r3, r3, #1 ; 0x1 83d4: e58d300c str r3, [sp, #12] 83d8: ea00000e b 8418 <main+0xcc> case 2: a++; break; 83dc: e59d300c ldr r3, [sp, #12] 83e0: e2833001 add r3, r3, #1 ; 0x1 83e4: e58d300c str r3, [sp, #12] 83e8: ea00000a b 8418 <main+0xcc> case 90: a++; break; 83ec: e59d300c ldr r3, [sp, #12] 83f0: e2833001 add r3, r3, #1 ; 0x1 83f4: e58d300c str r3, [sp, #12] 83f8: ea000006 b 8418 <main+0xcc> case 6: a++; break; 83fc: e59d300c ldr r3, [sp, #12] 8400: e2833001 add r3, r3, #1 ; 0x1 8404: e58d300c str r3, [sp, #12] 8408: ea000002 b 8418 <main+0xcc> case 4: a++; break; 840c: e59d300c ldr r3, [sp, #12] 8410: e2833001 add r3, r3, #1 ; 0x1 8414: e58d300c str r3, [sp, #12] default: break; } return 0; 8418: e3a03000 mov r3, #0 ; 0x0}
秘密原来就在于此……
0000834c <func>:int func(int a){ 834c: e24dd008 sub sp, sp, #8 ; 0x8 8350: e58d0004 str r0, [sp, #4] switch(a) 8354: e59d3004 ldr r3, [sp, #4] 8358: e3530009 cmp r3, #9 ; 0x9 835c: 908ff103 addls pc, pc, r3, lsl #2 ///看了下面的排列方式,也就清楚了这条指令的内涵 8360: ea000020 b 83e8 <func+0x9c> 8364: ea000008 b 838c <func+0x40> //0 8368: ea00000b b 839c <func+0x50> //1 836c: ea00000e b 83ac <func+0x60> //2 8370: ea00001c b 83e8 <func+0x9c> 8374: ea000018 b 83dc <func+0x90> //4 8378: ea00001a b 83e8 <func+0x9c> 837c: ea000012 b 83cc <func+0x80> //6 8380: ea000018 b 83e8 <func+0x9c> 8384: ea000017 b 83e8 <func+0x9c> 8388: ea00000b b 83bc <func+0x70> //9 { case 0: a++; break; 838c: e59d3004 ldr r3, [sp, #4] 8390: e2833001 add r3, r3, #1 ; 0x1 8394: e58d3004 str r3, [sp, #4] 8398: ea000012 b 83e8 <func+0x9c> case 1: a++; break; 839c: e59d3004 ldr r3, [sp, #4] 83a0: e2833001 add r3, r3, #1 ; 0x1 83a4: e58d3004 str r3, [sp, #4] 83a8: ea00000e b 83e8 <func+0x9c> case 2: a++; break; 83ac: e59d3004 ldr r3, [sp, #4] 83b0: e2833001 add r3, r3, #1 ; 0x1 83b4: e58d3004 str r3, [sp, #4] 83b8: ea00000a b 83e8 <func+0x9c> case 9: a++; break; 83bc: e59d3004 ldr r3, [sp, #4] 83c0: e2833001 add r3, r3, #1 ; 0x1 83c4: e58d3004 str r3, [sp, #4] 83c8: ea000006 b 83e8 <func+0x9c> case 6: a++; break; 83cc: e59d3004 ldr r3, [sp, #4] 83d0: e2833001 add r3, r3, #1 ; 0x1 83d4: e58d3004 str r3, [sp, #4] 83d8: ea000002 b 83e8 <func+0x9c> case 4: a++; break; 83dc: e59d3004 ldr r3, [sp, #4] 83e0: e2833001 add r3, r3, #1 ; 0x1 83e4: e58d3004 str r3, [sp, #4] default: break; } return a; 83e8: e59d3004 ldr r3, [sp, #4]}

最后再来一个极端的实验:

0000834c <func>:int func(int a){ 834c: e24dd008 sub sp, sp, #8 ; 0x8 8350: e58d0004 str r0, [sp, #4] switch(a) 8354: e59d3004 ldr r3, [sp, #4] 8358: e353003c cmp r3, #60 ; 0x3c //这里60是上限,至少要六个case,而且要有 case[0-2],否则编译退化为if 835c: 908ff103 addls pc, pc, r3, lsl #2 8360: ea000053 b 84b4 <func+0x168> 8364: ea00003b b 8458 <func+0x10c> //0 8368: ea00003e b 8468 <func+0x11c> //1 836c: ea000041 b 8478 <func+0x12c> //2 8370: ea00004f b 84b4 <func+0x168> 8374: ea00004b b 84a8 <func+0x15c> 8378: ea00004d b 84b4 <func+0x168> 837c: ea000045 b 8498 <func+0x14c> //6 8380: ea00004b b 84b4 <func+0x168> 8384: ea00004a b 84b4 <func+0x168> 8388: ea000049 b 84b4 <func+0x168> 838c: ea000048 b 84b4 <func+0x168> 8390: ea000047 b 84b4 <func+0x168> 8394: ea000046 b 84b4 <func+0x168> 8398: ea000045 b 84b4 <func+0x168> 839c: ea000044 b 84b4 <func+0x168> 83a0: ea000043 b 84b4 <func+0x168> 83a4: ea000042 b 84b4 <func+0x168> 83a8: ea000041 b 84b4 <func+0x168> 83ac: ea000040 b 84b4 <func+0x168> 83b0: ea00003f b 84b4 <func+0x168> 83b4: ea00003e b 84b4 <func+0x168> 83b8: ea00003d b 84b4 <func+0x168> 83bc: ea00003c b 84b4 <func+0x168> 83c0: ea00003b b 84b4 <func+0x168> 83c4: ea00003a b 84b4 <func+0x168> 83c8: ea000039 b 84b4 <func+0x168> 83cc: ea000038 b 84b4 <func+0x168> 83d0: ea000037 b 84b4 <func+0x168> 83d4: ea000036 b 84b4 <func+0x168> 83d8: ea000035 b 84b4 <func+0x168> 83dc: ea000034 b 84b4 <func+0x168> 83e0: ea000033 b 84b4 <func+0x168> 83e4: ea000032 b 84b4 <func+0x168> 83e8: ea000031 b 84b4 <func+0x168> 83ec: ea000030 b 84b4 <func+0x168> 83f0: ea00002f b 84b4 <func+0x168> 83f4: ea00002e b 84b4 <func+0x168> 83f8: ea00002d b 84b4 <func+0x168> 83fc: ea00002c b 84b4 <func+0x168> 8400: ea00002b b 84b4 <func+0x168> 8404: ea00002a b 84b4 <func+0x168> 8408: ea000029 b 84b4 <func+0x168> 840c: ea000028 b 84b4 <func+0x168> 8410: ea000027 b 84b4 <func+0x168> 8414: ea000026 b 84b4 <func+0x168> 8418: ea000025 b 84b4 <func+0x168> 841c: ea000024 b 84b4 <func+0x168> 8420: ea000023 b 84b4 <func+0x168> 8424: ea000022 b 84b4 <func+0x168> 8428: ea000021 b 84b4 <func+0x168> 842c: ea000020 b 84b4 <func+0x168> 8430: ea00001f b 84b4 <func+0x168> 8434: ea00001e b 84b4 <func+0x168> 8438: ea00001d b 84b4 <func+0x168> 843c: ea00001c b 84b4 <func+0x168> 8440: ea00001b b 84b4 <func+0x168> 8444: ea00001a b 84b4 <func+0x168> 8448: ea000019 b 84b4 <func+0x168> 844c: ea000018 b 84b4 <func+0x168> 8450: ea000017 b 84b4 <func+0x168> 8454: ea00000b b 8488 <func+0x13c> { case 0: a++; break; 8458: e59d3004 ldr r3, [sp, #4] 845c: e2833001 add r3, r3, #1 ; 0x1 8460: e58d3004 str r3, [sp, #4] 8464: ea000012 b 84b4 <func+0x168> case 1: a++; break; 8468: e59d3004 ldr r3, [sp, #4] 846c: e2833001 add r3, r3, #1 ; 0x1 8470: e58d3004 str r3, [sp, #4] 8474: ea00000e b 84b4 <func+0x168> case 2: a++; break; 8478: e59d3004 ldr r3, [sp, #4] 847c: e2833001 add r3, r3, #1 ; 0x1 8480: e58d3004 str r3, [sp, #4] 8484: ea00000a b 84b4 <func+0x168> case 60: a++; break; 8488: e59d3004 ldr r3, [sp, #4] 848c: e2833001 add r3, r3, #1 ; 0x1 8490: e58d3004 str r3, [sp, #4] 8494: ea000006 b 84b4 <func+0x168> case 6: a++; break; 8498: e59d3004 ldr r3, [sp, #4] 849c: e2833001 add r3, r3, #1 ; 0x1 84a0: e58d3004 str r3, [sp, #4] 84a4: ea000002 b 84b4 <func+0x168> case 4: a++; break; 84a8: e59d3004 ldr r3, [sp, #4] 84ac: e2833001 add r3, r3, #1 ; 0x1 84b0: e58d3004 str r3, [sp, #4] default: break; } return a; 84b4: e59d3004 ldr r3, [sp, #4]} 84b8: e1a00003 mov r0, r3 84bc: e28dd008 add sp, sp, #8 ; 0x8 84c0: e12fff1e bx lr

上面的case最大值取了60,若再增加,编译退化。而对于字符 case 'a' ,switch的退化条件有些区别,本质还是一样,不妨自己动手一试。

只是简单的贴了些代码,重在能说明问题的关键,点到为止。


相关阅读:
Top