優化 C 語言程序的技巧有哪些？

01-11

C語言編寫的程序裡面有很多地方可以優化，比如：
（1） i = i + 1 優化為 i += 1
（2） i = i * 8 優化成 i = i &<&< 3
（3）將不變條件的計算移到循環體外。
說明：將循環中與循環無關，不是每次循環都要做的操作，移到循環外部執行。

示例一：
for (int i = 0; i &< 10; i++ )
{
sum += i; back_sum = sum;
}
對於此for循環來說語句「back_Sum = sum;」沒必要每次都執行，只需要執行一次即可，因此可以改為：
for (int i = 0; i &< 10; i++ )
{
sum += i;
}

back_sum = sum;
示例二：
for (_UL i = 0; i &< func_calc_max(); i++)
{
//process;
}
函數func_calc_max()沒必要每次都執行，只需要執行一次即可，因此可以改為：
_UL max = func_calc_max();

for (_UL i = 0; i &< max; i++)
{
//process;
}
...
其他
歡迎大家補充一些優化C語言程序的方法（技巧），如果有相關的書籍什麼的能從本質上分析這種優化技巧的更好

相信你的 compiler，它往往比你更懂你的代碼以及你的硬體。

1. i = i + 1 和 i += 1 這兩種寫法對 compiler 來說沒有任何區別，在 x32 上都會生成 incl 指令。

2. modern compiler 已經很厲害了，示例一的兩種寫法生成的代碼是一樣的。

3. 所以大家都假設 func_calc_max() 和 loop body 沒有 side effect？

4. 如果要斤斤計較的話， for (int i = 0; i &< 10; i++ ) 中的 i++ 應該寫成 ++i。

5. http://csapp.cs.cmu.edu/ 第五章有很多乾貨。

@薛非對譚浩強是真愛，這都能扯到譚浩強上去。

真想搞優化，就去好好學演算法吧……這些東西都是細枝末節，沒什麼用，浪費時間而已……俗話說好鋼用在刀刃上。

從本質上分析這種優化技巧的書籍是《編譯原理》。

演算法不出問題的情況下，C語言能做到優化很有限。

問題的例子除非是hot trace裡面的代碼，否則對程序整體性能影響也不大。

其它的應該還有這些：

1）考慮cache line

2）考慮對齊

3）縮小循環，減少循環內操作

4）整數盡量使用乘法，減少除法

5）可以使用shift則用shift

6）如果支持硬體指令的操作，則不使用軟體庫。

例如一些加密啊，網路操作啊，hash，checksum啊

7）還有一些支持向量化的代碼，要學會討好你的編譯器。

8）再往下就是彙編了。

總得來說，如果你要做優化，你首先要非常懂你的硬體，不是電路，是架構的特點。

例如MIPS就不支持非對齊訪問，ARM則支持，印象中x86不但支持而且還比ARM快。

忘記這些打開-O2或者-O3

最近在學CSAPP。拋個磚。

我來接介紹一下如何從充分利用硬體的角度寫c語言程序。

以往談到優化，大家總是會想到去改進演算法，提高演算法的優越性，從而提高了程序的性能。因為考慮演算法的時候，其實只考慮了「計算複雜度」，事實上計算機完成一件事情，不僅僅是在CPU裡面運算這麼簡單，你至少還需要載入數據到計算機里CPU里不是嗎？而且CPU在一定程度上可以並行的執行你的程序，如何去利用這一點，優化你的程序呢？

接下來，我以矩陣乘法為例子，說明如何寫出「Machine-Friendly Codes」。

先介紹兩個思路，然後做實驗驗證。

一.利用CPU的指令級並行

第一個優化的思路，是充分利用CPU的性能。

絕大多數的現代處理器都採用了超標量（superscalar）CPU架構，這種架構充分利用了處理器內核中的多個執行單元，可以在同一個時鐘周期執行多條指令。

這種架構的好處就是，只要你寫的程序能夠被並行地處理，你不需要多付出額外的努力，就可以在執行的時候被CPU加速運行。所以，關鍵是怎麼寫出可以被並行處理的源代碼。

更加具體的闡釋如下:

這張圖片，以乘法為例子，演示了三個乘法是怎麼在cpu中執行的。

cpu把運算的執行分成了幾個階段。

假設一個乘法需要用到三個階段來完成。對於沒有數據相互依賴性的乘法運算可以並處理。比如這裡 a * b 和 a * c。好處也是很明顯的，由於並行處理，兩次乘法一共只需要四個階段就可以做完，而在不並行的時候需要六個階段。

為什麼後面 p1 * p2 和前面的運算不能並行？因為p1和p2的值和之前的運算有數據相關性。

二.利用存儲器的層次結構

