程序优化介绍(c语言).

《程序优化介绍(c语言).》由会员分享，可在线阅读，更多相关《程序优化介绍(c语言).（36页珍藏版）》请在金锄头文库上搜索。

1、程序优化介绍（c语言） 培训的对象 nC语言熟手 n对优化感兴趣的 n想培训又不愿看文档，想有人讲给你听的。 n想成为编程狂人的 n想成为性能狂人的 n相信优化是不必要的，或者认为优化应该交由 编译器完成的 为什么要程序优化 n一个优秀程序员的必要素养。 n编译器还不代替人工操作的程序优化 。 n低层程序需要优化。 n同样的DSP能跑出更多的功能。 n n？ n！优化还需要理由吗 程序优化的三个级别 n第一级：代码级 n第二级：算法级 n第三级：表驱动状态机 代码级优化 n代码调整是一种局部的思维方式；基本上不触及算法层级；它面 向的是代码，而不是问题； n语句调整，用汇编重写、指令调整、换一

2、种语言实现、换一个编 译器、循环展开、参数传递优化等都属于这一级； n这个级别的优化需要掌握大量的小的优化技巧和知识，需要不断 的积累； n简单的语句调整、公共表达式提取、废代码删除等当前的很多编 译器也能做到了，但也需要了解一些编译器的优化能力使自己的 代码配合编译器做好优化； n用汇编重写并不是简单把高级语言改写为汇编实现，那样写的汇 编很可能没有当今的编译器产生的代码好，所以如果决定用汇编 实现，那就应该按照汇编的角度来规划自己的实现，适当的参考 编译器生成的汇编码也是可取的(特别是新手，我也一样)；在某些 领域，使用CPU的新特性和新的指令集等将产生巨大的性能收益 ，这些地方经常采用汇

3、编来实现。 算法级优化 n算法级优化强调的重点是针对问题的算法；即选择和 构造适合于问题的算法；（冒泡排序还是快排的选择 问题是这一级早就应该完成的）很多经典算法都对问 题作了一些假设(包括我们当前已经完成的算法实现) ，而在面对实际问题时“新的视角”提示我们应该重新 检视这些假设，并尝试不同的思考问题的角度，寻求 适合于问题的新算法； n发掘问题的本来意义，从不同的角度思考面对的问题 ，使用适合于问题的的算法; 尝试打破一些规则，发 掘和怀疑自己的某些假定，恢复问题的本来面目； 表驱动状态机 n将问题抽象为另一种等价的数学模型或假想机器模型 ，比如构造出某种表驱动状态机；这一级其实是第二 级

4、的延伸，只是产生的效果更加明显，但它有其本身 的特点（任何算法和优化活动都可以看作是他的投影 ）；这一级一般可以产生无与伦比的快速程序， n 要达到这一级需要大量修炼的;并且思考时必须放 弃很多已有的概念或者这些概念不再重要，比如：变 量、指针、空间、函数、对象等，剩下的只应该是那 个表驱动状态机； 我想把这种境界描述为：空寂中， 一些输入驱动着一个带有状态的机器按设定好的最短 路线运转着；除此之外have nothing; 既：把解决一个 问题的算法看作一个机器，它有一些可变的状态、有 一些记忆、有一些按状态运行的规则，然后一些输入 驱动这个机器运转；这就是第三级要求的思考优化问 题的切入点

5、，也就是寻找一部机器，使它运行经过的 路径最短(可能是速度也可能是空间等等) 第一级优化 n要掌握一级优化，是很多人经过努力都能够达 到的层次，需要的是不断的积累各方面的技巧 就行了(虽然很繁琐)，写出的代码可以称为“好 的代码”； n手中无剑、心中有剑； 第二级优化 n要掌握二级优化，需要的是对问题的理解能力 和一些创造力，能够针对问题产生新的见解； 写出的代码可以称为“优秀的代码”； n手中有剑；心中亦有剑 ； 第三级优化 n要掌握三级优化，必须具有丰富的想象力和创 造力，需要大量的修炼和对问题本质的苦苦思 索；写出的代码可以称为“非凡的代码”； n手中无剑、心中亦无剑； 无级 n能够将这

