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

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