代碼優(yōu)化-之-優(yōu)化條件分支

1、代碼優(yōu)化-之一優(yōu)化條件分支HouSisongGM2007.10.05tag:代碼優(yōu)化，條件分支，飽和，MMX,CMOV,掩碼摘要：條件分支是編程中經(jīng)常使用的基本操作，然而在某些時候它確可能帶來嚴(yán)重的性能問題.當(dāng)前的 CPU 都能對條件分支做預(yù)測(動用了龐大的晶體管資源，如果分支預(yù)測正確，那么條件指令一般只需要花費一個 CPU 周期，而如果預(yù)測錯誤，那么將可能花費幾十個 CPU 周期！本文將討論條件分支的一些有效優(yōu)化方法.正文：文章為收集加經(jīng)驗編輯而成的文章，對優(yōu)化條件分支做了較全面的闡述.文章假定的 CPU 為 x86,示例代碼為 C/C+.A.什么是分支？分支是編程語言中的常見結(jié)構(gòu)；分支可以

2、分為條件分支和非條件分支；條件分支舉例：條件判斷:if(a255)a=255;elseif(a0)a=0;循環(huán)：for(i=0;i1000;+i).;while(!bOk)bOk=.;.對應(yīng)匯編指令的 jnz,jg 等等非條件分支舉例：函數(shù)調(diào)用(call)，函數(shù)返回(return/ret)，軟件中斷(int3)，直接跳轉(zhuǎn)(jmp),.B.CPU 分支預(yù)測錯誤的懲罰由來為了加快 CPU 的處理頻率，現(xiàn)代 CPU 都設(shè)計了多級流水線，有的甚至有 20 級以上；當(dāng) CPU 遇到跳轉(zhuǎn)指令的時候，會做一個預(yù)測，把預(yù)測的分支代碼載入流水線，當(dāng)發(fā)現(xiàn)預(yù)測錯誤的時候，需要清空流水線，重新載入正確的分支到流水線；

3、那么預(yù)測錯誤的代價周期數(shù)至少應(yīng)該和流水線長度相當(dāng)；然而考慮到各級的緩存失效、指令解碼等等，實際損失的周期數(shù)有可能是流水線長度的幾倍！對于非條件分支，一般來說 CPU 都能得到相當(dāng)高的預(yù)測準(zhǔn)確率；我們主要來討論一下條件分支的預(yù)測；(有人可能會說，當(dāng) CPU 遇到條件分支時不做預(yù)測不就沒有預(yù)測錯誤的懲罰了嗎？這種流水線空著的懲罰實質(zhì)和每次都預(yù)測錯誤然后清空流水線的代價相當(dāng)，退一步說就算每次隨機選擇一個分支來執(zhí)行也有 50%的收益)C:需要優(yōu)化的條件分支當(dāng)前的 CPU 對各種簡單的條件分支模式都能做出很的預(yù)測，比如奇偶模式：for(inti=0;i=64)|(b1=64).b0,b1=0改寫為:if

4、(b0|b1)=64).(請嘗試證明其等價性)F.將出現(xiàn)幾率高的分支優(yōu)先處理，從而提高預(yù)測準(zhǔn)確率G.優(yōu)化第一次執(zhí)行的條件分支當(dāng) CPU 第一次執(zhí)行到一個條件分支的時候，默認(rèn)的預(yù)測分支規(guī)則是不跳轉(zhuǎn)的那個分支(也就是緊接著條件跳轉(zhuǎn)指令之后的那些指令)；(下面的內(nèi)容主要討論完全替換掉分支的一些方法；移除分支意味著代碼的性能可以不受輸入數(shù)據(jù)的影響，并可能能更女?的使用 SIMD 類指令)H.使用條件狀態(tài)值生成掩碼來移除條件分支比如：if(color=0);/求負是為了生成掩碼，也可以減 1 來生成掩碼這里的思路是利用比較來產(chǎn)生 0 或 1 值，然后利用生成的值參與運算從而移除了分支；比如：if(col

5、or255)color=255;改寫為：color=(color|-(color255)&0 xFF;比如：if(a=b)returna;elsereturnb;改寫為：returna+(b-a)&-(ba);(警告：這里利用了 C/C+中比較的結(jié)果是 0 或 1,在其他語言或編譯器中可能定義不同)I.使用帶符號的移位生成掩碼來移除條件分支(建議使用該方案替代上面的條件狀態(tài)值方案)比如：if(color31);/帶符號移位從而生成需要的掩碼比如：if(color255)color=255;改寫為：color=(color|(255-color)31)&0 xFF;比如：

6、if(a=b)returna;elsereturnb;改寫為：returna+(b-a)&-(ba);移除分支的一個更通用的思路：針對不同類的數(shù)據(jù)生成不同的掩碼數(shù)據(jù)，然后讓原數(shù)據(jù)和掩碼參與運算得到想要的結(jié)果，從而移除分支；J:查表法移除分支比如：if(color255)color=255;/假設(shè) color 屬于-256.512改寫為：color=ColorTablecolor;其中 ColorTable 的建立：_ColorTable512+256+1;ColorTable=&_ColorTable256;for(i=-256;i=512;+i)if(i255)ColorTa

7、blei=255;elseColorTablei=i;比如：if(score=90)/score 屬于0.100returnA;|elseif(score=75)returnB;|elseif(score=60)returnC;|elsereturnD;|改寫為:returnscTablescore;其中 scTable 應(yīng)該預(yù)先存的值就不用再寫了吧:)K:使用 CMOV 條件傳送指令來移除條件分支(為了避免分支預(yù)測錯誤造成的性能損失，現(xiàn)代的 CPU 一般都提供了很多能夠避免分支的指令，比如條件傳送/掩碼生成/最值等指令，請查閱指令說明和支持的 CPU)CMOV 條件傳送指令是很多條具體的指令

