編寫高效的C代碼
原文標(biāo)題：Writing Efficient C and C Code Optimization
原文地址：http://www.codeproject.com/cpp/C___Code_Optimization.asp
原文作者：Koushik Ghosh
譯文作者：zhigang
前言
前段時(shí)間，我開發(fā)了一個(gè)輕量級(jí)的JPEG庫(kù)，用來(lái)在某種移動(dòng)設(shè)備上不失真地顯示圖像。我注意到一些技巧可以使程序運(yùn)行的更快。在這篇文章里，我收集和整理了所有的這些方法，用來(lái)在運(yùn)行速度和內(nèi)存占用方面對(duì)C代碼進(jìn)行優(yōu)化。
盡管編寫C代碼，已經(jīng)有了許多指導(dǎo)原則可以參考，但這并不表示你已經(jīng)徹底的了解你正在使用的編譯器和CPU。
經(jīng)常的，為了使代碼運(yùn)行的更快，會(huì)導(dǎo)致代碼長(zhǎng)度的增加，所謂以空間換時(shí)間，但是代碼長(zhǎng)度的增加有一種負(fù)面作用就是使程序的復(fù)雜度增加、可讀性減弱。尤其是當(dāng)你的程序最終運(yùn)行環(huán)境是手機(jī)、PDA之類的對(duì)內(nèi)存要求比較苛刻的設(shè)備的時(shí)候，這將會(huì)是不可接受的。所以，我們優(yōu)化的宗旨就是使程序在內(nèi)存占用和運(yùn)行速度兩個(gè)方面都要得到優(yōu)化。
聲明
實(shí)際上，在我的那個(gè)項(xiàng)目中，我使用了ARM公司的一篇文章中提到的技巧，因?yàn)槲业某绦蚴腔贏RM平臺(tái)的，你可以從這里http://www.arm.com/pdfs/DAI0034A_efficient_c.pdf取得這篇文章，我也從Internet上收集了許多其它的文章。但并不是每篇文章中提到的所有技巧都有用，所以，在這里，我只收集了有用且有效的，還有，我修改了其中的一些技巧使它幾乎適用于所有情況，而不僅僅是ARM。
我所作的工作只是將各個(gè)站點(diǎn)的技巧收集到一起，尤其是我在上面提到的那個(gè)PDF文件，我從來(lái)沒有說(shuō)過(guò)這些技巧使我自己的發(fā)明。在本文末尾的參考文獻(xiàn)部分，我羅列了所有技巧的來(lái)源。
哪里需要優(yōu)化
沒有這一點(diǎn)，所有的討論都無(wú)從談起。首先也是最重要的是要找出哪里需要優(yōu)化，程序的那一部分或者那個(gè)模塊運(yùn)行速度慢或者使用大量?jī)?nèi)存。程序的每個(gè)部分都被分別優(yōu)化，自然而然的整個(gè)程序又會(huì)變得運(yùn)行的比較快了。
優(yōu)化應(yīng)該主要針對(duì)程序中最經(jīng)常運(yùn)行的部分，尤其是被內(nèi)部循環(huán)反復(fù)調(diào)用的函數(shù)。
一個(gè)經(jīng)驗(yàn)豐富的程序員會(huì)很容易找出程序中需要著重優(yōu)化的部分，另外，還有許多工具可以用來(lái)確定這些部分。我曾經(jīng)用Visual C++ 的IDE內(nèi)建的Profiler，另外一個(gè)我用過(guò)的工具是Intel Vtune，這是一個(gè)非常好用的Profiler，都可以用來(lái)尋找程序中最費(fèi)時(shí)的地方。以我的經(jīng)驗(yàn)來(lái)看，導(dǎo)致程序運(yùn)行速度慢得罪魁禍?zhǔn)卓赡芫褪悄硞€(gè)內(nèi)部或嵌套循環(huán)，也可能是對(duì)第三方庫(kù)函數(shù)的調(diào)用。
整型數(shù) / Integers
如果一個(gè)變量的取值范圍是非負(fù)的，我們應(yīng)該使用unsigned int，而不是int。一些處理器在處理無(wú)符號(hào)整型數(shù)要比處理符號(hào)整型數(shù)快得多，這也是一個(gè)好的習(xí)慣，有利于代碼的自我文檔化(self-documenting)。
那么，在一個(gè)小循環(huán)（tight loop）中，定義一個(gè)整型變量，最好類似這樣：
register unsigned int variable_name;
然而，我們不能保證編譯器會(huì)注意到那個(gè)register關(guān)鍵字，也有可能，對(duì)某種處理器來(lái)說(shuō)，有沒有unsigned是一樣的。這兩個(gè)關(guān)鍵字并不是可以在所有的編譯器中應(yīng)用。
記住，整形數(shù)運(yùn)算要比浮點(diǎn)數(shù)運(yùn)算快得多，因?yàn)樘幚砥骺梢灾苯舆M(jìn)行整型數(shù)運(yùn)算，浮點(diǎn)數(shù)運(yùn)算需要依賴于外部的浮點(diǎn)數(shù)處理器或者浮點(diǎn)數(shù)數(shù)學(xué)庫(kù)。
我們處理小數(shù)的時(shí)候要精心些，比方說(shuō)我們?cè)谧鲆粋€(gè)簡(jiǎn)單的統(tǒng)計(jì)程序時(shí)，要限制結(jié)果不能超過(guò)100，要盡可能晚的把它轉(zhuǎn)化成浮點(diǎn)數(shù)。
除法和余數(shù) / Division and Remainder
在一般的處理器中，根據(jù)分子和分母的不同，一個(gè)32位的除法需要20-140個(gè)時(shí)鐘周期，等于一個(gè)固定的時(shí)間加上每個(gè)位被除的時(shí)間。
Time (分子/ 分母) = C0 + C1* log2 (分子/分母)
= C0 + C1 * (log2 (分子) - log2 (分母)).
現(xiàn)在的ARM處理器需要消耗20+4.3N個(gè)時(shí)鐘周期，這是一個(gè)非常費(fèi)時(shí)的操作，要盡可能的避免。在有些情況下，除法表達(dá)式可以用乘法表達(dá)是來(lái)重寫。比方說(shuō)，(a/b)>c可以寫成a>(c*b),條件是我們已經(jīng)知道b為非負(fù)數(shù)而且b*c不會(huì)超過(guò)整型數(shù)的取值范圍。如果我們能夠確定其中的一個(gè)操作數(shù)為unsigned，那么使用無(wú)符號(hào)除法將會(huì)更好，因?yàn)樗扔蟹?hào)除法快得多。
合并除法運(yùn)算和取余運(yùn)算 / Combining division and remainder
在一些情況下，除法運(yùn)算和取余運(yùn)算都需要用到，在這種情況下，編譯器會(huì)將除法運(yùn)算和取余運(yùn)算合并，因?yàn)槌ㄟ\(yùn)算總是同時(shí)返回商和余數(shù)。如果兩個(gè)運(yùn)算都要用到，我們可以將他們寫到一起（譯者：不要細(xì)究下面的代碼的含義，只是闡述寫到“一起”）
int func_div_and_mod (int a, int b) {
return (a / b) + (a % b);
}
除數(shù)是２的冪的除法和取余 / Division and remainder by powers of two
如果除法運(yùn)算中的除數(shù)是２的冪，我們對(duì)這個(gè)除法運(yùn)算還可以進(jìn)一步優(yōu)化，編譯器會(huì)使用移位運(yùn)算來(lái)進(jìn)行這種除法運(yùn)算。所以，我們要盡可能縮放比例為２的冪(比方說(shuō)要用６４而不用６６)。如果是無(wú)符號(hào)數(shù)，它要比有符號(hào)的快得多。
typedef unsigned int uint;
uint div32u (uint a) {
return a / 32;
}
int div32s (int a){
return a / 32;
}
這兩個(gè)除法都會(huì)避免調(diào)用除法函數(shù)，另外，無(wú)符號(hào)的除法要比有符號(hào)的除法使用更少的指令。有符號(hào)的除法要耗費(fèi)更多的時(shí)間，因?yàn)槌ㄊ鞘棺罱K結(jié)果趨向于零的，而移位則是趨向于負(fù)無(wú)窮。
取模運(yùn)算的變通 / An alternative for modulo arithmetic
我們一般使用取余運(yùn)算進(jìn)行取模，不過(guò)，有時(shí)候使用if語(yǔ)句也是可行的。考慮下面的兩個(gè)例子：
uint modulo_func1 (uint count)
{
return (++count % 60);
}
uint modulo_func2 (uint count)
{
if (++count >= 60)
count = 0;
return (count);
}
第二個(gè)例子要比第一個(gè)更可取，因?yàn)橛伤a(chǎn)生的代碼會(huì)更快，注意：這只是在count取值范圍在0 – 59之間的時(shí)候才行。
使用數(shù)組索引 / Using array indices
假設(shè)你要依據(jù)某個(gè)變量的值，設(shè)置另一個(gè)變量的取值為特定的字符，你可能會(huì)這樣做：
switch ( queue ) {
case 0 : letter = 'W';
break;
case 1 : letter = 'S';
break;
case 2 : letter = 'U';
break;
}
或者這樣：
if ( queue == 0 )
letter = 'W';
else if ( queue == 1 )
letter = 'S';
else
letter = 'U';
有一個(gè)簡(jiǎn)潔且快速的方式是簡(jiǎn)單的將變量的取值做成一個(gè)字符串索引，例如：
static char *classes="WSU";
letter = classes[queue];
全局變量 / Global variables
全局變量不會(huì)被分配在寄存器上，修改全局變量需要通過(guò)指針或者調(diào)用函數(shù)的方式間接進(jìn)行。所以編譯器不會(huì)將全局變量存儲(chǔ)在寄存器中，那樣會(huì)帶來(lái)額外的、不必要的負(fù)擔(dān)和存儲(chǔ)空間。所以在比較關(guān)鍵的循環(huán)中，我們要不使用全局變量。
如果一個(gè)函數(shù)要頻繁的使用全局變量，我們可以使用局部變量，作為全局變量的拷貝，這樣就可以使用寄存器了。條件是本函數(shù)調(diào)用的任何子函數(shù)不使用這些全局變量。
舉個(gè)例子：
int f(void);
int g(void);
int errs;
void test1(void)
{
errs += f();
errs += g();
}
void test2(void)
{
int localerrs = errs;
localerrs += f();
localerrs += g();
errs = localerrs;
}
可以看到test1()中每次加法都需要讀取和存儲(chǔ)全局變量errs，而在test2()中，localerrs分配在寄存器上，只需要一條指令。
使用別名 / Using Aliases
考慮下面的例子：
void func1( int *data )
{
int i;
for(i=0; i<10; i++)
{
anyfunc( *data, i);
}
}
即使*data從來(lái)沒有變化，編譯器卻不知道anyfunc()沒有修改它，于是程序每次用到它的時(shí)候，都要把它從內(nèi)存中讀出來(lái)，可能它只是某些變量的別名，這些變量在程序的其他部分被修改。如果能夠確定它不會(huì)被改變，我們可以這樣寫：
void func1( int *data )
{
int i;
int localdata;
localdata = *data;
for(i=0; i<10; i++)
{
anyfunc ( localdata, i);
}
}
這樣會(huì)給編譯器優(yōu)化工作更多的選擇余地。
活的變量和泄漏 / Live variables and spilling
寄存器的數(shù)量在每個(gè)處理器當(dāng)中都是固定的，所以在程序的某個(gè)特定的位置，可以保存在寄存器中的變量的數(shù)量是有限制的。
有些編譯器支持“生命周期分割”（live-range splitting），也就是說(shuō)在程序的不同部分，變量可以被分配到不同的寄存器或者內(nèi)存中。變量的生命范圍被定義成，起點(diǎn)是對(duì)該變量的一次空間分配，終點(diǎn)是在下次空間分配之前的最后一次使用之間。在這個(gè)范圍內(nèi)，變量的值是合法的，是活的。在生命范圍之外，變量不再被使用，是死的，它的寄存器可以供其他變量使用，這樣，編譯器就可以安排更多的變量到寄存器當(dāng)中。
可分配到寄存器的變量需要的寄存器數(shù)量等于經(jīng)過(guò)生命范圍重疊的變量的數(shù)目，如果這個(gè)數(shù)目超過(guò)可用的寄存器的數(shù)量，有些變量就必須被暫時(shí)的存儲(chǔ)到內(nèi)存中。這種處理叫做“泄漏(spilling)”。
編譯器優(yōu)先泄漏最不頻繁使用的變量，將泄漏的代價(jià)降到最低。可以通過(guò)以下方式避免變量的“泄漏”：
? 限制活變量的最大數(shù)目：通常可以使用簡(jiǎn)單小巧的表達(dá)式，在函數(shù)內(nèi)部不使用太多的變量。把大的函數(shù)分割成更加簡(jiǎn)單的、更加小巧的多個(gè)函數(shù)，也可能會(huì)有所幫助。
? 使用關(guān)鍵字register修飾最經(jīng)常使用的變量：告訴編譯器這個(gè)變量將會(huì)被經(jīng)常用到，要求編譯器使用非常高的優(yōu)先級(jí)將此變量分配到寄存器中。盡管如此，在某些情況下，變量還是可能被泄漏。
變量類型 / Variable Types
C編譯器支持基本的變量類型：char、short、int、long(signed、unsigned)、float、double。為變量定義最恰當(dāng)?shù)念愋停浅Ｖ匾驗(yàn)檫@樣可以減少代碼和數(shù)據(jù)的長(zhǎng)度，可以非常顯著的提高效率。
局部變量 / Local variables
如果可能，局部變量要避免使用char和short。對(duì)于char和short類型，編譯器在每次分配空間以后，都要將這種局部變量的尺寸減少到8位或16位。這對(duì)于符號(hào)變量來(lái)說(shuō)稱為符號(hào)擴(kuò)展，對(duì)無(wú)符號(hào)變量稱為無(wú)符號(hào)擴(kuò)展。這種操作是通過(guò)將寄存器左移24或16位，然后再有符號(hào)（或無(wú)符號(hào)的）右移同樣的位數(shù)來(lái)實(shí)現(xiàn)的，需要兩條指令（無(wú)符號(hào)字節(jié)變量的無(wú)符號(hào)擴(kuò)展需要一條指令）。
這些移位操作可以通過(guò)使用int和unsigned int的局部變量來(lái)避免。這對(duì)于那些首先將數(shù)據(jù)調(diào)到局部變量然后利用局部變量進(jìn)行運(yùn)算的情況尤其重要。即使數(shù)據(jù)以8位或16位的形式輸入或輸出，把他們當(dāng)作32位來(lái)處理仍是有意義的。
我們來(lái)考慮下面的三個(gè)例子函數(shù)：
int wordinc (int a)
{
return a + 1;
}
short shortinc (short a)
{
return a + 1;
}
char charinc (char a)
{
return a + 1;
}
他們的運(yùn)算結(jié)果是相同的，但是第一個(gè)代碼片斷要比其他片斷運(yùn)行的要快。
指針 / Pointers
如果可能，我們應(yīng)該使用結(jié)構(gòu)體的引用作為參數(shù)，也就是結(jié)構(gòu)體的指針，否則，整個(gè)結(jié)構(gòu)體就會(huì)被壓入堆棧，然后傳遞，這會(huì)降低速度。程序適用值傳遞可能需要幾K字節(jié)，而一個(gè)簡(jiǎn)單的指針也可以達(dá)到同樣的目的，只需要幾個(gè)字節(jié)就可以了。
如果在函數(shù)內(nèi)部不會(huì)改變結(jié)構(gòu)體的內(nèi)容，那么就應(yīng)該將參數(shù)聲明為const型的指針。舉個(gè)例子：
void print_data_of_a_structure ( const Thestruct *data_pointer)
{
...printf contents of the structure...
}
這個(gè)例子代碼告知編譯器在函數(shù)內(nèi)部不會(huì)改變外部結(jié)構(gòu)體的內(nèi)容，訪問(wèn)他們的時(shí)候，不需要重讀。還可以確保編譯器捕捉任何修改這個(gè)只讀結(jié)構(gòu)體的代碼，給結(jié)構(gòu)體以額外的保護(hù)。
指針鏈 / Pointer chains
指針鏈經(jīng)常被用來(lái)訪問(wèn)結(jié)構(gòu)體的信息，比如，下面的這段常見的代碼：
typedef struct { int x, y, z; } Point3;
typedef struct { Point3 *pos, *direction; } Object;
void InitPos1(Object *p)
{
p->pos->x = 0;
p->pos->y = 0;
p->pos->z = 0;
}
代碼中，處理器在每次賦值操作的時(shí)候都要重新裝載p->pos，因?yàn)榫幾g器不知道p->pos->x不是p->pos的別名。更好的辦法是將p->pos緩存成一個(gè)局部變量，如下：
void InitPos2(Object *p)
{
Point3 *pos = p->pos;
pos->x = 0;
pos->y = 0;
pos->z = 0;
}
另一個(gè)可能的方法是將Point3結(jié)構(gòu)體包含在Object結(jié)構(gòu)體中，完全避免指針的使用。
有條件的執(zhí)行 / Conditional Execution
條件執(zhí)行主要用在if語(yǔ)句中，同時(shí)也會(huì)用到由關(guān)系運(yùn)算(<,==,>等)或bool運(yùn)算(&&,!等)組成的復(fù)雜的表達(dá)式。
盡可能的保持if和else語(yǔ)句的簡(jiǎn)單是有好處的，這樣才能很好的條件化。關(guān)系表達(dá)式應(yīng)該被分成包含相似條件的若干塊。
下面的例子演示了編譯器如何使用條件執(zhí)行：
int g(int a, int b, int c, int d)
{
if (a > 0 && b > 0 && c < 0 && d < 0)
//分組化的條件被捆綁在一起
return a + b + c + d;
return -1;
}
條件被分組，便以其能夠條件化他們。
Boolean表達(dá)式和范圍檢查 / Boolean Expressions & Range checking
有一種常見的boolean表達(dá)式被用來(lái)檢查是否一個(gè)變量取值在某個(gè)特定的范圍內(nèi)，比方說(shuō)，檢查一個(gè)點(diǎn)是否在一個(gè)窗口內(nèi)。
bool PointInRectangelArea (Point p, Rectangle *r)
{
return (p.x >= r->xmin && p.x < r->xmax &&
p.y >= r->ymin && p.y < r->ymax);
}
這里還有一個(gè)更快的方法：把(x >= min && x < max) 轉(zhuǎn)換成 (unsigned)(x-min) < (max-min). 尤其是min為0時(shí)，更為有效。下面是優(yōu)化后的代碼：
bool PointInRectangelArea (Point p, Rectangle *r)
{
return ((unsigned) (p.x - r->xmin) < r->xmax &&
(unsigned) (p.y - r->ymin) < r->ymax);
}
Boolean表達(dá)式&與零的比較 / Boolean Expressions & Compares with zero
在比較(CMP)指令后，相應(yīng)的處理器標(biāo)志位就會(huì)被設(shè)置。這些標(biāo)志位也可以被其他的指令設(shè)置，諸如MOV, ADD, AND, MUL, 也就是基本的數(shù)學(xué)和邏輯運(yùn)算指令（數(shù)據(jù)處理指令）。假如一條數(shù)據(jù)處理指令要設(shè)置這些標(biāo)志位，那么N和Z標(biāo)志位的設(shè)置方法跟把數(shù)字和零比較的設(shè)置方法是一樣的。N標(biāo)志位表示結(jié)果是不是負(fù)數(shù)，Z標(biāo)志位表示結(jié)果是不是零。
在C語(yǔ)言中，處理器中的N和Z標(biāo)志位對(duì)應(yīng)的有符號(hào)數(shù)的關(guān)系運(yùn)算符是x < 0, x >= 0, x == 0, x != 0，無(wú)符號(hào)數(shù)對(duì)應(yīng)的是x == 0, x != 0 (or x > 0)。
C語(yǔ)言中，每用到一個(gè)關(guān)系運(yùn)算符，編譯器就會(huì)產(chǎn)生一個(gè)比較指令。如果關(guān)系運(yùn)算符是上面的其中一個(gè)，在數(shù)據(jù)處理指令緊跟比較指令的情況下，編譯器就會(huì)將比較指令優(yōu)化掉。比如：
int aFunction(int x, int y)
{
if (x + y < 0)
return 1;
else
return 0;
}
這樣做，會(huì)在關(guān)鍵循環(huán)中節(jié)省比較指令，使代碼長(zhǎng)度減少，效率增加。C語(yǔ)言中沒有借位(carry)標(biāo)志位和溢出(overflow)標(biāo)志位的概念，所以如果不使用內(nèi)嵌匯編語(yǔ)言，要訪問(wèn)C和V標(biāo)志位是不可能的。盡管如此，編譯器支持借位標(biāo)志位（無(wú)符號(hào)數(shù)溢出），比方說(shuō)：
int sum(int x, int y)
{
int res;
res = x + y;
if ((unsigned) res < (unsigned) x) // carry set? //
res++;
return res;
}
Lazy Evaluation Exploitation
In a if(a>10 && b=4) type of thing, make sure that the first part of the AND expression is the most likely to give a false answer (or the easiest/quickest to calculate), therefore the second part will be less likely to be executed.
用switch() 代替if...else...
在條件選擇比較多的情況下，可以用if…else…else…，像這樣：
if( val == 1)
dostuff1();
else if (val == 2)
dostuff2();
else if (val == 3)
dostuff3();
使用switch可以更快：
switch( val )
{
case 1: dostuff1(); break;
case 2: dostuff2(); break;
case 3: dostuff3(); break;
}
在if語(yǔ)句中，即使是最后一個(gè)條件成立，也要先判斷所有前面的條件是否成立。Switch語(yǔ)句能夠去除這些額外的工作。如果你不得不使用if…else，那就把最可能的成立的條件放在前面。
二進(jìn)制分解 / Binary Breakdown
把判斷條件做成二進(jìn)制的風(fēng)格，比如，不要使用下面的列表：
if(a==1) {
} else if(a==2) {
} else if(a==3) {
} else if(a==4) {
} else if(a==5) {
} else if(a==6) {
} else if(a==7) {
} else if(a==8)
{
}
而采用：
if(a<=4) {
if(a==1) {
} else if(a==2) {
} else if(a==3) {
} else if(a==4) {
}
}
else
{
if(a==5) {
} else if(a==6) {
} else if(a==7) {
} else if(a==8) {
}
}
甚至：
if(a<=4)
{
if(a<=2)
{
if(a==1)
{
/* a is 1 */
}
else
{
/* a must be 2 */
}
}
else
{
if(a==3)
{
/* a is 3 */
}
else
{
/* a must be 4 */
}
}
}
else
{
if(a<=6)
{
if(a==5)
{
/* a is 5 */
}
else
{
/* a must be 6 */
}
}
else
{
if(a==7)
{
/* a is 7 */
}
else
{
/* a must be 8 */
}
}
}
慢速、低效 快速、高效
c=getch();
switch(c){
case 'A':
{
do something;
break;
}
case 'H':
{
do something;
break;
}
case 'Z':
{
do something;
break;
}
} c=getch();
switch(c){
case 0:
{
do something;
break;
}
case 1:
{
do something;
break;
}
case 2:
{
do something;
break;
}
}
以上是兩個(gè)case語(yǔ)句之間的比較
switch語(yǔ)句和查找表 / Switch statement vs. lookup tables
switch語(yǔ)句通常用于以下情況：
? 調(diào)用幾個(gè)函數(shù)中的一個(gè)
? 設(shè)置一個(gè)變量或返回值
? 執(zhí)行幾個(gè)代碼片斷中的一個(gè)
如果case表示是密集的（譯者：連續(xù)的？），在使用switch語(yǔ)句的前兩種情況中，可以使用效率更高的查找表。比如下面的兩個(gè)實(shí)現(xiàn)匯編代碼轉(zhuǎn)換成字符串的例程：
char * Condition_String1(int condition) {
switch(condition) {
case 0: return "EQ";
case 1: return "NE";
case 2: return "CS";
case 3: return "CC";
case 4: return "MI";
case 5: return "PL";
case 6: return "VS";
case 7: return "VC";
case 8: return "HI";
case 9: return "LS";
case 10: return "GE";
case 11: return "LT";
case 12: return "GT";
case 13: return "LE";
case 14: return "";
default: return 0;
}
}
char * Condition_String2(int condition) {
if ((unsigned) condition >= 15) return 0;
return
"EQ\0NE\0CS\0CC\0MI\0PL\0VS\0VC\0HI\0LS\0GE\0LT\0GT\0LE\0\0" +
3 * condition;
}
第一個(gè)例程需要240個(gè)字節(jié)，第二個(gè)只需要72個(gè)。
循環(huán) / Loops
在大多數(shù)程序中，循環(huán)是一種常見的結(jié)構(gòu)，相當(dāng)數(shù)量的執(zhí)行時(shí)間被消耗在循環(huán)上，因此在時(shí)間苛刻的循環(huán)上付出注意是值得的。
循環(huán)終止 / Loop termination
如果編寫循環(huán)終止條件是不加留意，就可能會(huì)給程序帶來(lái)明顯的負(fù)擔(dān)。我們應(yīng)該盡量使用“倒數(shù)到零”的循環(huán)，使用簡(jiǎn)單的循環(huán)終止條件。循環(huán)終止條件相對(duì)簡(jiǎn)單，程序在執(zhí)行的時(shí)候也會(huì)消耗相對(duì)少的時(shí)間。拿下面兩個(gè)計(jì)算n!的例子來(lái)說(shuō)，第一個(gè)例子使用遞增循環(huán)，第二個(gè)使用遞減循環(huán)。
int fact1_func (int n)
{
int i, fact = 1;
for (i = 1; i <= n; i++)
fact *= i;
return (fact);
}
int fact2_func(int n)
{
int i, fact = 1;
for (i = n; i != 0; i--)
fact *= i;
return (fact);
}
結(jié)果是，第二個(gè)例子要比第一個(gè)快得多。
更快的for()循環(huán) / Faster for() loops
這是一個(gè)簡(jiǎn)單而有效的概念，通常情況下，我們習(xí)慣把for循環(huán)寫成這樣：
for( i=0; i<10; i++){ ... }
i值依次為：0,1,2,3,4,5,6,7,8,9
在不在乎循環(huán)計(jì)數(shù)器順序的情況下，我們可以這樣：
for( i=10; i--; ) { ... }
i值依次為: 9,8,7,6,5,4,3,2,1,0,而且循環(huán)要更快
這種方法是可行的，因?yàn)樗怯酶斓膇--作為測(cè)試條件的，也就是說(shuō)“i是否為非零數(shù)，如果是減一，然后繼續(xù)”。相對(duì)于原先的代碼，處理器不得不“把i減去10，結(jié)果是否為非零數(shù)，如果是，增加i，然后繼續(xù)”，在緊密循環(huán)(tight loop)中，這會(huì)產(chǎn)生顯著的區(qū)別。
這種語(yǔ)法看起來(lái)有一點(diǎn)陌生，卻完全合法。循環(huán)中的第三條語(yǔ)句是可選的（無(wú)限循環(huán)可以寫成這樣for(;;)）,下面的寫法也可以取得同樣的效果：
for(i=10; i; i--){}
或者:
for(i=10; i!=0; i--){}
我們唯一要小心的地方是要記住循環(huán)需要停止在0（如果循環(huán)是從50-80，這樣做就不行了），而且循環(huán)的計(jì)數(shù)器為倒計(jì)數(shù)方式。
另外，我們還可以把計(jì)數(shù)器分配到寄存器上，可以產(chǎn)生更為有效的代碼。這種將循環(huán)計(jì)數(shù)器初始化成循環(huán)次數(shù)，然后遞減到零的方法，同樣適用于while和do語(yǔ)句。
混合循環(huán)/ Loop jamming
在可以使用一個(gè)循環(huán)的場(chǎng)合，決不要使用兩個(gè)。但是如果你要在循環(huán)中進(jìn)行大量的工作，超過(guò)處理器的指令緩沖區(qū)，在這種情況下，使用兩個(gè)分開的循環(huán)可能會(huì)更快，因?yàn)橛锌赡苓@兩個(gè)循環(huán)都被完整的保存在指令緩沖區(qū)里了。
//原先的代碼
for(i=0; i<100; i++){
stuff();
}
for(i=0; i<100; i++){
morestuff();
}
//更好的做法
for(i=0; i<100; i++){
stuff();
morestuff();
}
函數(shù)循環(huán) / Function Looping
調(diào)用函數(shù)的時(shí)候，在性能上就會(huì)付出一定的代價(jià)。不光要改變程序指針，還要將那些正在使用的變量壓入堆棧，分配新的變量空間。為了提高程序的效率，在程序的函數(shù)結(jié)構(gòu)上，有很多工作可以做。保證程序的可讀性的同時(shí)，還要盡量控制程序的大小。
如果一個(gè)函數(shù)在一個(gè)循環(huán)中被頻繁調(diào)用，就可以考慮將這個(gè)循環(huán)放在函數(shù)的里面，這樣可以免去重復(fù)調(diào)用函數(shù)的負(fù)擔(dān)，比如：
for(i=0 ; i<100 ; i++)
{
func(t,i);
}
void func(int w,d)
{
lots of stuff.
}
可以寫成…
func(t);
void func(w)
{
for(i=0 ; i<100 ; i++)
{
//lots of stuff.
}
}
循環(huán)的拆解 / Loop unrolling
為了提高效率，可以將小的循環(huán)解開，不過(guò)這樣會(huì)增加代碼的尺寸。循環(huán)被拆開后，會(huì)降低循環(huán)計(jì)數(shù)器更新的次數(shù)，減少所執(zhí)行的循環(huán)的分支數(shù)目。如果循環(huán)只重復(fù)幾次，那它完全可以被拆解開，這樣，由循環(huán)所帶來(lái)的額外開銷就會(huì)消失。
比如:
for(i=0; i<3; i++){
something(i);
}
//更高效的方式
something(0);
something(1);
something(2);
因?yàn)樵诿看蔚难h(huán)中，i的值都會(huì)增加，然后檢查是否有效。編譯器經(jīng)常會(huì)把這種簡(jiǎn)單的循環(huán)解開，前提是這些循環(huán)的次數(shù)是固定的。對(duì)于這樣的循環(huán)：
for(i=0;i< limit;i++) { ... }
就不可能被拆解，因?yàn)槲覀儾恢浪h(huán)的次數(shù)到底是多少。不過(guò)，將這種類型的循環(huán)拆解開并不是不可能的。
與簡(jiǎn)單循環(huán)相比，下面的代碼的長(zhǎng)度要長(zhǎng)很多，然而具有高得多的效率。選擇8作為分塊大小，只是用來(lái)演示，任何合適的長(zhǎng)度都是可行的。例子中，循環(huán)的成立條件每八次才被檢驗(yàn)一次，而不是每次都要檢驗(yàn)。如果需要處理的數(shù)組的大小是確定的，我們就可以使用數(shù)組的大小作為分塊的大小（或者是能夠整除數(shù)組長(zhǎng)度的數(shù)值）。不過(guò)，分塊的大小跟系統(tǒng)的緩存大小有關(guān)。
//例1
#include<STDIO.H>
#define BLOCKSIZE (8)
void main(void)
{
int i = 0;
int limit = 33; /* could be anything */
int blocklimit;
/* The limit may not be divisible by BLOCKSIZE,
* go as near as we can first, then tidy up.
*/
blocklimit = (limit / BLOCKSIZE) * BLOCKSIZE;
/* unroll the loop in blocks of 8 */
while( i < blocklimit )
{
printf("process(%d)\n", i);
printf("process(%d)\n", i+1);
printf("process(%d)\n", i+2);
printf("process(%d)\n", i+3);
printf("process(%d)\n", i+4);
printf("process(%d)\n", i+5);
printf("process(%d)\n", i+6);
printf("process(%d)\n", i+7);
/* update the counter */
i += 8;
}
/*
* There may be some left to do.
* This could be done as a simple for() loop,
* but a switch is faster (and more interesting)
*/
if( i < limit )
{
/* Jump into the case at the place that will allow
* us to finish off the appropriate number of items.
*/
switch( limit - i )
{
case 7 : printf("process(%d)\n", i); i++;
case 6 : printf("process(%d)\n", i); i++;
case 5 : printf("process(%d)\n", i); i++;
case 4 : printf("process(%d)\n", i); i++;
case 3 : printf("process(%d)\n", i); i++;
case 2 : printf("process(%d)\n", i); i++;
case 1 : printf("process(%d)\n", i);
}
}
}
人口統(tǒng)計(jì)-計(jì)算非零位的個(gè)數(shù) / Population count - counting the number of bits set
例1測(cè)試單個(gè)的最低位，計(jì)數(shù)，然后移位。例2則是先除4，然后計(jì)算被4處的每個(gè)部分。循環(huán)拆解經(jīng)常會(huì)給程序優(yōu)化帶來(lái)新的機(jī)會(huì)。
//Example - 1
int countbit1(uint n)
{
int bits = 0;
while (n != 0)
{
if (n & 1) bits++;
n >>= 1;
}
return bits;
}
//Example - 2
int countbit2(uint n)
{
int bits = 0;
while (n != 0)
{
if (n & 1) bits++;
if (n & 2) bits++;
if (n & 4) bits++;
if (n & 8) bits++;
n >>= 4;
}
return bits;
}
及早的退出循環(huán) / Early loop breaking
通常沒有必要遍歷整個(gè)循環(huán)。舉例來(lái)說(shuō)，在數(shù)組中搜索一個(gè)特定的值，我們可以在找到我們需要值之后立刻退出循環(huán)。下面的例子在10000個(gè)數(shù)字中搜索-99。
found = FALSE;
for(i=0;i<10000;i++)
{
if( list[i] == -99 )
{
found = TRUE;
}
}
if( found ) printf("Yes, there is a -99. Hooray!\n");
這樣做是可行的，但是不管這個(gè)被搜索到的項(xiàng)目出現(xiàn)在什么位置，都會(huì)搜索整個(gè)數(shù)組。跟好的方法是，再找到我們需要的數(shù)字以后，立刻退出循環(huán)。
found = FALSE;
for(i=0; i<10000; i++)
{
if( list[i] == -99 )
{
found = TRUE;
break;
}
}
if( found ) printf("Yes, there is a -99. Hooray!\n");
如果數(shù)字出現(xiàn)在位置23上，循環(huán)就會(huì)終止，忽略剩下的9977個(gè)。
函數(shù)設(shè)計(jì) / Function Design
保持函數(shù)短小精悍，是對(duì)的。這可以使編譯器能夠跟高效地進(jìn)行其他的優(yōu)化，比如寄存器分配。
調(diào)用函數(shù)的開銷 / Function call overhead
對(duì)處理器而言，調(diào)用函數(shù)的開銷是很小的，通常，在被調(diào)用函數(shù)所進(jìn)行的工作中，所占的比例也很小。能夠使用寄存器傳遞的函數(shù)參數(shù)個(gè)數(shù)是有限制的。這些參數(shù)可以是整型兼容的（char,short,int以及float都占用一個(gè)字），或者是4個(gè)字以內(nèi)的結(jié)構(gòu)體（包括2個(gè)字的double和long long）。假如參數(shù)的限制是4，那么第5個(gè)及后面的字都會(huì)被保存到堆棧中。這會(huì)增加在調(diào)用函數(shù)是存儲(chǔ)這些參數(shù)的，以及在被調(diào)用函數(shù)中恢復(fù)這些參數(shù)的代價(jià)。
int f1(int a, int b, int c, int d) {
return a + b + c + d;
}
int g1(void) {
return f1(1, 2, 3, 4);
}
int f2(int a, int b, int c, int d, int e, int f) {
return a + b + c + d + e + f;
}
ing g2(void) {
return f2(1, 2, 3, 4, 5, 6);
}
g2函數(shù)中，第5、6個(gè)參數(shù)被保存在堆棧中，在f2中被恢復(fù)，每個(gè)參數(shù)帶來(lái)2次內(nèi)存訪問(wèn)。
最小化參數(shù)傳遞開銷 / Minimizing parameter passing overhead
為了將傳遞參數(shù)給函數(shù)的代價(jià)降至最低，我們可以：
盡可能確保函數(shù)的形參不多于四個(gè)，甚至更少，這樣就不會(huì)使用堆棧來(lái)傳遞參數(shù)。
如果一個(gè)函數(shù)形參多于四個(gè)，那就確保在這個(gè)函數(shù)能夠做大量的工作，這樣就可以抵消由傳遞堆棧參數(shù)所付出的代價(jià)。
用指向結(jié)構(gòu)體的指針作形參，而不是結(jié)構(gòu)體本身。
把相關(guān)的參數(shù)放到一個(gè)結(jié)構(gòu)里里面，然后把它的指針傳給函數(shù)，可以減少參數(shù)的個(gè)數(shù)，增加程序的可讀性。
將long類型的參數(shù)的個(gè)數(shù)降到最小，因?yàn)樗褂脙蓚€(gè)參數(shù)的空間。對(duì)于double也同樣適用。
避免出現(xiàn)參數(shù)的一部分使用寄存器傳輸，另一部分使用堆棧傳輸?shù)那闆r。這種情況下參數(shù)將被全部壓到堆棧里。
避免出現(xiàn)函數(shù)的參數(shù)個(gè)數(shù)不定的情況。這種情況下，所有參數(shù)都使用堆棧。
葉子函數(shù) / Leaf functions
如果一個(gè)函數(shù)不再調(diào)用其他函數(shù)，這樣的函數(shù)被稱為葉子函數(shù)。在許多應(yīng)用程序中，大約一半的函數(shù)調(diào)用是對(duì)葉子函數(shù)的調(diào)用。葉子函數(shù)在所有平臺(tái)上都可以得到非常高效的編譯，因?yàn)樗麄儾恍枰M(jìn)行參數(shù)的保存和恢復(fù)。在入口壓棧和在出口退棧的代價(jià)，跟一個(gè)足夠復(fù)雜的需要4個(gè)或者5個(gè)參數(shù)的葉子函數(shù)所完成的工作相比，是非常小的。如果可能的話，我們就要盡量安排經(jīng)常被調(diào)用的函數(shù)成為葉子函數(shù)。函數(shù)被調(diào)用的次數(shù)可以通過(guò)模型工具（profiling facility）來(lái)確定。這里有幾種方法可以確保函數(shù)被編譯成葉子函數(shù)：
不調(diào)用其他函數(shù)：包括那些被轉(zhuǎn)換成調(diào)用C語(yǔ)言庫(kù)函數(shù)的運(yùn)算，比如除法、浮點(diǎn)運(yùn)算。
使用關(guān)鍵字__inline修飾小的函數(shù)。
內(nèi)嵌函數(shù) / Inline functions
對(duì)于所有調(diào)試選項(xiàng)，內(nèi)嵌函數(shù)是被禁止的。使用inline關(guān)鍵字修飾函數(shù)后，跟普通的函數(shù)調(diào)用不同，代碼中對(duì)該函數(shù)的調(diào)用將會(huì)被函數(shù)體本身代替。這會(huì)是代碼更快，另一方面它會(huì)影響代碼的長(zhǎng)度，尤其是內(nèi)嵌函數(shù)比較大而且經(jīng)常被調(diào)用的情況下。
__inline int square(int x) {
return x * x;
}
#include <MATH.H>
double length(int x, int y){
return sqrt(square(x) + square(y));
}
使用內(nèi)嵌函數(shù)有幾個(gè)優(yōu)點(diǎn)：
沒有調(diào)用函數(shù)的開銷。因?yàn)楹瘮?shù)被直接代替，沒有任何額外的開銷，比如存儲(chǔ)和恢復(fù)寄存器。
更低的參數(shù)賦值開銷。參數(shù)傳遞的開銷通常會(huì)更低，因?yàn)樗恍枰獜?fù)制變量。如果其中一些參數(shù)是常量，編譯器還可以作進(jìn)一步的優(yōu)化。
內(nèi)嵌函數(shù)的缺點(diǎn)是如果函數(shù)在許多地方被調(diào)用，將會(huì)增加代碼的長(zhǎng)度。長(zhǎng)度差別的大小顯著依賴于內(nèi)嵌函數(shù)的大小和調(diào)用的次數(shù)。
僅將少數(shù)關(guān)鍵函數(shù)設(shè)置成內(nèi)嵌函數(shù)是明智的。如果設(shè)置得當(dāng)，內(nèi)嵌函數(shù)可以減少代碼的長(zhǎng)度，一次函數(shù)調(diào)用需要一定數(shù)量的指令，但是，使用優(yōu)化過(guò)的內(nèi)嵌函數(shù)可以編譯成更少的指令。
使用查找表 / Using Lookup Tables
有些函數(shù)可以近似成查找表，這樣可以顯著的提高效率。查找表的精度一般比計(jì)算公式的精度低，不過(guò)在大多數(shù)程序中，這種精度就足夠了。
許多信號(hào)處理軟件（比如MODEM調(diào)制軟件）會(huì)大量的使用sin和cos函數(shù)，這些函數(shù)會(huì)帶來(lái)大量的數(shù)學(xué)運(yùn)算。對(duì)于實(shí)時(shí)系統(tǒng)來(lái)說(shuō)，精度不是很重要，sin/cos查找表顯得更加實(shí)用。使用查找表的時(shí)候，盡量將相近的運(yùn)算合并成一個(gè)查找表，這樣要比使用多個(gè)查找表要更快和使用更少的空間。
浮點(diǎn)運(yùn)算 / Floating-Point Arithmetic
盡管浮點(diǎn)運(yùn)算對(duì)于任何處理器來(lái)講都是很費(fèi)時(shí)間的，有的時(shí)候，我們還是不得不用到負(fù)點(diǎn)運(yùn)算，比方說(shuō)實(shí)現(xiàn)信號(hào)處理。盡管如此，編寫浮點(diǎn)運(yùn)算代碼的時(shí)候，我們要牢記：
浮點(diǎn)除法是慢的。除法要比加法或者乘法慢兩倍，我們可以把被一個(gè)常數(shù)除的運(yùn)算寫成被這個(gè)數(shù)的倒數(shù)乘（比如，x=x/3.0寫成x=x*(1.0/3.0)）。倒數(shù)的計(jì)算在編譯階段就被完成。
使用float代替double。Float型變量消耗更少的內(nèi)存和寄存器，而且因?yàn)樗牡途人跃哂懈叩男省Ｔ诰茸銐虻那闆r下，就要使用float。
不要使用先驗(yàn)函數(shù)（transcendental functions），先驗(yàn)函數(shù)（比如sin，cos，log）是通過(guò)使用一系列的乘法和加法實(shí)現(xiàn)的，所以這些運(yùn)算會(huì)比普通的乘法慢10倍以上。
簡(jiǎn)化浮點(diǎn)表達(dá)式。編譯器在整型跟浮點(diǎn)型混合的運(yùn)算中不會(huì)進(jìn)行太多的優(yōu)化。比如3 * (x / 3) 不會(huì)被優(yōu)化成x，因?yàn)楦↑c(diǎn)運(yùn)算通常會(huì)導(dǎo)致精度的降低，甚至表達(dá)式的順序都是重要的： (a + b) + c 不等于 a + (b + c)。因此，進(jìn)行手動(dòng)的優(yōu)化是有好處的。
不過(guò)，在特定的場(chǎng)合下，浮點(diǎn)運(yùn)算的效率達(dá)不到指定的水平，這種情況下，最好的辦法可能是放棄浮點(diǎn)運(yùn)算，轉(zhuǎn)而使用定點(diǎn)運(yùn)算。當(dāng)變量的變化范圍足夠的小，定點(diǎn)運(yùn)算要比浮點(diǎn)運(yùn)算精度更高、速度更快。
其他的技巧 / Misc tips
一般情況下，可以用存儲(chǔ)空間換取時(shí)間。你可以緩存那些經(jīng)常用到的數(shù)據(jù)，而不是每次都重新計(jì)算、或者重新裝載。比如sin/cos表，或者偽隨機(jī)數(shù)的表（如果你不是真的需要隨機(jī)數(shù)，你可以在開始的時(shí)候計(jì)算1000個(gè)，在隨后的代碼中重復(fù)利用就是了）
盡量少的使用全局變量。
將一個(gè)文件內(nèi)部的變量聲明成靜態(tài)的，除非它有必要成為全局的。
不要使用遞歸。遞歸可以使代碼非常整齊和美觀，但會(huì)產(chǎn)生大量的函數(shù)調(diào)用和開銷。
訪問(wèn)單維數(shù)組要比多位數(shù)組快
使用#defined宏代替經(jīng)常用到的小函數(shù)。
參考文獻(xiàn) / References
（譯者略）
其他網(wǎng)絡(luò)資源 / Other URLs
http://www.xs4all.nl/~ekonijn/loopy.html
http://www.public.asu.edu/~sshetty/Optimizing_Code_Manual.doc
http://www.abarnett.demon.co.uk/tutorial.html
譯者聲明：作者對(duì)我的這片譯文并不知情，我在完全不知會(huì)作者的情況下翻譯了其發(fā)表于www.codeproject.com的文章，但我保留了原文的作者信息。請(qǐng)您僅將此文用于學(xué)術(shù)研究目的。如果您要將此文用于其它目的，請(qǐng)與原作者聯(lián)系。如果您認(rèn)為文章翻譯的有問(wèn)題，譯者將非常高興看到您提出的寶貴意見。