1、選擇合適的算法和數據結構
選擇一種合適的數據結構很重要,如果在一堆隨機存放的數中使用了大量的插入和刪除指令,那使用鏈表要快得多。數組與指針語句具有十分密切的關系,一般來說,指針比較靈活簡潔,而數組則比較直觀,容易理解。對於大部分的編譯器,使用指針比使用數組生成的代碼更短,執行效率更高。
在許多種情況下,可以用指針運算代替數組索引,這樣做常常能產生又快又短的代碼。與數組索引相比,指針一般能使代碼速度更快,占用空間更少。使用多維數組時差異更明顯。下面的代碼作用是相同的,但是效率不一樣。
數組索引 指針運算
For(;;){ p=array
A=array[t++]; for(;;){
a=*(p++);
。。。。。。。。。 。。。。。。。。。
} }
指針方法的優點是,array的地址每次裝入地址p後,在每次循環中只需對p增量操作。在數組索引方法中,每次循環中都必須根據t值求數組下標的復雜運算。
2、使用盡量小的數據類型
能夠使用字符型(char)定義的變量,就不要使用整型(int)變量來定義;能夠使用整型變量定義的變量就不要用長整型(long int),能不使用浮點型(float)變量就不要使用浮點型變量。當然,在定義變量後不要超過變量的作用范圍,如果超過變量的范圍賦值,C編譯器並不報錯,但程序運行結果卻錯了,而且這樣的錯誤很難發現。
在ICCAVR中,可以在Options中設定使用printf參數,盡量使用基本型參數(%c、%d、%x、%X、%u和%s格式說明符),少用長整型參數(%ld、%lu、%lx和%lX格式說明符),至於浮點型的參數(%f)則盡量不要使用,其他C編譯器也一樣。在其他條件不變的情況下,使用%f參數,會使生成的代碼的數量增加很多,執行速度降低。
3、減少運算的強度
（1）、查表
一個聰明的游戲大蝦,基本上不會在自己的主循環裡搞什麼運算工作,絕對是先計算好了,再到循環裡查表。看下面的例子:
舊代碼:
long factorial(int i)
{
if (i == 0)
return 1;
else
return i * factorial(i - 1);
}
新代碼:
static long factorial_table[] =
{1, 1, 2, 6, 24, 120, 720 //etc };
long factorial(int i)
{
return factorial_table[i];
}
如果表很大,不好寫,就寫一個init函數,在循環外臨時生成表格。
（2）、求余運算
a=a%8;
可以改為:
a=a&7;
說明:位操作只需一個指令周期即可完成,而大部分的C編譯器的"%"運算均是調用子程序來完成,代碼長、執行速度慢。通常,只要求是求2n方的余數,均可使用位操作的方法來代替。
（3）、平方運算
a=pow(a, 2.0);
可以改為:
a=a*a;
說明:在有內置硬件乘法器的單片機中(如51系列),乘法運算比求平方運算快得多,因為浮點數的求平方是通過調用子程序來實現的,在自帶硬件乘法器的AVR單片機中,如ATMega163中,乘法運算只需2個時鐘周期就可以完成。既使是在沒有內置硬件乘法器的AVR單片機中,乘法運算的子程序比平方運算的子程序代碼短,執行速度快。
如果是求3次方,如:
a=pow(a,3。0);
更改為:
a=a*a*a;
則效率的改善更明顯。
（4）、用移位實現乘除法運算
a=a*4;
b=b/4;
可以改為:
a=a<<2;
b=b>>2;
通常如果需要乘以或除以2n,都可以用移位的方法代替。在ICCAVR中,如果乘以2n,都可以生成左移的代碼,而乘以其他的整數或除以任何數,均調用乘除法子程序。用移位的方法得到代碼比調用乘除法子程序生成的代碼效率高。實際上,只要是乘以或除以一個整數,均可以用移位的方法得到結果,如:
a=a*9
可以改為:
a=(a<<3)+a
采用運算量更小的表達式替換原來的表達式,下面是一個經典例子:
舊代碼:
x= w % 8;
y= pow(x, 2.0);
z= y * 33;
for (i = 0;i < MAX;i++)
{
h = 14 * i;
printf("%d", h);
}
新代碼:
x= w&7; // 位操作比求余運算快
y= x*x; // 乘法比平方運算快
z = (y << 5) + y; // 位移乘法比乘法快
for (i = h = 0; i < MAX; i++)
{
h += 14; // 加法比乘法快
printf("%d", h);
}
（5）、避免不必要的整數除法
整數除法是整數運算中最慢的,所以應該盡可能避免。一種可能減少整數除法的地方是連除,這裡除法可以由乘法代替。這個替換的副作用是有可能在算乘積時會溢出,所以只能在一定范圍的除法中使用。
舊代碼:
int i, j, k, m;
m = i / j / k;
新代碼:
int i, j, k, m;
m = i / (j * k);
（6）、使用增量和減量操作符
在使用到加一和減一操作時盡量使用增量和減量操作符,因為增量符語句比賦值語句更快,原因在於對大多數CPU來說,對內存字的增、減量操作不必明顯地使用取存儲器和寫存儲器的指令,比如下面這條語句:
x=x+1;
模仿大多數微機匯編語言為例,產生的代碼類似於:
move A,x ;把x從存儲器取出存入累加器A
add A,1 ;累加器A加1
store x ;把新值存回x
如果使用增量操作符源代碼如下:
++x;
生成的代碼如下:
incr x ;x加1
顯然,不用取指令和存指令,增、減量操作執行的速度加快,同時長度也縮短了。
還有，最好用前置，後置需要保存一次。
（7）、使用復合賦值表達式
復合賦值表達式(如a-=1及a+=1等)都能夠生成高質量的程序代碼。
舊代碼:
a=a+b;
新代碼:
a+=b;
（8）、提取公共的子表達式
在某些情況下,C++編譯器不能從浮點表達式中提出公共的子表達式,因為這意味著相當於對表達式重新排序。需要特別指出的是,編譯器在提取公共子表達式前不能按照代數的等價關系重新安排表達式。這時,程序員要手動地提出公共的子表達式（在VC.NET裡有一項"全局優化"選項可以完成此工作,但效果就不得而知了）。
舊代碼:
float a, b, c, d, e, f;
。。。
e = b * c / d;
f = b / d * a;
新代碼:
float a, b, c, d, e, f;
。。。
const float t(b / d);
e = c * t;
f = a * t;
舊代碼:
float a, b, c, e, f;
。。。
e = a / c;
f = b / c;
新代碼:
float a, b, c, e, f;
。。。
const float t(1.0f / c);
e = a * t;
f = b * t;
4、結構體成員的布局
很多編譯器有"使結構體字,雙字或四字對齊"的選項。但是,還是需要改善結構體成員的對齊,有些編譯器可能分配給結構體成員空間的順序與他們聲明的不同。但是,有些編譯器並不提供這些功能,或者效果不好。所以,要在付出最少代價的情況下實現最好的結構體和結構體成員對齊,建議采取下列方法:
（1）按數據類型的長度排序
把結構體的成員按照它們的類型長度排序,聲明成員時把長的類型放在短的前面。編譯器要求把長型數據類型存放在偶數地址邊界。在申明一個復雜的數據類型 (既有多字節數據又有單字節數據)時,應該首先存放多字節數據,然後再存放單字節數據,這樣可以避免存儲器的空洞。編譯器自動地把結構的實例對齊在內存的偶數邊界。
（2）把結構體填充成最長類型長度的整倍數
把結構體填充成最長類型長度的整倍數。照這樣,如果結構體的第一個成員對齊了,所有整個結構體自然也就對齊了。下面的例子演示了如何對結構體成員進行重新排序:
舊代碼: //普通順序
struct
{
char a[5];
long k;
double x;
baz;
}
新代碼: //新的順序並手動填充了幾個位元組
struct
{
double x;
long k;
char a[5];
char pad[7];
baz;
}
這個規則同樣適用於類的成員的布局。
（3）按數據類型的長度排序本地變量
當編譯器分配給本地變量空間時,它們的順序和它們在源代碼中聲明的順序一樣,和上一條規則一樣,應該把長的變量放在短的變量前面。如果第一個變量對齊了,其他變量就會連續的存放,而且不用填充字節自然就會對齊。有些編譯器在分配變量時不會自動改變變量順序,有些編譯器不能產生4字節對齊的棧,所以4字節可能不對齊。下面這個例子演示了本地變量聲明的重新排序:
舊代碼,普通順序
short ga, gu, gi;
long foo, bar;
double x, y, z[3];
char a, b;
float baz;
新代碼,改進的順序
double z[3];
double x, y;
long foo, bar;
float baz;
short ga, gu, gi;
（4）把頻繁使用的指針型參數拷貝到本地變量
避免在函數中頻繁使用指針型參數指向的值。因為編譯器不知道指針之間是否存在沖突,所以指針型參數往往不能被編譯器優化。這樣數據不能被存放在寄存器中,而且明顯地占用了存儲器帶寬。注意,很多編譯器有"假設不沖突"優化開關（在VC裡必須手動添加編譯器命令行/Oa或/Ow）,這允許編譯器假設兩個不同的指針總是有不同的內容,這樣就不用把指針型參數保存到本地變量。否則,請在函數一開始把指針指向的數據保存到本地變量。如果需要的話,在函數結束前拷貝回去。
舊代碼:
// 假設 q != r
void isqrt(unsigned long a, unsigned long*q, unsigned long* r)
{
*q = a;
if (a >0)
{
while (*q> (*r = a / *q))
{
*q = (*q+ *r) >> 1;
}
}
*r = a - *q* *q;
}
新代碼:
// 假設 q != r
void isqrt(unsigned long a, unsigned long*q, unsigned long* r)
{
unsignedlong qq, rr;
qq = a;
if (a >0)
{
while (qq> (rr = a / qq))
{
qq = (qq+ rr) >> 1;
}
}
rr = a - qq* qq;
*q = qq;
*r = rr;
}
