當(dāng)初在學(xué)校實(shí)驗(yàn)室的時(shí)候，常常寫一個(gè)算法，讓程序跑著四處去晃蕩一下回來，結(jié)果也就出來了?？晒ぷ骱?，算法效率似乎重要多了，畢竟得真槍實(shí)彈放到產(chǎn)品中，賣給客戶的；很多時(shí)候，還要搞到嵌入式設(shè)備里實(shí)時(shí)地跑，這么一來真是壓力山大了~~~。這期間，對(duì)于程序優(yōu)化也算略知皮毛，下面就針對(duì)這個(gè)問題講講。
首先說明一下，這里說的程序優(yōu)化是指程序效率的優(yōu)化。一般來說，程序優(yōu)化主要是以下三個(gè)步驟：
1.算法優(yōu)化
2.代碼優(yōu)化
3.指令優(yōu)化
算法優(yōu)化
算法上的優(yōu)化是必須首要考慮的，也是最重要的一步。一般我們需要分析算法的時(shí)間復(fù)雜度，即處理時(shí)間與輸入數(shù)據(jù)規(guī)模的一個(gè)量級(jí)關(guān)系，一個(gè)優(yōu)秀的算法可以將算法復(fù)雜度降低若干量級(jí)，那么同樣的實(shí)現(xiàn)，其平均耗時(shí)一般會(huì)比其他復(fù)雜度高的算法少（這里不代表任意輸入都更快）。
比如說排序算法，快速排序的時(shí)間復(fù)雜度為O(nlogn)，而插入排序的時(shí)間復(fù)雜度為O(n*n)，那么在統(tǒng)計(jì)意義下，快速排序會(huì)比插入排序快，而且隨著輸入序列長(zhǎng)度n的增加，兩者耗時(shí)相差會(huì)越來越大。但是，假如輸入數(shù)據(jù)本身就已經(jīng)是升序(或降序)，那么實(shí)際運(yùn)行下來，快速排序會(huì)更慢。
因此，實(shí)現(xiàn)同樣的功能，優(yōu)先選擇時(shí)間復(fù)雜度低的算法。比如對(duì)圖像進(jìn)行二維可分的高斯卷積，圖像尺寸為MxN，卷積核尺寸為PxQ，那么
直接按卷積的定義計(jì)算，時(shí)間復(fù)雜度為O(MNPQ)
如果使用2個(gè)一維卷積計(jì)算，則時(shí)間復(fù)雜度為O(MN(P+Q))
使用2個(gè)一位卷積+FFT來實(shí)現(xiàn)，時(shí)間復(fù)雜度為O(MNlogMN)
如果采用高斯濾波的遞歸實(shí)現(xiàn)，時(shí)間復(fù)雜度為O(MN)（參見paper：Recursive implementation of the Gaussian filter，源碼在GIMP中有）
很顯然，上面4種算法的效率是逐步提高的。一般情況下，自然會(huì)選擇最后一種來實(shí)現(xiàn)。
還有一種情況，算法本身比較復(fù)雜，其時(shí)間復(fù)雜度難以降低，而其效率又不滿足要求。這個(gè)時(shí)候就需要自己好好地理解算法，做些修改了。一種是保持算法效果來提升效率，另一種是舍棄部分效果來?yè)Q取一定的效率，具體做法得根據(jù)實(shí)際情況操作。
代碼優(yōu)化
代碼優(yōu)化一般需要與算法優(yōu)化同步進(jìn)行，代碼優(yōu)化主要是涉及到具體的編碼技巧。同樣的算法與功能，不同的寫法也可能讓程序效率差異巨大。一般而言，代碼優(yōu)化主要是針對(duì)循環(huán)結(jié)構(gòu)進(jìn)行分析處理，目前想到的幾條原則是：
a.避免循環(huán)內(nèi)部的乘(除)法以及冗余計(jì)算
這一原則是能把運(yùn)算放在循環(huán)外的盡量提出去放在外部，循環(huán)內(nèi)部不必要的乘除法可使用加法來替代等。如下面的例子，灰度圖像數(shù)據(jù)存在BYTE Img[MxN]的一個(gè)數(shù)組中，對(duì)其子塊　　(R1至R2行，C1到C2列)像素灰度求和，簡(jiǎn)單粗暴的寫法是：

