你的for循环真的高效吗——优化for循环第二章

yzd

浏览: 1818398 次
性别:
来自: 北京

最近访客更多访客>>

churchchen86

devcang

ecs2003

southking

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1784)

社区版块

存档分类

我始终相信，人类最伟大的发明就是汽车和计算机，对于一部汽车，我们如果不经过专业的了解汽车内部结构的工程师调试，就算你是保时捷，也达不到理想的速度。对于计算机来说，我始终觉得，我们很多人只是明白程序的写法，例如一个程序：
<textarea cols="50" rows="15" name="code" class="cpp">#include <stdio.h>
char *hello = "hello";
char *__ = ",";
int main()
{
char *world = "world";
printf("%s%s%s/n",hello,__,world);
return 0;
}</textarea>
我们都知道这个程序输hello，world，对了！我们却不知道字符串hello，字符串__，字符串world是不是在一个位置，如果你觉得，不必关心这些了，反正程序已经达到了效果，那么请你离开这个网页，不要浪费你的时间。
回到计算机上来，我们要让计算机发挥最大的性能，就必须也要像“了解汽车内部结构的工程师”一样的了解计算机，我时常赞叹计算机设计的优美。为了加快访问的速度，我们加入了缓存，缓存的加入，就像我们在超高速行驶汽车时，再优秀的发动机也不能完全燃烧汽油，而且速度越高，会由于空气的不足，导致汽油燃烧不尽，从而成了汽车提速的瓶颈，然后，我们在汽车的身上再多开几个洞（这就是你为什么见到豪华跑车身上都有几个洞），把空气压缩进发动起，从而提高速度。这和计算机缓存有着异曲同工之妙，好好利用，就相当于，你比别人跑得更快。

对于计算机缓存来说，我们都知道他是高速但是昂贵的（难道在跑车开几个洞就不昂贵了吗，是不是很像？），对于缓存优化，我们紧紧介绍L1缓存的优化（如果你会好好利用，它足以让你的程序运行时间降低很多）。
<img src="http://hi.csdn.net/attachment/201106/3/0_13070653910au1.gif" alt="">

什么是L1缓存，在计算机CPU中，我们为了提高程序的执行效率和CPU加载相关代码和数据的速度所加入的一种存储设备，当然，一般CPU会有L2缓存，甚至是L3缓存，很多人的电脑L1缓存的一行只能放入16个字节，就是只能放入4个整数型数据（gcc 4.4版本，32位计算机，酷睿2双核，2.0G赫兹处理速度），可以把计算机L1缓存看成一个二维矩阵，写个程序给你看看吧！
<textarea cols="50" rows="15" name="code" class="cpp">#include <stdio.h>
int main()
{
int array[4][4];
int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
 array[i][j]=0;
return 0;
}</textarea>

<textarea cols="50" rows="15" name="code" class="cpp">#include <stdio.h>
int main()
{
int array[4][4];
int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
 array[j][i]=0;
return 0;
}</textarea>
我们比较着两个程序，当然，你运行时发现不了谁对谁快，但是，我慢慢给你说，这只是一个例子，上面的程序是先按照行，再按照列输出的，我们叫程序1，下面的是先输出列，在输出行，我们叫程序2。我告诉过你们，你们可以把这个缓存想象成一个n×4的矩阵，然后我们就在把我们的程序所用到的数据加载到L1中去。作为一个程序员，我们要知道，程序是局部存储原理，就是，我们把相似的数据存放在一起，这也就是为什么C语言会有这么多不同的段，什么BSS啦，什么data啦，等等，我们也把经常访问的数据段放在一起，因为程序都是以“块”的形式来存取的，这就是为什么硬盘读取一般都是4K的页？同样，内存给缓存还是以这样的块来读取的，只不过一个块的大小逐渐降低，具体怎么递减，别问我，我也不知道！
好了，我告诉这两个程序的效率吧，假设我们的L1缓存时一个类似的2×4的矩阵（实际没这么小，为了举例子方便），我们看第一个程序，首先，我们先加载array[0][0]，在每次加载的时候，我们都会检查我们的缓存中是不是有我们需要的数据，当然，我们第一次加载我们所要的数据，我们的缓存中当然没有我们要的数据了，第一次加载我们把array[0][0]，array[0][1]，array[0][2]，array[0][3]这四个缓存数组加载到需要加载的缓存行，也就是第一行或者第二行，怎么加载的，在Linux中，是有一个时间限制的和引用次数来双重决定的，我们并不讨论这个问题，我们假设加载到第一行上，就这四个数据，然后我们的程序1接着访问array[0][1]，检查在缓存中有我们要的数据，我们就不用在加载了，直接给寄存器就好了，当到了array[1][0]时，没有我们要的数据，我们就再把它加载到第二行中去，是array[1][0]，array[1][1]，array[1][2]，array[1][3]这四个数据，访问完了这四个数据时，我们再接着访问array[2][0]，缓存中还是没有，我们就把它加载打第一行中去，这样，我们一共就加载了4次数据。
但是程序2就不是这样了，我们先访问array[0][0]，没有，照样我们加载到缓存行1中，当然，计算机还是加载array[0][0]，array[0][1]，array[0][2]，array[0][3]，但是，我们接着就访问array[1][0]，缓存中没有，我们就在加载array[1][0]，array[1][1]，array[1][2]，array[1][3]这四个数据到缓存行2中去，然后在访问array[3][0]，还是没有，在加载，以此类推，我们加载了一共4×4次数据，效率怎么样，我就用告诉你：我曾问大师，汽车提高速度的瓶颈是什么？大师说：瞬间燃烧的汽油量和热量的利用率。我默然低下头，那么计算机的瓶颈就是能不能大规模的提取我要的数据和IO操作的效率。
当然实际上我们的缓存L1一般是没这么小的，但是你看这个程序：
<textarea cols="50" rows="15" name="code" class="cpp">#include <stdio.h>
int main()
{
int i,j;
int array1[256][256];
int array2[256][256];
for(i=0;i<256;i++)
for(j=0;j<256;j++)
 array1[i][j]=array2[i][j];
return 0;
}</textarea>
我们得加载两个数组，每个数组的大小是256×256，这个超过L1缓存的大小，效率就显现出来了！要不你写成这样试试：
<textarea cols="50" rows="15" name="code" class="cpp">#include <stdio.h>
int main()
{
int i,j;
int array1[256][256];
int array2[256][256];
for(i=0;i<256;i++)
for(j=0;j<256;j++)
 array1[j][i]=array2[j][i];
return 0;
}</textarea>
运行时加上系统API函数的时间函数，读者自己实验看看！

关于L1缓存的大小，每个CPU不同，这个也是不同的，所以不敢妄加告诉大家。
结尾话：
贝多芬说，音乐家是离上帝最近的人，其实他漏掉了另一种——程序员，为什么你没成为计算机中“贝多芬”？原因很简单，贝多芬曾因为弹钢琴她的手指缝发热而不得不用水浸湿后再弹。写程序一个道理。多余话不说。

分享到：