C语言优化分支代码——避免跳转指令堵塞流水线

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

(注意修改下充斥后的扩充名)

同一、起因——饱和处理

  以编排图象处理程序时,经常出现RGB值超过[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指令集,它们纯天然就是发生饱满运算指令,而且还足以并行计算。
  分支预测对于循环语句所编译的跳转效果比好,因为于循环时肯定会履跳转,只有最终一糟巡回结束时才见面预测失败。而对做饱和处理功能就是有些好了,这是因每次循环计算出底RGB值都是休平等的(因为本来就未是暨一个像素),预测失败的可能非常挺。所以分支预测对饱和处理做的献微乎其微。
  而以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。
  再将原数与地方求得的掩码进行“与”运算。

  有矣面很算法启发思维后,我们格外易想发处理>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]界定外,结果不变换。

  还可免可以另行优化呢?由于一个勤不可能还要小于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办法用2次较和2次跳转;
    本办法用2次于(、2次以比结实转为数值)、2次求负、1差与运算、1次还是运算。

  可以看来,本办法在回落2次跳转的情况下,增加了同步6不良的个运算。幸好各运算都是粗略指令,都是1独时钟周期内虽能够好的下令。所以当现世超流水线CPU情况下,这6不成位运算比if跳反开销少。

  上面讨论的就是如C语言那样“比较运算结果是0或1”情况下之算法,如果是诸如BASIC那样“比较运算结果是0或-1”怎么处置也?其实非常粗略,我们要之正是0和-1,BASIC也支撑AND、OR、XOR等各运算符。代码就如此形容:
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不同。
为此我于基准满足的当儿将该位取反就实施了(C语言注意“^”是异或运算符)。

 

2.5 转为十六迈入制字符

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

解释:
个中的“( (‘A’ – (‘0’+10))”会编译优化成常数的。
至于何以进行逆转换,估计只有用查表法了。