同樣的事情，使用不一樣的方法去完成，雖然最終的結(jié)果一樣，但是完成的效率往往不一樣。假如你離家一千公里路程，過年要回家過春節(jié)，你可以走路回家，可以騎自行車回家，可以騎摩托車回家，可以坐汽車回家，可以坐火車回家，當(dāng)然也可以坐飛機(jī)回家，雖然最終目的都是到達(dá)一千公里的家鄉(xiāng)，但是乘坐不同的交通工具，回家的時間各異。在程序中，這些不同的“交通工具”我們稱之為算法。
代碼的運(yùn)算速度取決于以下幾個方面：
（1）處理器的主頻和設(shè)計架構(gòu)；
（2）處理器的總線帶寬；
（3）程序代碼的設(shè)計編寫；
（4）程序中所使用算法本身的復(fù)雜度，比如MPEG比JPEG復(fù)雜，JPEG比BMP圖片的編碼復(fù)雜。
比如在一個圖像轉(zhuǎn)換的項目中，需要將RGB格式的彩色圖像先轉(zhuǎn)換成黑白圖像。圖像轉(zhuǎn)換的公式如下：
Y = 0.299 * R + 0.587 * G + 0.114 * B;
圖像尺寸640*480*24 bits，RGB圖像已經(jīng)按照RGBRGB順序排列的格式，放在內(nèi)存里面了。
例如，將這個噴火的戰(zhàn)斗機(jī)引擎，轉(zhuǎn)換為右邊的黑白圖片。
圖片輸入和輸出的定義如下：
#define XSIZE (640)
#define YSIZE (480)
#define IMGSIZE XSIZE*YSIZE
typedef struct rgb
{
uint8_t r;
uint8_t g;
uint8_t b;
}RGB;
RGB in[IMGSIZE]; /* 未轉(zhuǎn)換的圖片數(shù)據(jù) */
uint8_t out[IMGSIZE]; /* 轉(zhuǎn)換后的圖片數(shù)據(jù) */
優(yōu)化原則：
圖像是一個二維數(shù)組，我用一個一維數(shù)組來存儲。編譯器處理一維數(shù)組的效率要高于二維數(shù)組。
第一個程序：
void convert_rgb_image(void)
{
int i = 0;
for(i = 0; i < IMGSIZE; i++)
{
uint8_t r = in[i].r;
uint8_t g = in[i].g;
uint8_t b = in[i].b;
double temp_out = 0.299 * r + 0.587 * g + 0.114 * b;
out[i] = temp_out;
}
}
分別用VC6.0和交叉編譯工具，生成2個版本，分別在PC和嵌入式開發(fā)板上面運(yùn)行。
A、在PC上，由于存在硬件浮點(diǎn)處理器，CPU頻率也夠高，運(yùn)行時間為20秒。
B、在嵌入式開發(fā)板 ，主頻時鐘比較低，也沒有浮點(diǎn)處理器，浮點(diǎn)操作被編譯器分解成了整數(shù)運(yùn)算，運(yùn)行時間為120秒左右。
第一次優(yōu)化
優(yōu)化原則：
去掉浮點(diǎn)數(shù)運(yùn)算。
在公式Y = 0.299 * R + 0.587 * G + 0.114 * B中，由于RGB的取值范圍都是0~255，只是系數(shù)都是浮點(diǎn)數(shù)，將RGB的系數(shù)轉(zhuǎn)換為：
R的系數(shù)：0.299 = 299 / 1000
G的系數(shù)：0.587 = 587 / 1000
B的系數(shù)：0.114 = 114 / 1000
所以圖片轉(zhuǎn)換公式可表示成：Y = （299 * R + 587 * G + 114 * B）/ 1000
即轉(zhuǎn)換圖片的程序變?yōu)椋?/p>
void convert_rgb_image(void)
{
int i = 0;
for(i = 0; i < IMGSIZE; i++)
{
uint8_t r = in[i].r;
uint8_t g = in[i].g;
uint8_t b = in[i].b;
double temp_out = (299 * r + 587 * g + 114 * b) / 1000;
out[i] = temp_out;
}
}
再次編譯生成兩個平臺的應(yīng)用程序運(yùn)行，發(fā)現(xiàn)：
A、在PC上運(yùn)行的時間為2秒
B、在嵌入式開發(fā)板上運(yùn)行的時間為45秒
第二次優(yōu)化
優(yōu)化原則：
處理器在進(jìn)行除法運(yùn)算時，處理速度比較慢，去除除法操作
將公式Y = （299 * R + 587 * G + 114 * B）/ 1000的RGB的系數(shù)優(yōu)化如下：
R的系數(shù)：0.299 = 299 / 1000 = 1224 / 4096
G的系數(shù)：0.587 = 587 / 1000 = 2404 / 4096
B的系數(shù)：0.114 = 114 / 1000 = 467 / 4096
由于4096是2的倍數(shù)，除法可用效率更高的移位操作進(jìn)行優(yōu)化，所以圖片轉(zhuǎn)換公式為：
Y = (1224 * R + 2404 * G + 467 * G) >> 12
所以圖片轉(zhuǎn)換程序為：
void convert_rgb_image(void)
{
int i = 0;
for(i = 0; i < IMGSIZE; i++)
{
int r = 1224 * in[i].r;
int g = 2404 * in[i].g;
int b = 467 * in[i].b;
int temp_out = (r + g + b) >> 12;
out[i] = temp_out;
}
}
再次編譯運(yùn)行，發(fā)現(xiàn)在嵌入式開發(fā)板上運(yùn)行時間為30秒。
第三次優(yōu)化
優(yōu)化原則：
由于每一次轉(zhuǎn)換的RGB系數(shù)都要經(jīng)過計算得到，減少各個系數(shù)的計算次數(shù)。
優(yōu)化代碼如下：
#define RGB_SIZE (256)
int R[RGB_SIZE];
int G[RGB_SIZE];
int B[RGB_SIZE];
void rgb_table_init(void)
{
int i = 0;
for(i = 0; i < RGB_SIZE; i++)
{
R[i] = 1224 * i;
R[i] = R[i] >> 12;
G[i] = 2404 * i;
G[i] = G[i] >> 12;
B[i] = 467 * i;
B[i] = B[i] >> 12;
}
}
void convert_rgb_image(void)
{
int i = 0;
for(i = 0; i < IMGSIZE; i++)
{
int r = R[in[i].r];
int g = G[in[i].g];
int b = B[in[i].b];
int temp_out = r + g + b;
out[i] = temp_out;
}
}
再次編譯運(yùn)行，發(fā)現(xiàn)在嵌入式開發(fā)板上運(yùn)行時間為2秒。
第四次優(yōu)化
優(yōu)化原則：
32位的嵌入式CPU，都至少有2個算術(shù)邏輯單元(ALU)，讓2個ALU一起運(yùn)行
優(yōu)化代碼如下：
#define RGB_SIZE (256)
int R[RGB_SIZE];
int G[RGB_SIZE];
int B[RGB_SIZE];
void rgb_table_init(void)
{
int i = 0;
for(i = 0; i < RGB_SIZE; i++)
{
R[i] = 1224 * i;
R[i] = R[i] >> 12;
G[i] = 2404 * i;
G[i] = G[i] >> 12;
B[i] = 467 * i;
B[i] = B[i] >> 12;
}
}
void convert_rgb_image(void)
{
int i = 0;
for(i=0; i < IMGSIZE; i += 2)
{
/* 給第一個算術(shù)邏輯單元執(zhí)行 */
int r0 = R[in[i].r];
int g0 = G[in[i].g];
int b0 = B[in[i].b];
int temp_out_0 = r0 + g0 + b0;
out[i] = temp_out_0;
/* 給第二個算術(shù)邏輯單元執(zhí)行 */
int r1 = R[in[i+1].r];
int g1 = G[in[i+1].g];
int b1 = B[in[i+1].b];
int temp_out_1 = r1 + g1 + b1;
out[i+1] = temp_out_1;
/* 如果有更多算術(shù)邏輯單元，可以類似的處理代碼 */
}
}
再次編譯運(yùn)行，發(fā)現(xiàn)在嵌入式開發(fā)板上運(yùn)行時間為1秒。
第五次優(yōu)化
優(yōu)化原則：
由于各個數(shù)據(jù)類型大小不一樣，處理速度也不一樣，因此可以對數(shù)據(jù)類型優(yōu)化
優(yōu)化代碼如下：
#define RGB_SIZE (256)
uint16_t R[RGB_SIZE];
uint16_t G[RGB_SIZE];
uint16_t B[RGB_SIZE];
void rgb_table_init(void)
{
uint8_t i = 0;
for(i = 0; i <= RGB_SIZE; i++)
{
R[i] = 1224 * i;
R[i] = R[i] >> 12;
G[i] = 2404 * i;
G[i] = G[i] >> 12;
B[i] = 467 * i;
B[i] = B[i] >> 12;
}
}
inline void convert_rgb_image(void)
{
uint32_t i = 0;
for(i=0; i < IMGSIZE; i += 2)
{
/* 給第一個算術(shù)邏輯單元執(zhí)行 */
uint16_t r0 = R[in[i].r];
uint16_t g0 = G[in[i].g];
uint16_t b0 = B[in[i].b];
uint32_t temp_out_0 = r0 + g0 + b0;
out[i] = temp_out_0;
/* 給第二個算術(shù)邏輯單元執(zhí)行 */
uint16_t r1 = R[in[i+1].r];
uint16_t g1 = G[in[i+1].g];
uint16_t b1 = B[in[i+1].b];
uint32_t temp_out_1 = r1 + g1 + b1;
out[i+1] = temp_out_1;
}
}
將函數(shù)聲明為inline,這樣編譯器就會將其嵌入到母函數(shù)中，可以減少CPU調(diào)用子函數(shù)所產(chǎn)生的開銷。
再次編譯運(yùn)行，發(fā)現(xiàn)在嵌入式開發(fā)板上運(yùn)行時間為0.5秒。
后續(xù)可優(yōu)化的方向：
（1）將RGB查表的數(shù)據(jù)放入CPU的高速緩沖存儲器（Cache）中，從而提升程序運(yùn)行時的加載速度。
（2）代碼使用匯編語言進(jìn)行編寫
說明：本文來源于網(wǎng)絡(luò)，我僅僅是對文章進(jìn)行了一定的整理，刪繁就簡，如有侵權(quán)，請及時聯(lián)系我刪除！