1 int sum = 0;
2 for(int i = R1; i < R2; i++)
3 {
4     for(int j = C1; j < C2; j++)
5     {
6         sum += Image[i * N + j];
7     }
8 }

但另一種寫法：
1 int sum = 0;
2 BYTE *pTemp = Image + R1 * N;
3 for(int i = R1; i < R2; i++, pTemp += N)
4 {
5     for(int j = C1; j < C2; j++)
6     {
7         sum += pTemp[j];
8     }
9 }

可以分析一下兩種寫法的運(yùn)算次數(shù)，假設(shè)R=R2-R1，C=C2-C1，前面一種寫法i++執(zhí)行了R次，j++和sum+=…這句執(zhí)行了RC次，則總執(zhí)行次數(shù)為3RC+R次加法，RC次乘法；同　　樣地可以分析后面一種寫法執(zhí)行了2RC+2R+1次加法，1次乘法。性能孰好孰壞顯然可知。
b.避免循環(huán)內(nèi)部有過多依賴和跳轉(zhuǎn)，使cpu能流水起來
關(guān)于CPU流水線技術(shù)可google/baidu，循環(huán)結(jié)構(gòu)內(nèi)部計(jì)算或邏輯過于復(fù)雜，將導(dǎo)致cpu不能流水，那這個(gè)循環(huán)就相當(dāng)于拆成了n段重復(fù)代碼的效率。
另外ii值是衡量循環(huán)結(jié)構(gòu)的一個(gè)重要指標(biāo)，ii值是指執(zhí)行完1次循環(huán)所需的指令數(shù)，ii值越小，程序執(zhí)行耗時(shí)越短。下圖是關(guān)于cpu流水的簡(jiǎn)單示意圖：

簡(jiǎn)單而不嚴(yán)謹(jǐn)?shù)卣f，cpu流水技術(shù)可以使得循環(huán)在一定程度上并行，即上次循環(huán)未完成時(shí)即可處理本次循環(huán)，這樣總耗時(shí)自然也會(huì)降低。
先看下面一段代碼：

1 for(int i = 0; i < N; i++)
2 {
3     if(i < 100) a[i] += 5;
4     else if(i < 200) a[i] += 10;
5     else a[i] += 20;
6 }

這段代碼實(shí)現(xiàn)的功能很簡(jiǎn)單，對(duì)數(shù)組a的不同元素累加一個(gè)不同的值，但是在循環(huán)內(nèi)部有3個(gè)分支需要每次判斷，效率太低，有可能不能流水；可以改寫為3個(gè)循環(huán)，這樣循環(huán)內(nèi)部就不　　用進(jìn)行判斷，這樣雖然代碼量增多了，但當(dāng)數(shù)組規(guī)模很大(N很大)時(shí)，其效率能有相當(dāng)?shù)膬?yōu)勢(shì)。改寫的代碼為：
1 for(int i = 0; i < 100; i++)
 2 {
 3     a[i] += 5;       
 4 }
 5 for(int i = 100; i < 200; i++)
 6 {
 7     a[i] += 10;       
 8 }
 9 for(int i = 200; i < N; i++)
