关于嵌套循环效率研究

本文为原创，转载请注明：http://blog.chinaunix.net/uid/26772321.html引言    大家都知道，当进行嵌套循环时，大循环放最外面和放最里面所造成的执行效率会不同，本篇文章会通过汇编代码进行分析具体情况。测试环境    系统：ubuntu 14.04.1    编译器：gcc-4.8    编译命令：gcc test.c -o test -g -Wall测试代码：#include stdio.h>/* 大循环在外 */void big_in_out (void){    int i;    int j;    int k;    for (i = 10000; i != 0; i--)        for (j = 1000; j != 0; j--)            for (k = 100; k != 0; k--)                ;}/* 大循环在内 */void big_in_in (void){    int i;    int j;    int k;    for (i = 100; i != 0; i--)        for (j = 1000; j != 0; j--)            for (k = 10000; k != 0; k--)                ;}int main (int argc, char * argv[]){    return 0;}通过objdump命令，获取其汇编代码，如下：#include stdio.h>void big_in_out (void){  4004ed:    55     push %rbp  4004ee:    48 89 e5     mov %rsp,%rbp    int i;    int j;    int k;    for (i = 10000; i != 0; i--)  4004f1:    c7 45 f4 10 27 00 00     movl $0x2710,-0xc(%rbp)            # i = 10000           4004f8:    eb 2a     jmp 400524 big_in_out+0x37>                      # 跳转至400524                 for (j = 1000; j != 0; j--)  4004fa:    c7 45 f8 e8 03 00 00     movl $0x3e8,-0x8(%rbp)             # j = 1000                   400501:    eb 17     jmp 40051a big_in_out+0x2d>                      # 跳转至40051a                     for (k = 100; k != 0; k--)  400503:    c7 45 fc 64 00 00 00     movl $0x64,-0x4(%rbp)              # k = 100           40050a:    eb 04     jmp 400510 big_in_out+0x23>                      # 跳转至400510               40050c:    83 6d fc 01     subl $0x1,-0x4(%rbp)                        # k = k - 1               400510:    83 7d fc 00     cmpl $0x0,-0x4(%rbp)                        # 判断k是否为0               400514:    75 f6     jne 40050c big_in_out+0x1f>                      # 不为0跳转至40050c                int i;    int j;    int k;    for (i = 10000; i != 0; i--)        for (j = 1000; j != 0; j--)  400516:    83 6d f8 01     subl $0x1,-0x8(%rbp)                        # j = j - 1               40051a:    83 7d f8 00     cmpl $0x0,-0x8(%rbp)                        # 判断j是否为0               40051e:    75 e3     jne 400503 big_in_out+0x16>                      # j不为0跳转至400503     {    int i;    int j;    int k;    for (i = 10000; i != 0; i--)  400520:    83 6d f4 01     subl $0x1,-0xc(%rbp)                        # i = i - 1               400524:    83 7d f4 00     cmpl $0x0,-0xc(%rbp)                        # 判断i是否为0               400528:    75 d0     jne 4004fa big_in_out+0xd>                       # i不为0跳转至4004fa             for (j = 1000; j != 0; j--)            for (k = 100; k != 0; k--)                ;                                                                        }  40052a:    5d     pop %rbp  40052b:    c3     retq000000000040052c big_in_in>:void big_in_in (void){  40052c:    55     push %rbp  40052d:    48 89 e5     mov %rsp,%rbp    int i;    int j;    int k;    for (i = 100; i != 0; i--)  400530:    c7 45 f4 64 00 00 00     movl $0x64,-0xc(%rbp)              # i = 100                   400537:    eb 2a     jmp 400563 big_in_in+0x37>                       # 跳转至400563                    for (j = 1000; j != 0; j--)  400539:    c7 45 f8 e8 03 00 00     movl $0x3e8,-0x8(%rbp)             # j = 1000               400540:    eb 17     jmp 400559 big_in_in+0x2d>                       # 跳转至400559                         for (k = 10000; k != 0; k--)  400542:    c7 45 fc 10 27 00 00     movl $0x2710,-0x4(%rbp)            # k = 10000           400549:    eb 04     jmp 40054f big_in_in+0x23>                       # 跳转至40054f           40054b:    83 6d fc 01     subl $0x1,-0x4(%rbp)                        # k = k - 1           40054f:    83 7d fc 00     cmpl $0x0,-0x4(%rbp)                        # 判断k是否为0           400553:    75 f6     jne 40054b big_in_in+0x1f>                       # 不为0跳转至40054b    int i;    int j;    int k;    for (i = 100; i != 0; i--)        for (j = 1000; j != 0; j--)  400555:    83 6d f8 01     subl $0x1,-0x8(%rbp)                        # j = j - 1           400559:    83 7d f8 00     cmpl $0x0,-0x8(%rbp)                        # 判断j是否为0           40055d:    75 e3     jne 400542 big_in_in+0x16>                       # j不为0跳转至400542     {    int i;    int j;    int k;    for (i = 100; i != 0; i--)  40055f:    83 6d f4 01     subl $0x1,-0xc(%rbp)                        # i = i - 1           400563:    83 7d f4 00     cmpl $0x0,-0xc(%rbp)                        # 判断i是否为0           400567:    75 d0     jne 400539 big_in_in+0xd>                        # i不为0跳转至400539             for (j = 1000; j != 0; j--)            for (k = 10000; k != 0; k--)                ;                                                                 }  400569:    5d     pop %rbp  40056a:    c3     retq000000000040056b main>:int main (int argc, char * argv[]){  40056b:    55     push %rbp  40056c:    48 89 e5     mov %rsp,%rbp  40056f:    89 7d fc     mov %edi,-0x4(%rbp)  400572:    48 89 75 f0     mov %rsi,-0x10(%rbp)    return 0;  400576:    b8 00 00 00 00     mov $0x0,%eax}循环结果    由于是嵌套循环，即使循环0次，比如for(i = 0; i != 0; i--)情况，都需要执行4条指令，分别是：赋值、跳转、比较、判断跳转。具体的例子如18行~22行汇编代码所体现的情况(假设k赋值为0)。而for的主循环结构为3条指令，分别为：赋值、比较、判断跳转。具体例子同样也是18行~22行的汇编代码所体现。所以在嵌套循环中，假如其中一个循环结构需要循环n次，它所需要执行的指令量ALL为：ALL = 4 + 3n大循环在外    好的，根据以上所得的结论，我们可以很轻松的计算出大循环在外的整个三层循环所需要执行的指令数量，如下：i = 10000j = 1000k = 100i循环结构指令数量 = 4 + i * 3 = 30004j循环结构指令数量 = 4 + j * 3 = 3004k循环结构指令数量 = 4 + k * 3 = 304i循环结构被循环次数 = 1j循环结构被循环次数 = ik循环结构被循环次数 = i * j整个结构指令数量 = i循环结构指令数量 * i循环结构被循环次数 + j循环结构指令数量 * j循环结构被循环次数 + k循环结构指令数量 * k循环结构被循环次数整个结构指令数量 = 30004 * 1 + 3004 * 10000 + 304 * 1000 * 10000 = 3070070004大循环在内    同上，我们也可以计算出大循环在内的整个三层循环所需要执行的指令数量，如下：i = 100j = 1000k = 10000i循环结构指令数量 = 4 + i * 3 = 304j循环结构指令数量 = 4 + j * 3 = 3004k循环结构指令数量 = 4 + k * 3 = 30004i循环结构被循环次数 = 1j循环结构被循环次数 = ik循环结构被循环次数 = i * j整个结构指令数量 = i循环结构指令数量 * i循环结构被循环次数 + j循环结构指令数量 * j循环结构被循环次数 + k循环结构指令数量 * k循环结构被循环次数整个结构指令数量 = 304 * 1 + 3004 * 100 + 30004 * 100 * 1000 = 3000700704结论    可以很清楚得看出来，大循环在内所需要执行的指令数量 。表示在嵌套循环中，把大循环放入内层比把大循环放入外层的代码要高。而为什么会这样，我们可以通过数学进行计算，如下：假设 X1,X2,X3,X4,X5,...,Xn都为正整数，他们代表着循环次数，并且 0 1 2 3 4 5 n。大循环在外的情况第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)总指令数为ALL1 = (4 + 3X1)X2X3X4X5...Xn + (4 + 3X2)X3X4X5...Xn + (4 + 3X3)X4X5...Xn + (4 + 3X4)X5...Xn +...+ (4 + 3Xn-1)Xn + (4 + 3Xn)ALL1 = 4X2X3X4X5...Xn + 3X1X2X3X4X5...Xn + 4X3X4X5...Xn + 3X2X3X4X5...Xn + 4X4X5...Xn + 3X2X3X4...Xn + 4X5...Xn + 3X4X5...Xn +...+ 4Xn + 3Xn-1Xn + 4 + 3Xn合并同类项后，得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)总指令数为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)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合并同类项后，得ALL2 = 4 + 3X1X2X3X4X5...Xn + 7X1X2X3X4...Xn-1 + 7X1X2X3...Xn-2 + 7X1X2...Xn-3 +7X1...Xn-4 + ... + 7X2X1 + 7X1 结果大循环在外的总指令数为ALL1，大循环在内的总指令数为ALL2，我们用ALL1的每一项除以ALL2中对应的每一项，结果为R，如下R1 = 4 / 4 = 1R2 = 3X1X2X3X4X5...Xn / 3X1X2X3X4X5...Xn = 1R3 = 7X2X3X4X5...Xn / 7X1X2X3X4...Xn-1 = Xn / X1 > 1R4 = 7X3X4X5...Xn / 7X1X2X3...Xn-2 = XnXn-1 / X1X2 > 1R5 = 7X4X5...Xn / 7X1X2...Xn-3 = XnXn-1Xn-2 / X1X2X3 > 1R6 = 7X5...Xn / 7X1...Xn-4 = XnXn-1Xn-2Xn-3 / X1X2X3X4 > 1......Rm-1 = 7Xn-1Xn / 7X2X1 > 1Rm = 7Xn / 7X1 > 1    从以上结果可以很明显的看出，除了ALL1和ALL2公有项4，3X1X2X3X4X5...Xn相除为1，其他ALL1的每一项对应除以ALL2的每一项，结果R都大于1，说明ALL1中的每一项都大于ALL2中对应的每一项，即说明了ALL1 > ALL2 ，同时也证明了大循环在外所需要执行的指令数量大于大循环在内所需要执行的指令数量，也就是将大循环放在内层时比大循环放在外层的循环效率要高的。