标签 Assembly 下的文章

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有很大提升。

小心'溢出'陷阱

这几天以前曾经做过的一个项目上线测试了,果不其然,没有经过’战争洗礼’的产品就是靠不住,这不出了若干问题。害得我逃了半天课远程支持。

其中的一个问题很值得思考。其所在的模块并非是一个核心功能模块,而是一个提高系统Availability的一个功能模块,主要功能就是监视磁盘占用率。我们通过配置给出允许使用的磁盘空间大小(以M Byte为单位),以及两个阈值,即当占用率达到多少的时候,Do A;达到多少的时候Do B。

我们假设用变量quota代表配置中读取的配额数值,而total代表实际检测到的占用数值,一般关于文件大小的系统调用都是用byte作为单位的,也就是说我们需要做一个转换,假设换算后的变量为quota1。由于最初我们没有考虑周全的原因,我们使用unsigned int作为quota、quota1和total的存储类型。结果在家里没有做过认真的测试,导致一到现场就’露馅’了。这个问题反应到家里后,一个同事发现了这一问题,并作了修改,经过简单的测试,好像表面上问题消失了。再一次提交到现场后,问题依旧。

由于那位同事还有其他工作,我只能逃课改问题,经过一段时间的代码Review终于发现了些许’蛛丝马迹’,简单表述一下,原来这里的代码是这样的:

计算total;
quota1 = quota * 1024 * 1024;
拿total和quota1之比与配额阈值作比较;

注意这里的total和quota1是unsigned long long,也就是64位的,而quota是unsigned int,即32位的。首先quota肯定不会出现溢出的可能,因为检查配置发现这个数不大。那么为什么从日志观察,quota1有问题呢?

比如我们的quota配置为1004800,那么在换算后正确的数值应该是053609164800,而日志中打印出来的结果却是1342177280。基本上可以肯定问题出在quota1 = quota * 1024 * 1024;这个转换式上。

我们大概可以用下面的程序来模拟一下这个问题:
int main() {
        long m = 1004800;
        unsigned long long n;
        n = m * 1024 * 1024;
        printf("%llu\n", n);
}

由于n = m * 1024 * 1024这个计算式的工作流程是这样的,先将m * 1024 * 1024的结果保存在一个临时变量中,然后再将这个临时变量值赋给n,这里是在Solaris9下利用GDB反汇编的结果:

(gdb) disas main
Dump of assembler code for function main:
0x0001066c <main+0>:    save  %sp, -128, %sp
0×00010670 <main+4>:    sethi  %hi(0xf5400), %o0
0×00010674 <main+8>:    or  %o0, 0×100, %o0     ! 0xf5500
0×00010678 <main+12>:   st  %o0, [ %fp + -20 ]
0x0001067c <main+16>:   ld  [ %fp + -20 ], %o0
0×00010680 <main+20>:   sll  %o0, 0×14, %o0
0×00010684 <main+24>:   st  %o0, [ %fp + -28 ]
0×00010688 <main+28>:   sra  %o0, 0x1f, %o0
0x0001068c <main+32>:   st  %o0, [ %fp + -32 ]
0×00010690 <main+36>:   sethi  %hi(0×10400), %o0
0×00010694 <main+40>:   or  %o0, 0×358, %o0     ! 0×10758 <_lib_version+8>
0×00010698 <main+44>:   ld  [ %fp + -32 ], %o1
0x0001069c <main+48>:   ld  [ %fp + -28 ], %o2
0x000106a0 <main+52>:   call  0×20800 <printf>
0x000106a4 <main+56>:   nop
0x000106a8 <main+60>:   mov  %o0, %i0
0x000106ac <main+64>:   nop
0x000106b0 <main+68>:   ret
0x000106b4 <main+72>:   restore

%o0 = 0xf5500 = 1004800
store %o0 -> fp + -20
大概看一下:
0×00010670 <main+4>:    sethi  %hi(0xf5400), %o0
0×00010674 <main+8>:    or  %o0, 0×100, %o0     ! 0xf5500
0×00010678 <main+12>:   st  %o0, [ %fp + -20 ]
这三句实际上是在栈上分配一个变量m,并赋值为1004800,这里编译器利用sethi  %hi(0xf5400), %o0和or  %o0, 0×100, %o0两句在寄存器%o0中构造出1004800(即0xf5500),然后将寄存器的值通过st指令写入到%fp – 20的位置。即m占据着从%fp – 17到%fp – 20这四个字节。

