優(yōu)化很多時(shí)候是必要的，特別對(duì)于瓶頸程序。這里討論一段代碼的優(yōu)化過(guò)程，從而演示一段簡(jiǎn)單的代碼優(yōu)化過(guò)程,并希望得到一些建議。
先描述一下需求：
一個(gè)16位數(shù)的序列，將其奇數(shù)位置放到一個(gè)序列，偶數(shù)問(wèn)題放到另外一個(gè)序列。注意奇數(shù)和偶數(shù)序列的長(zhǎng)度不一定相同。
最簡(jiǎn)單的代碼：
1
void CTestClass::SplitToEvenOddSeqs(short *sp,short *dp1,short *dp2,int evenLen,int oddLen)
2
3
{
4
5 int i;
6
7 for(i = 0;i<oddLen;i++,sp+=2,dp1++,dp2++)
8
9
{
10
11 dp1[0] = sp[0];
12
13 dp2[0] = sp[1];
14
15
}
16
17 if(i != evenLen)
18
19 dp1[0] = sp[0];
20
21
}
22
23
這段代碼可以達(dá)到必要的功能，但他肯定不是優(yōu)化的。
1．循環(huán)中，每次需要訪問(wèn)5個(gè)變量。
2．每次循環(huán)需要一個(gè)判斷，4個(gè)加法
3．最后的不等式判斷也
考慮到dp1和dp2總是同時(shí)訪問(wèn)，于是定義一個(gè)結(jié)構(gòu)體：
typedef struct tagDstData
{
short dp1;
short dp2;
}TagDstData;
現(xiàn)在的算法為：
void CTestClass::SplitToEvenOddSeqs(short *sp,TagDstData *dp,int evenLen,int oddLen)
{
int i;
for(i = 0;i<oddLen;i++,sp+=2,dp++){
dp->dp1 = sp[0];
dp->dp2 = sp[1];
}
if(i < evenLen)
dp->dp1 = sp[0];
}
這樣做以后CPU每次讀取dp只需要一次。循環(huán)條件少了一次加法。
上面代碼每次復(fù)制一個(gè)16bit的值，總共四個(gè)字節(jié)要復(fù)制兩次，考慮把這個(gè)地方優(yōu)化一下。優(yōu)化后的代碼如下：
void CTestClass::SplitToEvenOddSeqs2(short *sp,TagDstData *dp,int evenLen,int oddLen)
{
long *lSp = (long *)sp;
long *spEnd = (long *)(sp + (oddLen<<1));
long *lDp = (long *)dp;
while(lSp < spEnd){
*lDp++ = *lSp++;
}
if(oddLen < evenLen)
dp[evenLen].dp1 = *((short *)lSp);
}
這里先不考慮字節(jié)序的問(wèn)題。
這樣優(yōu)化后和前面比較起來(lái)有那些改進(jìn)？
1．循環(huán)體內(nèi)只有一個(gè)指令；對(duì)于++運(yùn)算，很多處理器都能很好處理。
2．循環(huán)條件檢查只有一條比較指令
其實(shí)這里的檢查的比較指令還可以優(yōu)化一下，因?yàn)楸容^指令比較長(zhǎng)，看一下下面的改進(jìn)：
反正是四個(gè)字節(jié)的復(fù)制，不如下計(jì)算好復(fù)制的4個(gè)字節(jié)數(shù)量；再循環(huán)。
void CTestClass::SplitToEvenOddSeqs3(short *sp,TagDstData *dp,int evenLen,int oddLen)
{
long *lSp = (long *)sp;
long *spEnd = (long *)(sp + (oddLen<<1));
long *lDp = (long *)dp;
long nDWORDs = oddLen>>1;
while(nDWORDs–){
*lDp++ = *lSp++;
}
if(oddLen - evenLen)
dp[evenLen].dp1 = *((short *)lSp);
}
寫好上面四段代碼，拿VS2005編譯一下發(fā)現(xiàn)，測(cè)試代碼如下：
void CompareData(TagDstData *spDst,short *pSrcTest)
{
for(int i = 0;i<10240;i++)
{
//if(spDst[0].dp1 )//if we access spDst here, the time will be longer
if(spDst[0].dp1 > pSrcTest[0]|| spDst[0].dp2 >pSrcTest[1])
{
printf(”
Split arithmetic is not right!\n”);
break;
}
pSrcTest +=2;
}
printf(”
Split arithmetic is right!\n”);
}
int _tmain(int argc, _TCHAR* argv[])
{
int i,f ;
int now;
CTestClass testClass;
short spSrc[20480];
short spDst1[10240];
short spDst2[10240];
TagDstData spDst[10240];
short *pSrcTest = spSrc;
memset(spSrc,2,20480<<1);
memset(spDst1,0,10240<<1);
memset(spDst2,0,10240<<1);
memset(spDst,0,20480<<1);
CStopWatch stop1;
stop1.Start();
for(i = 0;i<100000; i++)
testClass.SplitToEvenOddSeqs(spSrc,spDst1,spDst2,10240,10240);
now = stop1.Now();
printf(”time2 =%d\n”,now);
stop1.Start();
for(i = 0;i<100000; i++)
testClass.SplitToEvenOddSeqs(spSrc,spDst,10240,10240);
now = stop1.Now();
printf(”time3 =%d\n”,now);
for(i=0;i<20480;i++)
spSrc[i] = i;
memset(spDst,0,10240<<1);
CStopWatch stop2;
for(f = 0;f<100000; f++)
testClass.SplitToEvenOddSeqs2(spSrc,spDst,10240,10240);
now = stop2.Now();
printf(”time4 =%d\n”,now);
CompareData(spDst,pSrcTest);
memset(spDst,0,10240<<1);
CStopWatch stop3;
for(f = 0;f<100000; f++)
testClass.SplitToEvenOddSeqs3(spSrc,spDst,10240,10240);
now = stop3.Now();
printf(”time5 =%d\n”,now);
CompareData(spDst,pSrcTest);
return 0;
}
注：其中CStopWatch是我寫的用來(lái)計(jì)算時(shí)間的類。
如果把CompareData中訪問(wèn)spDst的代碼注釋掉，運(yùn)行的結(jié)果：
Intel® Core™2 CPU 6400 2.13Ghz 1GB
time2 =753945 us
time3 =494852 us
time4 =0 us
time5 =0 us
Intel® Core™2 Duo CPU T7250 @2.00GHz 2.00 GHz 2GB
Time2 = 847431 us
Time3=523269 us
Time4=1 us
Time5 =1 us
Pentium® 4 CPU 2.6 GHz 512MB
Time2 = 613622 us
Time3=616545 us
Time4=1 us
Time5 =1 us
如果使用VC6編譯，各種運(yùn)行結(jié)果如下：
Intel® Core™2 CPU 6400 2.13Ghz 1GB
time2 =2041530 us
time3 =1352753 us
time4 =930849 us
time5 =501492 us
Intel® Core™2 Duo CPU T7250 @2.00GHz 2.00 GHz 2GB
time2 =1878766 ustime3 =1380009 ustime4 =959918 us
time5 =523022 us
Pentium® 4 CPU 2.6 GHz 512MB
time2 =2098438 us
time3 =1855219 us
time4 =1068678 us
time5 =610458 us
再把CompareData還原，在VC2005中編譯，執(zhí)行結(jié)果如下：
Intel® Core™2 CPU 6400 2.13Ghz 1GB
time2 =1007759 us
time3 =1364986 us
time4 =876046 us
time5 =437623 us
Intel® Core™2 Duo CPU T7250 @2.00GHz 2.00 GHz 2GB
time2 =1103970 ustime3 =1403941 ustime4 =630279 ustime5 =313330 us
Pentium® 4 CPU 2.6 GHz 512MB
time2 =1218860 ustime3 =1743361 ustime4 =478785 us
time5 =241885 us
使用VC6重新編譯：
Intel® Core™2 CPU 6400 2.13Ghz 1GB
time2 =2026392 us
time3 =1359155 us
time4 =946604 us
time5 =511307 us
Intel® Core™2 Duo CPU T7250 @2.00GHz 2.00 GHz 2GB
time2 =1921379 ustime3 =1410035 ustime4 =967616 ustime5 =528601 us
Pentium® 4 CPU 2.6 GHz 512MB
time2 =2089173 ustime3 =1849719 ustime4 =1062956 ustime5 =610357 us
當(dāng)然這里有重復(fù)運(yùn)算對(duì)算法的運(yùn)行時(shí)間的影響；但考慮所有的算法都是對(duì)同樣的內(nèi)存操作，不考慮。那么我們發(fā)現(xiàn)的就是算法的效率提高是明顯的。算法運(yùn)行時(shí)間縮短為原來(lái)的1/3到1/4。
另外有幾個(gè)問(wèn)題需要在這里討論一下：
1．演示了時(shí)間問(wèn)題的同時(shí)，還看到一個(gè)奇怪的問(wèn)題就是如果注釋了CompareData，在VC2005上得到的后面兩個(gè)算法的時(shí)間幾乎為0。為什么？而VC6的編譯沒有這樣的現(xiàn)象？
2．在VC6上編譯得到的結(jié)果與VC2005編譯得到的結(jié)果相比，VC2005結(jié)果更好，為什么？（這個(gè)很弱智了）
3．我覺得程序還可以再優(yōu)化，怎么樣做？
歡迎大家就這個(gè)簡(jiǎn)單的優(yōu)化問(wèn)題，提出討論。