代码优化-之-优化条件分支

1、代码优化之优化条件分支                   HouSisongGM   2007.10.05tag:代码优化,条件分支,饱和,MMX,CMOV,掩码摘要: 条件分支是编程中经常使用的基本操作,然而在某些时候它确可能带来严重的性能问题.当前的CPU都能对条件分支做预测(动用了庞大的晶体管资源),如果分支预测正确,那么条件指令一般只需要花费一个CPU周期,而如果预测错误,那么

2、将可能花费几十个CPU周期!  本文将讨论条件分支的一些有效优化方法.正文：  文章为收集加经验编辑而成的文章,对优化条件分支做了较全面的阐述. 文章假定的CPU为x86,示例代码为C/C+.A.什么是分支?  分支是编程语言中的常见结构；分支可以分为条件分支和非条件分支；  条件分支举例:    条件判断: if (a>255) a=255; else if (a<0) a=0;    循环: for (i=0;i<1000;+i) .;   &

3、#160;       while(!bOk) bOk=.;             .    对应汇编指令的jnz,jg等等  非条件分支举例:    函数调用(call)，函数返回(return/ret)，软件中断(int 3)，直接跳转(jmp),.  B.CPU分支预测错误的惩罚由来  为了加快CPU的处理频率，现代CP

4、U都设计了多级流水线，有的甚至有20级以上；当CPU遇到跳转指令的时候，会做一个预测，把预测的分支代码载入流水线，当发现预测错误的时候，需要清空流水线，重新载入正确的分支到流水线；那么预测错误的代价周期数至少应该和流水线长度相当；然而考虑到各级的缓存失效、指令解码等等，实际损失的周期数有可能是流水线长度的几倍!   对于非条件分支，一般来说CPU都能得到相当高的预测准确率；我们主要来讨论一下条件分支的预测； (有人可能会说，当CPU遇到条件分支时不做预测不就没有预测错误的惩罚了吗? 这种流水线空着的惩罚实质和每次都预测错误然后清空流水线的代价相当，退一步

5、说就算每次随机选择一个分支来执行也有50%的收益)C:需要优化的条件分支  当前的CPU对各种简单的条件分支模式都能做出很的预测，比如奇偶模式：  for (int i=0;i<1000;+i)       if (a%2=0) do0();     else do1();    而对于随机的分支模式，再好的预测器也不可能做出好的预测；  我们要优化条件分支，这些分支代码应该满足：该分支处于时间热点上，并且分支预测错误率较高；这样我们才能得到优化的收

6、益；   (intel的VTune工具可以采样分支预测错误率)D.把条件分支移动到热点外  比如前面的那个奇偶循环模式,假设CPU不能正确预测,那么可以尝试改写为两个for循环,一个处理偶数,一个处理奇数;  一些图像处理算法里(比如模板运算/卷积运算/形态学运算等),经常需要判断边界像素点,进行特殊处理;可以考略的优化方案是把边界区域和内部区域分开处理;或者条件允许的话,可以扩大原图像的边界,形成"哨兵"数据,这样访问像素的时候就不用考虑越界的问题了;E.合并多个条件来减少条件分支  比如: if ( (a0=0) &am

7、p;& (a1=0) && (a2=0) ) .    编译器将生成3个条件跳转指令,而且使分支可预测性大大降低;  可以改写为: if ( (a0|a1|a2)=0 ) .    从而同时改进代码和分支预测率;  比如:if ( (b0>=64) | (b1>=64) .  /b0,b1>=0  改写为: if ( (b0|b1)>=64 ) .  (请尝试证明其等价性)F.将出现几率高的分支优先处理,从而提高预测准确率G.优化第一次执

8、行的条件分支  当CPU第一次执行到一个条件分支的时候,默认的预测分支规则是不跳转的那个分支(也就是紧接着条件跳转指令之后的那些指令);   (下面的内容主要讨论完全替换掉分支的一些方法; 移除分支意味着代码的性能可以不受输入数据的影响,并可能能更好的使用SIMD类指令)H.使用条件状态值生成掩码来移除条件分支  比如: if (color<0) color=0;  改写为: color &=-(color>=0);/求负是为了生成掩码,也可以减1来生成掩码  这里的思路是利用比较来产生0或1值,然后利用生成的值参

9、与运算从而移除了分支;    比如: if (color>255) color=255;  改写为: color = (color | -(color>255) ) & 0xFF;  比如: if (a>=b) return a; else return b;  改写为: return  a + ( (b-a) & -(b>a) );  (警告:这里利用了C/C+中比较的结果是0或1,在其他语言或编译器中可能定义不同)I.使用带符号的移位生成掩码来移除条件分支  (

10、建议使用该方案替代上面的条件状态值方案)  比如: if (color<0) color=0; /color为long类型  改写为: color &=(color>>31);  /带符号移位从而生成需要的掩码  比如: if (color>255) color=255;  改写为: color = (color | (255-color)>>31) ) & 0xFF;  比如: if (a>=b) return a; else return b;  改写为: ret

