同样的事情,使用不一样的方法去完成,虽然最终的结果一样,但是完成的效率往往不一样。假如你离家一千公里路程,过年要回家过春节,你可以走路回家,可以骑自行车回家,可以骑摩托车回家,可以坐汽车回家,可以坐火车回家,当然也可以坐飞机回家,虽然最终目的都是到达一千公里的家乡,但是乘坐不同的交通工具,回家的时间各异。在程序中,这些不同的“交通工具”我们称之为算法。
代码的运算速度取决于以下几个方面:
(2)处理器的总线带宽;
(3)程序代码的设计编写;
(4)程序中所使用算法本身的复杂度,比如MPEG比JPEG复杂,JPEG比BMP图片的编码复杂。
比如在一个图像转换的项目中,需要将RGB格式的彩色图像先转换成黑白图像。图像转换的公式如下:
Y = 0.299 * R + 0.587 * G + 0.114 * B;
图像尺寸640*480*24 bits,RGB图像已经按照RGBRGB顺序排列的格式,放在内存里面了。
例如,将这个喷火的战斗机引擎,转换为右边的黑白图片。
图片输入和输出的定义如下:
#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]; /* 未转换的图片数据 */ uint8_t out[IMGSIZE]; /* 转换后的图片数据 */
优化原则:
图像是一个二维数组,我用一个一维数组来存储。编译器处理一维数组的效率要高于二维数组。
第一个程序:
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和嵌入式开发板上面运行。
A、在PC上,由于存在硬件浮点处理器,CPU频率也够高,运行时间为20秒。
B、在嵌入式开发板 ,主频时钟比较低,也没有浮点处理器,浮点操作被编译器分解成了整数运算,运行时间为120秒左右。
第一次优化
优化原则:
去掉浮点数运算。
在公式Y = 0.299 * R + 0.587 * G + 0.114 * B中,由于RGB的取值范围都是0~255,只是系数都是浮点数,将RGB的系数转换为:
R的系数:0.299 = 299 / 1000
G的系数:0.587 = 587 / 1000
B的系数:0.114 = 114 / 1000
所以图片转换公式可表示成:Y = (299 * R + 587 * G + 114 * B)/ 1000
即转换图片的程序变为:
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; } }
再次编译生成两个平台的应用程序运行,发现:
A、在PC上运行的时间为2秒
B、在嵌入式开发板上运行的时间为45秒
第二次优化
优化原则:
处理器在进行除法运算时,处理速度比较慢,去除除法操作
将公式Y = (299 * R + 587 * G + 114 * B)/ 1000的RGB的系数优化如下:
R的系数:0.299 = 299 / 1000 = 1224 / 4096
G的系数:0.587 = 587 / 1000 = 2404 / 4096
B的系数:0.114 = 114 / 1000 = 467 / 4096
由于4096是2的倍数,除法可用效率更高的移位操作进行优化,所以图片转换公式为:
Y = (1224 * R + 2404 * G + 467 * G) >> 12
所以图片转换程序为:
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; } }
再次编译运行,发现在嵌入式开发板上运行时间为30秒。
第三次优化
优化原则:
由于每一次转换的RGB系数都要经过计算得到,减少各个系数的计算次数。
优化代码如下:
#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; } }
再次编译运行,发现在嵌入式开发板上运行时间为2秒。
第四次优化
优化原则:
32位的嵌入式CPU,都至少有2个算术逻辑单元(ALU),让2个ALU一起运行
优化代码如下:
#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) { /* 给第一个算术逻辑单元执行 */ 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; /* 给第二个算术逻辑单元执行 */ 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; /* 如果有更多算术逻辑单元,可以类似的处理代码 */ } }
再次编译运行,发现在嵌入式开发板上运行时间为1秒。
第五次优化
优化原则:
由于各个数据类型大小不一样,处理速度也不一样,因此可以对数据类型优化
优化代码如下:
#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) { /* 给第一个算术逻辑单元执行 */ 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; /* 给第二个算术逻辑单元执行 */ 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; } }
将函数声明为inline,这样编译器就会将其嵌入到母函数中,可以减少CPU调用子函数所产生的开销。
再次编译运行,发现在嵌入式开发板上运行时间为0.5秒。
后续可优化的方向:
(1)将RGB查表的数据放入CPU的高速缓冲存储器(Cache)中,从而提升程序运行时的加载速度。
(2)代码使用汇编语言进行编写
说明:本文来源于网络,我仅仅是对文章进行了一定的整理,删繁就简,如有侵权,请及时联系我删除!