程序优化介绍(c语言)

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

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

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

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

5、很多人经过努力都能够达到的层次，需要的是不断的积累各方面的技巧就行了(虽然很繁琐)，写出的代码可以称为“好的代码”；n手中无剑、心中有剑；第二级优化n要掌握二级优化，需要的是对问题的理解能力和一些创造力，能够针对问题产生新的见解；写出的代码可以称为“优秀的代码”； n手中有剑；心中亦有剑 ；第三级优化n要掌握三级优化，必须具有丰富的想象力和创造力，需要大量的修炼和对问题本质的苦苦思索；写出的代码可以称为“非凡的代码”；n手中无剑、心中亦无剑；无级n能够将这三个层级的优化熟练运用(我想把这种境界称作“综级优化”)的人必须掌握比别人更多的知识、了解更多的知识领域、了解最底层的技术和最高层的抽象；并

6、且还要求有丰富的实践经验、想象能力和创造能力; 这些都是不可或缺的； n就是不杀，就是和平警示1n警示：不是所有的代码(项目)都需要优化 n警示：不是每个人都要去做优化工作 n警示：优化是有方向和侧重点的，不只是单纯的速度 n警示：首先是正确，然后才有优化 n警示：简洁的代码，很多时候就是最好的代码 警示2n警示：优化不是一种理论，它是一种实践 n警示：充分优化的笨拙算法实现始终比不上一个更好的算法的普通实现,即优化首先是设计的优化 n警示：代码优化是门黑色艺术，代码的优化永无止境 n警示：无论是谁，他的资源也不是无限的，代码优化要避免过犹不及 n警示：如果确信不需要优化，那根本不进行优化，就

7、是最好的优化！ 多使用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位的数据更有效率。使用位操作。减少除法和取模的运算n使用位操作。减少除法和取模的运算 int I,J,k;I = 257 / 8;J = 456 % 32; K = 257 % 8写成int I,J,k;I = 2

8、57 3;J = 456 - (456 4 4); K= 257 & 7; 在上面好像程序麻烦了好多，但是，仔细查看产生的汇编代码就会明白，方法1调用了基本的取模函数和除法函数，既有函数调用，还有很多汇编代码和寄存器参与运算；而方法2则仅仅是几句相关的汇编，代码更简洁，效率更高。当然，由于编译器的不同，可能效率的差距不大，但是，以目前的MS C ,ARM C 来看，效率的差距还是不小。避免不必要的整数除法n整数除法是整数运算中最慢的，所以应该尽可能避免。一种可能减少整数除法的地方是连除，这里除法可以由乘法代替。这个替换的副作用是有可能在算乘积时会溢出，所以只能在一定范围的除法中使用。

9、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 一目了然，for (;)指令少，不占用寄存器，而且没有判断跳转，比while (1)好。使用数组型代替指针型n 使用指针会使编译器很难优化它。因为缺乏有效的指针代码优化的方法，编译器总是假设指针可以访问内存的任意地方，包

10、括分配给其他变量的储存空间。所以为了编译器产生优化得更好的代码，要避免在不必要的地方使用指针。一个典型的例子是访问存放在数组中的数据。C+ 允许使用操作符 或指针来访问数组，使用数组型代码会让优化器减少产生不安全代码的可能性。比如，x0 和x2 不可能是同一个内存地址，但 *p 和 *q 可能。强烈建议使用数组型，因为这样可能会有意料之外的性能提升。 把频繁使用的指针型参数拷贝到本地变量n避免在函数中频繁使用指针型参数指向的值。因为编译器不知道指针之间是否存在冲突，所以指针型参数往往不能被编译器优化。这样是数据不能被存放在寄存器中，而且明显地占用了内存带宽。注意，很多编译器有“假设不冲突”优化

11、开关（在VC里必须手动添加编译器命令行/Oa或/Ow），这允许编译器假设两个不同的指针总是有不同的内容，这样就不用把指针型参数保存到本地变量。否则，请在函数一开始把指针指向的数据保存到本地变量。如果需要的话，在函数结束前拷贝回去。尽可能使用常量(const)n尽可能使用常量(const)。C+ 标准规定，如果一个const声明的对象的地址不被获取，允许编译器不对它分配储存空间。这样可以使代码更有效率，而且可以生成更好的代码。 把本地函数声明为静态的(static)n如果一个函数在实现它的文件外未被使用的话，把它声明为静态的(static)以强制使用内部连接。否则，默认的情况下会把函数定义为外部

