C程序优化之路(三)
――liyuming1978@163.com
本文讲述在编写C程序代码的常用优化办法，分为I/O篇，内存篇，算法篇。MMX本来我也想归在这里的，但是由于内容和标题不太符和，决定换一个名字，叫MMX技术详解，和H263视频压缩技术中的MMX应用两篇文章。
三．算法篇
在上一篇中我们讲述了对内存操作的优化，这一篇则主要讲述一些常用的优化算法。这个东东太多，内容可能会有点凌乱，见谅。
I．从小处说起：
先说说一些小地方先：
① 比如n/2写为n>>1这个是常用的方法，不过要注意的是这两个不是完全等价的！因为：如果n＝3的话，n/2=1;n>>1=1;但是，如果n＝-3的话，n/2=-1;n>>1=-2所以说在正数的时候，他们都是向下取整，但是负数的时候就不一样了。（在JPG2000中的整数YUV到RGB变换一定要使用>>来代替除法就是这个道理）
② 还有就是a=a+1要写为a++; a=a+b要写为a+=b（估计一般用VB的才会写a=a+1 :P）
③ 将多种运算融合：比如a[i++];就是先访问a[i]，再令i加1；从汇编的角度上说，这个确实是优化的，如果写为a[i]，和i++的话，有可能就会有两次的对i变量的读，一次写（具体要看编译器的优化能力了），但是如果a[i++]的话，就一定只读写i变量一次。不过这里有一个问题要注意：在条件判断内的融合一定要小心，比如：（idct变换中的0块判断，陈王算法）
if (!((x1 = (blk[8*4]<<8)) | (x2 = blk[8*6]) | (x3 = blk[8*2]) | (x4 = blk[8*1]) | (x5 = blk[8*7]) | (x6 = blk[8*5]) | (x7 = blk[8*3])))
在条件判断中融合了赋值语句，但是实际上如果条件为真的话，是不需要这些赋值语句的，也就是说当条件真的时候，多了一些垃圾语句，这些是在h263源码上的问题，虽然这些垃圾语句使得计算0块的时候，时间增加了30％，但是由于idct仅仅占1%的时间，0块又仅仅30%~70%的时间，所以这些性能损失是没有什么关系的。（这是后来我用汇编改写源码的时候得到的结论）。这里也说明了，程序优化一定重点在最耗时的地方。对于不耗时的代码优化是没有太大的实用意义的。
II．以内存换速度：
天下总是难有双得的事情，编程也是一样，大多数情况，速度同内存（或者是性能，比如说压缩性能什么的）是不可兼得的。目前程序加速的常用算法一个大方面就是利用查表来避免计算（比如在jpg有huffman码表，在YUV到RGB变换也有变换表）这样原来的复杂计算现在仅仅查表就可以了，虽然浪费了内存，不过速度显著提升，还是很划算的。在数据库查询里面也有这样的思想，将热点存储起来以加速查询。 现在介绍一个简单的例子，（临时想的，呵呵）：比如，在程序中要经常（一定要是经常！）计算1000到2000的阶乘，那么我们可以使用一个数组a[1000]先把这些值算好，保留下来，以后要计算1200！的时候，查表a[1200-1000]就可以了。
III．化零为整
由于零散的内存分配，以及大量小对象建立耗时很大，所以对它们的优化有时会很有效果，比如上一篇我说的链表存在的问题，就是因为大量的零散内存分配。现在就从一个vb的程序说起，以前我用vb给别人编小程序的时候，（呵呵，主要是用vb编程比vc快，半天就可以写一个）在使用MSFlexGrid控件的时候（就是一个表格控件），发现如果一行一行的增加新行，刷新速度十分的慢，所以我就每次增加100行，等到数据多到再加新行的时候，再加100行，这样就“化零为整”了，使用这样的方法，刷新的速度比原来快了n倍！其实这样的思想应用很多，如：程序运行的时候，其实就占用了一定的空间，后来的小块内存分配是先在这个空间上的，这就保证了内存碎片尽可能的少，同时加快运行速度。
IV．条件语句或者case语句将最有可能的放在前面
优化效果不明显。想得到就用吧，想不到就算了。
V．为了程序的可读性，不去做那些编译器可以做的或者优化不明显的处理：
这个是很重要的，一个普通程序的好坏，主要是它的可读性，可移植性，可重用性，然后才是它的性能。所以，如果编译器本身可以帮助我们优化的话，我们就没有必要写那些大家都不怎么看得懂的东西。比如a＝52（结束）－16（起始）；这样写可能是因为在别人读程序的时候，一下就明白了a的含义。我们不用写为a＝36，因为编译器是会帮我们算出来的。
IV．具体情况具体分析：
具体情况具体分析，这是放之四海而皆准的真理。没有具体的分析，就不能针对问题灵活应用解决的办法。下面我就说说分析的方法。即如何找到程序的耗时点：（从最简单的办法说起，先说明一个函数GetTickCount(),这个函数在头尾各调用一次，返回值相减就是程序的耗时，精确到1ms）
① 对于认为是比较耗时的函数，运行两次，或者将函数内部的语句注释掉（要保证程序可以运行），看看多（或者少了）多少时间。这个办法简单不精确。
② 每个地方都用GetTickCount()函数测试时间，注意GetTickCount()只能精确到ms。一般的小于10ms就不太精确了。
③ 使用另外一个函数QueryPerformanceCounter（&Counter）和QueryPerformanceFrequency(&Frequency)，前面计算cpu时钟周期，后面是cpu频率相除就是时间。不过如果你要精确到这一步的话，建议将进程设置为最高级别，防止它被阻塞。
最后讲讲我处理的一个程序：程序要求我忘了，反正里面有一个函数，函数里面有一个大的循环，循环内部的处理比较耗时。结果最初程序表现出来的状况是开始还很快，越到后面越慢；我在跟踪程序中变量的时候，发现最初的循环在循环几次后就跳出了，而后面的循环次数越来越多。找到了为什么慢的原因，就可以对症下药了，我的处理是每次循环不是从头开始，而是从上一次循环跳出的地方开始左右循环（因为可能下一次循环跳出的地方别上一次的小，所以也要遍历前面的），这样程序的速度在后面也很快了。我讲这个的道理就是在实际运用中，要具体的分析程序慢的真正原因，才能达到最佳的优化效果。