11、urn  a + ( (b-a) & -(b>a) );  移除分支的一个更通用的思路: 针对不同类的数据生成不同的掩码数据,然后让原数据和掩码参与运算得到想要的结果,从而移除分支;  J: 查表法移除分支  比如: if (color<0) color=0;         else if (color>255) color=255; /假设color属于-256.512   改写为: color=ColorTable

12、color;      其中ColorTable的建立:            _ColorTable512+256+1;  ColorTable=&_ColorTable256;      for (i=-256;i<=512;+i)           

13、0;    if (i<0) ColorTablei=0;          else if (i>255) ColorTablei=255;          else ColorTablei=i;          比如: if (score>=90)  /score属于0.1

14、00             return 'A'         else if (score>=75)             return 'B'       

15、60; else if (score>=60)            return 'C'         else            return 'D'    改写为: return scTablescore; &

16、#160;    其中scTable应该预先存的值就不用再写了吧:)K:使用CMOV条件传送指令来移除条件分支  (为了避免分支预测错误造成的性能损失,现代的CPU一般都提供了很多能够避免分支的指令,比如条件传送/掩码生成/最值等指令,请查阅指令说明和支持的CPU)  CMOV条件传送指令是很多条具体的指令,它们根据条件寄存器的值来决定是否赋值.  比如: if (x<0) x=-x;  用CMOV改写为(汇编):       mov  

17、edx, eax   /假设x的值在eax寄存器,该指令使edx=eax       neg   eax        /eax=-eax   /该指令的结果将设置条件寄存器的状态       cmovs eax,edx    /如果状态为负,将edx的值传递给eax    &#

18、160;    CMOV指令列表:  CMOVA/CMOVNBE CMOVAE/CMOVNB/CMOVNC  CMOVB/CMOVC/CMOVNAE  CMOVBE/CMOVNA CMOVE/CMOVZ CMOVG/CMOVNLE CMOVGE/CMOVNL  CMOVL/CMOVNGE CMOVLE/CMOVNG CMOVNE/CMOVNZ CMOVNO  CMOVNP/CMOVPO CMOVNS CMOVO CMOVP/CMOVPE CMOVS  x87浮点CMOV指令列表:  FCMOVB

19、 FCMOVBE FCMOVE FCMOVNB FCMOVNBE FCMOVNE  FCMOVNU FCMOVUL:使用MMX/SSE2中的饱和指令  对于颜色的饱和处理,比如:      if (color<0) color=0;         else if (color>255) color=255;   x86CPU从奔腾MMX开始,提供了MMX指令集(后来的SSE2也有类似指令);增加了对饱和处理的指令