第二個優化的思路是，利用存儲器的層次結構，計算機的存儲結構是分層的，越靠近CPU的存儲器，取數據就越快，就節約時間。所以可以盡量的利用「局部性原理」，把要用的數據都放到上層。

舉個例子，一個i7的處理器的存儲結構大致是這樣：

對於一個CPU而言，一開始數據總是在內存，或者硬碟，甚至更遠的雲端。在取數據的時候，存儲器結構會把數據一層一層往上load。而對CPU而言，有一個存放數據的地方叫Cahce，需要把數據從內存按需讀入Cache中再做運算。從內存中讀入數據，是以 Cache Line為單位的，一個Cache line所攜帶的有用數據的多少叫做Block Size，在上圖的i7中一個Cache Line的大小是64 bytes。

在一個程序運行的時候，每次遇到要到內存中去取某個數據，就會去取一個Cache Line（這是一個相對比較昂貴的操作），因為Cache Line 是有一定大小的，也就是說你取到的除了你這次要用的數據，還會取到相鄰的一大段數據，如果你這次取到Cache Line中的數據能夠在後面被多次用到，CPU就不用再跑到內存中取上來一個Cache Line了，從而就節約了時間。

舉一個矩陣乘法的例子。

利用二維數組去存一個矩陣，數組中的數據在內存裡面是按行連續存儲的。

假設：我們在這裡使用的數據類型是double，也就是 8 bytes的數據類型，一個Cache Line的 Block Size是64 bytes。

在這樣的假設下，我們來比較兩種矩陣乘法的性能。

第一種是矩陣乘法最普通的寫法。考慮最內層的循環。對於矩陣A來說，由於是按行讀取下一個元素的，每次取一個數據，取上來Cache Line會被用到8次，所以Miss Rate是0.125。對於矩陣B來說，由於是按列讀取的，相鄰的數據不會馬上被用到，Miss Rate是1。

這裡Miss Rate是指，當需要一個數據的時候，需要的Cache Line不在Cache中，需要去內存中取新的Cache Line的概率。

第二種是優化了的矩陣乘法的寫法。考慮最內層的循環。對於矩陣B和C來說，都是按行讀取下一個元素的，每次取一個數據，取上來Cache Line會被用到8次，所以Miss Rate都是0.125。

由於第二種矩陣乘法的寫法充分的利用了Cache，所以相對第一種寫法，會比較快。

三.測試環境說明

光分析是沒有用的，做一下實驗！還是用矩陣乘法程序來做實驗。

我的機器信息：

My machine Info: Ubuntu Kylin 16.04 , Intel? Core? i5-4200U CPU @ 1.60GHz × 4

實驗的思路：

先隨機生成兩個N×N的矩陣，在編寫矩陣乘法的程序，在調用前和調用後讀取時間，從而可以確定這個矩陣乘法的函數的performance。

How to determine performance？


Convenient way to express performance of program that operates on vectors or lists
Length = n
In our case: CPE = cycles per OP

T = CPE*n （+ Overhead）

如何來估算程序的性能呢？我使用CPE來衡量矩陣乘法的性能。

首先得到一個程序的時間。然後查機器信息的到我的機器的主頻。從而用時間乘以頻率得到這段時間內的機器運行的時鐘周期數。

用時鐘周期數除以總共的運算的次數，得到平均每次運算所需要的CPU時鐘周期。用來衡量這個程序的性能。

首先，用來記時的程序如下：

#include & #include & #include & #define N 500 //N是矩陣維度


