淺談程序優化

w427 9年前發布 | 17K 次閱讀程序優化

當初在學校實驗室的時候，常常寫一個算法，讓程序跑著四處去晃蕩一下回來，結果也就出來了。可工作后，算法效率似乎重要多了，畢竟得真槍實彈放到產品中，賣給客戶的；很多時候，還要搞到嵌入式設備里實時地跑，這么一來真是壓力山大了~~~。這期間，對于程序優化也算略知皮毛，下面就針對這個問題講講。首先說明一下，這里說的程序優化是指程序效率的優化。一般來說，程序優化主要是以下三個步驟： 1.算法優化 2.代碼優化 3.指令優化 算法優化

算法上的優化是必須首要考慮的，也是最重要的一步。一般我們需要分析算法的時間復雜度，即處理時間與輸入數據規模的一個量級關系，一個優秀的算法可以將算法復雜度降低若干量級，那么同樣的實現，其平均耗時一般會比其他復雜度高的算法少（這里不代表任意輸入都更快）。比如說排序算法，快速排序的時間復雜度為O(nlogn)，而插入排序的時間復雜度為O(n*n)，那么在統計意義下，快速排序會比插入排序快，而且隨著輸入序列長度n的增加，兩者耗時相差會越來越大。但是，假如輸入數據本身就已經是升序(或降序)，那么實際運行下來，快速排序會更慢。因此，實現同樣的功能，優先選擇時間復雜度低的算法。比如對圖像進行二維可分的高斯卷積，圖像尺寸為MxN，卷積核尺寸為PxQ，那么直接按卷積的定義計算，時間復雜度為O(MNPQ) 如果使用2個一維卷積計算，則時間復雜度為O(MN(P+Q)) 使用2個一位卷積+FFT來實現，時間復雜度為O(MNlogMN) 如果采用高斯濾波的遞歸實現，時間復雜度為O(MN)（參見paper：Recursive implementation of the Gaussian filter，源碼在GIMP中有）很顯然，上面4種算法的效率是逐步提高的。一般情況下，自然會選擇最后一種來實現。還有一種情況，算法本身比較復雜，其時間復雜度難以降低，而其效率又不滿足要求。這個時候就需要自己好好地理解算法，做些修改了。一種是保持算法效果來提升效率，另一種是舍棄部分效果來換取一定的效率，具體做法得根據實際情況操作。 代碼優化

代碼優化一般需要與算法優化同步進行，代碼優化主要是涉及到具體的編碼技巧。同樣的算法與功能，不同的寫法也可能讓程序效率差異巨大。一般而言，代碼優化主要是針對循環結構進行分析處理，目前想到的幾條原則是： a.避免循環內部的乘(除)法以及冗余計算 這一原則是能把運算放在循環外的盡量提出去放在外部，循環內部不必要的乘除法可使用加法來替代等。如下面的例子，灰度圖像數據存在BYTE Img[MxN]的一個數組中，對其子塊 (R1至R2行，C1到C2列)像素灰度求和，簡單粗暴的寫法是：

int sum = 0; 
for(int i = R1; i < R2; i++)
{
    for(int j = C1; j < C2; j++)
    {
        sum += Image[i * N + j];
    }
}

但另一種寫法：

int sum = 0;
BYTE *pTemp = Image + R1 * N;
for(int i = R1; i < R2; i++, pTemp += N)
{
    for(int j = C1; j < C2; j++)
    {
        sum += pTemp[j];
    }
}

可以分析一下兩種寫法的運算次數，假設R=R2-R1，C=C2-C1，前面一種寫法i++執行了R次，j++和sum+=…這句執行了RC次，則總執行次數為3RC+R次加法，RC次乘法；同樣地可以分析后面一種寫法執行了2RC+2R+1次加法，1次乘法。性能孰好孰壞顯然可知。 b.避免循環內部有過多依賴和跳轉，使cpu能流水起來 關于CPU流水線技術可google/baidu，循環結構內部計算或邏輯過于復雜，將導致cpu不能流水，那這個循環就相當于拆成了n段重復代碼的效率。另外ii值是衡量循環結構的一個重要指標，ii值是指執行完1次循環所需的指令數，ii值越小，程序執行耗時越短。下圖是關于cpu流水的簡單示意圖：淺談程序優化簡單而不嚴謹地說，cpu流水技術可以使得循環在一定程度上并行，即上次循環未完成時即可處理本次循環，這樣總耗時自然也會降低。先看下面一段代碼：

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

這段代碼實現的功能很簡單，對數組a的不同元素累加一個不同的值，但是在循環內部有3個分支需要每次判斷，效率太低，有可能不能流水；可以改寫為3 個循環，這樣循環內部就不用進行判斷，這樣雖然代碼量增多了，但當數組規模很大(N很大)時，其效率能有相當的優勢。改寫的代碼為：

for(int i = 0; i < 100; i++)
{
    a[i] += 5;        
}
for(int i = 100; i < 200; i++)
{
    a[i] += 10;        
}
for(int i = 200; i < N; i++)
{
    a[i] += 20;
}

關于循環內部的依賴，見如下一段程序：

for(int i = 0; i < N; i++)
{
    int x = f(a[i]);
    int y = g(x);
    int z = h(x,y);
}

