当前页面: 开发资料首页 → Java 专题 → C程序优化之路(三)

C程序优化之路(三)

摘要: 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频率相除就是时间。不过如果你要精确到这一步的话，建议将进程设置为最高级别，防止它被阻塞。
最后讲讲我处理的一个程序：程序要求我忘了，反正里面有一个函数，函数里面有一个大的循环，循环内部的处理比较耗时。结果最初程序表现出来的状况是开始还很快，越到后面越慢；我在跟踪程序中变量的时候，发现最初的循环在循环几次后就跳出了，而后面的循环次数越来越多。找到了为什么慢的原因，就可以对症下药了，我的处理是每次循环不是从头开始，而是从上一次循环跳出的地方开始左右循环（因为可能下一次循环跳出的地方别上一次的小，所以也要遍历前面的），这样程序的速度在后面也很快了。我讲这个的道理就是在实际运用中，要具体的分析程序慢的真正原因，才能达到最佳的优化效果。
作者相关文章： C程序优化之路(二)(原作) C程序优化之路(原作)
对该文的评论 liyuming1978(2002-12-13 10:40:53)
我把这些天大家好的说法写一下： 1.ilovepotato的连续内存访问会提高cache命中率，加速时间，这个我在mmx汇编里面测试了，确实有用 2.magmng提供了链接 http://www.codingnow.com/2000/download/pentopt.htm 很好 3.ilovepotato 说的VTune 当了还没有用，不知道好不好。 4.tongchi说的 a＋＋和a＋＝1是一样的，测试确实如此，他提供了看汇编的好办法，测试好用！！！ 5.goldenlinn 提到的内存池技术，不过我查阅了该项技术是用于各种对象分配的，不仅仅陷于链表 6.qimans说的链表数组，很有特点，估计很有用。 7.Analyst对二维数组申请的不同看法，我没有学编译原理，具体的不知道，我看h。263上是这么写的。需要查资料确定一下。
liyuming1978(2002-12-13 10:32:07)
so 3x tongchi 真牛，以前我都不知道，还废了半天劲用debug，我记下来了，感谢大家的支持！！
tongchi(2002-12-12 22:41:27)
从“运行到光标处”按钮往后，依序为Run to cursor、Quick Watch、Watch、Variable、Registers、Memory、Call Stack、Disassembly，最后一个Disassembly就是。一开始它所在的窗口被覆盖了，多点一次就可以看见汇编代码了。
liyuming1978(2002-12-12 21:35:11)
是哪个？是运行到光标处那个吗？那个不行呀大侠，说详细一点吧。候教！！！
tongchi(2002-12-12 19:47:34)
下面是Release方式编译后的结果，如果连Debug方式下，a++和a = a + 1都没有区别，Release下就更不可能有了。注意，如果不使用a（比如说没有中间的printf，Release方式下，a++和a = a + 1）会被“优化掉”，根本就不产生中间代码。其实成熟的编译器完全可以帮我们做到这些，写程序的精力应该放在程序逻辑上，而不是这种无谓的指令问题上，单条的指令，编译器都能会帮我们优化到最好。不管在什么平台上，如果你的编译器不具备这样的功能，还是那句话，扔了算了。
//a++; mov eax, DWORD PTR _a$[esp+12] add esp, 8 inc eax //printf("%d", a); push eax push OFFSET FLAT:??_C@_02MECO@?$CFd?$AA@ ; `string' mov DWORD PTR _a$[esp+12], eax call _printf //a = a + 1; mov eax, DWORD PTR _a$[esp+12] add esp, 8 inc eax //printf("%d", a); push eax push OFFSET FLAT:??_C@_02MECO@?$CFd?$AA@ ; `string' mov DWORD PTR _a$[esp+12], eax call _printf
p.s. debug方式下，在代码某处设置断点后开始调试，在断点处停下后，调试工具栏的最后一个按钮就可以察看编译后的汇编代码。Release方式下也可以这样用，但是没法同时看到源码。用这种方法:Project->Setting（Win32 Release）->C/C++ ->Category:Listing Files->Listing file type:Assembly with Source Code，编译完成后在编译目录中就会有Release方式下编译后的汇编文件，源码和汇编都有。
liyuming1978(2002-12-12 18:52:56)
这几天在做h26L的研究，有的忙 mmx的部分可能要晚一点出来了在mmx部分还会有一些基于intel cpu上的优化我当了http://www.codingnow.com/2000/download/pentopt.htm上的内容等我学好了在把一些心得写出来
另外我写的都是有代码测试的，保证准确呵呵，可不能误导了大家
zrhk(2002-12-12 17:22:20) up
coppermine(2002-12-12 15:55:06)
很好！继续！
我也做过图像处理，除了算法之外，编码对运行效率的提高也是不可小视的。
pp616(2002-12-12 15:43:22)
呵呵。我喜欢程序快。但不喜欢没道理的快。 liyuming1978(2002-12-12 14:53:02)
另外如果你写的Code是对时间要求很高的,那么最好不要指望编译器会帮你做,因为假如有一天,你需要把你的代码从PC移植到DSP,虽然都是C代码,但是你会发现由于编译器不一样,效率会相差很多,所以我认为,一个好程序员必须养成好的习惯.
深受启发
liyuming1978(2002-12-12 14:50:50)
tongchi 我想这是bebug版本下的汇编码，debug是没有优化的？？？怎么才能像你那样看到源码，有什么好用的工具？
tongchi(2002-12-12 12:26:41)
如果你的编译器对于a++和a = a + 1还不能等同处理，那这个编译器扔了算了。
tongchi(2002-12-12 12:22:32)
书上说a++速度比a = a+1要快! //int a = 0; mov dword ptr [ebp-4],0 //a++; mov eax,dword ptr [ebp-4] add eax,1 mov dword ptr [ebp-4],eax //int b = 0; mov dword ptr [ebp-8],0 //b = b + 1; mov ecx,dword ptr [ebp-8] add ecx,1 mov dword ptr [ebp-8],ecx
上面是VC编译后的结果，请问快在哪儿？
xrenwu(2002-12-12 11:50:26)
good！
magmng(2002-12-12 10:51:37)
http://www.codingnow.com/2000/download/pentopt.htm
ilovepotato(2002-12-12 10:19:24)
大家可以用Intel的VTune来测性能,很好用.
ilovepotato(2002-12-12 10:17:36)
我想再补充一点，特别是对搞图像处理的人应该会比较有用，因为经常有需要访问大数组。这时候请注意Cache的访问，比如大家都可以测试一下下面两段代码：第一段: //pbuffer 是一个2000*1600的int数组，用一维数组存放， for(i=0；i<1600;i++) for(j=0;j<2000;j++) pbuffer[i*1600+j]++; 第二段: for(j=0;j<2000;j++) for(i=0；i<1600;i++) pbuffer[i*1600+j]++; 这两段计算量是一样的,但是时间是不一样的,在我的机器上,后一段花的时间大约是第一段的两到三倍,原因是后一段的内存访问是不连续的,因此Cache的命中率会非常低,所以这条原则就是尽量访问相邻内存. 其实大家如果要学习如何优化代码,最好的教科书就是Intel的优化手册,可以在Intel的网站下.虽然只是介绍IA CPU的优化,但是现在很多处理器包括DSP,都是有很多相同之处,所以很多原理都是一样的. 另外如果你写的Code是对时间要求很高的,那么最好不要指望编译器会帮你做,因为假如有一天,你需要把你的代码从PC移植到DSP,虽然都是C代码,但是你会发现由于编译器不一样,效率会相差很多,所以我认为,一个好程序员必须养成好的习惯.
Jinq0123(2002-12-12 9:58:44)
有没有用于统计各函数执行时间的代码库？ VC带的Profile只给出些无用的信息...
zfive5(2002-12-12 8:58:28)
adi
lx_cyh(2002-12-12 8:54:21)
的确,我相信每个C编译器都会把 a=a+1语句优化成一条inc类似的指令我们都想得到,我就不信搞编译器的想不到,除非它们........ 因此,教育别人时,不要说得过于武断
liyuming1978(2002-12-11 20:49:58)
我刚刚想用 debug 看一下a++ 同a+=1这些语句在汇编下的不同, 结果发现乱七八糟的语句太多了,我想应该有什么工具可以很方便的看汇编代码的, (不然qq怎么那么容易改呢,不会就用windows自带的debug吧) 那位大侠知道的 ,告诉一声谢谢了!
还有就是其实在很多应用中,目前主要是视频上的,程序优化特别的重要,我们都说什么游戏引擎的 ,那都是很优化的代码不然岂不是要慢死呵呵!
liyuming1978(2002-12-11 19:54:51)
有人希望学习MMX技术吗
wwl_f117(2002-12-11 19:34:57)
a++速度比a = a+1要快!下面的也一样. 这里谈的是优化! 优化是在原有的正确的代码之上的更进一步的提升. 对于现在的cpu,这点速度确实起不了什么作用,但是在pda,手机,数字收音机等嵌入式系统里面,代码的优化显得及其总要!
magmng(2002-12-11 19:14:46)
② 还有就是a=a+1要写为a++; a=a+b要写为a+=b（估计一般用VB的才会写a=a+1 :P）
为什么不相信编译器？
XiaoJingZi(2002-12-11 18:04:16)
一般，意义不大，请不要浪费电子墨水
MPU(2002-12-11 17:44:00)
支持。。。。希望继续........................
↑返回目录
前一篇: Data Transfer Object
后一篇: C程序优化之路(二)