|
C代码优化-让你的软件飞起来
2007-09-27 09:40 来源: 作者: 网友评论 0 条 浏览次数 37
速度取决于算法
同样的事情,方法不一样,效果也不一样。比如,汽车引擎,可以让你的速度超越马车,却无法超越音速;涡轮引擎,可以轻松超越音障,却无法飞出地球;如果有火箭发动机,就可以到达火星。代码的运算速度取决于以下几个方面:0 算法本身的复杂度,比如MPEG比JPEG复杂,JPEG比BMP图片的编码复杂。1 CPU自身的速度和设计架构 2 CPU的总线带宽 3 您自己的代码的写法
我们一个图象模式识别的项目,需要将RGB格式的彩色图像先转换成黑白图像。图像转换的公式如下:
Y = 0.299 * R + 0.587 * G + 0.114 * B;
图像尺寸640*480*24bit,RGB图像已经按照RGBRGB顺序排列的格
式,放在内存里面了。
例如,将这个喷火的战斗机引擎,转换为右边的黑白图片
我已经悄悄的完成了第一个优化
以下是输入和输出的定义:
#define XSIZE 640
#define YSIZE 480
#define IMGSIZE XSIZE*YSIZE
Typedef struct RGB
{
unsigned char R;
unsigned char G;
unsigned char B;
}RGB;
struct RGB in[IMGSIZE] //需要计算的原始数据
Unsigned char out[IMGSIZE] //计算后的结果
看得出来优化在
哪里吗?
我已经悄悄的完成了第一个优化
#define XSIZE 640
#define YSIZE 480
#define IMGSIZE XSIZE*YSIZE
Typedef struct RGB
{
unsigned char R;
unsigned char G;
unsigned char B;
}RGB;
struct RGB in[IMGSIZE] //需要计算的原始数据
Unsigned char out[IMGSIZE] //计算后的结果
优化原则:
图像是一个2D数组,我用一个1维数组来存储。
编译器处理1维数组的效率要高过2维数组
先写一个代码
Y = 0.299 * R + 0.587 * G + 0.114 * B;
Void calc_lum()
{int I;
for(i=0;i<IMGSIZE;i++)
{double r,g,b,y;
unsigned char yy;
r=in.r; g=in.g; b=in.b;
y=0.299*r+0.587*g+0.114*b;
yy=y; out=yy;
}
}
这大概是能想得出来的最简单的写法了,实在看不出有什么毛病,好
了,编译一下跑一跑吧。
第一次试跑Void calc_lum()
{int I;
for(i=0;i<IMGSIZE;i++)
{double r,g,b,y;
unsigned char yy;
r=in.r; g=in.g; b=in.b;
y=0.299*r+0.587*g+0.114*b;
yy=y; out=yy;
}
}
这个代码分别用VC6.0和GCC编译,生成2个版本,分别在PC上和
我的embedded system上面跑。
速度多少?说出来吓死你!
第一次试跑的成绩
在PC上,由于存在硬件浮点处理器,CPU
频率也够高,计算速度为20秒
我的embedded system ,没有以上2个
优势,浮点操作被编译器分解成了整数运
算,运算速度为120秒左右
这只是一副图像的运算速度!!
去掉浮点运算
上面这个代码还没有跑,我已经知道会很慢了,因为这其中有大量
的浮点运算。只要能不用浮点运算,一定能快很多。
Y = 0.299 * R + 0.587 * G + 0.114 * B;
那这个公式怎么能用定点的整数运算替代呢?
0.299 * R可以如何化简?
Y = 0.299 * R + 0.587 * G + 0.114 * B;
Y=D+E+F;
D=0.299*R;
E=0.587*G;
F=0.114*B;
我们就先简化算式D吧!
RGB的取值范围都是0~255,都是整数,只是这个系数比较麻烦,
不过这个系数可以表示为:
0.299=299/1000
所以D=(R*299)/1000
Y=(R*299)/1000+(G*587)/1000+(B*114)/1000
再简化为:
Y=(R*299+G*587+B*114)/1000
这一下,能快多少呢?
化简后的成绩
Embedded system
上的速度45秒
PC上的速度2秒
0.299 * R进一步化简
Y=(R*299+G*587+B*114)/1000
这个式子好像还有点复杂,可以再砍掉一个除法运算。
前面的算式D可以这样写:
0.299=299/1000=1224/4096
所以D=(R*1224)/4096
Y=(R*1224)/1000+(G*2404)/4096+(B*467)/4096
再简化为:
Y=(R*1224+G*2404+B*467)/4096
这里的/4096除法,因为它是2的N次方,所以可以用移位操作替
代,往右移位12bit就是把某个数除以4096了
Y = 0.299 * R + 0.587 * G + 0.114 * B
Y=(R*1224+G*2404+B*467)/4096
Void calc_lum()
{int I;
for(i=0;i<IMGSIZE;i++)
{int r,g,b,y;
r=1224*in.r; g=2404*in.g; b=467*in.b;
y=r+g+b;
y=y>>12; //这里去掉了除法运算
out=y;
}
}
这个代码编译后,又快了20%
0.299 * R进一步化简
还是太慢!
虽然快了不少,还是太慢了一些,
20秒处理一幅图像,地球人都不能
接受!
但是目前这个式子好像优化到极限
了,要想突破音障,只能拆掉活塞
发动机,安装蜗轮引擎!
仔细端详一下这个式子!
仔细端详一下这个式子!
RGB的取值有文章可做,RGB的取值永远都大于等于0,小于等于
255,我们能不能将D,E,F都预先计算好呢?然后用查表算法计
算呢?
我们使用3个数组分别存放DEF的256种可能的取值,然后。。。
Y = 0.299 * R + 0.587 * G + 0.114 * B;
Y=D+E+F;
D=0.299*R;
E=0.587*G;
F=0.114*B;
查表数组初始化
Int D[256],E[256],F[256]; //查表数组
Void table_init()
{int I;
for(i=0;i<256;i++)
{D=i*1224; D=D>>12;
E=i*2404; E=E>>12;
F=i*467; F=F>>12;
}
}
Y = 0.299 * R + 0.587 * G + 0.114 * B;
Y=D+E+F;
D=0.299*R;
E=0.587*G;
F=0.114*B;
使用查表数组
Y = 0.299 * R + 0.587 * G + 0.114 * B;
Y=D+E+F;
D=0.299*R;
E=0.587*G;
F=0.114*B;
Void calc_lum()
{int I;
for(i=0;i<IMGSIZE;i++)
{int r,g,b,y;
r=D[in.r]; g=E[in.g]; b=F[in.b]; //查表
y=r+g+b;
out=y;
}
}
突破音障!
这一次的成绩把我吓出一身冷汗,执行时间居然从30秒一下提高到
了2秒!在PC上测试这段代码,眼皮还没眨一下,代码就执行完了。
一下提高15倍,爽不爽?
还能再
快吗? 120
秒
45秒
30秒
2秒
下一
程,几
秒?
很多embedded sysytem 的32bitCPU,都至少有2个ALU,能不
能让2个ALU都跑起来?
Void calc_lum()
{int I;
for(i=0;i<IMGSIZE;i++)
{int r,g,b,y;
r=D[in.r]; g=E[in.g]; b=F[in.b]; //查表
y=r+g+b;
out=y;
}
} Void calc_lum()
{int I;
for(i=0;i<IMGSIZE;i+=2) //一次并行处理2个数据
{int r,g,b,y, r1,g1,b1,y1;
r=D[in.r]; g=E[in.g]; b=F[in.b]; //查表
y=r+g+b;
out=y;
r1=D[in[i+1].r]; g1=E[in[i+1].g]; b1=F[in[i+1].b]; //查表
y1=r1+g1+b1;
out[i+1]=y1;
}
}
踩足油门,向2马赫进军!
并行计算
2个ALU处理的数据不能有数据依赖,也就是说:
某个ALU的输入条件不能是别的ALU的输出,这样
才可以并行
给第一个ALU执行给第二个ALU执行
一次并行处理2组数据
所以这里一次加2
Void calc_lum()
{int I;
for(i=0;i<IMGSIZE;i+=2) //一次并行处理2个数据
{int r,g,b,y, r1,g1,b1,y1;
r=D[in.r]; g=E[in.g]; b=F[in.b]; //查表
y=r+g+b;
out=y;
r1=D[in[i+1].r]; g1=E[in[i+1].g]; b1=F[in[i+1].b]; //查表
y1=r1+g1+b1;
out[i+1]=y1;
}
}
这一次的成绩是:
加足燃料,进军3马赫!
Int D[256],E[256],F[256]; //查表数组
Void table_init()
{int I;
for(i=0;i<256;i++)
{D=i*1224; D=D>>12;
E=i*2404; E=E>>12;
F=i*467; F=F>>12;
}
}
看看这个代码,
到这里,似乎已经足够快了,但是我们反复实验,发现,还有办法再快!
可以将
Int D[256],E[256],F[256]; //查表数组
更改为:
Unsigned short D[256],E[256],F[256]; //查表数组
这是因为编译器处理int类型和处理unsigned
short类型的效率不一样
再改动一下
Unsigned short D[256],E[256],F[256]; //查表数组
Inline Void calc_lum()
{int I;
for(i=0;i<IMGSIZE;i+=2) //一次并行处理2个数据
{int r,g,b,y, r1,g1,b1,y1;
r=D[in.r]; g=E[in.g]; b=F[in.b]; //查表
y=r+g+b;
out=y;
r1=D[in[i+1].r]; g1=E[in[i+1].g]; b1=F[in[i+1].b]; //查表
y1=r1+g1+b1;
out[i+1]=y1;
}
}
将函数声明为inline,这样编译器就会将其
嵌入到母函数中,可以减少CPU调用子函
数所产生的开销
这2个小小的改进带来的效益!
现在,我们已经达到了客户的要求!
其实,我们还可以飞出地球的!
如果加上以下措施,应该还可以更快:
•把查表的数据放置在CPU的高速数据CACHE
里面
•把函数calc_lum()用汇编语言来写
其实,CPU的潜力是很大的
•不要抱怨你的CPU,记住一句话:“只要功率足
够,砖头都能飞!”
•同样的需求,写法不一样,速度可以从120秒
变化为0.5秒,说明CPU的潜能是很大的!看你
如何去挖掘。 |
阿莫论坛20周年了!感谢大家的支持与爱护!!
曾经有一段真挚的爱情摆在我的面前,我没有珍惜,现在想起来,还好我没有珍惜……
|