其中f，g，h都是一個函數，可以看到這段代碼中x依賴于a[i]，y依賴于x，z依賴于xy，每一步計算都需要等前面的都計算完成才能進行，這樣對cpu的流水結構也是相當不利的，盡量避免此類寫法。另外C語言中的restrict關鍵字可以修飾指針變量，即告訴編譯器該指針指向的內存只有其自己會修改，這樣編譯器優化時就可以無所顧忌，但目前VC的編譯器似乎不支持該關鍵字，而在DSP上，當初使用restrict后，某些循環的效率可提升90%。 c.定點化 定點化的思想是將浮點運算轉換為整型運算，目前在PC上我個人感覺差別還不算大，但在很多性能一般的DSP上，其作用也不可小覷。定點化的做法是將數據乘上一個很大的數后，將所有運算轉換為整數計算。例如某個乘法我只關心小數點后3位，那把數據都乘上10000后，進行整型運算的結果也就滿足所需的精度了。 d.以空間換時間 空間換時間最經典的就是查表法了，某些計算相當耗時，但其自變量的值域是比較有限的，這樣的情況可以預先計算好每個自變量對應的函數值，存在一個表格中，每次根據自變量的值去索引對應的函數值即可。如下例：

//直接計算
for(int i = 0 ; i < N; i++)
{
    double z = sin(a[i]);
}

//查表計算
double aSinTable[360] = {0, ..., 1,...,0,...,-1,...,0};
for(int i = 0 ; i < N; i++)
{
    double z = aSinTable[a[i]];
}

后面的查表法需要額外耗一個數組double aSinTable[360]的空間，但其運行效率卻快了很多很多。 e.預分配內存 預分配內存主要是針對需要循環處理數據的情況的。比如視頻處理，每幀圖像的處理都需要一定的緩存，如果每幀申請釋放，則勢必會降低算法效率，如下所示：

//處理一幀
void Process(BYTE *pimg)
{
    malloc
    ...
    free
}

//循環處理一個視頻
for(int i = 0; i < N; i++)
{
    BYTE *pimg = readimage();
    Process(pimg)；
}

//處理一幀
void Process(BYTE *pimg， BYTE *pBuffer)
{
    ...
}

//循環處理一個視頻
malloc pBuffer
for(int i = 0; i < N; i++)
{
    BYTE *pimg = readimage();
    Process(pimg, pBuffer)；
}
free

前一段代碼在每幀處理都malloc和free，而后一段代碼則是有上層傳入緩存，這樣內部就不需每次申請和釋放了。當然上面只是一個簡單說明，實際情況會比這復雜得多，但整體思想是一致的。 指令優化

對于經過前面算法和代碼優化的程序，一般其效率已經比較不錯了。對于某些特殊要求，還需要進一步降低程序耗時，那么指令優化就該上場了。指令優化一般是使用特定的指令集，可快速實現某些運算，同時指令優化的另一個核心思想是打包運算。目前PC上intel指令集有MMX，SSE和SSE2/3/4 等，DSP則需要跟具體的型號相關，不同型號支持不同的指令集。intel指令集需要intel編譯器才能編譯，安裝icc后，其中有幫助文檔，有所有指令的詳細說明。例如MMX里的指令 __m64 _mm_add_pi8(__m64 m1, __m64 m2)，是將m1和m2中8個8bit的數對應相加，結果就存在返回值對應的比特段中。假設2個N數組相加，一般需要執行N個加法指令，但使用上述指令只需執行N/8個指令，因為其1個指令能處理8個數據。實現求2個BYTE數組的均值，即z[i]=(x[i]+y[i])/2，直接求均值和使用MMX指令實現2種方法如下程序所示：

#define N 800
BYTE x[N],Y[N], Z[N];
inital x,y;...
//直接求均值
for(int i = 0; i < N; i++)
{
    z[i] = (x[i] + y[i]) >> 1;
}

//使用MMX指令求均值，這里N為8的整數倍，不考慮剩余數據處理
__m64 m64X, m64Y, m64Z;
for(int i = 0; i < N; i+=8)
{
    m64X = *(__m64 *)(x + i);
    m64Y = *(__m64 *)(y + i);
    m64Z = _mm_avg_pu8(m64X, m64Y);
    *(__m64 *)(x + i) = m64Z;
}

使用指令優化需要注意的問題有： a.關于值域，比如2個8bit數相加，其值可能會溢出；若能保證其不溢出，則可使用一次處理8個數據，否則，必須降低性能，使用其他指令一次處理4個數據了； b.剩余數據，使用打包處理的數據一般都是4、8或16的整數倍，若待處理數據長度不是其單次處理數據個數的整數倍，剩余數據需單獨處理； 補充——如何定位程序熱點

程序熱點是指程序中最耗時的部分，一般程序優化工作都是優先去優化熱點部分，那么如何來定位程序熱點呢？一般而言，主要有2種方法，一種是通過觀察與分析，通過分析算法，自然能知道程序熱點；另一方面，觀察代碼結構，一般具有最大循環的地方就是熱點，這也是前面那些優化手段都針對循環結構的原因。另一種方法就是利用工具來找程序熱點。x86下可以使用vtune來定位熱點，DSP下可使用ccs的profile功能定位出耗時的函數，更近一步地，通過查看編譯保留的asm文件，可具體分析每個循環結構情況，了解到該循環是否能流水，循環ii值，以及制約循環ii值是由于變量的依賴還是運算量等詳細信息，從而進行有針對性的優化。由于Vtune剛給卸掉，沒法截圖；下圖是CCS編譯生成的一個asm文件中一個循環的截圖：淺談程序優化最后提一點，某些代碼使用Intel編譯器編譯可以比vc編譯器編譯出的程序快很多，我遇到過最快的可相差10倍。對于gcc編譯后的效率，目前還沒測試過。

來自：http://www.techug.com/program-optimization

本文由用戶 w427 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/news/view/41f15d

程序優化

淺談程序優化

相關資訊

相關經驗

相關文檔