10 {
11     a[i] += 20;
12 }
關(guān)于循環(huán)內(nèi)部的依賴，見如下一段程序：
1 for(int i = 0; i < N; i++)
2 {
3     int x = f(a[i]);
4     int y = g(x);
5     int z = h(x,y);
6 }
其中f，g，h都是一個(gè)函數(shù)，可以看到這段代碼中x依賴于a[i]，y依賴于x，z依賴于xy，每一步計(jì)算都需要等前面的都計(jì)算完成才能進(jìn)行，這樣對(duì)cpu的流水結(jié)構(gòu)也是相當(dāng)不利的，盡　　量避免此類寫法。另外C語言中的restrict關(guān)鍵字可以修飾指針變量，即告訴編譯器該指針指向的內(nèi)存只有其自己會(huì)修改，這樣編譯器優(yōu)化時(shí)就可以無所顧忌，但目前VC的編譯器似乎不支　　持該關(guān)鍵字，而在DSP上，當(dāng)初使用restrict后，某些循環(huán)的效率可提升90%。
c.定點(diǎn)化
定點(diǎn)化的思想是將浮點(diǎn)運(yùn)算轉(zhuǎn)換為整型運(yùn)算，目前在PC上我個(gè)人感覺差別還不算大，但在很多性能一般的DSP上，其作用也不可小覷。定點(diǎn)化的做法是將數(shù)據(jù)乘上一個(gè)很大的數(shù)后，將　　所有運(yùn)算轉(zhuǎn)換為整數(shù)計(jì)算。例如某個(gè)乘法我只關(guān)心小數(shù)點(diǎn)后3位，那把數(shù)據(jù)都乘上10000后，進(jìn)行整型運(yùn)算的結(jié)果也就滿足所需的精度了。
d.以空間換時(shí)間
空間換時(shí)間最經(jīng)典的就是查表法了，某些計(jì)算相當(dāng)耗時(shí)，但其自變量的值域是比較有限的，這樣的情況可以預(yù)先計(jì)算好每個(gè)自變量對(duì)應(yīng)的函數(shù)值，存在一個(gè)表格中，每次根據(jù)自變量的　　值去索引對(duì)應(yīng)的函數(shù)值即可。如下例：
1 //直接計(jì)算
 2 for(int i = 0 ; i < N; i++)
 3 {
 4     double z = sin(a[i]);
 5 }
 6
 7 //查表計(jì)算
 8 double aSinTable[360] = {0, ..., 1,...,0,...,-1,...,0};
 9 for(int i = 0 ; i < N; i++)
10 {
11     double z = aSinTable[a[i]];
12 }
后面的查表法需要額外耗一個(gè)數(shù)組double aSinTable[360]的空間，但其運(yùn)行效率卻快了很多很多。
e.預(yù)分配內(nèi)存
預(yù)分配內(nèi)存主要是針對(duì)需要循環(huán)處理數(shù)據(jù)的情況的。比如視頻處理，每幀圖像的處理都需要一定的緩存，如果每幀申請(qǐng)釋放，則勢(shì)必會(huì)降低算法效率，如下所示：
1 //處理一幀
 2 void Process(BYTE *pimg)
 3 {
 4     malloc
 5     ...
 6     free
 7 }
 8
 9 //循環(huán)處理一個(gè)視頻
10 for(int i = 0; i < N; i++)
11 {
12     BYTE *pimg = readimage();
13     Process(pimg)；
14 }
1 //處理一幀
 2 void Process(BYTE *pimg， BYTE *pBuffer)
 3 {
 4     ...
 5 }
 6
 7 //循環(huán)處理一個(gè)視頻
 8 malloc pBuffer
 9 for(int i = 0; i < N; i++)
