switch语句性能考量
每年都有应届毕业生来到公司，每年都要对新同事进行代码方面的培训，比如编码规范就是其中之一。编码规范初听起来比较新鲜，但是培训时间长了，显然有些乏味。今年我打算改变策略，让新同事结合已有规范文档和项目代码，自己先挖掘一遍，然后大家通过坐下来讨论的互动方式来加深对规范的理解，每次讨论时间限制在1 hour以内，不给大家打瞌睡的机会^_^。
上周和新同事一起讨论表达式和语句，说到了switch和if，谈到了他们的用途和区别。大家都清楚switch语句被称为多分支语句，当代码中即将出现3个及3个以上分支时，推荐用switch，这样代码可读性好，清晰，格式工整；但是同样switch也是有局限的，就是switch(xx)中的xx必须是整型变量；如果你的条件判断是字符串比较，就无法直接使用switch了。switch的这一局限实际上是有原因的，为什么呢？在于其性能优化。那switch语句在底层到底是如何实现的呢？和if语句相比，switch除了美观之外，优势又在哪里呢？我们唯有到汇编层去看个究竟了。
我们先来看看if多分支的情况：//Windows XP + gcc v3.4.2 (mingw-special)
//testif.c
int test_if_performance(int i) {
int rv = i;
if (rv == 10) {
rv += 100;
} else if (rv == 11) {
rv += 101;
} else if (rv == 12) {
rv += 102;
} else if (rv == 13||rv == 14 || rv == 15) {
rv += 105;
} else {
rv += 0;
}
return rv;
}
我们通过-S选项得到test_if_performance的汇编代码，我们加上了-O2的优化选项：
//gcc -S O2 testif.c
//testif.s
… …
_test_if_performance:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %edx
cmpl $10, %edx
je L11
cmpl $11, %edx
je L12
cmpl $12, %edx
je L13
leal -13(%edx), %eax
cmpl $2, %eax
ja L3
addl $105, %edx
L3:
popl %ebp
movl %edx, %eax
ret
.p2align 4,,7
L11:
popl %ebp
movl $110, %edx
movl %edx, %eax
ret
.p2align 4,,7
L12:
popl %ebp
movl $112, %edx
movl %edx, %eax
ret
.p2align 4,,7
L13:
popl %ebp
movl $114, %edx
movl %edx, %eax
ret
从这段汇编码来看，if语句是逐个判断下来的，如果i = 19的话，程序需要从头判断到尾，"一个都不能少"^_^。那么拥有同样语义功能的switch代码又是如何实现的呢？我们继续看下去。
// testswitch.c 这个文件实现的是和上述testif.c同样的功能
int test_switch_performance(int i) {
int rv = i;
switch(rv) {
case 10:
rv += 100;
break;
case 11:
rv += 101;
break;
case 12:
rv += 102;
break;
case 13:
case 14:
case 15:
rv += 105;
break;
default:
rv += 0;
}
return rv;
}
我们同样用-O2来得到switch的汇编代码：
//gcc -S O2 testswitch.c
//testswitch.s
… …
_test_switch_performance:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %ecx
leal -10(%ecx), %edx
movl %ecx, %eax
cmpl $5, %edx
ja L2
jmp *L10(,%edx,4)
.section .rdata,"dr"
.align 4
L10:
.long L3
.long L4
.long L5
.long L8
.long L8
.long L8
.text
.p2align 4,,7
L8:
leal 105(%ecx), %eax
.p2align 4,,15
L2:
popl %ebp
ret
.p2align 4,,7
L3:
popl %ebp
leal 100(%ecx), %eax
ret
.p2align 4,,7
L4:
popl %ebp
leal 101(%ecx), %eax
ret
.p2align 4,,7
L5:
popl %ebp
leal 102(%ecx), %eax
ret
看完汇编码，第一感觉：cmpl少了许多，一个只读数据段中的L10的标签映入眼帘，以L10标签为起始的内存中依次存储了L3、L4、L5和三个L8的地址，看起来就像是一个地址数组，或者是一个地址表，访问这个数组中的元素实际上就是调用每个元素对应地址中的一段代码。我们继续往前看，来证实一下这个想法。代码不多，比对着汇编指令手册读起来也不甚难。
pushl %ebp
movl %esp, %ebp // 将栈帧地址存在%ebp中
movl 8(%ebp), %ecx // 将rv值存储到%ecx中
leal -10(%ecx), %edx // 将rv值-10之后的值，作为地址偏移量存放到%edx
movl %ecx, %eax // 将%ecx中的rv值存储到%eax中
cmpl $5, %edx // 比较5 vs. (rv – 10)，显然5是编译器经过代码扫描后，算出的一个最大偏移值
ja L2 // jump if above ，如果5 > %edx中的值，则跳到L2继续执行
jmp *L10(,%edx,4) // 如果5 <= %edx中的值，则jmp *L10(,%edx,4)
解析一下jmp *L10(,%edx,4)，按照书中所说，*L10(,%edx,4)应该对应一个叫indexed memory mode的模式，格式一般是base_address(offset_address, index, size)，含义就是base_address + offset_address + index * size；这样似乎就一目了然了。我们拿i = 12为例，经过前面的计算，%edx中存储的是2，L10(,%edx,4)相当于L10 + 0 + 2 * 4，也就是起始地址=L10 + 8的那个内存区域，恰好是L5的起始地址，jmp *L10(,%edx,4)，直接将代码执行routine转到L5了：
L5:
popl %ebp
leal 102(%ecx), %eax
ret
显然这和前面的猜测是一致的，switch并没有使用性能低下的逐个cmpl的方式，而是形成了一个跳转表(以L10为首地址的地址数组)，并将传入switch的那个整型值经过已经的运算后作为offset值，通过一个jmp直接转到目的代码区，这样无论switch有多少个分支，实际上都只是做了一次cmpl，性能照比多if有很大提升。
© 2008, bigwhite. 版权所有.
Related posts:
评论