程序優(yōu)化介紹(c語言)

1、程序優(yōu)化介紹（c語言）培訓(xùn)的對象nC語言熟手n對優(yōu)化感興趣的n想培訓(xùn)又不愿看文檔，想有人講給你聽的。n想成為編程狂人的n想成為性能狂人的n相信優(yōu)化是不必要的，或者認為優(yōu)化應(yīng)該交由編譯器完成的為什么要程序優(yōu)化n一個優(yōu)秀程序員的必要素養(yǎng)。n編譯器還不代替人工操作的程序優(yōu)化 。n低層程序需要優(yōu)化。n同樣的DSP能跑出更多的功能。nn？n！優(yōu)化還需要理由嗎程序優(yōu)化的三個級別 n第一級：代碼級 n第二級：算法級n第三級：表驅(qū)動狀態(tài)機 代碼級優(yōu)化n代碼調(diào)整是一種局部的思維方式；基本上不觸及算法層級；它面向的是代碼，而不是問題； n語句調(diào)整，用匯編重寫、指令調(diào)整、換一種語言實現(xiàn)、換一個編譯器、循環(huán)展開、參數(shù)

2、傳遞優(yōu)化等都屬于這一級； n這個級別的優(yōu)化需要掌握大量的小的優(yōu)化技巧和知識，需要不斷的積累； n簡單的語句調(diào)整、公共表達式提取、廢代碼刪除等當前的很多編譯器也能做到了，但也需要了解一些編譯器的優(yōu)化能力使自己的代碼配合編譯器做好優(yōu)化； n用匯編重寫并不是簡單把高級語言改寫為匯編實現(xiàn)，那樣寫的匯編很可能沒有當今的編譯器產(chǎn)生的代碼好，所以如果決定用匯編實現(xiàn)，那就應(yīng)該按照匯編的角度來規(guī)劃自己的實現(xiàn)，適當?shù)膮⒖季幾g器生成的匯編碼也是可取的(特別是新手，我也一樣)；在某些領(lǐng)域，使用CPU的新特性和新的指令集等將產(chǎn)生巨大的性能收益，這些地方經(jīng)常采用匯編來實現(xiàn)。 算法級優(yōu)化n算法級優(yōu)化強調(diào)的重點是針對問題的算

3、法；即選擇和構(gòu)造適合于問題的算法；（冒泡排序還是快排的選擇問題是這一級早就應(yīng)該完成的）很多經(jīng)典算法都對問題作了一些假設(shè)(包括我們當前已經(jīng)完成的算法實現(xiàn))，而在面對實際問題時“新的視角”提示我們應(yīng)該重新檢視這些假設(shè)，并嘗試不同的思考問題的角度，尋求適合于問題的新算法；n發(fā)掘問題的本來意義，從不同的角度思考面對的問題，使用適合于問題的的算法; 嘗試打破一些規(guī)則，發(fā)掘和懷疑自己的某些假定，恢復(fù)問題的本來面目； 表驅(qū)動狀態(tài)機 n將問題抽象為另一種等價的數(shù)學(xué)模型或假想機器模型，比如構(gòu)造出某種表驅(qū)動狀態(tài)機；這一級其實是第二級的延伸，只是產(chǎn)生的效果更加明顯，但它有其本身的特點（任何算法和優(yōu)化活動都可以看作是

4、他的投影）；這一級一般可以產(chǎn)生無與倫比的快速程序， n 要達到這一級需要大量修煉的;并且思考時必須放棄很多已有的概念或者這些概念不再重要，比如：變量、指針、空間、函數(shù)、對象等，剩下的只應(yīng)該是那個表驅(qū)動狀態(tài)機； 我想把這種境界描述為：空寂中，一些輸入驅(qū)動著一個帶有狀態(tài)的機器按設(shè)定好的最短路線運轉(zhuǎn)著；除此之外have nothing; 既：把解決一個問題的算法看作一個機器，它有一些可變的狀態(tài)、有一些記憶、有一些按狀態(tài)運行的規(guī)則，然后一些輸入驅(qū)動這個機器運轉(zhuǎn)；這就是第三級要求的思考優(yōu)化問題的切入點，也就是尋找一部機器，使它運行經(jīng)過的路徑最短(可能是速度也可能是空間等等)第一級優(yōu)化n要掌握一級優(yōu)化，是

