优化---C程序员之终极标靶

一个用户往往把他的生命中大部分时间用来等待计算机输出结果,为了减
少这个等待时间,用户不得不采购更快的计算机,增加内存或更换整个网络
.开发者有责任尽量避免他的程序耗费昂贵的资源,为用户挽回宝贵的时间
和金钱.--原作者
---------------------------------------------------------------------------
介绍:

最简单的优化方法是借助prof工具判断程序的瓶颈在哪里,你必须判断出
程序的那些部分消耗了大量资源.

一旦你判断出瓶颈(比如说执行上万次的循环),你所做的第一件事就是重
新设计程序,减低循环次数.当然,现在绝大多数优化编译器可以做到这一
点,(不过最好还是自己来--东楼),但是记住,当以下情况出现时,优化是
在浪费时间:
1)程序只写了一部分
2)程序还没有测试通过
3)看起来已经足够快了

还要注意的就是判断程序的用途,如果仅仅为了得到一份报告而写的仅运
行一次的程序,用户往往在午餐前运行程序,这时,程序只要在他们回来之
前运行完就可以了,如果程序调用其他的程序,而且其他程序都比较慢,那
么优不优化效果都差不多,但是,如果是GUI图形用户界面程序(比如鼠标光
标显示程序),那么一点点的延迟都会遭到用户的投诉

完成优化后,带上所有的优化命令编译,然后用你实际使用的数据测试它,
如果做不到这一点,请小心选择你的测试数据,程序员多半倾向于按照程序
的要求给输入数据,但用户可不这么干.

如果你已经完成了所有优化,但是程序仍然看起来不快,注意一下你的操作
系统,很多多任务操作系统按时间片来划分用户资源,如果给你的资源太少,
那和你的系统管理员联系吧.

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一次,然后将结
果代入第二个式子,节约了一次除法运算.

11.公用代码块

一些公用处理模块,为了满足各种不同的调用需要,往往在内部采用了大量的
if-then-else结构,这样很不好,判断语句如果太复杂,会消耗大量的时间的,应
该尽量减少公用代码块的使用.(任何情况下,空间优化和时间优化都是对立的--
东楼).
当然,如果仅仅是一个(3==x)之类的简单判断,适当使用一下,也还是允许的.记
住,优化永远是追求一种平衡,而不是走极端.

12.采用递归

与LISP之类的语言不同,C语言一开始就病态地喜欢用重复代码循环,许多C程序
员(包括东楼)都是除非算法要求,坚决不用递归.事实上,C编译器们对优化递归
调用一点都不反感,相反,它们还很喜欢干这件事.只有在递归函数需要传递大量
参数,可能造成瓶颈的时候,才应该使用循环代码,其他时候,还是用递归好些.

13.查表(游戏程序员必修课)

一个聪明的游戏大虾,基本上不会在自己的主循环里搞什么运算工作,绝对是先
计算好了,再到循环里查表.(东楼每一次写游戏,基本上都有一大堆表格).看下
面的例子:

旧代码:
    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函数,在循环外临时生成表格.

14.变量

在最内层循环避免使用全局变量和静态变量,除非你能确定它在循环周期中不会
动态变化,大多数编译器们优化变量仅有置成寄存器变量一招,而对于动态变量,
它们干脆放弃对整个表达式的优化.

尽量避免把一个变量地址传递给另一个函数,虽然这个还很常用.C语言的编译器
们总是先假定每一个函数的变量都是内部变量,这是由它的机制决定的,在这种
情况下,它们的优化完成得最好,但是,一旦一个变量有可能被别的函数改变,这
帮兄弟就再也不敢把变量放到寄存器里了,严重影响速度.看例子:

a = b();
c(&d);

因为d的地址被c函数使用,有可能被改变,编译器不敢把它长时间的放在寄存器
里,一旦运行到c(&d),编译器就把它丢回内存,如果在循环里,会造成N次频繁的
在内存和寄存器之间读写d的动作,众所周知,CPU在系统总线上的读写速度可是
慢得可以.比如你的赛杨300,CPU主频300,总线速度最多66M,为了一个总线读,
CPU可能要等4-5个周期,得..得..得..想起来都打颤.