【转】C程序优化之路

本文讲述在编写C程序代码的常用优化办法，分为I/O篇，内存篇，算法篇，MMX汇编篇。
　　一．I/O篇
　　 如果有文件读写的话，那么对文件的访问将是影响程序运行速度的一大因素。提高文件访问速度的主要办法有两个：一是采用内存映射文件，二是使用内存缓冲。下面是一组测试数据（见《UNIX环境高级编程》3.9节），显示了用18种不同的缓存长度，读1 468 802字节文件所得到的结果。
　　缓冲大小
　　用户CPU（秒）
　　系统CPU（秒）
　　时钟时间（秒）
　　循环次数（秒）
　　1
　　23.8
　　397.9
　　423.4
　　1 468 802
　　2
　　12.3
　　202.0
　　215.2
　　734 401
　　4
　　6.1
　　100.6
　　107.2
　　367 201
　　8
　　3.0
　　50.7
　　54.0
　　183 601
　　16
　　1.5
　　25.3
　　27.0
　　91 801
　　32
　　0.7
　　12.8
　　13.7
　　45 901
　　64
　　0.3
　　6.6
　　7.0
　　22 951
　　128
　　0.2
　　3.3
　　3.6
　　11 476
　　256
　　0.1
　　1.8
　　1.9
　　5 738
　　512
　　0.0
　　1.0
　　1.1
　　2 869
　　1 024
　　0.0
　　0.6
　　0.6
　　1 435
　　2 048
　　0.0
　　0.4
　　0.4
　　718
　　4 096
　　0.0
　　0.4
　　0.4
　　359
　　8 192
　　0.0
　　0.3
　　0.3
　　180
　　16 384
　　0.0
　　0.3
　　0.3
　　90
　　32 768
　　0.0
　　0.3
　　0.3
　　45
　　65 536
　　0.0
　　0.3
　　0.3
　　23
　　131 072
　　0.0
　　0.3
　　0.3
　　12
　　可见，一般的当内存缓冲区大小为8192的时候，性能就已经是最佳的了，这也就是为什么在H.263等图像编码程序中，缓冲区大小为8192的原因（有的时候也取2048大小）。使用内存缓冲区方法的好处主要是便于移植，占用内存少，便于硬件实现等。下面是读取文件的C伪码：
　　 int Len;
　　BYTE buffer[8192];
　　 ASSERT(buffer==NULL);
　　 If buffer is empty{
　　 Len=read(File,buffer,8192);
　　 If(len==0) No data and exit;
　　 }
　　
　　但是如果内存比较大的时候，采用内存映射文件可以达到更佳性能，并且编程实现简单。内存映射的具体使用说明见msdn October 2001中的Platform SDK
　　Documentation―Base Services―File Storage―File Mapping。下面是一点建议：
　　① 内存映射文件不能超过虚拟内存的大小，最好也不要太大，如果内存映射文件接近虚拟内存大小的时候，反而会大大降低程序的速度（其实是因为虚拟内存不足导致系统运行效率降低），这个时候，可以考虑分块映射，但是我觉得如果这样，还不如直接使用内存缓冲来得直接一些。
　　② 可以将两种方法统一使用，如我在编大图像文件数据处理的时候（因为是Unix工作站，内存很大GB单位）使用了内存映射文件，但是为了最佳性能，也使用了一行图像缓存，这样在读取文件中数据的时候，就保证了仅仅是顺序读写（内存映射文件中，对顺序读写有专门的优化）。
　　③ 在写文件的时候使用内存映射文件要有一点小技巧：应该先创建足够大的文件，然后将这个文件映射，在处理完这个文件的时候，用函数SetFilePointer和SetEndOfFile来对文件进行截尾。
　　④ 对内存映射文件进行操作与对内存进行操作类似（使用起来就象数组一样），那么如果有大块数据读写的时候，切记使用memcpy（）函数（或者CopyMemory（）函数）
　　 总之，如果要使用内存映射文件，必须：1.处理的文件比较的小，2.处理的文件很大，但是运行环境内存也很大，并且一般在运行该程序的时候不运行其他消耗内存大的程序，同时用户对速度有特别的要求，而且对内存占用没有什么要求。如果以上两个条件不满足的时候，建议使用内存缓冲区的办法。