12、连接。这样可能会影响某些编译器的优化比如，自动内联。IO缓冲n如果有文件读写的话，那么对文件的访问将是影响程序运行速度的一大因素。提高文件访问速度的主要办法有两个：一是采用内存映射文件，二是使用内存缓冲。下面是一组测试数据（见UNIX环境高级编程3.9节），显示了用18种不同的缓存长度，读1 468 802字节文件所得到的结果。 可见，一般的当内存缓冲区大小为8192的时候，性能就已经是最佳的了，这也就是为什么在H.263等图像编码程序中，缓冲区大小为8192的原因（有的时候也取2048大小）。使用内存缓冲区方法的好处主要是便于移植，占用内存少，便于硬件实现等。 字符串的赋值n计算机程序中最大

13、的矛盾是空间和时间的矛盾，那么，从这个角度出发逆向思维来考虑程序的效率问题，我们就有了解决问题的方法-以空间换时间。 例如：字符串的赋值。方法A：通常的办法：#define LEN 32char string1 LEN;memset (string1,0,LEN);strcpy (string1,This is a example!） n方法B：const char string2LEN =This is a example!; char * cp; cp = string2 ; 从上面的例子可以看出，A和B的效率是不能比的。在同样的存储空间下，B直接使用指针就可以操作了，而A需要调用两个字符

14、函数才能完成。B的缺点在于灵活性没有A好。在需要频繁更改一个字符串内容的时候，A具有更好的灵活性；如果采用方法B，则需要预存许多字符串，虽然占用了大量的内存，但是获得了程序执行的高效率。字符串的赋值n将函数改为宏函数，宏函数占用了大量的空间，而函数占用了时间。大家要知道的是，函数调用是要使用系统的栈来保存数据的，如果编译器里有栈检查选项，一般在函数的头会嵌入一些汇编语句对当前栈进行检查；同时，CPU也要在函数调用时保存和恢复当前的现场，进行压栈和弹栈操作，所以，函数调用需要一些CPU时间。而宏函数不存在这个问题。宏函数仅仅作为预先写好的代码嵌入到当前程序，不会产生函数调用，所以仅仅是占用了空间

15、，在频繁调用同一个宏函数的时候，该现象尤其突出。 将函数改为宏函数查表1n目前程序加速的常用算法一个大方面就是利用查表来避免计算（比如在jpg有huffman码表，在YUV到RGB变换也有变换表）这样原来的复杂计算现在仅仅查表就可以了，虽然浪费了内存，不过速度显著提升，还是很划算的。在数据库查询里面也有这样的思想，将热点存储起来以加速查询。 现在介绍一个简单的例子：比如，在程序中要经常计算1000到2000的阶乘，那么我们可以使用一个数组a1000先把这些值算好，保留下来，以后要计算1200！的时候，查表a1200-1000就可以了。查表2n有一个程序是这样的switch ( queue )

16、case 0 : letter = W; break;case 1 : letter = S; break;case 2 : letter = U; break;n可以优化成这样static char *classes=WSU;letter = classesqueue;考虑动态内存分配n动态内存分配（C+中的“new”）可能总是为长的基本类型（四字对齐）返回一个已经对齐的指针。但是如果不能保证对齐，使用以下代码来实现四字对齐。这段代码假设指针可以映射到 long 型。n例子 double* p = (double*)new BYTEsizeof(double) * number_of_dou

17、bles+7L;double* np = (double*)(long(p) + 7L) & 8L); 现在，你可以使用 np 代替 p 来访问数据。注意：释放储存空间时仍然应该用delete p。充分分解小的循环n要充分利用CPU的指令缓存，就要充分分解小的循环。特别是当循环体本身很小的时候，分解循环可以提高性能。很多编译器并不能自动分解循环。 这也可以理解成展开小的循环。按类型长度排序n把结构体的成员按照它们的类型长度排序，声明成员时把长的类型放在短的前面。 Switch 的用法nSwitch 可能转化成多种不同算法的代码。其中最常见的是跳转表和比较链/树。推荐对case的值依照发

18、生的可能性进行排序，把最有可能的放在第一个，当switch用比较链的方式转化时，这样可以提高性能。此外，在case中推荐使用小的连续的整数，因为在这种情况下，所有的编译器都可以把switch 转化成跳转表。减少运算，保存中间变量n计算机用于计算的时间远大于用于保存变量的时间 a = x + 1/x + 1/(x * x);if(test) b = 1 + 1/x + 1/(x * x) + 1/(2 + x);c = y + 1/x + 1/(x * x) + 1/(2 + x);d = z + 1/x + 1/(x * x) + 1/(2 + x) + int_func(x);e = q + 1/x + 1/(x * x) + 1/(2 + x) + int_func(x);t0 = 1/x;t1 = t0 + t0 * t0;a = x + t1;if(test) t2 = t1 + 1/(2 + x);b = 1 + t2;c = y + t2;d = z + t2 + int_func(x);e = q + 1/x + 1/(x * x) + 1/(2 + x) + int_func(x);算法优化一列n数学是计算机之母，没有数学的依据和基础，就没有计算机的发展，所以在编写程