你的for循环真的高效吗——优化for循环.doc

在我们所写的程序中，几乎没有不用到for循环的，但是，对于for循环，很多人确实效率很低的，包括我看得很多代码，for循环的执行效率非常低，下面我就举个例子来说明： view plaincopy to clipboardprint?1 #include 2 char *string=zhangbo; 3 int main(int argc,char *argv) 4 5 int i; 6 for(i=0;istrlen(string);i+) 7 printf(%in,i); 8 return (0); 9 这个上边的程序程序我想大家都明白，那我问问读者，你知道这个程序的效率是多少吗？你肯定不屑的说，不就是n吗？其实，你错了，你说的n只是在算法层面上的优化，其实对于底层的优化还没做好，这段代码的效率是n2（n的平方），为什么？是这样的，我们在每次循环的时候，都会调用strlen函数，这个函数的效率也是n，所以，我们要再加一个变量，比如下边所看到的， view plaincopy to clipboardprint?10 #include 11 char *string=zhangbo; 12 int main(int argc,char *argv) 13 14 int i,k; 15 k=strlen(zhangbo); 16 for(i=0;ik;i+) 17 printf(%in,i); 18 return (0); 19 这个程序的效率是2n，当n很大时，我就不说了。再看这个例子：view plaincopy to clipboardprint?20 #include 21 int main(int argc,char *argv) 22 23 int i,m,k1，k2,k3,k4,k5,k6,k7,k8; 24 m=10000000; 25 26 for(i=0;im;i+) 27 k1+; k5+; 28 k2+; k6+; 29 k3+; k7+; 30 k4+; k8+; 31 32 return (0); 33 我们再看这个for循环，我们是让这些数每次循环都加1，这个效率也不是达到了最优，是这样的，在每次for循环的时候，编译器会给变量i，变量m每个独占一个寄存器，因为是循环嘛，编译器给i和m也是为了效率考虑，不用再向寄存器加载每次循环的判断变量了，但是，一般基于Intel的处理器都只有8个通用寄存器，这样，我们就剩下了6个寄存器给for循环里的内容中的变量使用，但是，我们的变量有8个，我们这时会在把其他的变量入栈，这样，我们的效率变低了，每次出战或者入栈都会消耗两个CPU时钟周期，这样，我们就总共满了8个周期，但是，如果更多呢？呵呵！我们可以这样该我们的程序；view plaincopy to clipboardprint?34 #include 35 int main(int argc,char *argv) 36 37 int i,m,k1，k2,k3,k4,k5,k6,k7,k8; 38 m=10000000; 39 40 for(i=0;im;i+) 41 k1+; k5+; 42 k2+; k6+; 43 44 for(i=0;im;i+) 45 k3+; k7+; 46 k4+; k8+; 47 48 return (0) 49 这样的效率就得到了很大改善！我始终相信，人类最伟大的发明就是汽车和计算机，对于一部汽车，我们如果不经过专业的了解汽车内部结构的工程师调试，就算你是保时捷，也达不到理想的速度。对于计算机来说，我始终觉得，我们很多人只是明白程序的写法，例如一个程序：view plaincopy to clipboardprint?1 #include 2 char *hello = hello; 3 char *_ = ,; 4 int main() 5 6 char *world = world; 7 printf(%s%s%sn,hello,_,world); 8 return 0; 9 我们都知道这个程序输hello，world，对了！我们却不知道字符串hello，字符串_，字符串world是不是在一个位置，如果你觉得，不必关心这些了，反正程序已经达到了效果，那么请你离开这个网页，不要浪费你的时间。回到计算机上来，我们要让计算机发挥最大的性能，就必须也要像“了解汽车内部结构的工程师”一样的了解计算机，我时常赞叹计算机设计的优美。为了加快访问的速度，我们加入了缓存，缓存的加入，就像我们在超高速行驶汽车时，再优秀的发动机也不能完全燃烧汽油，而且速度越高，会由于空气的不足，导致汽油燃烧不尽，从而成了汽车提速的瓶颈，然后，我们在汽车的身上再多开几个洞（这就是你为什么见到豪华跑车身上都有几个洞），把空气压缩进发动起，从而提高速度。这和计算机缓存有着异曲同工之妙，好好利用，就相当于，你比别人跑得更快。对于计算机缓存来说，我们都知道他是高速但是昂贵的（难道在跑车开几个洞就不昂贵了吗，是不是很像？），对于缓存优化，我们紧紧介绍L1缓存的优化（如果你会好好利用，它足以让你的程序运行时间降低很多）。 什么是L1缓存，在计算机CPU中，我们为了提高程序的执行效率和CPU加载相关代码和数据的速度所加入的一种存储设备，当然，一般CPU会有L2缓存，甚至是L3缓存，很多人的电脑L1缓存的一行只能放入16个字节，就是只能放入4个整数型数据（gcc 4.4版本，32位计算机，酷睿2双核，2.0G赫兹处理速度），可以把计算机L1缓存看成一个二维矩阵，写个程序给你看看吧！view plaincopy to clipboardprint?10 #include 11 int main() 12 13 int array44; 14 int i,j; 15 for(i=0;i4;i+) 16 for(j=0;j4;j+) 17 arrayij=0; 18 return 0; 19 view plaincopy to clipboardprint?20 #include 21 int main() 22 23 int array44; 24 int i,j; 25 for(i=0;i4;i+) 26 for(j=0;j4;j+) 27 arrayji=0; 28 return 0; 29 我们比较着两个程序，当然，你运行时发现不了谁对谁快，但是，我慢慢给你说，这只是一个例子，上面的程序是先按照行，再按照列输出的，我们叫程序1，下面的是先输出列，在输出行，我们叫程序2。我告诉过你们，你们可以把这个缓存想象成一个n4的矩阵，然后我们就在把我们的程序所用到的数据加载到L1中去。作为一个程序员，我们要知道，程序是局部存储原理，就是，我们把相似的数据存放在一起，这也就是为什么C语言会有这么多不同的段，什么BSS啦，什么data啦，等等，我们也把经常访问的数据段放在一起，因为程序都是以“块”的形式来存取的，这就是为什么硬盘读取一般都是4K的页？同样，内存给缓存还是以这样的块来读取的，只不过一个块的大小逐渐降低，具体怎么递减，别问我，我也不知道！好了，我告诉这两个程序的效率吧，假设我们的L1缓存时一个类似的24的矩阵（实际没这么小，为了举例子方便），我们看第一个程序，首先，我们先加载array00，在每次加载的时候，我们都会检查我们的缓存中是不是有我们需要的数据，当然，我们第一次加载我们所要的数据，我们的缓存中当然没有我们要的数据了，第一次加载我们把array00，array01，array02，array03这四个缓存数组加载到需要加载的缓存行，也就是第一行或者第二行，怎么加载的，在Linux中，是有一个时间限制的和引用次数来双重决定的，我们并不讨论这个问题，我们假设加载到第一行上，就这四个数据，然后我们的程序1接着访问array01，检查在缓存中有我们要的数据，我们就不用在加载了，直接给寄存器就好了，当到了array10时，没有我们要的数据，我们就再把它加载到第二行中去，是array10，array11，array12，array13这四个数据，访问完了这四个数据时，我们再接着访问array20，缓存中还是没有，我们就把它加载打第一行中去，这样，我们一共就加载了4次数据。但是程序2就不是这样了，我们先访问array00，没有，照样我们加载到缓存行1中，当然，计算机还是加载array00，array01，array02，array03，但是，我们接着就访问array10，缓存中没有，我们就在加载array10，array11，array12，array13这四个数据到缓存行2中去，然后在访问array30，还是没有，在加载，以此类推，我们加载了一共44次数据，效率怎么样，我就用告诉你：我曾问大师，汽车提高速度的瓶颈是什么？大师说：瞬间燃烧的汽油量和热量的利用率。我默然低下头，那么计算机的瓶颈就是能不能大规模的提取我要的数据和IO操作的效率。当然实际上我们的缓存L1一般是没这么小的，但是你看这个程序：view plaincopy to clipboardprint?30 #include 31 int main() 32 33 int i,j; 34 int array1256256; 35 int array2256256; 36 for(i=0;i256;i+) 37 for(j=0;j256;j+) 38 array1ij=array2ij; 39 return 0; 40 我们得加载两个数组，每个数组的大小是256256，这个超过L1缓存的大小，效率就显现出来了！要不你写成这样试试：view plaincopy to clipboardprint?41 #include 42 int main() 43 44 int i,j; 45 int array1256256; 46 int array2256256; 47 for(i=0;i256;i+) 48