10 {
11     BYTE *pimg = readimage();
12     Process(pimg, pBuffer)；
13 }
14 free
前一段代碼在每幀處理都malloc和free，而后一段代碼則是有上層傳入緩存，這樣內(nèi)部就不需每次申請(qǐng)和釋放了。當(dāng)然上面只是一個(gè)簡(jiǎn)單說明，實(shí)際情況會(huì)比這復(fù)雜得多，但整體思想　　是一致的。
指令優(yōu)化
對(duì)于經(jīng)過前面算法和代碼優(yōu)化的程序，一般其效率已經(jīng)比較不錯(cuò)了。對(duì)于某些特殊要求，還需要進(jìn)一步降低程序耗時(shí)，那么指令優(yōu)化就該上場(chǎng)了。指令優(yōu)化一般是使用特定的指令集，可快速實(shí)現(xiàn)某些運(yùn)算，同時(shí)指令優(yōu)化的另一個(gè)核心思想是打包運(yùn)算。目前PC上intel指令集有MMX，SSE和SSE2/3/4等，DSP則需要跟具體的型號(hào)相關(guān)，不同型號(hào)支持不同的指令集。intel指令集需要intel編譯器才能編譯，安裝icc后，其中有幫助文檔，有所有指令的詳細(xì)說明。
例如MMX里的指令 __m64 _mm_add_pi8(__m64 m1, __m64 m2)，是將m1和m2中8個(gè)8bit的數(shù)對(duì)應(yīng)相加，結(jié)果就存在返回值對(duì)應(yīng)的比特段中。假設(shè)2個(gè)N數(shù)組相加，一般需要執(zhí)行N個(gè)加法指令，但使用上述指令只需執(zhí)行N/8個(gè)指令，因?yàn)槠?個(gè)指令能處理8個(gè)數(shù)據(jù)。
實(shí)現(xiàn)求2個(gè)BYTE數(shù)組的均值，即z[i]=(x[i]+y[i])/2，直接求均值和使用MMX指令實(shí)現(xiàn)2種方法如下程序所示：
1 #define N 800
 2 BYTE x[N],Y[N], Z[N];
 3 inital x,y;...
 4 //直接求均值
 5 for(int i = 0; i < N; i++)
 6 {
 7     z[i] = (x[i] + y[i]) >> 1;
 8 }
 9
10 //使用MMX指令求均值，這里N為8的整數(shù)倍，不考慮剩余數(shù)據(jù)處理
11 __m64 m64X, m64Y, m64Z;
12 for(int i = 0; i < N; i+=8)
13 {
14     m64X = *(__m64 *)(x + i);
15     m64Y = *(__m64 *)(y + i);
16     m64Z = _mm_avg_pu8(m64X, m64Y);
17     *(__m64 *)(x + i) = m64Z;
18 }
使用指令優(yōu)化需要注意的問題有：
a.關(guān)于值域，比如2個(gè)8bit數(shù)相加，其值可能會(huì)溢出；若能保證其不溢出，則可使用一次處理8個(gè)數(shù)據(jù)，否則，必須降低性能，使用其他指令一次處理4個(gè)數(shù)據(jù)了；
b.剩余數(shù)據(jù)，使用打包處理的數(shù)據(jù)一般都是4、8或16的整數(shù)倍，若待處理數(shù)據(jù)長(zhǎng)度不是其單次處理數(shù)據(jù)個(gè)數(shù)的整數(shù)倍，剩余數(shù)據(jù)需單獨(dú)處理；
補(bǔ)充——如何定位程序熱點(diǎn)
程序熱點(diǎn)是指程序中最耗時(shí)的部分，一般程序優(yōu)化工作都是優(yōu)先去優(yōu)化熱點(diǎn)部分，那么如何來定位程序熱點(diǎn)呢？
一般而言，主要有2種方法，一種是通過觀察與分析，通過分析算法，自然能知道程序熱點(diǎn)；另一方面，觀察代碼結(jié)構(gòu)，一般具有最大循環(huán)的地方就是熱點(diǎn)，這也是前面那些優(yōu)化手段都針對(duì)循環(huán)結(jié)構(gòu)的原因。
另一種方法就是利用工具來找程序熱點(diǎn)。x86下可以使用vtune來定位熱點(diǎn)，DSP下可使用ccs的profile功能定位出耗時(shí)的函數(shù)，更近一步地，通過查看編譯保留的asm文件，可具體分析每個(gè)循環(huán)結(jié)構(gòu)情況，了解到該循環(huán)是否能流水，循環(huán)ii值，以及制約循環(huán)ii值是由于變量的依賴還是運(yùn)算量等詳細(xì)信息，從而進(jìn)行有針對(duì)性的優(yōu)化。由于Vtune剛給卸掉，沒法截圖；下圖是CCS編譯生成的一個(gè)asm文件中一個(gè)循環(huán)的截圖：

最后提一點(diǎn)，某些代碼使用Intel編譯器編譯可以比vc編譯器編譯出的程序快很多，我遇到過最快的可相差10倍。對(duì)于gcc編譯后的效率，目前還沒測(cè)試過。