二．内存篇
　　 在上一篇中我们讲述了如何优化文件的读写，这一篇则主要讲述对内存操作的优化，主要有数组的寻址，指针链表等，还有一些实用技巧。
　　I．优化数组的寻址
　　 在编写程序时，我们常常使用一个一维数组a[M×N]来模拟二维数组a[N][M]，这个时候访问a[]一维数组的时候：我们经常是这样写a[j×M＋i]（对于a[j][i]）。这样写当然是无可置疑的，但是显然每个寻址语句j×M＋i都要进行一次乘法运算。现在再让我们看看二维数值的寻址，说到这里我们不得不深入到C编译器在申请二维数组和一维数组的内部细节上��实际在申请二位数组和一维数组，编译器的处理是不一样的，申请一个a[N][M]的数组要比申请一个a[M×N]的数组占用的空间大！二维数组的结构是分为两部分的：
　　① 是一个指针数组，存储的是每一行的起始地址，这也就是为什么在a[N][M]中，a[j]是一个指针而不是a[j][0]数据的原因。
　　② 是真正的M×N的连续数据块，这解释了为什么一个二维数组可以象一维数组那样寻址的原因。（即a[j][i]等同于(a[0])[j×M＋i]）
　　清楚了这些，我们就可以知道二维数组要比（模拟该二维数组的）一维数组寻址效率高。因为a[j][i]的寻址仅仅是访问指针数组得到j行的地址，然后再+i,是没有乘法运算的！
　　 所以，在处理一维数组的时候，我们常常采用下面的优化办法：（伪码例子）
　　 int a[M*N];
　　 int *b=a;
　　 for(…){
　　 b[…]=…;
　　 …………
　　 b[…]=…;
　　 b+=M;
　　}
　　这个是遍历访问数组的一个优化例子，每次b+=M就使得b更新为下一行的头指针。当然如果你愿意的话，可以自己定义一个数组指针来存储每一行的起始地址。然后按照二维数组的寻址办法来处理一维数组。不过，在这里我建议你干脆就直接申请一个二维数组比较的好。下面是动态申请和释放一个二维数组的C代码。
　　int get_mem2Dint(int ***array2D, int rows, int columns) //h.263源代码
　　{
　　int i;
　　
　　if((*array2D = (int**)calloc(rows, sizeof(int*))) == NULL) no_mem_exit(1);
　　if(((*array2D)[0] = (int* )calloc(rows*columns,sizeof(int ))) == NULL) no_mem_exit(1);
　　for(i=1 ; i<rows ; i++)
　　(*array2D)[i] = (*array2D)[i-1] + columns ;
　　return rows*columns*sizeof(int);
　　}
　　void free_mem2D(byte **array2D)
　　{
　　if (array2D){
　　 if (array2D[0]) free (array2D[0]);
　　 else error ("free_mem2D: trying to free unused memory",100);
　　 free (array2D);
　　 } else{
　　 error ("free_mem2D: trying to free unused memory",100);
　　 }
　　}
　　顺便说一下，如果你的数组寻址有一个偏移量的话，不要写为a[x+offset]，而应该为 b=a+offset，然后访问b[x]。
　　不过，如果你不是处理对速度有特别要求的程序的话，这样的优化也就不必要了。记住，如果编普通程序的话，可读性和可移值性是第一位的。
　　II．从负数开始的数组
　　 在编程的时候，你是不是经常要处理边界问题呢？在处理边界问题的时候，经常下标是从负数开始的，通常我们的处理是将边界处理分离出来，单独用额外的代码写。那么当你知道如何使用从负数开始的数组的时候，边界处理就方便多了。下面是静态使用一个从－1开始的数组：
　　int a[M];
　　int *pa=a+1;
　　现在如果你使用pa访问a的时候就是从－1到M－2了，就是这么简单。（如果你动态申请a的话，free（a）可不要free（pa）因为pa不是数组的头地址）
　　III．我们需要链表吗
　　 相信大家在学习《数据结构》的时候，对链表是相当熟悉了，所以我看有人在编写一些耗时算法的时候，也采用了链表的形式。这样编写当然对内存的占用（似乎）少了，可是速度呢？如果你测试：申请并遍历10000个元素链表的时间与遍历相同元素的数组的时间，你就会发现时间相差了百倍！（以前测试过一个算法，用链表是1分钟，用数组是4秒钟）。所以这里我的建议是：在编写耗时大的代码时，尽可能不要采用链表！
　　 其实实际上采用链表并不能真正节省内存，在编写很多算法的时候，我们是知道要占用多少内存的（至少也知道个大概），那么与其用链表一点点的消耗内存，不如用数组一步就把内存占用。采用链表的形式一定是在元素比较少，或者该部分基本不耗时的情况下。
　　(我估计链表主要慢是慢在它是一步步申请内存的，如果能够象数组一样分配一个大内存块的话，应该也不怎么耗时，这个没有具体测试过。仅仅是猜想 :P)

三．算法篇
　　 在上一篇中我们讲述了对内存操作的优化，这一篇则主要讲述一些常用的优化算法。这个东东太多，内容可能会有点凌乱，见谅。
　　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频率相除就是时间。不过如果你要精确到这一步的话，建议将进程设置为最高级别，防止它被阻塞。
　　最后讲讲我处理的一个程序：程序要求我忘了，反正里面有一个函数，函数里面有一个大的循环，循环内部的处理比较耗时。结果最初程序表现出来的状况是开始还很快，越到后面越慢；我在跟踪程序中变量的时候，发现最初的循环在循环几次后就跳出了，而后面的循环次数越来越多。找到了为什么慢的原因，就可以对症下药了，我的处理是每次循环不是从头开始，而是从上一次循环跳出的地方开始左右循环（因为可能下一次循环跳出的地方别上一次的小，所以也要遍历前面的），这样程序的速度在后面也很快了。我讲这个的道理就是在实际运用中，要具体的分析程序慢的真正原因，才能达到最佳的优化效果。

三．算法篇
　　 在上一篇中我们讲述了对内存操作的优化，这一篇则主要讲述一些常用的优化算法。这个东东太多，内容可能会有点凌乱，见谅。
　　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频率相除就是时间。不过如果你要精确到这一步的话，建议将进程设置为最高级别，防止它被阻塞。
　　最后讲讲我处理的一个程序：程序要求我忘了，反正里面有一个函数，函数里面有一个大的循环，循环内部的处理比较耗时。结果最初程序表现出来的状况是开始还很快，越到后面越慢；我在跟踪程序中变量的时候，发现最初的循环在循环几次后就跳出了，而后面的循环次数越来越多。找到了为什么慢的原因，就可以对症下药了，我的处理是每次循环不是从头开始，而是从上一次循环跳出的地方开始左右循环（因为可能下一次循环跳出的地方别上一次的小，所以也要遍历前面的），这样程序的速度在后面也很快了。我讲这个的道理就是在实际运用中，要具体的分析程序慢的真正原因，才能达到最佳的优化效果。