代碼優(yōu)化-之-優(yōu)化浮點(diǎn)數(shù)取整

代碼優(yōu)化一之一優(yōu)化浮點(diǎn)數(shù)取整HouSisong@GM2007.05.19tag:浮點(diǎn)數(shù)轉(zhuǎn)換為整數(shù)fpu,sse,sse2,讀緩沖區(qū)優(yōu)化，代碼優(yōu)化ftol，取整,f2l,ftoi,f2i,floattoint摘要：本文首先給出一個(gè)浮點(diǎn)數(shù)取整的需求，并使用默認(rèn)的取整方式，然后通過(guò)嘗試各種方法來(lái)優(yōu)化它的速度；最終的浮點(diǎn)數(shù)取整實(shí)現(xiàn)速度甚至達(dá)到了初始代碼的5倍（是vc6代碼的18倍）?。ㄗ⒁猓何恼轮械臏y(cè)試結(jié)果在不同的CPU和系統(tǒng)環(huán)境下可能有不同的結(jié)果，數(shù)據(jù)僅作參考）（2007.06.08更新：補(bǔ)充SSE3新增的FPU取整指令fisttp的說(shuō)明）（2007.06.04更新：一些修正、補(bǔ)充double取整、補(bǔ)充FPU的RC場(chǎng)說(shuō)明）正文：為了便于討論，這里代碼使用C++,涉及到匯編優(yōu)化的時(shí)候假定為x86平臺(tái)；使用的編譯器為vc2005;測(cè)試使用的CPU為AMD64x24200+,測(cè)試時(shí)使用的單線程執(zhí)行；為了代碼的可讀性，沒(méi)有加入異常處理代碼；A:需要優(yōu)化的原始代碼（使用了大量的浮點(diǎn)數(shù)到整數(shù)的轉(zhuǎn)換）#include<stdio.h>#include<stdlib.h>#include<time.h>volatilelongtestResult;//使用一個(gè)全局域的volatile變量以避免編譯器把需要測(cè)試的代碼優(yōu)化掉constlongtestDataCount=10000000;constlongtestCount=20;floatfSrc[testDataCount];#defineasmasmvoidftol_test_0（）{longtmp=0;for(longi=0;i<testDataCount;++i)tmp+=(long)fSrc[i];//需要優(yōu)化的浮點(diǎn)數(shù)取整testResult=tmp;}intmain(){//intifor(longi=O;i<testDataCount;++i)fSrc[i]=(float)(rand()*(1.0/RAND_MAX)*(rand()—(RAND_MAX〉〉1))*rand()*(1.0/RAND_MAX));//testdoublestart0=(double)clock();for(longc=O;c<testCount;++c)ftol_test_0();startO=((double)clock()-startO)*(1.0/CLOCKS_PER_SEC);//outprintf("Result=%udSeconds=%8.5f",testResult,start0)；return0;}//////////////////////////////////////////////////////////////////////////////////速度測(cè)試：//===============================================================//ftol_test_01.047秒(VC6編譯3.64秒)：//(使用vc2005的SSE編譯選項(xiàng)“/arch:SSE”0.437秒)////////////////////////////////////////////////////////////////////////////////一般編譯器生成的浮點(diǎn)數(shù)轉(zhuǎn)換為整數(shù)的指令序列都比預(yù)想的速度慢很多,它的性能代價(jià)很容易被人忽略；在VC6編譯器下上面的代碼需要運(yùn)行3.64秒，代碼先修改FPU的取整模式（RC場(chǎng)），完成取整后在恢復(fù)RC場(chǎng)；VC2006生成的代碼在CPU支持SSE的時(shí)候會(huì)調(diào)用使用cvttsd2si指令實(shí)現(xiàn)的版本，從而加快了取整的速度，達(dá)到了1.047秒，快了很多！讓我們來(lái)嘗試?yán)^續(xù)優(yōu)化這個(gè)含有大量取整操作的函數(shù)ftol_test_0；B：最容易想到的就是用浮點(diǎn)協(xié)處理器（FPU）（也可以稱作x87）來(lái)優(yōu)化取整將設(shè)置FPU取整方式和恢復(fù)FPU的取整方式的代碼放到循環(huán)體外面從而加快了速度voidftol_test_fpu（）{asm{//設(shè)置FPU的取整方式為了直接使用fistp浮點(diǎn)指令FNSTCWRC_Old//保存協(xié)處理器控制字，用來(lái)恢復(fù)FNSTCWRC_Edit//保存協(xié)處理器控制字，用來(lái)修改FWAITORRC_Edit,OxOFOO//改為RC=11使FPU向零取整FLDCWRC_Edit//載入?yún)f(xié)處理器控制字，RC場(chǎng)已經(jīng)修改movecx,testDataCountxoreax,eaxtestecx,ecxjleEndLoopleaedx,[fSrc+ecx*4]negecxStartLoop:flddwordptr[edx+ecx*4]fistpisrcaddeax,isrcincecxjnzStartLoopEndLoop:movtestResult,eax;//恢復(fù)FPU的取整方式FWAITFLDCWRC_Old}}//RC場(chǎng)占用第11、10bit位用于控制舍入方向//RC=00向最近（或偶數(shù)）舍入RC=01向下（負(fù)無(wú)窮大）舍入//RC=10向上（正無(wú)窮大）舍入RC=11向零舍入//提示：一般的編程語(yǔ)言環(huán)境中，RC場(chǎng)都會(huì)設(shè)置為一個(gè)默認(rèn)值（一般為RC=00）,//語(yǔ)言就可能利用這一點(diǎn)做快速的取整（比如Delphi中的round函數(shù)），但某些引入的//第三方庫(kù)或代碼可能會(huì)修改該默認(rèn)值，從而造成以前運(yùn)行正確的程序出現(xiàn)異常情況//////////////////////////////////////////////////////////////////////////////////速度測(cè)試：//===============================================================//ftol_test_fpu0.407秒////////////////////////////////////////////////////////////////////////////////SSE3增加了一條FPU取整指令fisttp,和fistp指令功能幾乎相同（我的電腦上經(jīng)過(guò)測(cè)試速度也相同）但默認(rèn)向0取整，和RC場(chǎng)設(shè)置無(wú)關(guān)，所以使用fisttp的代碼就可以不管RC場(chǎng)了，有利于簡(jiǎn)化代碼和優(yōu)化性能；C:利用浮點(diǎn)數(shù)的編碼格式來(lái)''手工〃處理浮點(diǎn)數(shù)到整數(shù)的轉(zhuǎn)換（利用了IEEE浮點(diǎn)編碼格式）inlinelongftolieee(floatf){longa=*(long*)(&f);unsignedlongmantissa=(a&((1<<23)-1))|(1<<23);//不支持非規(guī)格化浮點(diǎn)數(shù)longexponent=((a&0x7fffffff)〉〉23);longr=(mantissa<<8)>>(31+127-exponent);longsign=(a〉〉31);return((r入(sign))-sign)&?((exponent-127)〉〉31);}voidftol_test_ieee(){longtmp=0;for(longi=0;i<testDataCount;++i)tmp+=_ftol_ieee(fSrc[i]);testResult=tmp;}//////////////////////////////////////////////////////////////////////////////////速度測(cè)試：//===============================================================//ftol_test_ieee0.828秒////////////////////////////////////////////////////////////////////////////////手工實(shí)現(xiàn)居然超過(guò)了VC2005的SSE實(shí)現(xiàn)（主要是VC2005的實(shí)現(xiàn)函數(shù)調(diào)用開(kāi)銷(xiāo)太大）；如果能夠允許存在誤差的話，還有一個(gè)快速的取整算法（注意，該函數(shù)的結(jié)果和標(biāo)準(zhǔn)不完全相同）：//ftol_test_ieee_M0.438秒D:對(duì)于Double到整數(shù)的轉(zhuǎn)換有一個(gè)超強(qiáng)的算法(利用了IEEE浮點(diǎn)編碼格式)inlinelong_ftol_ieee_MagicNumber(doublex){staticconstdoublemagic=6755399441055744.0;//(1<<51)|(1<<52)doubletmp=x;tmp+=(x>0)?-0.499999999999:+0.499999999999;//如果需要4舍5入取整就去掉這一行tmp+=magic;return*(long*)&tmp;}voidftol_test_ieee_MagicNumber(){longtmp=0;for(longi=0;i<testDataCount;++i)tmp+=_ftol_ieee_MagicNumber(fSrc[i]);testResult=tmp;}（警告：該算法要求FPU的計(jì)算精度為高精度模式，某些程序可能為了速度而將FPU改成了低精度模式，比如在D3D中會(huì)默認(rèn)調(diào)整該設(shè)置）//////////////////////////////////////////////////////////////////////////////////速度測(cè)試：//===============================================================//ftol_test_ieee_MagicNumber1.813秒////////////////////////////////////////////////////////////////////////////////如果需要4舍5入取整，速度就能快出很多，降低到0.407秒(ftol_test_ieee,ftol_test_ieee_MagicNumber的實(shí)現(xiàn)主要參考了：云風(fēng)的《_ftol的優(yōu)化》：/2005/12/_ftol_opt.html和/cgi-bin/fcarticles.cgi?show=64008這里有改動(dòng))E：借鑒vc2005的SSE實(shí)現(xiàn)使用cvttss2si指令voidftol_test_sse(){asm{movecx,testDataCountxoreax,eaxtestecx,ecxjleEndLoopleaedx,[fSrc+ecx*4]negecxStartLoop:cvttss2siebx,dwordptr[edx+ecx*4]addeax,ebx