8、，它們根據(jù)條件寄存器的值來決定是否賦值比如：if(x0)x=-x;用 CMOV 改寫為(匯編):movedx,eax/假設(shè) x 的值在 eax 寄存器，該指令使 edx=eaxnegeax/eax=-eax/該指令的結(jié)果將設(shè)置條件寄存器的狀態(tài)cmovseax,edx/如果狀態(tài)為負，將 edx 的值傳遞給 eaxCMOV 指令列表:CMOVA/CMOVNBECMOVAE/CMOVNB/CMOVNCCMOVB/CMOVC/CMOVNAECMOVBE/CMOVNACMOVE/CMOVZCMOVG/CMOVNLECMOVGE/CMOVNLCMOVL/CMOVNGECMOVLE/CMOVNGCMOVNE

9、/CMOVNZCMOVNOCMOVNP/CMOVPOCMOVNSCMOVOCMOVP/CMOVPECMOVSx87 浮點 CMOV 指令列表：FCMOVBFCMOVBEFCMOVEFCMOVNBFCMOVNBEFCMOVNEFCMOVNUFCMOVUL:使用 MMX/SSE2 中的飽和指令對于顏色的飽和處理，比如：if(color255)color=255;x86CPU 從奔騰 MMX 開始，提供了 MMX 指令集(后來的 SSE2 也有類似指令);增加了對飽和處理的指令支持，在圖像處理和聲音處理中得到了廣泛應(yīng)用；(我的 blog 的很多文章有使用 MMX/SSE 指令的例子)(MMX/SSE

10、 之類的 SIMD 指令還能夠同時并行執(zhí)行多路數(shù)據(jù)，從而加快執(zhí)行速度)M:使用 CMP 掩碼生成指令來移除條件分支比如：/r=(xx,生成掩碼 0 xFFFFFFFF 或者 0pandmm0,mm3/a 或者 0pandnmm3,mm1/0 或者 bpormm0,mm3CMP 指令包括：CMPPS,CMPSS,CMPPD,CMPS,CMPSB,CMPSW,CMPSDPCMPEQB,PCMPEQD,PCMPEQW,PCMPGTB,PCMPGTD,PCMPGTWCMPXCHG,CMPXCHG8B 等N:使用 MIN/MAX 指令來移除條件分支MAXPS,MAXPD,MAXSS,MAXSD,MINP

11、S,MINPD,MINSS,MINSDPMAXSW,PMAXUB,PMINSW,PMINUB 等上一篇：Alpha顏色混合的魔法上篇下一篇：Alpha顏色混合的魔法下篇查看評論9樓kissthefuture2011-07-0716:13發(fā)表回復(fù)viewplain1.voidThreshold(LPBYTElpDIBBits,intlWidth,intlHeight,CRectrc,intiThreshold)2.6.7.inti,j;8.9.unsignedchar*lpSrc;10.11.lpSrc=(unsignedchar*)lpDIBBits+rc.top*lWidth+rc.left

12、;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-2009:29發(fā)表回復(fù)分享到:3.intrcwidth=rc.right-rc.left+1;/roi區(qū)域?qū)挾?.5.intXstep=lWidth-rcwi

