剑指offer (2)

  • R4y 
  • 未分类

西西弗斯一般的生活,loop,loop,感觉良好,卒

For A While

空循环体

forwhile哪个效率高?自古也是成了圣战的话题。
这里自己做一个简单分析。

int main(){    while(1);}int main(){    for(;;);}    

两种死循环语句,后者是歪果仁喜欢用的,倒是觉得第一种更贴切。之后使用gcc

g++ *.c -S [-O1/-O2/-O3]

发现在这种情况下,编译器给出的汇编内容实际上都是一样的,两种循环一样,三种优化也是一样。下面是其汇编代码。

        .file   "while.cpp"        .def    ___main;        .scl    2;      .type   32;     .endef        .section        .text.startup,"x"        .p2align 4,,15        .globl  _main        .def    _main;  .scl    2;      .type   32;     .endef_main:LFB0:        .cfi_startproc    ; 调用框架指令        pushl   %ebp    ; 这里把当前域(Caller)的基址压栈        .cfi_def_cfa_offset 8    ;         .cfi_offset 5, -8        movl    %esp, %ebp    ; 把esp值传入ebp        .cfi_def_cfa_register 5        andl    $-16, %esp    ;         call    ___mainL2:                            ; 这里是我们的循环部分        jmp     L2        .cfi_endprocLFE0:        .ident  "GCC: (MinGW.org GCC-6.3.0-1) 6.3.0"

可以看到 LFB0 的代码是main的caller部分,主要功能是把当前函数的ebp(基址寄存器)压栈,以便函数返回时数据的恢复。之后把esp传给ebp,就是以当前的栈地址作为main函数(被调用函数的地址)。

andl    $-16, %esp    ;

这句本来有点懵,不过实际上看看这个-16是什么就很清楚了,

-16D = 11110000B

所以实际上这个and 是对esp寄存的一次掩码。掩去esp的第四位。

不过这里的核心代码统统是下面这句了:

L2:     jmp  L2

一个指令,一个操作数。很简洁简单,并看不出差别

自加

int main(){    int i = 0;     /* ++i while循环 */     while (++i < 10);     i = 0;     /* ++i dowhile循环 */     do;     while (++i < 10);     /* ++i for循环 */     for (i = 0; i < 10; ++i);}

这里使用自加作为循环体,非空循环体。下面一样是汇编代码。

        .file   "add.cpp"        .def    ___main;        .scl    2;      .type   32;     .endef        .text        .globl  _main        .def    _main;  .scl    2;      .type   32;     .endef_main:LFB0:        .cfi_startproc        pushl   %ebp        .cfi_def_cfa_offset 8        .cfi_offset 5, -8        movl    %esp, %ebp        .cfi_def_cfa_register 5        andl    $-16, %esp        subl    $16, %esp        ; 由于栈是向低地址生长,所以这里开辟栈空间        call    ___main        movl    $0, 12(%esp)    ; 这里是间接寻址 esp+0*0+12    实际上是我们局部变量 i 的值的初始化;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;    L3:        addl    $1, 12(%esp)        cmpl    $9, 12(%esp)        setle   %al        testb   %al, %al        je      L2        jmp     L3L2:        movl    $0, 12(%esp);;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;L5:        addl    $1, 12(%esp)        cmpl    $9, 12(%esp)        setle   %al        testb   %al, %al        je      L4        jmp     L5L4:        movl    $0, 12(%esp);;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;L7:        cmpl    $9, 12(%esp)        jg      L6        addl    $1, 12(%esp)        jmp     L7;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;L6:        movl    $0, %eax    ; main返回值是0        leave        .cfi_restore 5        .cfi_def_cfa 4, 4        ret        .cfi_endprocLFE0:        .ident  "GCC: (MinGW.org GCC-6.3.0-1) 6.3.0"

很明显这里的循环体所对应的操作已经出现了差异。相比较这三种循环。

  • while 6
  • do_while 6
  • for 4

综上看出了,实际上可能在部分情况下for是有优势的。不过实际上我们对比,在while中实际上多了两条语句

setle   %altestb   %al, %al

setle D, D = (SF ^ OF) | ZF, 小于等于(有符号<=)
这个指令不常见,所以去search之。这个指令是属于访问条件码指令。

作用: <= 时设定操作数值为1 ,否则为0 //一般与cmp指令组合使用

所以上述的指令目的,是判断Cmp的结果是不是小于等于,如果是就把al置1。再判断al是否为1。如果是0就跳出,否则说明,还需要继续循环。
不过实际上,觉得这一步是相当冗余的。不知为何

留下点什么吧