6、三个层级的优化熟练运用(我想把这 种境界称作“综级优化”)的人必须掌握比别人更 多的知识、了解更多的知识领域、了解最底层 的技术和最高层的抽象；并且还要求有丰富的 实践经验、想象能力和创造能力; 这些都是不 可或缺的； n就是不杀，就是和平 警示1 n警示：不是所有的代码(项目)都需要优化 n警示：不是每个人都要去做优化工作 n警示：优化是有方向和侧重点的，不只是单纯 的速度 n警示：首先是正确，然后才有优化 n警示：简洁的代码，很多时候就是最好的代码 警示2 n警示：优化不是一种理论，它是一种实践 n警示：充分优化的笨拙算法实现始终比不上一个更好 的算法的普通实现,即优化首先是设计的优化 n

7、警示：代码优化是门黑色艺术，代码的优化永无止境 n警示：无论是谁，他的资源也不是无限的，代码优化 要避免过犹不及 n警示：如果确信不需要优化，那根本不进行优化，就 是最好的优化！ 多使用32位的数据类型 n编译器有很多种，但它们都包含的典型的32位 类型是：int，signed，signed int，unsigned ，unsigned int，long，signed long，long int ，signed long int，unsigned long，unsigned long int。尽量使用有符号32位的数据类型， 因为它们比16位的数据甚至8位的数据更有效 率。 使用位操作。减少除

8、法和取模的运算 n使用位操作。减少除法和 取模的运算 int I,J,k; I = 257 / 8; J = 456 % 32; K = 257 % 8 写成 int I,J,k; I = 257 3; J = 456 - (456 4 4); K= 257 在上面好像程序麻烦了好多， 但是，仔细查看产生的汇编代 码就会明白，方法1调用了基本 的取模函数和除法函数，既有 函数调用，还有很多汇编代码 和寄存器参与运算；而方法2则 仅仅是几句相关的汇编，代码 更简洁，效率更高。当然，由 于编译器的不同，可能效率的 差距不大，但是，以目前的MS C ,ARM C 来看，效率的差距 还是不小。 避免不

9、必要的整数除法 n整数除法是整数运算中最慢的，所以应该尽可 能避免。一种可能减少整数除法的地方是连除 ，这里除法可以由乘法代替。这个替换的副作 用是有可能在算乘积时会溢出，所以只能在一 定范围的除法中使用。 while (1) V.S. for (;) n在编程中，我们常常需要用到无限循环，常用的两种 方法是while (1) 和 for (;)。这两种方法效果完全一样 ，但那一种更好呢？然我们看看它们编译后的代码： 编译前 while (1); for (;); 编译后 mov eax,1 jmp foo+23h test eax,eax je foo+23h jmp foo+18h 一目了

10、然，for (;)指令少，不占用寄存器，而且没有判 断跳转，比while (1)好。 使用数组型代替指针型 n 使用指针会使编译器很难优化它。因为缺乏有效的 指针代码优化的方法，编译器总是假设指针可以访问 内存的任意地方，包括分配给其他变量的储存空间。 所以为了编译器产生优化得更好的代码，要避免在不 必要的地方使用指针。一个典型的例子是访问存放在 数组中的数据。C+ 允许使用操作符 或指针来访问 数组，使用数组型代码会让优化器减少产生不安全代 码的可能性。比如，x0 和x2 不可能是同一个内存 地址，但 *p 和 *q 可能。强烈建议使用数组型，因为 这样可能会有意料之外的性能提升。 把频繁使

