欢迎光临散文网 会员登陆 & 注册

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

2023-05-11 21:58 作者:breakerzh  | 我要投稿

分支控制流在处理器指令执行中的开销与效率影响:

1. branch predictor 分支预测失败造成的开销 miss penalty 不中处罚,pipeline stall 流水线堵塞。

2. 对 SIMD 指令级并行不友好,SIMD 寄存器中各分量,无法即执行条件指令又同时运算。

----------

分支消除的推导步骤


20200315-194427885 P1 - 06:25


1. 先将 if-else 改为三元条件运算符表达式。

2. 将 c ? x : y 转换为等价形式 y - (c ? (y - x) : 0),假定没有算术溢出。


20200315-194427885 P1 - 07:54


3. [关键点] 重新考虑 bool 系统,0 仍作为 false,但将 -1 (0xff...f) 作为 true。三元条件表达式转换为 y - (c2 & (y - x))

这里的关键思想是用真值的位特性,及位运算(这里是按位与),来替代条件判断。


20200315-194427885 P1 - 08:53


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 位里),只要把它们向右移出即可。

----------


20200315-200153559 P2 - 01:15



只会写 if 的菜炸了,手动分支消除,带你装〇带你飞!的评论 (共 条)

分享到微博请遵守国家法律