算法优化
1.选择一个更好的算法:
应该熟悉算法语言,知道各种算法的优缺点,一般很多计算机资料文本上有介绍,应该能够看得懂算法描述.
这里是一些明显可以通用的替换:
慢的算法 替换成
顺序查找 二分法查找或乱序查找
插入排序或冒泡排序 快速排序,合并排序,根(radix)排序
还要选择一种合适的数据结构,比如你在一堆随机存放
的数中使用了大量的插入和删除指令,那使用链表要快得多.如果你要做二
分法查找,那提前排下序非常重要.
2.写一些清晰,可读性好并且简单的代码
一个人容易看得懂的程序同样也容易被编译器读懂.一个大而复杂的表达式往往会把编译器脑袋都弄大,为了防止自己发疯,编译器往往放弃对这段代码的优化.但绝对不会向你报告,出于维护自己面子起见,东楼发现所有的编译器都只会向你报告它优化了多少,而决不会报告它干不了的有多少,东楼就亲眼见到一个瓜编译器因为一个表达式弄昏了头,把整个模块的优化都放弃了,回来居然还恬不知耻的报告优化非常顺利,整个儿一个报喜不报忧.
适当的时候尽量减小每个函数的代码量,不过也别走极端,别为了优化把一个函数写成10页纸的一堆函数,那编译器倒高兴了,可人发疯了.
3.透视你的程序
一个程序写出来,凭直觉就应该感觉出哪些地方快,哪些地方慢,一般说来,最快的运算就是分配一块内存,给指针赋值,还有就是两个整数的加法运算,别的都有点慢,最慢的就要数打开文件啦,打开新的进程啦,读写一大块内存啦,寻找啦,排序啦等等,别看这帮虾子指令都只要几个微秒,可成百上千的杀将过来,东楼可受不了.一定不能让这帮虾子进循环,干了它.
这是经常犯的一个错误:
if (x != 0) x = 0;
程序的原意是当x等于0时,节约时间不执行赋值操作,可你别忘了,赋值语句才是最快的,那还不如直接写成下面的语句更来劲.
x = 0;
还有就是一些神勇的大虾,非得等到编译器把代码输出成汇编语言级然后拿着计算器一行行加汇编指令的个数和周期数,才算优化完成了,不过可别忘了,最后一次优化不是obj代码级的,而是由link程序完成的,这没多大用.
4.理解你的编译程序选项
许多编译程序有几级优化选项,注意使用最优化的一项,特别注意gcc,优化选项非常多,小心使用,别弄得适得其反.通常情况下一旦选用最高级优化,编译程序会近乎病态地追求代码优化,精简指令,(如DJGPP的-O3),但少数情况下,这会影响程序的正确性,这是你只有改自己的程序啦.不过也有这种情况,就是一些参数会影响优化的程序,但是不会影响普通程序,这时只有具体情况具体
分析了.
5.内联(内嵌)
gcc(使用-finline-functions参数),还有一些别的编译器可以在最高级优化中内联一些小的函数.K&C编译器则只有在库函数是用汇编写成的时候才内联,C++编译器普遍支持内联函数.不过把C函数写成宏也能达到加速的作用,不过必须是在程序完全除错之后,因为绝大多数除错程序不支持宏除错.
宏内联的例子:
旧代码:
int foo(a, b)
{
a = a - b;
b++;
a = a * b;
return a;
}
新代码:
#define foo(a, b) (((a)-(b)) * ((b)+1))
注意最外层括号是必须的,因为当宏在表达式中展开时,你不知道表达式里还有没有比乘法级别更高的运算.
一些警告:
1.无限制地使用宏可以使代码爆炸,程序会很快消耗完你所有的资源,包 括物理内存,最后系统要么崩溃,要么把你的代码放到虚拟内存(磁盘上)中去,那你再怎么优化也没用了
2.C的宏每次调用都要对参数赋值,如果参数很多很复杂,那光赋值就要消耗大量的CPU时间,效果还不如不用宏
3.因为宏允许包含很复杂的表达式,所以编译程序会非常辛苦,为了使自己不至于完全发疯,一般编译程序对宏能包含的字符数都有一个限制,注意别犯规.
4.一旦用了宏,prof程序也跟着糊涂起来了,这是它说的话可信度可不高
6.循环展开
这是经典的速度优化,但许多编译程序(如gcc -funroll-loops)能自动完成这个事,所以现在你自己来优化这个显得效果不明显.(这里说一句,云风工作室的云风朋友曾来信和东楼专门探讨过这个问题,他根据自己在DJGPP的经验认定循环展开无效,东楼猜测可能就是因为gcc在编译时自动进行了展开,所以手工展开已经没多大效果了.但这个方法总是对的).
旧代码:
for (i = 0; i < 100; i++)
{
do_stuff(i);
}
新代码:
for (i = 0; i < 100; )
{
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
do_stuff(i); i++;
}
可以看出,新代码里比较指令由100次降低为10次,循环时间节约了90%.
不过注意:对于中间变量或结果被更改的循环,编译程序往往拒绝展开,(怕担责任呗),这时候就需要你自己来做展开工作了.
还有一点请注意,在有内部指令cache的CPU上(如MMX芯片),因为循环展开的代码很大,往往cache溢出,这时展开的代码会频繁地在CPU 的cache和内存之间调来调去,又因为cache速度很高,所以此时循环展开反而会变慢.还有就是循环展开会影响矢量运算优化.
7.循环嵌套
把相关循环放到一个循环里,也会加快速度.
旧
代码:
for (i = 0; i < MAX; i++) /* initialize 2d array to 0's */
for (j = 0; j < MAX; j++)
a[i][j] = 0.0;
for (i = 0; i < MAX; i++) /* put 1's along the diagonal */
a[i][i] = 1.0;
新代码:
for (i = 0; i < MAX; i++) /* initialize 2d array to 0's */
{
for (j = 0; j < MAX; j++)
a[i][j] = 0.0;
a[i][i] = 1.0; /* put 1's along the diagonal */
}
8.循环转置
有些机器对JNZ(为0转移)有特别的指令处理,速度非常快,如果你的循环对方向不敏感,可以由大向小循环
旧代码:
for (i = 1; i <= MAX; i++)
{
...
}
新代码:
i = MAX+1;
while (--i)
{
...
}
不过千万注意,如果指针操作使用了i值,这种方法可能引起指针索引超界的严重错误(i = MAX+1;).当然你可以通过对i做加减运算来纠正,但是这样加速的作用就没有了除非类似于以下情况
旧代码:
char a[MAX+5];
for (i = 1; i <= MAX; i++)
{
*(a+i+5)=0;
}
新代码:
i = MAX+1;
while (--i)
{
*(a+i+4)=0;
}
9.减小运算强度
采用运算量更小的表达式替换原来的表达式,下面是一个经典例子:
旧代码:
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);
}
10.循环不变计算
对于一些不需要循环变量参加运算的计算任务可以把它们放到循环外面,现在许多编译器还是能自己干这件事,不过对于中间使用了变量的算式它们就不敢动了,所以很多情况下你还得自己干.那位大哥说了,不就是把没必要的表达式拿出来嘛,这话咱可得商量商量,这里的计算任务可不是仅仅表达式那么简单,什么调用函数啦,指针运算啦,数组访问啦,总之,凡是你相让计算机干的事都算计算任务.对于那些在循环中调用的函数,也不能让它们轻松了,把它扒光了看看,凡是没必要执行多次的操作通通提出来,放到一个init函数里,循环前调用.另外尽量减少喂食次数,没必要的话尽量不给它传参,需要循环变量的话让它自己建立一个静态循环变量自己累加,速度会快一点.
还有就是结构体访问,东楼的经验,凡是在循环里对一个结构体的两个以上的元素执行了访问,就有必要建立中间变量了(结构这样,那C++的对象呢?想想看),看下面的例子:
旧代码:
total =
a->b->c[4]->aardvark +
a->b->c[4]->baboon +
a->b->c[4]->cheetah +
a->b->c[4]->dog;
新
代码:
struct animals * temp = a->b->c[4];
total =
temp->aardvark +
temp->baboon +
temp->cheetah +
temp->dog;
一些老的C语言编译器不做聚合优化,而符合ANSI规范的新的编译器可以自动完成这个优化,看例子:
float a, b, c, d, f, g;
...
a = b / c * d;
f = b * g / c;
这种写法当然要得,但是没有优化
float a, b, c, d, f, g;
...
a = b / c * d;
f = b / c * g;
如果这么写的话,一个符合ANSI规范的新的编译器可以只计算b/c一次,然后将结果代入第二个式子,节约了一次除法运算.