5、很多人經(jīng)過努力都能夠達到的層次，需要的是不斷的積累各方面的技巧就行了(雖然很繁瑣)，寫出的代碼可以稱為“好的代碼”；n手中無劍、心中有劍；第二級優(yōu)化n要掌握二級優(yōu)化，需要的是對問題的理解能力和一些創(chuàng)造力，能夠針對問題產(chǎn)生新的見解；寫出的代碼可以稱為“優(yōu)秀的代碼”； n手中有劍；心中亦有劍 ；第三級優(yōu)化n要掌握三級優(yōu)化，必須具有豐富的想象力和創(chuàng)造力，需要大量的修煉和對問題本質(zhì)的苦苦思索；寫出的代碼可以稱為“非凡的代碼”；n手中無劍、心中亦無劍；無級n能夠?qū)⑦@三個層級的優(yōu)化熟練運用(我想把這種境界稱作“綜級優(yōu)化”)的人必須掌握比別人更多的知識、了解更多的知識領(lǐng)域、了解最底層的技術(shù)和最高層的抽象；并

6、且還要求有豐富的實踐經(jīng)驗、想象能力和創(chuàng)造能力; 這些都是不可或缺的； n就是不殺，就是和平警示1n警示：不是所有的代碼(項目)都需要優(yōu)化 n警示：不是每個人都要去做優(yōu)化工作 n警示：優(yōu)化是有方向和側(cè)重點的，不只是單純的速度 n警示：首先是正確，然后才有優(yōu)化 n警示：簡潔的代碼，很多時候就是最好的代碼 警示2n警示：優(yōu)化不是一種理論，它是一種實踐 n警示：充分優(yōu)化的笨拙算法實現(xiàn)始終比不上一個更好的算法的普通實現(xiàn),即優(yōu)化首先是設(shè)計的優(yōu)化 n警示：代碼優(yōu)化是門黑色藝術(shù)，代碼的優(yōu)化永無止境 n警示：無論是誰，他的資源也不是無限的，代碼優(yōu)化要避免過猶不及 n警示：如果確信不需要優(yōu)化，那根本不進行優(yōu)化，就

7、是最好的優(yōu)化！ 多使用32位的數(shù)據(jù)類型n編譯器有很多種，但它們都包含的典型的32位類型是：int，signed，signed int，unsigned，unsigned int，long，signed long，long int，signed long int，unsigned long，unsigned long int。盡量使用有符號32位的數(shù)據(jù)類型，因為它們比16位的數(shù)據(jù)甚至8位的數(shù)據(jù)更有效率。使用位操作。減少除法和取模的運算n使用位操作。減少除法和取模的運算 int I,J,k;I = 257 / 8;J = 456 % 32; K = 257 % 8寫成int I,J,k;I = 2

8、57 3;J = 456 - (456 4 4); K= 257 & 7; 在上面好像程序麻煩了好多，但是，仔細查看產(chǎn)生的匯編代碼就會明白，方法1調(diào)用了基本的取模函數(shù)和除法函數(shù)，既有函數(shù)調(diào)用，還有很多匯編代碼和寄存器參與運算；而方法2則僅僅是幾句相關(guān)的匯編，代碼更簡潔，效率更高。當然，由于編譯器的不同，可能效率的差距不大，但是，以目前的MS C ,ARM C 來看，效率的差距還是不小。避免不必要的整數(shù)除法n整數(shù)除法是整數(shù)運算中最慢的，所以應(yīng)該盡可能避免。一種可能減少整數(shù)除法的地方是連除，這里除法可以由乘法代替。這個替換的副作用是有可能在算乘積時會溢出，所以只能在一定范圍的除法中使用。

9、while (1) V.S. for (;)n在編程中，我們常常需要用到無限循環(huán)，常用的兩種方法是while (1) 和 for (;)。這兩種方法效果完全一樣，但那一種更好呢？然我們看看它們編譯后的代碼： 編譯前 while (1); for (;); 編譯后 mov eax,1 jmp foo+23h test eax,eax je foo+23h jmp foo+18h 一目了然，for (;)指令少，不占用寄存器，而且沒有判斷跳轉(zhuǎn)，比while (1)好。使用數(shù)組型代替指針型n 使用指針會使編譯器很難優(yōu)化它。因為缺乏有效的指針代碼優(yōu)化的方法，編譯器總是假設(shè)指針可以訪問內(nèi)存的任意地方，包

