优化很多时候是必要的，特别对于瓶颈程序。这里讨论一段代码的优化过程，从而演示一段简单的代码优化过程,并希望得到一些建议。
先描述一下需求：
一个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．我觉得程序还可以再优化，怎么样做？
欢迎大家就这个简单的优化问题，提出讨论。