11、用的指针型参数拷贝到本地 变量 n避免在函数中频繁使用指针型参数指向的值。因为编 译器不知道指针之间是否存在冲突，所以指针型参数 往往不能被编译器优化。这样是数据不能被存放在寄 存器中，而且明显地占用了内存带宽。注意，很多编 译器有“假设不冲突”优化开关（在VC里必须手动添加 编译器命令行/Oa或/Ow），这允许编译器假设两个 不同的指针总是有不同的内容，这样就不用把指针型 参数保存到本地变量。否则，请在函数一开始把指针 指向的数据保存到本地变量。如果需要的话，在函数 结束前拷贝回去。 尽可能使用常量(const) n尽可能使用常量(const)。C+ 标准规定，如 果一个const声明的对象

12、的地址不被获取，允 许编译器不对它分配储存空间。这样可以使代 码更有效率，而且可以生成更好的代码。 把本地函数声明为静态的(static) n如果一个函数在实现它的文件外未被使用的话 ，把它声明为静态的(static)以强制使用内部连 接。否则，默认的情况下会把函数定义为外部 连接。这样可能会影响某些编译器的优化 比如，自动内联。 IO缓冲 n如果有文件读写的话，那么对文件的访问将是影响程 序运行速度的一大因素。提高文件访问速度的主要办 法有两个：一是采用内存映射文件，二是使用内存缓 冲。下面是一组测试数据（见UNIX环境高级编程 3.9节），显示了用18种不同的缓存长度，读1 468 802

13、字节文件所得到的结果。 可见，一般的当内存缓冲区大小为8192的时候，性 能就已经是最佳的了，这也就是为什么在H.263等图像 编码程序中，缓冲区大小为8192的原因（有的时候也 取2048大小）。使用内存缓冲区方法的好处主要是便 于移植，占用内存少，便于硬件实现等。 字符串的赋值 n计算机程序中最大的矛盾是空间和时间的矛盾 ，那么，从这个角度出发逆向思维来考虑程序 的效率问题，我们就有了解决问题的方法-以 空间换时间。 例如：字符串的赋值。 方法A：通常的办法： #define LEN 32 char string1 LEN; memset (string1,0,LEN); strcpy (

14、string1,This is a example!） n方法B：const char string2LEN =This is a example!; char * cp; cp = string2 ; 从上面的例子可以看出，A和B的效率是不能比的。 在同样的存储空间下，B直接使用指针就可以操作了 ，而A需要调用两个字符函数才能完成。B的缺点在 于灵活性没有A好。在需要频繁更改一个字符串内容 的时候，A具有更好的灵活性；如果采用方法B，则 需要预存许多字符串，虽然占用了大量的内存，但是 获得了程序执行的高效率。 字符串的赋值 n将函数改为宏函数，宏函数占用了大量的空间 ，而函数占用了时间。大家

15、要知道的是，函数 调用是要使用系统的栈来保存数据的，如果编 译器里有栈检查选项，一般在函数的头会嵌入 一些汇编语句对当前栈进行检查；同时，CPU 也要在函数调用时保存和恢复当前的现场，进 行压栈和弹栈操作，所以，函数调用需要一些 CPU时间。而宏函数不存在这个问题。宏函数 仅仅作为预先写好的代码嵌入到当前程序，不 会产生函数调用，所以仅仅是占用了空间，在 频繁调用同一个宏函数的时候，该现象尤其突 出。 将函数改为宏函数 查表1 n目前程序加速的常用算法一个大方面就是利用查表来 避免计算（比如在jpg有huffman码表，在YUV到RGB 变换也有变换表）这样原来的复杂计算现在仅仅查表 就可以了，虽然浪费了内存，不过速度显著提升，还 是很划算的。在数据库查询里面也有这样的思想，将 热点存储起来以加速查询。 现在介绍一个简单的例子 ：比如，在程序中要经常计算1000到2000的阶乘， 那么我们可以使用一个数组a1000先把这些值算好 ，保留下来，以后要计算1200！的时候，查表a1200 -1000就可以了。 查表2 n有一个程序是这样的 switch ( queue ) case 0 : letter = W