一直以来写东西都说可以用右移一位来代替除以2操作, 会提高性能, 但一直不知道为什么, 这次折腾一下, 看看是在哪里提高性能的.
目录
直接看汇编
对照C语言代码:
1
2
3
4
5
6
7
// 除法
int a = 8;
int b = a / 2;
// 位运算
int a = 8;
int b = a >> 2;
一定要用中间变量储存结果, 否则编译器会优化(开了-O0也没用), 不会生成对应的汇编代码. 使用clang -O0 -S c_file -o nasm_file将C语言代码转换成汇编.
位运算
1
2
3
4
movl $8, -4(%rbp)
movl -4(%rbp), %ecx
sarl $1, %ecx
movl %ecx, -8(%rbp)
去掉无关的代码, 位运算代码转换成汇编就这几步:
- 将8入栈(因为是自动变量, 所谓的存入栈区)
- 将栈中变量取出, 放入通用寄存器
ecx - 将
ecx寄存器中数据右移一位, 结果存在ecx中 - 将
ecx数据入栈
除法
1
2
3
4
5
6
7
8
9
movl $2, %ecx
movl $8, -4(%rbp)
movl -4(%rbp), %edx
movl %eax, -12(%rbp)
movl %edx, %eax
cltd
idivl %ecx
movl %eax, -8(%rbp)
movl -12(%rbp), %eax
因为没系统学过汇编, 所以看除法比上面位运算要麻烦得多.
- 向通用寄存器
ecx中存入2(因为不是自动变量, 不入栈) - 将8入栈
- 将栈变量取出, 放入通用寄存器
edx - 将累加寄存器
eax中数据暂存入栈中(一会解释) - 把
edx数据移入eax - 将
eax扩充为四字(8字节) - 将
ecx数据作为除数计算除法 - 将
eax中的结果入栈(赋给变量a) - 将上面栈中暂存的
eax数据放回eax
就看这多出来的步骤就比位移要麻烦. 首先解释一下除法, 计算机底层做除法时, 被除数位数是除数两倍长, 所以可以看到要使用edx的空间, 把eax扩充为四字, 然后用idivl命令的操作数ecx作为除数进行计算, 计算结果存放在eax中, 余数存在edx中, 但并没有看到对edx数据做什么处理, 也符合整型除法不管余数的原则.
再说明一下把eax数据入栈的操作, 因为累加寄存器中的数据还有用处, 但下一步除法要用它存放被除数, 此时四个寄存器eax, ebx, ecx, edx都用上了, 所以暂时从栈里借点地方, 之后再还回来.
移位操作
如果还是进行除法操作, 换成用无符号整型, 会发现生成的汇编和位运算一样:
1
2
unsigned int a = 8;
unsigned int b = a / 2;
这就要提一下有符号和无符号的移位操作了. 无符号的整型无所谓, 正常左移右移就可以, 而有符号整型有符号位, 在 macOS 上的 LLVN 9.1.0 中, 正数右移左面补0, 负数右移左面补1, 相当于符号位不变; 而左移会给出警告, 提示结果未定义, 忽略警告执行的话, 符号位不变, 正数右面补0, 负数补1. 总体来说, 和直觉相对.
虽然结果上是对的, 但有符号整型的左移毕竟是未定义行为, 所以在除法时会做出判断, 体现在汇编上就是使和idivl指令, 而不是右移sarl. 再加上除法会计算余数, 即使用不上, 所以在步数上和指令本身执行时间都不如移位.
看上去很简单的道理, 其实后面包含自底向上的组成原理, 编译原理, 汇编和C语言知识. 汇编真有趣, 我再也不看了…