優化很多時候是必要的，特別對于瓶頸程序。這里討論一段代碼的優化過程，從而演示一段簡單的代碼優化過程,并希望得到一些建議。
先描述一下需求：
一個16位數的序列，將其奇數位置放到一個序列，偶數問題放到另外一個序列。注意奇數和偶數序列的長度不一定相同。
最簡單的代碼：
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
這段代碼可以達到必要的功能，但他肯定不是優化的。
1．循環中，每次需要訪問5個變量。
2．每次循環需要一個判斷，4個加法
3．最后的不等式判斷也
考慮到dp1和dp2總是同時訪問，于是定義一個結構體：
typedef struct tagDstData
{
short dp1;
short dp2;
}TagDstData;
現在的算法為：
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只需要一次。循環條件少了一次加法。
上面代碼每次復制一個16bit的值，總共四個字節要復制兩次，考慮把這個地方優化一下。優化后的代碼如下：
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);
}
這里先不考慮字節序的問題。
這樣優化后和前面比較起來有那些改進？
1．循環體內只有一個指令；對于++運算，很多處理器都能很好處理。
2．循環條件檢查只有一條比較指令
其實這里的檢查的比較指令還可以優化一下，因為比較指令比較長，看一下下面的改進：
反正是四個字節的復制，不如下計算好復制的4個字節數量；再循環。
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編譯一下發現，測試代碼如下：
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是我寫的用來計算時間的類。
如果把CompareData中訪問spDst的代碼注釋掉，運行的結果：
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編譯，各種運行結果如下：
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中編譯，執行結果如下：
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
當然這里有重復運算對算法的運行時間的影響；但考慮所有的算法都是對同樣的內存操作，不考慮。那么我們發現的就是算法的效率提高是明顯的。算法運行時間縮短為原來的1/3到1/4。
另外有幾個問題需要在這里討論一下：
1．演示了時間問題的同時，還看到一個奇怪的問題就是如果注釋了CompareData，在VC2005上得到的后面兩個算法的時間幾乎為0。為什么？而VC6的編譯沒有這樣的現象？
2．在VC6上編譯得到的結果與VC2005編譯得到的結果相比，VC2005結果更好，為什么？（這個很弱智了）
3．我覺得程序還可以再優化，怎么樣做？
歡迎大家就這個簡單的優化問題，提出討論。