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

《代码优化-之-优化条件分支》由会员分享，可在线阅读，更多相关《代码优化-之-优化条件分支（9页珍藏版）》请在金锄头文库上搜索。

1、代码优化之优化条件分支tag:代码优化,条件分支,饱和,MMX,CMOV,掩码摘要: 条件分支是编程中经常使用的基本操作,然而在某些时候它确可能带来严重的性能问题.当前的CPU都能对条件分支做预测(动用了庞大的晶体管资源),如果分支预测正确,那么条件指令一般只需要花费一个CPU周期,而如果预测错误,那么将可能花费几十个CPU周期! 本文将讨论条件分支的一些有效优化方法.正文： 文章为收集加经验编辑而成的文章,对优化条件分支做了较全面的阐述.文章假定的CPU为x86,示例代码为C/C+.A.什么是分支? 分支是编程语言中的常见结构；分支可以分为条件分支和非条件分支； 条件分支举例: 条件判断:

2、if (a255) a=255; else if (a0) a=0; 循环: for (i=0;i1000;+i) .; while(!bOk) bOk=.; . 对应汇编指令的jnz,jg等等 非条件分支举例: 函数调用(call)，函数返回(return/ret)，软件中断(int 3)，直接跳转(jmp),.B.CPU分支预测错误的惩罚由来 为了加快CPU的处理频率，现代CPU都设计了多级流水线，有的甚至有20级以上；当CPU遇到跳转指令的时候，会做一个预测，把预测的分支代码载入流水线，当发现预测错误的时候，需要清空流水线，重新载入正确的分支到流水线；那么预测错误的代价周期数至少应该和流

3、水线长度相当；然而考虑到各级的缓存失效、指令解码等等，实际损失的周期数有可能是流水线长度的几倍! 对于非条件分支，一般来说CPU都能得到相当高的预测准确率；我们主要来讨论一下条件分支的预测；(有人可能会说，当CPU遇到条件分支时不做预测不就没有预测错误的惩罚了吗?这种流水线空着的惩罚实质和每次都预测错误然后清空流水线的代价相当，退一步说就算每次随机选择一个分支来执行也有50%的收益)C:需要优化的条件分支 当前的CPU对各种简单的条件分支模式都能做出很的预测，比如奇偶模式： for (int i=0;i=64) | (b1=64) . /b0,b1=0 改写为: if ( (b0|b1)=64

4、 ) . (请尝试证明其等价性)F.将出现几率高的分支优先处理,从而提高预测准确率G.优化第一次执行的条件分支 当CPU第一次执行到一个条件分支的时候,默认的预测分支规则是不跳转的那个分支(也就是紧接着条件跳转指令之后的那些指令); (下面的内容主要讨论完全替换掉分支的一些方法; 移除分支意味着代码的性能可以不受输入数据的影响,并可能能更好的使用SIMD类指令)H.使用条件状态值生成掩码来移除条件分支 比如: if (color=0);/求负是为了生成掩码,也可以减1来生成掩码 这里的思路是利用比较来产生0或1值,然后利用生成的值参与运算从而移除了分支; 比如: if (color255) c

5、olor=255; 改写为: color = (color | -(color255) ) & 0xFF; 比如: if (a=b) return a; else return b; 改写为: return a + ( (b-a) & -(ba) ); (警告:这里利用了C/C+中比较的结果是0或1,在其他语言或编译器中可能定义不同)I.使用带符号的移位生成掩码来移除条件分支 (建议使用该方案替代上面的条件状态值方案) 比如: if (color31); /带符号移位从而生成需要的掩码 比如: if (color255) color=255; 改写为: color = (color | (25

6、5-color)31) ) & 0xFF; 比如: if (a=b) return a; else return b; 改写为: return a + ( (b-a) & -(ba) ); 移除分支的一个更通用的思路: 针对不同类的数据生成不同的掩码数据,然后让原数据和掩码参与运算得到想要的结果,从而移除分支;J: 查表法移除分支 比如: if (color255) color=255; /假设color属于-256.512 改写为: color=ColorTablecolor; 其中ColorTable的建立: _ColorTable512+256+1; ColorTable=&_Color

7、Table256; for (i=-256;i=512;+i) if (i255) ColorTablei=255; else ColorTablei=i; 比如: if (score=90) /score属于0.100 return A; else if (score=75) return B; else if (score=60) return C; else return D; 改写为: return scTablescore; 其中scTable应该预先存的值就不用再写了吧:)K:使用CMOV条件传送指令来移除条件分支 (为了避免分支预测错误造成的性能损失,现代的CPU一般都提供了很多

8、能够避免分支的指令,比如条件传送/掩码生成/最值等指令,请查阅指令说明和支持的CPU) CMOV条件传送指令是很多条具体的指令,它们根据条件寄存器的值来决定是否赋值. 比如: if (x0) x=-x; 用CMOV改写为(汇编): mov edx, eax /假设x的值在eax寄存器,该指令使edx=eax neg eax /eax=-eax /该指令的结果将设置条件寄存器的状态 cmovs eax,edx /如果状态为负,将edx的值传递给eax CMOV指令列表: CMOVA/CMOVNBE CMOVAE/CMOVNB/CMOVNC CMOVB/CMOVC/CMOVNAE CMOVBE/C

9、MOVNA CMOVE/CMOVZ CMOVG/CMOVNLE CMOVGE/CMOVNL CMOVL/CMOVNGE CMOVLE/CMOVNG CMOVNE/CMOVNZ CMOVNO CMOVNP/CMOVPO CMOVNS CMOVO CMOVP/CMOVPE CMOVS x87浮点CMOV指令列表: FCMOVB FCMOVBE FCMOVE FCMOVNB FCMOVNBE FCMOVNE FCMOVNU FCMOVUL:使用MMX/SSE2中的饱和指令 对于颜色的饱和处理,比如: if (color255) color=255; x86CPU从奔腾MMX开始,提供了MMX指令集(

10、后来的SSE2也有类似指令);增加了对饱和处理的指令支持,在图像处理和声音处理中得到了广泛应用;(我的blog的很多文章有使用MMX/SSE指令的例子)(MMX/SSE之类的SIMD指令还能够同时并行执行多路数据,从而加快执行速度)M:使用CMP掩码生成指令来移除条件分支 比如: /r = (x 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, PCM

11、PEQW, PCMPGTB, PCMPGTD, PCMPGTW CMPXCHG,CMPXCHG8B 等N:使用MIN/MAX指令来移除条件分支 MAXPS,MAXPD,MAXSS,MAXSD,MINPS,MINPD,MINSS,MINSD PMAXSW, PMAXUB, PMINSW, PMINUB等分享到： 上一篇：Alpha颜色混合的魔法 上篇 下一篇：Alpha颜色混合的魔法 下篇查看评论9楼kissthefuture2011-07-07 16:13发表回复view plain1. voidThreshold(LPBYTElpDIBBits,intlWidth,intlHeight,CRectrc,intiThreshold)2. 3. intrcwidth=rc.right-rc.left+1;/roi区域宽度4. 5. intXstep=lW