20、支持,在图像处理和声音处理中得到了广泛应用;(我的blog的很多文章有使用MMX/SSE指令的例子)(MMX/SSE之类的SIMD指令还能够同时并行执行多路数据,从而加快执行速度)M:使用CMP掩码生成指令来移除条件分支  比如:     /r = (x < y) ? a : b    / In: MM0 = a,  MM1 = b, MM2 = x, MM3 = y    / Out: MM0 = r    pcmpgtd mm3, mm

21、2 /比较y>x,生成掩码0xFFFFFFFF 或者 0    pand mm0, mm3    /a 或者 0    pandn mm3, mm1   /0 或者 b    por mm0, mm3  CMP指令包括:   CMPPS,CMPSS,CMPPD,CMPS,CMPSB,CMPSW,CMPSD  PCMPEQB, PCMPEQD, PCMPEQW, PCMPGTB, PCMPGTD, PCMPGTW

22、  CMPXCHG,CMPXCHG8B 等N:使用MIN/MAX指令来移除条件分支  MAXPS,MAXPD,MAXSS,MAXSD,MINPS,MINPD,MINSS,MINSD  PMAXSW, PMAXUB, PMINSW, PMINUB等 分享到： · 上一篇：Alpha颜色混合的魔法 上篇· 下一篇：Alpha颜色混合的魔法 下篇查看评论9楼 kissthefuture 2011-07-07 16:13发表 回复view plain1. void Threshold(LPBY

23、TE lpDIBBits, int lWidth, int lHeight, CRect rc, int iThreshold)   2.    3. int rcwidth = rc.right - rc.left + 1; / roi 区域宽度   4.   5. int Xstep&

24、#160;= lWidth - rcwidth; /步长，一维数组   6.   7. int i,j;   8.   9. unsigned char *lpSrc;   10.   11. lpSrc = (unsigned char *)lpDIBBits + rc.top * lWidth&

25、#160;+ rc.left;   12.   13. for ( i= rc.top; i &lt;= rc.bottom; i+)   14.    15. for (j = rc.left; j&lt;= rc.right; j+)   16.    17. if(*

26、lpSrc &gt;= iThreshold)   18.   19. *lpSrc = 255;   20.   21. else   22.   23. *lpSrc = 0;   24.   25. lpSrc +;   26.    27.  

27、 28. lpSrc += Xstep;   29.    30.    写的很好8楼 vbar 2010-03-20 09:29发表 回复学习了。7楼 good 2008-07-07 11:55发表 回复非常有道理，顶6楼 wazdxm1980 2008-04-14 08:28发表 回复你好，这是我改写的二值化代码，但运行后，发现效果不对。好像仅对边缘部分起作用。能帮我看一下么？谢谢&

28、#160;void THRESHOLD_MMX(BYTE* pSource, BYTE* pDest,int nNumberOfPixels,int Thresh)  BYTE b = (BYTE) abs(Thresh); / make 64 bits value with b in each byte _int64 c = b; for ( int i = 1; i &lt;= 7; i+ )  c = c &lt;&lt; 8; c |= b;  / 8 pixel

29、s are processed in one loop int nNumberOfLoops = nNumberOfPixels / 8; _m64* pIn = (_m64*) pSource; / input pointer _m64* pOut = (_m64*) pDest; / output pointer _m64 tmp; / work variable _mm_empty(); / emms _m64 nChange64 = Get_m64(c); for ( i = 0; i &lt; nNumbe

30、rOfLoops; i+ )  tmp = _mm_cmpgt_pi8(*pIn, nChange64); / 这句话的意思是*pIn与nChange64的每8位进行比较，如果前者大于后者，返回0xFF,否则返回0。 *pOut = tmp; pIn+; / next 8 pixels pOut+;  5楼 wazdxm1980 2007-11-30 10:27发表 回复to: housisong 我按照你的建议做了一下，感觉速度没有明显提高，稍微快了一点点。 谢谢4楼 housisong 2007-11-29 17:38发表 回复to: wazdxm1980 你可以尝试把