关于嵌套循环效率研究

本文为原创，转载请注明：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                       retq

000000000040052c <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                       retq

000000000040056b <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 = 10000
j = 1000
k = 100

i循环结构指令数量 = 4 + i * 3 = 30004
j循环结构指令数量 = 4 + j * 3 = 3004
k循环结构指令数量 = 4 + k * 3 = 304

i循环结构被循环次数 = 1
j循环结构被循环次数 = i
k循环结构被循环次数 = i * j

整个结构指令数量 = i循环结构指令数量 * i循环结构被循环次数 + j循环结构指令数量 * j循环结构被循环次数 + k循环结构指令数量 * k循环结构被循环次数

整个结构指令数量 = 30004 * 1 + 3004 * 10000 + 304 * 1000 * 10000 = 3070070004

大循环在内

    同上，我们也可以计算出大循环在内的整个三层循环所需要执行的指令数量，如下：

i = 100
j = 1000
k = 10000

i循环结构指令数量 = 4 + i * 3 = 304
j循环结构指令数量 = 4 + j * 3 = 3004
k循环结构指令数量 = 4 + k * 3 = 30004

i循环结构被循环次数 = 1
j循环结构被循环次数 = i
k循环结构被循环次数 = i * j

整个结构指令数量 = i循环结构指令数量 * i循环结构被循环次数 + j循环结构指令数量 * j循环结构被循环次数 + k循环结构指令数量 * k循环结构被循环次数

整个结构指令数量 = 304 * 1 + 3004 * 100 + 30004 * 100 * 1000 = 3000700704

结论

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

假设 X₁,X₂,X₃,X₄,X₅,...,X_n都为正整数，他们代表着循环次数，并且 0 < X₁ < X₂ < X₃ < X₄ < X₅ < ..... < X_n。
大循环在外的情况
第n层(最内层)的循环结构所需要执行的指令次数为: (4 + 3X₁)X₂X₃X₄X₅...X_n
第n-1层循环结构所需要执行的指令次数为: (4 + 3X₂)X₃X₄X₅...X_n
第n-2层循环结构所需要执行的指令次数为: (4 + 3X₃)X₄X₅...X_n
....................
第2层循环结构所需要执行指令次数为: (4 + 3X_n-1)X_n
第1层循环结构所需要执行的指令次数为: (4 + 3X_n)
总指令数为

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 + 3X_n)X_n-1X_n-2X_n-3X_n-4...X₁
第n-1层循环结构所需要执行的指令次数为: (4 + 3X_n-1)X_n-2X_n-3X_n-4...X₁
第n-2层循环结构所需要执行的指令次数为: (4 + 3X_n-2)X_n-3X_n-4...X₁
....................
第2层循环结构所需要执行指令次数为: (4 + 3X₂)X₁
第1层循环结构所需要执行的指令次数为: (4 + 3X₁)

总指令数为

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

结果
大循环在外的总指令数为ALL₁，大循环在内的总指令数为ALL₂，我们用ALL₁的每一项除以ALL₂中对应的每一项，结果为R，如下

R1 = 4 / 4 = 1
R2 = 3X1X2X3X4X5...Xn / 3X1X2X3X4X5...Xn = 1
R3 = 7X2X3X4X5...Xn / 7X1X2X3X4...Xn-1 = Xn / X1 > 1
R4 = 7X3X4X5...Xn / 7X1X2X3...Xn-2 = XnXn-1 / X1X2 > 1
R5 = 7X4X5...Xn / 7X1X2...Xn-3 = XnXn-1Xn-2 / X1X2X3 > 1
R6 = 7X5...Xn / 7X1...Xn-4 = XnXn-1Xn-2Xn-3 / X1X2X3X4 > 1
......
Rm-1 =  7Xn-1Xn / 7X2X1 > 1
Rm = 7Xn / 7X1 > 1

    从以上结果可以很明显的看出，除了ALL₁和ALL₂公有项4，3X₁X₂X₃X₄X₅...X_n相除为1，其他ALL₁的每一项对应除以ALL₂的每一项，结果R都大于1，说明ALL₁中的每一项都大于ALL₂中对应的每一项，即说明了ALL₁ > ALL₂ ，同时也证明了大循环在外所需要执行的指令数量大于大循环在内所需要执行的指令数量，也就是将大循环放在内层时比大循环放在外层的循环效率要高的。