Chinaunix首页 | 论坛 | 博客

tolimit

首页　| 　博文目录　| 　关于我

lwfbibi

  • 博客访问： 318047
  • 博文数量： 26
  • 博客积分： 10
  • 博客等级： 民兵
  • 技术积分： 1631
  • 用 户 组： 普通用户
  • 注册时间： 2012-03-09 00:51
个人简介

努力 奋斗 专注于linux内核 微信：tolimit 扣扣：348958453

文章分类

全部博文（26）

文章存档

2015年（26）

我的朋友
最近访客
推荐博文
相关博文
关于嵌套循环效率研究

分类： C/C++

2015-02-06 12:05:39

本文为原创，转载请注明：http://blog.chinaunix.net/uid/26772321.html


引言

    大家都知道，当进行嵌套循环时，大循环放最外面和放最里面所造成的执行效率会不同，本篇文章会通过汇编代码进行分析具体情况。

测试环境

  •     系统：ubuntu 14.04.1
  •     编译器：gcc-4.8
  •     编译命令：gcc test.c -o test -g -Wall
测试代码：
  1. #include <stdio.h>

  3. /* 大循环在外 */
  4. void big_in_out (void)
  5. {
  6.     int i;
  7.     int j;
  8.     int k;

  10.     for (i = 10000; i != 0; i--)
  11.         for (j = 1000; j != 0; j--)
  12.             for (k = 100; k != 0; k--)
  13.                 ;
  14. }

  16. /* 大循环在内 */
  17. void big_in_in (void)
  18. {
  19.     int i;
  20.     int j;
  21.     int k;

  23.     for (i = 100; i != 0; i--)
  24.         for (j = 1000; j != 0; j--)
  25.             for (k = 10000; k != 0; k--)
  26.                 ;
  27. }

  29. int main (int argc, char * argv[])
  30. {
  31.     return 0;
  32. }

通过objdump命令，获取其汇编代码，如下：
  1. #include <stdio.h>

  3. void big_in_out (void)
  4. {
  5.   4004ed:    55     push %rbp
  6.   4004ee:    48 89 e5     mov %rsp,%rbp
  7.     int i;
  8.     int j;
  9.     int k;

  11.     for (i = 10000; i != 0; i--)
  12.   4004f1:    c7 45 f4 10 27 00 00     movl $0x2710,-0xc(%rbp)            # i = 10000         
  13.   4004f8:    eb 2a     jmp 400524 <big_in_out+0x37>                      # 跳转至400524         
  14.         for (j = 1000; j != 0; j--)
  15.   4004fa:    c7 45 f8 e8 03 00 00     movl $0x3e8,-0x8(%rbp)             # j = 1000                 
  16.   400501:    eb 17     jmp 40051a <big_in_out+0x2d>                      # 跳转至40051a         
  17.             for (k = 100; k != 0; k--)
  18.   400503:    c7 45 fc 64 00 00 00     movl $0x64,-0x4(%rbp)              # k = 100         
  19.   40050a:    eb 04     jmp 400510 <big_in_out+0x23>                      # 跳转至400510             
  20.   40050c:    83 6d fc 01     subl $0x1,-0x4(%rbp)                        # k = k - 1             
  21.   400510:    83 7d fc 00     cmpl $0x0,-0x4(%rbp)                        # 判断k是否为0             
  22.   400514:    75 f6     jne 40050c <big_in_out+0x1f>                      # 不为0跳转至40050c            
  23.     int i;
  24.     int j;
  25.     int k;

  27.     for (i = 10000; i != 0; i--)
  28.         for (j = 1000; j != 0; j--)
  29.   400516:    83 6d f8 01     subl $0x1,-0x8(%rbp)                        # j = j - 1             
  30.   40051a:    83 7d f8 00     cmpl $0x0,-0x8(%rbp)                        # 判断j是否为0             
  31.   40051e:    75 e3     jne 400503 <big_in_out+0x16>                      # j不为0跳转至400503     
  32. {
  33.     int i;
  34.     int j;
  35.     int k;

  37.     for (i = 10000; i != 0; i--)
  38.   400520:    83 6d f4 01     subl $0x1,-0xc(%rbp)                        # i = i - 1             
  39.   400524:    83 7d f4 00     cmpl $0x0,-0xc(%rbp)                        # 判断i是否为0             
  40.   400528:    75 d0     jne 4004fa <big_in_out+0xd>                       # i不为0跳转至4004fa     
  41.         for (j = 1000; j != 0; j--)
  42.             for (k = 100; k != 0; k--)
  43.                 ;                                                                        
  44. }
  45.   40052a:    5d     pop %rbp
  46.   40052b:    c3     retq

  48. 000000000040052c <big_in_in>:

  50. void big_in_in (void)
  51. {
  52.   40052c:    55     push %rbp
  53.   40052d:    48 89 e5     mov %rsp,%rbp
  54.     int i;
  55.     int j;
  56.     int k;

  58.     for (i = 100; i != 0; i--)
  59.   400530:    c7 45 f4 64 00 00 00     movl $0x64,-0xc(%rbp)              # i = 100                 
  60.   400537:    eb 2a     jmp 400563 <big_in_in+0x37>                       # 跳转至400563            
  61.         for (j = 1000; j != 0; j--)
  62.   400539:    c7 45 f8 e8 03 00 00     movl $0x3e8,-0x8(%rbp)             # j = 1000             
  63.   400540:    eb 17     jmp 400559 <big_in_in+0x2d>                       # 跳转至400559             
  64.             for (k = 10000; k != 0; k--)
  65.   400542:    c7 45 fc 10 27 00 00     movl $0x2710,-0x4(%rbp)            # k = 10000         
  66.   400549:    eb 04     jmp 40054f <big_in_in+0x23>                       # 跳转至40054f         
  67.   40054b:    83 6d fc 01     subl $0x1,-0x4(%rbp)                        # k = k - 1         
  68.   40054f:    83 7d fc 00     cmpl $0x0,-0x4(%rbp)                        # 判断k是否为0         
  69.   400553:    75 f6     jne 40054b <big_in_in+0x1f>                       # 不为0跳转至40054b
  70.     int i;
  71.     int j;
  72.     int k;

  74.     for (i = 100; i != 0; i--)
  75.         for (j = 1000; j != 0; j--)
  76.   400555:    83 6d f8 01     subl $0x1,-0x8(%rbp)                        # j = j - 1         
  77.   400559:    83 7d f8 00     cmpl $0x0,-0x8(%rbp)                        # 判断j是否为0         
  78.   40055d:    75 e3     jne 400542 <big_in_in+0x16>                       # j不为0跳转至400542     
  79. {
  80.     int i;
  81.     int j;
  82.     int k;

  84.     for (i = 100; i != 0; i--)
  85.   40055f:    83 6d f4 01     subl $0x1,-0xc(%rbp)                        # i = i - 1         
  86.   400563:    83 7d f4 00     cmpl $0x0,-0xc(%rbp)                        # 判断i是否为0         
  87.   400567:    75 d0     jne 400539 <big_in_in+0xd>                        # i不为0跳转至400539     
  88.         for (j = 1000; j != 0; j--)
  89.             for (k = 10000; k != 0; k--)
  90.                 ;                                                                 
  91. }
  92.   400569:    5d     pop %rbp
  93.   40056a:    c3     retq

  95. 000000000040056b <main>:

  97. int main (int argc, char * argv[])
  98. {
  99.   40056b:    55     push %rbp
  100.   40056c:    48 89 e5     mov %rsp,%rbp
  101.   40056f:    89 7d fc     mov %edi,-0x4(%rbp)
  102.   400572:    48 89 75 f0     mov %rsi,-0x10(%rbp)
  103.     return 0;
  104.   400576:    b8 00 00 00 00     mov $0x0,%eax
  105. }

循环结果

    由于是嵌套循环，即使循环0次，比如for(i = 0; i != 0; i--)情况，都需要执行4条指令，分别是：赋值、跳转、比较、判断跳转。具体的例子如18行~22行汇编代码所体现的情况(假设k赋值为0)。而for的主循环结构为3条指令，分别为：赋值、比较、判断跳转。具体例子同样也是18行~22行的汇编代码所体现。所以在嵌套循环中，假如其中一个循环结构需要循环n次，它所需要执行的指令量ALL为：
  1. ALL = 4 + 3n


大循环在外

    好的，根据以上所得的结论，我们可以很轻松的计算出大循环在外的整个三层循环所需要执行的指令数量，如下：
  1. i = 10000
  2. j = 1000
  3. k = 100
  5. i循环结构指令数量 = 4 + i * 3 = 30004
  6. j循环结构指令数量 = 4 + j * 3 = 3004
  7. k循环结构指令数量 = 4 + k * 3 = 304
  9. i循环结构被循环次数 = 1
  10. j循环结构被循环次数 = i
  11. k循环结构被循环次数 = i * j
  13. 整个结构指令数量 = i循环结构指令数量 * i循环结构被循环次数 + j循环结构指令数量 * j循环结构被循环次数 + k循环结构指令数量 * k循环结构被循环次数
  15. 整个结构指令数量 = 30004 * 1 + 3004 * 10000 + 304 * 1000 * 10000 = 3070070004

大循环在内

    同上，我们也可以计算出大循环在内的整个三层循环所需要执行的指令数量，如下：
  1. i = 100
  2. j = 1000
  3. k = 10000
  5. i循环结构指令数量 = 4 + i * 3 = 304
  6. j循环结构指令数量 = 4 + j * 3 = 3004
  7. k循环结构指令数量 = 4 + k * 3 = 30004
  9. i循环结构被循环次数 = 1
  10. j循环结构被循环次数 = i
  11. k循环结构被循环次数 = i * j
  13. 整个结构指令数量 = i循环结构指令数量 * i循环结构被循环次数 + j循环结构指令数量 * j循环结构被循环次数 + k循环结构指令数量 * k循环结构被循环次数
  15. 整个结构指令数量 = 304 * 1 + 3004 * 100 + 30004 * 100 * 1000 = 3000700704

结论

    可以很清楚得看出来，大循环在内所需要执行的指令数量 < 大循环在外所需执行的指令数量。表示在嵌套循环中，把大循环放入内层比把大循环放入外层的代码要高。而为什么会这样，我们可以通过数学进行计算，如下：

假设 X1,X2,X3,X4,X5,...,Xn都为正整数，他们代表着循环次数，并且 0 < X1 < X2 < X3 < X4 < X5 < ..... < Xn。
大循环在外的情况
第n层(最内层)的循环结构所需要执行的指令次数为: (4 + 3X1)X2X3X4X5...Xn
第n-1层循环结构所需要执行的指令次数为: (4 + 3X2)X3X4X5...Xn
第n-2层循环结构所需要执行的指令次数为: (4 + 3X3)X4X5...Xn
....................
第2层循环结构所需要执行指令次数为: (4 + 3Xn-1)Xn
第1层循环结构所需要执行的指令次数为: (4 + 3Xn)
总指令数为
  1. ALL1 = (4 + 3X1)X2X3X4X5...Xn + (4 + 3X2)X3X4X5...Xn + (4 + 3X3)X4X5...Xn + (4 + 3X4)X5...Xn +...+ (4 + 3Xn-1)Xn + (4 + 3Xn)
  2. ALL1 = 4X2X3X4X5...Xn + 3X1X2X3X4X5...Xn + 4X3X4X5...Xn + 3X2X3X4X5...Xn + 4X4X5...Xn + 3X2X3X4...Xn + 4X5...Xn + 3X4X5...Xn +...+ 4Xn + 3Xn-1Xn + 4 + 3Xn
  3. 合并同类项后，得
  4. ALL1 = 4 + 3X1X2X3X4X5...Xn + 7X2X3X4X5...Xn + 7X3X4X5...Xn + 7X4X5...Xn +7X5...Xn + ... + 7Xn-1Xn + 7Xn 

大循环在内的情况
第n层(最内层)的循环结构所需要执行的指令次数为: (4 + 3Xn)Xn-1Xn-2Xn-3Xn-4...X1
第n-1层循环结构所需要执行的指令次数为: (4 + 3Xn-1)Xn-2Xn-3Xn-4...X1
第n-2层循环结构所需要执行的指令次数为: (4 + 3Xn-2)Xn-3Xn-4...X1
....................
第2层循环结构所需要执行指令次数为: (4 + 3X2)X1
第1层循环结构所需要执行的指令次数为: (4 + 3X1)
总指令数为
  1. ALL2 = (4 + 3Xn)Xn-1Xn-2Xn-3Xn-4...X1 + (4 + 3Xn-1)Xn-2Xn-3Xn-4...X1 + (4 + 3Xn-2)Xn-3Xn-4...X1 + (4 + 3Xn-3)Xn-4...X1 +...+ (4 + 3X2)X1 + (4 + 3X1)
  2. ALL2 = 4X1X2X3X4...Xn-1 + 3X1X2X3X4X5...Xn + 4X1X2X3...Xn-2 + 3X1X2X3X4...Xn-1 + 4X1X2...Xn-3 + 3X1X2X3...Xn-2 + 4X1...Xn-4 + 3X1X2...Xn-3 +...+ 4X1 + 3X2X1 + 4 + 3X1
  3. 合并同类项后，得
  4. ALL2 = 4 + 3X1X2X3X4X5...Xn + 7X1X2X3X4...Xn-1 + 7X1X2X3...Xn-2 + 7X1X2...Xn-3 +7X1...Xn-4 + ... + 7X2X1 + 7X1 

结果
大循环在外的总指令数为ALL1，大循环在内的总指令数为ALL2，我们用ALL1的每一项除以ALL2中对应的每一项，结果为R，如下
  1. R1 = 4 / 4 = 1
  2. R2 = 3X1X2X3X4X5...Xn / 3X1X2X3X4X5...Xn = 1
  3. R3 = 7X2X3X4X5...Xn / 7X1X2X3X4...Xn-1 = Xn / X1 > 1
  4. R4 = 7X3X4X5...Xn / 7X1X2X3...Xn-2 = XnXn-1 / X1X2 > 1
  5. R5 = 7X4X5...Xn / 7X1X2...Xn-3 = XnXn-1Xn-2 / X1X2X3 > 1
  6. R6 = 7X5...Xn / 7X1...Xn-4 = XnXn-1Xn-2Xn-3 / X1X2X3X4 > 1
  7. ......
  8. Rm-1 = 7Xn-1Xn / 7X2X1 > 1
  9. Rm = 7Xn / 7X1 > 1
    从以上结果可以很明显的看出，除了ALL1和ALL2公有项4，3X1X2X3X4X5...Xn相除为1，其他ALL1的每一项对应除以ALL2的每一项，结果R都大于1，说明ALL1中的每一项都大于ALL2中对应的每一项，即说明了ALL1 > ALL2 ，同时也证明了大循环在外所需要执行的指令数量大于大循环在内所需要执行的指令数量，也就是将大循环放在内层时比大循环放在外层的循环效率要高的。



阅读(9078) | 评论(1) | 转发(1) |
2

上一篇：linux 下开发服务性能评估参考表

下一篇：linux调度器源码研究 - 概述（一）

给主人留下些什么吧！~~

我是茶媒网2015-02-14 15:19:31

好好学习。茶叶加盟网www.chamei.com

回复 | 举报
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6