13、dth;/步長，一維數(shù)組學(xué)習(xí)了7樓good2008-07-0711:55發(fā)表回復(fù)非常有道理，頂6樓wazdxm19802008-04-1408:28發(fā)表回復(fù)你好，這是我改寫的二值化代碼，但運行后，發(fā)現(xiàn)效果不對。好像僅對邊緣部分起作用。能幫我看一下么？謝謝voidTHRESHOLD_MMX(BYTE*pSource,BYTE*pDest,intnNumberOfPixels,intThresh)BYTEb=(BYTE)abs(Thresh);/make64bitsvaluewithbineachbyte_int64c=b;for(inti=1;i<=7;i+)|c=c&lt

14、;<8;c|=b;/8pixelsareprocessedinoneloop|intnNumberOfLoops=nNumberOfPixels/8;_m64*pIn=(_m64*)pSource;/inputpointer_m64*pOut=(_m64*)pDest;/outputpointer_m64tmp;/workvariable_mm_empty();/emms_m64nChange64=Get_m64(c);for(i=0;i<nNumberOfLoops;i+)(tmp=_mm_cmpgt_pi8(*pIn,nChange64);/這句話的意思是*pI

15、n與nChange64的每8位進行比較，如果前者大于后者，返回0 xFF,否則返回0。*pOut=tmp;pIn+;/next8pixelspOut+;5樓wazdxm19802007-11-3010:27發(fā)表回復(fù)to:housisong我按照你的建議做了一下，感覺速度沒有明顯提高，稍微快了一點點謝謝4樓housisong2007-11-2917:38發(fā)表回復(fù)to:wazdxm1980你可以嘗試把if(*lpSrc>=iThreshold)*lpSrc=255;else*lpSrc=0;改寫成：*lpSrc=(iThreshold_sub1-(*lpSrc)>&am

16、p;gt;8;(iThreshold應(yīng)該大于0吧！其中：longiThreshold_sub1=iThreshold-1;/循環(huán)外計算)你測試一下看看效果但對于這個問題，建議使用MMX，比如使用PCMPGTB指令|3樓wazdxm19802007-11-2910:01發(fā)表回復(fù)主要是上面的分支語句，其他的我覺得差不多還可以2樓wazdxm19802007-11-2910:00發(fā)表回復(fù)引用舉報這是一個常見的二值化代碼，voidThreshold(LPBYTEIpDIBBits,intIWidth,intIHeight,CRectrc,intiThreshold)(intrcwidth=rc.right-rc.left+1;/roi區(qū)域?qū)挾萯ntXstep=lWidth-rcwidth;/步長，一維數(shù)組inti,j;un