10、括分配給其他變量的儲存空間。所以為了編譯器產(chǎn)生優(yōu)化得更好的代碼，要避免在不必要的地方使用指針。一個典型的例子是訪問存放在數(shù)組中的數(shù)據(jù)。C+ 允許使用操作符 或指針來訪問數(shù)組，使用數(shù)組型代碼會讓優(yōu)化器減少產(chǎn)生不安全代碼的可能性。比如，x0 和x2 不可能是同一個內(nèi)存地址，但 *p 和 *q 可能。強烈建議使用數(shù)組型，因為這樣可能會有意料之外的性能提升。 把頻繁使用的指針型參數(shù)拷貝到本地變量n避免在函數(shù)中頻繁使用指針型參數(shù)指向的值。因為編譯器不知道指針之間是否存在沖突，所以指針型參數(shù)往往不能被編譯器優(yōu)化。這樣是數(shù)據(jù)不能被存放在寄存器中，而且明顯地占用了內(nèi)存帶寬。注意，很多編譯器有“假設(shè)不沖突”優(yōu)化

11、開關(guān)（在VC里必須手動添加編譯器命令行/Oa或/Ow），這允許編譯器假設(shè)兩個不同的指針總是有不同的內(nèi)容，這樣就不用把指針型參數(shù)保存到本地變量。否則，請在函數(shù)一開始把指針指向的數(shù)據(jù)保存到本地變量。如果需要的話，在函數(shù)結(jié)束前拷貝回去。盡可能使用常量(const)n盡可能使用常量(const)。C+ 標準規(guī)定，如果一個const聲明的對象的地址不被獲取，允許編譯器不對它分配儲存空間。這樣可以使代碼更有效率，而且可以生成更好的代碼。 把本地函數(shù)聲明為靜態(tài)的(static)n如果一個函數(shù)在實現(xiàn)它的文件外未被使用的話，把它聲明為靜態(tài)的(static)以強制使用內(nèi)部連接。否則，默認的情況下會把函數(shù)定義為外部

12、連接。這樣可能會影響某些編譯器的優(yōu)化比如，自動內(nèi)聯(lián)。IO緩沖n如果有文件讀寫的話，那么對文件的訪問將是影響程序運行速度的一大因素。提高文件訪問速度的主要辦法有兩個：一是采用內(nèi)存映射文件，二是使用內(nèi)存緩沖。下面是一組測試數(shù)據(jù)（見UNIX環(huán)境高級編程3.9節(jié)），顯示了用18種不同的緩存長度，讀1 468 802字節(jié)文件所得到的結(jié)果。 可見，一般的當內(nèi)存緩沖區(qū)大小為8192的時候，性能就已經(jīng)是最佳的了，這也就是為什么在H.263等圖像編碼程序中，緩沖區(qū)大小為8192的原因（有的時候也取2048大?。Ｊ褂脙?nèi)存緩沖區(qū)方法的好處主要是便于移植，占用內(nèi)存少，便于硬件實現(xiàn)等。 字符串的賦值n計算機程序中最大

13、的矛盾是空間和時間的矛盾，那么，從這個角度出發(fā)逆向思維來考慮程序的效率問題，我們就有了解決問題的方法-以空間換時間。 例如：字符串的賦值。方法A：通常的辦法：#define LEN 32char string1 LEN;memset (string1,0,LEN);strcpy (string1,This is a example!） n方法B：const char string2LEN =This is a example!; char * cp; cp = string2 ; 從上面的例子可以看出，A和B的效率是不能比的。在同樣的存儲空間下，B直接使用指針就可以操作了，而A需要調(diào)用兩個字符

