优化分支代码——制止跳转指令堵塞流水线

File:      noifop.txt
Name:      优化分支代码——制止跳转指令堵塞流水生产线
Author:    zyl910
Blog:      http://blog.csdn.net/zyl910/
Version:   V2.00
Updata:    2006-10-11

(注意修改下载后的扩张名)

壹 、起因——饱和处理

C语言,  在编写图象处理程序时,常常出现库罗德GB值超过[0,
255]限制的图景。那时,得做饱和拍卖,将越界数值饱和到分界,即那样的代码:
if (r <   0) r =   0;
if (r > 255) r = 255;
if (g <   0) g =   0;
if (g > 255) g = 255;
if (b <   0) b =   0;
if (b > 255) b = 255;

  但这么的代码执行效用是十分的低的。那是因为if区块会编写翻译成跳转指令,而跳转指令对于严重影响现代超流水线CPU的流水生产线成效。
  那时CPU产商建议了四个缓解方案:一是增多了分段预测硬件,尽量减少跳转指令对流程的熏陶;二是统一筹划了MMX/SSE等SIMD指令集,它们纯天然就有饱满运算指令,而且还足以并行总括。
  分支预测对于循环语句所编译的跳转效果较好,因为在循环时肯定会履行跳转,唯有最后一回巡回甘休时才会预测战败。而对此做饱和处理效果就不怎么好了,这是因为每一回循环总结出的奥迪Q3GB值都以不雷同的(因为本来就不是同三个像素),预测失败的也许性相当大。所以分支预测对饱和处理做的进献微乎其微。
  而采用SIMD指令呢。那是一种万分周密的消除方案,在有规则的事态下极力推荐SIMD指令。但鉴于高级语言不可能描述SIMD指令,所以只可以手工业用汇编编辑SIMD代码,那无疑给精晓代码带来困难。再者,大家有时候需求在像Java、.Net那样的虚拟机平台下编写制定图象处理程序,而此时是心有余而力不足间接动用SIMD指令集的。
  所以,大家须要一种在例行指令集下(能用高级语言表明)做饱和拍卖的算法,且能躲避if跳转。

  先尝试小于零时的饱满处清理计算法。

  还记得“与”运算有哪些服从吧?当三个平头与掩码经行与运算时,全1掩码会保留原值,全0掩码会重临零。
  然后揣摩什么转变所需的掩码。C语言比较运算的的结果是0和1,如何将它们成为全0或全1的掩码呢?答案很简单,求负
或 减一。由于求负写法简洁,所以喜欢用求负:
n &= -(n >= 0)

  首先将n与0实行相比较。当 n>=0 时,相比结实为1;当 n<0
时,相比较结实为0。
  然后求负。当 n>=0 时,结果为-1(全1);当 n<0
时,结果为全0。
  再将原数与地点求得的掩码举办“与”运算。

  有了上边13分算法启发思维后,我们很简单想出处理>255场地包车型地铁算法:
n = (n | -(n >= 256) ) & 0xFF

  首先将n与256开始展览相比较。当 n<256 时,比较结实为0;当 n>=256
时,相比较结实为1。
  然后求负。当 n>=256 时,结果为-1(全1);当 n<256
时,结果为0。
  再将原数与地方求得的掩码进行“或”运算。
  最终跟0xFF进行与运算,使全1变成0xFF(十进制的255)。至于 n<256
的,本来就在[0, 255]范围内,结果不变。

  还可不得以再优化呢?由于3个数不可能还要小于0和超出255,所以能够将着两行代码合并成一行。由于我们一般是将结果保存到一个BYTE型变量中,进行三次强制类型转换就行了,不必要“&
0xFF”。最终,每便写那么长代码太难为了,应该将它封装成宏:
#define LIMITSU_FAST(n, bits) ( (n) & -((n) >= 0) | -((n) >=
(1<<(bits))) )
#define LIMITSU_SAFE(n, bits) ( (LIMITSU_FAST(n, bits)) &
((1<<(bits)) – 1) )

  bits代表限制多少位,如BYTE正是8。借使认为参数过多,能够再定义宏,或概念内联函数:
#define LIMITSU_BYTE(n) ((BYTE)(LIMITSU_FAST(n, 8)))

  以往分析一下运算复杂度:
    if办法必要一次相比和1次跳转;
    本办法供给一次相比(、3回将相比结实转为数值)、1遍求负、叁遍与运算、1遍或运算。

  能够观望,本办法在缩减一遍跳转的情景下,扩充了共6遍的位运算。幸而位运算都以粗略指令,都以一个时钟周期内就能成功的吩咐。所以在现世超流水生产线CPU情形下,那八遍位运算比if跳转耗费少。

  上边商讨的只是像C语言那样“相比较运算结果是0或1”景况下的算法,假若是像BASIC这样“比较运算结果是0或-1”如何是好吧?其实很简短,大家要求的便是0和-1,BASIC也支撑AND、O中华V、XO哈弗等位运算符。代码就好像此写:
by =  ((n And (n >= 0) Or (n >= 256)) And &HFF)

  测试:略。请看old目录下的V100.rar

 

二、推广

  该方法不但方便做饱和拍卖,还足以放手到其余地方去。

2.1 条件掩码

#define IFMASKNUM(n, c) ( (n) & -(c) )

参数:
  n: 掩码
  c: 条件。为0或1

再次回到值: 若c为1,则重临值是n;若c为0,则赶回值为0。

 

2.2 MIN与MAX

#define FASTMIN(a, b) ( (a) + ( ((b)-(a)) & -((b)<(a)) ) )
#define FASTMAX(a, b) ( (a) + ( ((b)-(a)) & -((b)>(a)) ) )

解释:
  将b与a实行比较时实际上会实施减法操作,而且前边有“b-a”,那会被编写翻译器优化的。
  注意该方法会时有发生溢出,所以唯有像C语言这样不会抛出整数溢出尤其的言语才行。

 

2.3 大小写转换

#define CHARUCASE(c) ( (c) ^ (0x20 & -((c)>=’a’ && (c)<=’z’) )
)
#define CHARLCASE(c) ( (c) ^ (0x20 & -((c)>=’A’ && (c)<=’Z’) ) )

解释:
‘A’的ASCII码是0x41
‘a’的ASCII码是0x61
它们相差了0x20,就是D5不一样。
之所以小编在尺度满足的时候将该位取反就行了(注意“^”是异或运算符)。

 

2.5 转为十六进制字符

#define TOHEXCHAR(i) (‘0’ + (i) + ( (‘A’ – (‘0’+10)) & -((i)>=10) ))

解释:
个中的“( (‘A’ – (‘0’+10))”会编写翻译优化成常数的。
有关哪些开展逆袭换,猜度只有用查表法了。