incecxjnzStartLoopincecxjnzStartLoopEndLoop:movtestResult,eax;//////////////////////////////////////////////////////////////////////////////////速度測(cè)試：//===============================================================//ftol_test_sse0.422秒////////////////////////////////////////////////////////////////////////////////F:cvttss2si是一個(gè)單指令單數(shù)據(jù)流的指令，我們可以使用它的單指令多數(shù)據(jù)流的版本:cvttps2dq指令；它能同時(shí)將4個(gè)float取整！StartLoop://—次循環(huán)處理16個(gè)floatcvttps2dqxmm2,xmmwordptr[edx+ecx*4]cvttps2dqxmm3,xmmwordptr[edx+ecx*4+16]cvttps2dqxmm4,xmmwordptr[edx+ecx*4+16*2]cvttps2dqxmm5,xmmwordptr[edx+ecx*4+16*3]padddxmm2,xmm3padddxmm4,xmm5addecx,16padddxmm0,xmm2padddxmm1,xmm4jnzStartLoopEndLoop:padddxmm0,xmm1movapsxmm1,xmm0movhlpsxmm1,xmm0padddxmm0,xmm1movapsxmm2,xmm0shufpsxmm2,xmm0,1padddxmm0,xmm2movdeax,xmm0movresult,eax}returnresult;}voidftol_test_sse_expand16(){longtmp=0;for(longi=0;i<testDataCount;i+=2000){tmp+=ftol_sse_expand16(&fSrc[i],2000);//2000=16*125}//todo:因?yàn)閠estDataCount是2000的倍數(shù)，所以這里不用處理邊界了testResult=tmp;}//////////////////////////////////////////////////////////////////////////////////速度測(cè)試：//===============================================================//ftol_test_sse_expand160.281秒////////////////////////////////////////////////////////////////////////////////G:由于函數(shù)需要讀取大量的數(shù)據(jù)來(lái)處理，所以可以考慮優(yōu)化讀緩沖區(qū)（也可以考慮使用顯式預(yù)讀指令）