14、函數(shù)才能完成。B的缺點在于靈活性沒有A好。在需要頻繁更改一個字符串內(nèi)容的時候，A具有更好的靈活性；如果采用方法B，則需要預(yù)存許多字符串，雖然占用了大量的內(nèi)存，但是獲得了程序執(zhí)行的高效率。字符串的賦值n將函數(shù)改為宏函數(shù)，宏函數(shù)占用了大量的空間，而函數(shù)占用了時間。大家要知道的是，函數(shù)調(diào)用是要使用系統(tǒng)的棧來保存數(shù)據(jù)的，如果編譯器里有棧檢查選項，一般在函數(shù)的頭會嵌入一些匯編語句對當前棧進行檢查；同時，CPU也要在函數(shù)調(diào)用時保存和恢復(fù)當前的現(xiàn)場，進行壓棧和彈棧操作，所以，函數(shù)調(diào)用需要一些CPU時間。而宏函數(shù)不存在這個問題。宏函數(shù)僅僅作為預(yù)先寫好的代碼嵌入到當前程序，不會產(chǎn)生函數(shù)調(diào)用，所以僅僅是占用了空間

15、，在頻繁調(diào)用同一個宏函數(shù)的時候，該現(xiàn)象尤其突出。 將函數(shù)改為宏函數(shù)查表1n目前程序加速的常用算法一個大方面就是利用查表來避免計算（比如在jpg有huffman碼表，在YUV到RGB變換也有變換表）這樣原來的復(fù)雜計算現(xiàn)在僅僅查表就可以了，雖然浪費了內(nèi)存，不過速度顯著提升，還是很劃算的。在數(shù)據(jù)庫查詢里面也有這樣的思想，將熱點存儲起來以加速查詢。 現(xiàn)在介紹一個簡單的例子：比如，在程序中要經(jīng)常計算1000到2000的階乘，那么我們可以使用一個數(shù)組a1000先把這些值算好，保留下來，以后要計算1200！的時候，查表a1200-1000就可以了。查表2n有一個程序是這樣的switch ( queue )

16、case 0 : letter = W; break;case 1 : letter = S; break;case 2 : letter = U; break;n可以優(yōu)化成這樣static char *classes=WSU;letter = classesqueue;考慮動態(tài)內(nèi)存分配n動態(tài)內(nèi)存分配（C+中的“new”）可能總是為長的基本類型（四字對齊）返回一個已經(jīng)對齊的指針。但是如果不能保證對齊，使用以下代碼來實現(xiàn)四字對齊。這段代碼假設(shè)指針可以映射到 long 型。n例子 double* p = (double*)new BYTEsizeof(double) * number_of_dou

17、bles+7L;double* np = (double*)(long(p) + 7L) & 8L); 現(xiàn)在，你可以使用 np 代替 p 來訪問數(shù)據(jù)。注意：釋放儲存空間時仍然應(yīng)該用delete p。充分分解小的循環(huán)n要充分利用CPU的指令緩存，就要充分分解小的循環(huán)。特別是當循環(huán)體本身很小的時候，分解循環(huán)可以提高性能。很多編譯器并不能自動分解循環(huán)。 這也可以理解成展開小的循環(huán)。按類型長度排序n把結(jié)構(gòu)體的成員按照它們的類型長度排序，聲明成員時把長的類型放在短的前面。 Switch 的用法nSwitch 可能轉(zhuǎn)化成多種不同算法的代碼。其中最常見的是跳轉(zhuǎn)表和比較鏈/樹。推薦對case的值依照發(fā)

18、生的可能性進行排序，把最有可能的放在第一個，當switch用比較鏈的方式轉(zhuǎn)化時，這樣可以提高性能。此外，在case中推薦使用小的連續(xù)的整數(shù)，因為在這種情況下，所有的編譯器都可以把switch 轉(zhuǎn)化成跳轉(zhuǎn)表。減少運算，保存中間變量n計算機用于計算的時間遠大于用于保存變量的時間 a = x + 1/x + 1/(x * x);if(test) b = 1 + 1/x + 1/(x * x) + 1/(2 + x);c = y + 1/x + 1/(x * x) + 1/(2 + x);d = z + 1/x + 1/(x * x) + 1/(2 + x) + int_func(x);e = q + 1/x + 1/(x * x) + 1/(2 + x) + int_func(x);t0 = 1/x;t1 = t0 + t0 * t0;a = x + t1;if(test) t2 = t1 + 1/(2 + x);b = 1 + t2;c = y + t2;d = z + t2 + int_func(x);e = q + 1/x + 1/(x * x) + 1/(2 + x) + int_func(x);算法優(yōu)化一列n數(shù)學(xué)是計算機之母，沒有數(shù)學(xué)的依據(jù)和基礎(chǔ)，就沒有計算機的發(fā)展，所以在編寫程