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

代码优化之优化条件分支HouSisongGM 2007.10.05tag:代码优化,条件分支,饱和,MMX,CMOV,掩码摘要: 条件分支是编程中经常使用的基本操作,然而在某些时候它确可能带来严重的性能问题.当前的CPU都能对条件分支做预测(动用了庞大的晶体管资源),如果分支预测正确,那么条件指令一般只需要花费一个CPU周期,而如果预测错误,那么将可能花费几十个CPU周期! 本文将讨论条件分支的一些有效优化方法.正文： 文章为收集加经验编辑而成的文章,对优化条件分支做了较全面的阐述.文章假定的CPU为x86,示例代码为C/C+.A.什么是分支? 分支是编程语言中的常见结构；分支可以分为条件分支和非条件分支； 条件分支举例: 条件判断: 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遇到跳转指令的时候，会做一个预测，把预测的分支代码载入流水线，当发现预测错误的时候，需要清空流水线，重新载入正确的分支到流水线；那么预测错误的代价周期数至少应该和流水线长度相当；然而考虑到各级的缓存失效、指令解码等等，实际损失的周期数有可能是流水线长度的几倍! 对于非条件分支，一般来说CPU都能得到相当高的预测准确率；我们主要来讨论一下条件分支的预测；(有人可能会说，当CPU遇到条件分支时不做预测不就没有预测错误的惩罚了吗?这种流水线空着的惩罚实质和每次都预测错误然后清空流水线的代价相当，退一步说就算每次随机选择一个分支来执行也有50%的收益)C:需要优化的条件分支 当前的CPU对各种简单的条件分支模式都能做出很的预测，比如奇偶模式： for (int i=0;i=64) | (b1=64) . /b0,b1=0 改写为: if ( (b0|b1)=64 ) . (请尝试证明其等价性)F.将出现几率高的分支优先处理,从而提高预测准确率G.优化第一次执行的条件分支 当CPU第一次执行到一个条件分支的时候,默认的预测分支规则是不跳转的那个分支(也就是紧接着条件跳转指令之后的那些指令); (下面的内容主要讨论完全替换掉分支的一些方法; 移除分支意味着代码的性能可以不受输入数据的影响,并可能能更好的使用SIMD类指令)H.使用条件状态值生成掩码来移除条件分支 比如: if (color=0);/求负是为了生成掩码,也可以减1来生成掩码 这里的思路是利用比较来产生0或1值,然后利用生成的值参与运算从而移除了分支; 比如: if (color255) color=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 | (255-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=&_ColorTable256; 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一般都提供了很多能够避免分支的指令,比如条件传送/掩码生成/最值等指令,请查阅指令说明和支持的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/CMOVNA 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指令集(后来的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, PCMPEQW, 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=lWidth-rcwidth;/步长，一维数组6. 7. inti,j;8. 9. unsignedchar*lpSrc;10. 11. lpSrc=(unsignedchar*)lpDIBBits+rc.top*lWidth+rc.left;12. 13. for(i=rc.top;i<=rc.bottom;i+)14. 15. for(j=rc.left;j<=rc.right;j+)16. 17. if(*lpSrc>=iThreshold)18. 19. *lpSrc=255;20. 21. else22. 23. *lpSrc=0;24. 25. lpSrc+;26. 27. 28. lpSrc+=Xstep;29. 30. 写的很好8楼vbar2010-03-20 09:29发表回复学习了。7楼good2008-07-07 11:55发表回复非常有道理，顶6楼wazdxm19802008-04-14 08:28发表回复你好，这是我改写的二值化代码，但运行后，发现效果不对。好像仅对边缘部分起作用。能帮我看一下么？谢谢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 <= 7; i+ )c = c << 8;c |= b;/ 8 pixels are processed in one loopint 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 < nNumberOfLoops; i+ )tmp = _mm_cmpgt_pi8(*pIn, nChange64); / 这句话的意思是*pIn与nChange64的每8位进行比较，如果前者大于后者，返回0xFF,否则返回0。*pOut = tmp;pIn+; / next 8 pixelspOut+;5楼wazdxm19802007-11-30 10:27发表回复to: housisong我按照你的建议做了一下，感觉速度没有明显提高，稍微快了一点点。谢谢4楼housisong2007-11-29 17:38发表回复to: wazdxm1980你可以尝试把if(*lpSrc >= iThreshold)*lpSrc = 255;else*lpSrc = 0;改写成:*lpSrc=(iThreshold_sub1-(*lpSrc) >>8;（iThreshold应该大于0吧! 其中: long iThreshold_sub1= iThreshold-1; /循环外计算）你测试一下看看效果但对于这个问题，建议使用MMX，比如使用PCMPGTB指令3楼wazdxm19802007-11-29 10:01发表回复主要是上面的分支语句，其他的我觉得差不多还可以2楼wazdxm19802007-11-29 10:00发表回复引用举报这是一个常见的二值化代码，void Threshold(LPBYTE lpDIBBits, int lWidth, int lHeight, CRect rc, int iThreshold)int rcwidth = rc.right - rc.left + 1; / roi 区域宽度int Xstep = lWidth - rcwidth; /步长，一维数组int i,j;unsig