本文讲述在编写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频率相除就是时间。不过如果你要精确到这一步的话,建议将进程设置为最高级别,防止它被阻塞。
最后讲讲我处理的一个程序:程序要求我忘了,反正里面有一个函数,函数里面有一个大的循环,循环内部的处理比较耗时。结果最初程序表现出来的状况是开始还很快,越到后面越慢;我在跟踪程序中变量的时候,发现最初的循环在循环几次后就跳出了,而后面的循环次数越来越多。找到了为什么慢的原因,就可以对症下药了,我的处理是每次循环不是从头开始,而是从上一次循环跳出的地方开始左右循环(因为可能下一次循环跳出的地方别上一次的小,所以也要遍历前面的),这样程序的速度在后面也很快了。我讲这个的道理就是在实际运用中,要具体的分析程序慢的真正原因,才能达到最佳的优化效果。
评论
发表评论