只会写 if 的菜炸了,手动分支消除,带你装〇带你飞!

分支控制流在处理器指令执行中的开销与效率影响:
1. branch predictor 分支预测失败造成的开销 miss penalty 不中处罚,pipeline stall 流水线堵塞。
2. 对 SIMD 指令级并行不友好,SIMD 寄存器中各分量,无法即执行条件指令又同时运算。
----------
分支消除的推导步骤
1. 先将 if-else 改为三元条件运算符表达式。
2. 将 c ? x : y 转换为等价形式 y - (c ? (y - x) : 0),假定没有算术溢出。
3. [关键点] 重新考虑 bool 系统,0 仍作为 false,但将 -1 (0xff...f) 作为 true。三元条件表达式转换为 y - (c2 & (y - x))
这里的关键思想是用真值的位特性,及位运算(这里是按位与),来替代条件判断。
4. [关键点] 构造新的 bool 条件变量 c2。原 bool 条件变量 c 是由关系运算 > < == != 求值出来的,真值只能是 false=0, true=1,现在要构造 true 时 c2 真值为 -1。对于这个例子,v < 10 时,要让 c2=-1,v >= 10 时,要让 c2=0。
构造方法 1. 直接给原条件表达式前加负号 c2=-(v < 10)
构造方法 2. 这个更高效,没有关系运算,也就是没有比较指令,而是做减法差值,然后通过移位时保留符号位来产生 -1 (0xff...f)。作者写的是 c2=(v - 10) >> 15,为什么是右移 15 位,而不是 31 位,因为这个例子中 v - 10 是 ASCII 码差值(距离),最大的差值是 -127 和 127,有效值在低 15 位里(实际上是在低 8 位里),只要把它们向右移出即可。
----------