再往下
sll  %o0, 0×14, %o0,
st  %o0, [ %fp + -28 ]
这里是编译器做的优化,它没有乘以两次1024,而是直接乘以1024*1024的结果,也就是2^20,即将%o0逻辑左移20位,即逻辑左移0×14,我们知道逻辑左移即把操作数看成无符号数。对寄存器操作数进行移位,不管左右移,空出的位均补0,我们可以来手工逻辑左移一次,目前%o0中存储的是无符号数0xf5500, 即 0000 0000 0000 1111 0101 0101 0000 0000(B),我们逻辑左移20位后为0101 0000 0000 0000 0000 0000 0000 0000(B), 即0×50000000,即1342177280。之后利用st指令将改寄存器的值存入到%fp – 28开始的8个字节当中(即从%fp – 21到%fp – 28)。这样我们读出来的n值也就是1342177280了。

如何修正呢?看下面的例子:
int main() {
        long m = 1004800;
        unsigned long long n = m;

        n *= 1024 * 1024;
        printf("%llu\n", n);
}

(gdb) disas main
Dump of assembler code for function main:
0x0001066c <main+0>:    save  %sp, -128, %sp
0×00010670 <main+4>:    sethi  %hi(0xf5400), %o0
0×00010674 <main+8>:    or  %o0, 0×100, %o0     ! 0xf5500
0×00010678 <main+12>:   st  %o0, [ %fp + -20 ]
0x0001067c <main+16>:   ld  [ %fp + -20 ], %o0
0×00010680 <main+20>:   st  %o0, [ %fp + -28 ]
0×00010684 <main+24>:   sra  %o0, 0x1f, %o0
0×00010688 <main+28>:   st  %o0, [ %fp + -32 ]
0x0001068c <main+32>:   ldd  [ %fp + -32 ], %o0
0×00010690 <main+36>:   mov  %o0, %o2
0×00010694 <main+40>:   mov  %o1, %o3
0×00010698 <main+44>:   srl  %o3, 0xc, %o5
0x0001069c <main+48>:   sll  %o2, 0×14, %o4
0x000106a0 <main+52>:   or  %o5, %o4, %o0
0x000106a4 <main+56>:   sll  %o3, 0×14, %o1
0x000106a8 <main+60>:   std  %o0, [ %fp + -32 ]
0x000106ac <main+64>:   sethi  %hi(0×10400), %o0
0x000106b0 <main+68>:   or  %o0, 0×378, %o0     ! 0×10778 <_lib_version+8>
0x000106b4 <main+72>:   ld  [ %fp + -32 ], %o1
0x000106b8 <main+76>:   ld  [ %fp + -28 ], %o2
0x000106bc <main+80>:   call  0×20820 <printf>
0x000106c0 <main+84>:   nop
0x000106c4 <main+88>:   mov  %o0, %i0
0x000106c8 <main+92>:   nop
0x000106cc <main+96>:   ret
0x000106d0 <main+100>:  restore

和上面的汇编差不多少,主要的差别就是再st  %o0, [ %fp + -28 ]后,所有的操作均针对8位的m了,而且寄存器也不仅仅一个%o0参与(位数不够了),这句之后都是关于8字节的运算了。也就不存在溢出了。毕竟汇编细节看起来还是很费劲的,大家能明白其中的意思即可。

其实简单来看我们可以这么来理解:
n = m * 1024 * 1024;
n *= 1024 * 1024;

前一个式子可以看成 m’ = m * 1024 * 1024; n = m’;这样我们可以简单的认为m’这个中间变量和m存储空间一致。
而n *= 1024 * 1024 <=> n *= 1048576 <=> n = n * 1048576,都是在n的基础上操作,不会出现溢出问题。

溢出问题一般都很隐蔽,很难轻易发现,大家要格外注意。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats