首页 > 其他 > 详细

关于嵌套循环效率研究

时间：2015-02-12 02:27:42      阅读：331      评论：0      收藏：0      [点我收藏+]

本文为原创，转载请注明：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 ，同时也证明了大循环在外所需要执行的指令数量大于大循环在内所需要执行的指令数量，也就是将大循环放在内层时比大循环放在外层的循环效率要高的。



关于嵌套循环效率研究

原文：http://blog.chinaunix.net/uid-26772321-id-4823545.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！