int main(){

    //c=a×b

double a[N][N]={0};

double b[N][N]={0};

double c[N][N]={0};
    // 準備a，b兩個隨機生成的矩陣

srand(1);

for(int i=0;i&
三. 測試矩陣乘法
1.ijk類型的矩陣乘法
首先作為一個基礎，先測試了不做任何優化的矩陣乘法，如下：
void MatrixMultiply_ijk(double a[][N], double b[][N], double c[][N])//c=a*b

{

for(int i=0;i&
得到的一次測試的結果如下：
Time use:687704 *10^-6 s

Total size: A:250000,B:250000

Total operators: 250000000

Element type:double

My machine INfo: Ubuntu Kylin 16.04 , Intel? Core? i5-4200U CPU @ 1.60GHz × 4

Total Cycles: 1100326400

Total Cycles/Total operators: 4.401306


2.kij類型的矩陣乘法
接著，我測試了kij類型的矩陣乘法，相比於最普通的矩陣乘法，相比上一種，它減少了cache miss
void MatrixMultiply_kij(double a[][N], double b[][N], double c[][N])//c=a*b

{

for(int k=0;k&
得到的一次測試結果如下：
Time use:477054 *10^-6 s

Total size: A:250000,B:250000

Total operators: 250000000

Element type:double

My machine INfo: Ubuntu Kylin 16.04 , Intel? Core? i5-4200U CPU @ 1.60GHz × 4

Total Cycles: 763286400

Total Cycles/Total operators: 3.053146


從結果上來看，採取kij的方法，相比不做優化，能提高16%的CPE
3. kij+並行計算
同時採用兩種優化的思路。在採用kij順序的矩陣乘法的同時，同時通過並行計算加速。
void MatrixMultiply_kij_unloop(double a[][N], double b[][N], double c[][N])//c=a*b

{

for(int k=0;k&
當然在一次循環中展開多次並行運算可能效果會比兩次要好，我測試了一下展開十次的效果。如下：
Time use:399723 *10^-6 s

Total size: A:250000,B:250000

Total operators: 250000000

Element type:double

My machine INfo: Ubuntu Kylin 16.04 , Intel? Core? i5-4200U CPU @ 1.60GHz × 4

Total Cycles: 639556800

Total Cycles/Total operators: 2.558227


值得一提的是，之前的測試結果都是用的不做任何優化的gcc命令編譯，所得到的結果。
我發現如果用了-O2命令，優化效果會有顯著的提高，比自己動手優化得到的效果都好的多。
例如使用 gcc -O2 優化選項，對kij+unloop優化，得到的測試結果如下，得到的CPE大概是0.7左右。
Time use:106952 *10^-6 s

Total size: A:250000,B:250000

Total operators: 250000000

Element type:double

My machine INfo: Ubuntu Kylin 16.04 , Intel? Core? i5-4200U CPU @ 1.60GHz × 4

Total Cycles: 171123200

Total Cycles/Total operators: 0.684493


因此，我只想說，GCC真的是厲害，它做的優化比你能想到的都厲害多了！！！ QAQ ！！！

雖然對於優化C代碼有很多有效的指導方針，但是對於徹底地了解編譯器和你工作的機器依然無法取代，通常，加快程序的速度也會加大代碼量。這些增加的代碼也會影響一個程序的複雜度和可讀性，這是不可接受的，比如你在一些小型的設備上編程，例如：移動設備、PDA……，這些有著嚴格的內存限制，於是，在優化的座右銘是:寫代碼在內存和速度都應該優化。
看看這篇文章C代碼優化小貼士

例子裡面基本都是編譯器相關的，感覺實用性不大，說不定編譯器都幫你做好了。
優化c可以多多考慮cacheline相關的東西。
此外可以學一學多核的東西，使用得當的話，性能可以得到不錯的提升。

你說的這些優化其實都應該是現代編譯器乾的事情，而且他們都已經乾的非常好了。
C語言的優化，重要的是了解編譯器是如何優化代碼的，然後用優化器能看得懂的方式去寫代碼。這個就取決於你對編譯器的了解了。去查一下你要的用的編譯器會做哪些優化吧。例如把遞歸改寫成尾遞歸，讓編譯器能把它優化成循環一類的。
intel的編譯器的一個例子。
Guidelines to Vectorize Innermost LoopsFollow these guidelines to vectorize innermost loop bodies.
Use:


straight-line code (a single basic block)
vector data only; that is, arrays and invariant expressions on the right hand side of assignments. Array references can appear on the left hand side of assignments.
only assignment statements

Avoid:


function calls (other than math library calls)
unvectorizable operations (either because the loop cannot be vectorized, or because an operation is emulated through a number of instructions)
mixing vectorizable types in the same loop (leads to lower resource utilization)
data-dependent loop exit conditions (leads to loss of vectorization)

其實除非是高度運算密集型程序，做這種事情不是很有必要，因為代碼是高度為編譯器考慮寫的，編譯器看懂了，人就不一定看得懂了……

記得用-O

很難說這是優化。
（1） i = i + 1 優化為 i += 1//後者簡潔，前者啰嗦。更好的寫法也許應該是 i++
（2） i = i * 8 優化成 i = i &<&< 3//這兩者並不一定等價
（3） 將不變條件的計算移到循環體外。 //在我看來這是常識。
示例一：

for (int i = 0; i &< 10; i++ )
{
sum += i; back_sum = sum;
}

這恐怕是譚浩強派的代碼，原本就不該這麼寫。
示例二：

for (_UL i = 0; i &< func_calc_max(); i++)
{
//process;
}

這應該屬於對for的語義了解不深，也是譚式風格的一種。
如果要總結譚式都有哪些垃圾風格
我這裡倒是有不少例子。
見：
譚浩強《C程序設計》中的各種錯誤

  推薦閱讀：


※怎麼學習C語言指針？
※ZOJ Haiku Review  段錯誤！估計是指針，不知道哪裡錯了？
TAG:編程 | C編程語言 | 優化 |