pxorxmm0,xmm0pxorxmm1,xmm1movecx,count16negecxStartLoop:[edx+ecx*4][edx+ecx*4+16][edx+ecx*4+16*2][edx+ecx*4+16*3][edx+ecx*4][edx+ecx*4+16][edx+ecx*4+16*2][edx+ecx*4+16*3]cvttps2dqxmm3,xmmwordptrcvttps2dqxmm4,xmmwordptrcvttps2dqxmm5,xmmwordptrpadddxmm2,xmm3padddxmm4,xmm5addecx,16padddxmm0,xmm2padddxmm1,xmm4jnzStartLoopEndLoop:padddxmm0,xmm1movapsxmm1,xmm0movhlpsxmm1,xmm0padddxmm0,xmm1movapsxmm2,xmm0shufpsxmm2,xmm0,1padddxmm0,xmm2movdeax,xmm0movresult,eax}returnresult;}voidftol_test_sse_expand16_prefetch(){longtmp=0;//////////////////////////////////////////////////////////////////////////////////速度測(cè)試：//===============================================================//ftol_test_sse_expand16_prefetch0.219秒////////////////////////////////////////////////////////////////////////////////H:補(bǔ)充Double的取整，完整測(cè)試源代碼#include<stdio.h>#include<stdlib.h>#include<time.h>volatilelongtestResult;//使用一個(gè)全局域的volatile變量以避免編譯器把需要測(cè)試的代碼優(yōu)化掉constlongtestDataCount=10000000;constlongtestCount=20;doublefSrc[testDataCount];#defineasmasmvoiddftol_test_0(){longtmp=0;for(longi=0;i<testDataCount;++i){tmp+=(long)fSrc[i];//需要優(yōu)化的浮點(diǎn)取整}testResult=tmp;}voiddftol_test_fpu(){longisrc;asm//設(shè)置FPU的取整方式為了直接使用fistp浮點(diǎn)指令{FNSTCWRC_Old//保存協(xié)處理器控制字，用來(lái)恢復(fù)FNSTCWRC_Edit//保存協(xié)處理器控制字，用來(lái)修改FWAITORRC_Edit,OxOFOO//改為RC=11使FPU向零取整FLDCWRCEdit//載入?yún)f(xié)處理器控制字，RC場(chǎng)已經(jīng)修改//}//asm//{movecx,testDataCountxoreax,eaxtestecx,ecxjleEndLoopleaedx,[fSrc+ecx*8]negecxStartLoop:fldqwordptr[edx+ecx*8]fistpisrcaddeax,isrcincecxjnzStartLoop

EndLoop:movtestResult,eax;//}//asm//恢復(fù)FPU的取整方式//{FWAITFLDCWRC_Old}}inlinelongdftol_ieee_MagicNumber(doublex)(1<<5//如果需要(1<<5//如果需要4staticconstdoublemagic=6755399441055744.0;//1)|(1<<52)doubletmp=x;tmp+=(x>0)?-0.499999999999:+0.499999999999;舍5入取整就去掉這一行tmp+=magic;return*(long*)&tmp;}voiddftol_test_ieee_MagicNumber(){longtmp=0;for(longi=0;i<testDataCount;++i)tmp+=dftol_ieee_MagicNumber(fSrc[i]);testResult=tmp;}voiddftol_test_sse2(){asm{movecx,testDataCountxoreax,eaxtestecx,ecxjleEndLoopleaedx,[fSrc+ecx*8]negecxStartLoop:cvttsd2siebx,qwordptr[edx+ecx*8]addeax,ebxincecxjnzStartLoopEndLoop:movtestResult,eax;}}longdftol_sse2_expand8(double*psrc,longcount8){longresult;asm{movecx,count8testecx,ecxjleEndLooppxorxmm0,xmm0pxorxmm1,xmm1movedx,psrcleaedx,[edx+ecx*8]negecxStartLoop://—次循環(huán)處理8個(gè)doublecvttpd2dqxmm2,xmmwordptr[edx+ecx*8]cvttpd2dqxmm3,xmmwordptr[edx+ecx*8+16]cvttpd2dqxmm4,xmmwordptr[edx+ecx*8+16*2]cvttpd2dqxmm5,xmmwordptr[edx+ecx*8+16*3]padddxmm2,xmm3padddxmm4,xmm5addecx,8padddxmm0,xmm2padddxmm1,xmm4jnzStartLoopEndLoop:padddxmm0,xmm1movapsxmm1,xmm0shufpsxmm1,xmm0,1padddxmm0,xmm1movdeax,xmm0movresult,eax}returnresult;}voiddftol_test_sse2_expand8(){longtmp=0;for(longi=0;i<testDataCount;i+=2000){tmp+=dftol_sse2_expand8(&fSrc[i],2000);//2000=8*256}//todo:因?yàn)閠estDataCount是2000的倍數(shù)，所以這里不用處理邊界了testResult=tmp;}longdftol_sse2_expand8_prefetch(double*psrc,longcount8){longresult;asm{movecx,count8testecx,ecxjleEndLoop//預(yù)讀movedx,psrcleaedx,[edx+ecx*8]negecxReadStartLoop:moveax,dwordptr[edx+ecx*8]addecx,8jnzReadStartLooppxorxmm0,xmm0pxorxmm1,xmm1movecx,count8negecxStartLoop:cvttpd2dqxmm2,xmmwordptr[edx+ecx*8]cvttpd2dqxmm3,xmmwordptr[edx+ecx*8+16]cvttpd2dqxmm4,xmmwordptr[edx+ecx*8+16*2]cvttpd2dqxmm5,xmmwordptr[edx+ecx*8+16*3]padddxmm2,xmm3padddxmm4,xmm5addecx,8padddxmm0,xmm2padddxmm1,xmm4jnzStartLoopEndLoop:padddxmm0,xmm1movapsxmm2,xmm0shufpsxmm2,xmm0,1padddxmm0,xmm2movdeax,xmm0movresult,eax}returnresult;}voiddftol_test_sse2_expand8_prefetch(){longtmp=0;for(longi=0;i<testDataCount;i+=2000){tmp+=dftol_sse2_expand8_prefetch(&fSrc[i],2000);}testResult=tmp;}intmain(){//intifor(longi=O;i<testDataCount;++i)fSrc[i]=(float)(rand()*(1.0/RAND_MAX)*(rand()—(RAND_MAX〉〉1))*rand()*(1.0/RAND_MAX));//testdoublestart0=(double)clock();for(longc=O;c