关于＜高质量C/C++编程指南＞中提到的多重for循环效率问题

柏仔

最近在看这本书的时候看到他的
［建议4-4-1］在多重循环中，如果有可能，应当将最长的循环放在最内层，最短的循环放在最外层，以减少CPU跨切循环层的次数。
他的意思是这样的效率高些。于是我写了for1和for2两个程序来作比较。用time运行的结果却分别是：

1. 
   
2. //for1
   
3. real    0m4.089s
   
4. user    0m1.761s
   
5. sys     0m1.023s
   

复制代码

1. 
   
2. //for2
   
3. real    0m15.376s
   
4. user    0m12.003s
   
5. sys     0m0.958s
   

复制代码

for1和for2的代码：
[php]
//for1
#include <stdio.h>
#include "for.h"

int main(void)
{
        for (row=0; row<ROW_COUNT; row++)
        {
                for (col=0; col<COL_COUNT; col++)
                {
                        a[row][col] = 0;
                }
        }

        return 0;
}
[/php]
[php]
//for2
#include <stdio.h>
#include "for.h"

int main(void)
{
        for (col=0; col<COL_COUNT; col++)
        {
                for (row=0; row<ROW_COUNT; row++)
                {
                        a[row][col] = 0;
                }
        }
        return 0;
}
[/php]

[php]
//for.h
int row;
int col;
#define ROW_COUNT 1000000
#define COL_COUNT 100
static int a[ROW_COUNT][COL_COUNT];
[/php]

for2循环就是按他的建议来写的，但占用时间却明显比for1多
还有，“以减少CPU跨切循环层的次数”这一句如何理解？我不明白原理
谢谢

biinn

Post by 柏仔
最近在看这本书的时候看到他的
［建议4-4-1］在多重循环中，如果有可能，应当将最长的循环放在最内层，最短的循环放在最外层，以减少CPU跨切循环层的次数。

没读过这本书，但感觉这个建议有问题：两个循环都是判断跳转指令，没有区别。两种方法中， CPU 跨切循环层的次数是相同的。将最长的循环放在最内层并不能减少CPU跨切循环层的次数。

在两次相邻的内循环中，对于你的 for1 的例子，a[row][col] 和 a[row][col+1] 的内存是相邻的，寻址变量（指针）++ 就实现了。但对于你的 for2 的例子，a[row][col] 和 a[row+1][col] 的内存是不相邻的，必须用 base+offset, offset+=COL_COUNT 来寻址。

所以 for1 要快。

soloforce

Post by biinn

在两次相邻的内循环中，对于你的 for1 的例子，a[row][col] 和 a[row][col+1] 的内存是相邻的，寻址变量（指针）++ 就实现了。但对于你的 for2 的例子，a[row][col] 和 a[row+1][col] 的内存是不相邻的，必须用 base+offset, offset+=COL_COUNT 来寻址。

所以 for1 要快。

我原先也以为是数组寻址开销的差异。后来看看生成的汇编，生成的代码是对称的。也就是说应该不是数组寻址带来的问题。

但把数组赋值改成  x=1 以后， for1 和for2的执行时间相差无几，说明数组引用的确有所不同。

期待明确的解释

woolzey

似乎是cache的问题。for1的cache命中率比较高，for2里面每次赋值的内存间隔太大，所以cache效率比较低。

我也是猜的，没有实验。

biinn

在上一贴中，我只是凭概念猜想了一下，其中有一个错误：原代码中的 a 是 int 类型，所以即使访问两个相邻的成员, 寻址指针也要加 4， 不能 ++。如果 a 是 char 类型，才可能用 ++ 寻址。但编译时要用优化参数 -O.

经过试验，在我的电脑上 for1.c 和 for2.c 的汇编代码类似, 只是 100 和 1000000 调换了位置, 而且二者的执行时间也几乎是相同的, 没有出现像楼主那么大的差别. 建议楼主多运行几次, 再比较结果.

当我将 a 改为 char 类型后，编译时加上-O 参数，汇编代码的确是用 inc 指令寻址的。 但不解的事情是：此时两个程序不加优化参数编译后的汇编代码是对称的，但执行时间差了 4 倍，而且比 int 的程序慢大约 300 倍。

int 型的 for1.c 的执行时间：  0.005s (real)
char 型的 for1.c 的执行时间：1.4s(real)
char 型的 for1.c 的执行时间：5.6s(real)

为什么 char 的比 int 的慢? 不明白......

mousse

都是大牛人阿 ...........

自然平衡

Post by biinn
在上一贴中，我只是凭概念猜想了一下，其中有一个错误：原代码中的 a 是 int 类型，所以即使访问两个相邻的成员, 寻址指针也要加 4， 不能 ++。如果 a 是 char 类型，才可能用 ++ 寻址。但编译时要用优化参数 -O.

经过试验，在我的电脑上 for1.c 和 for2.c 的汇编代码类似, 只是 100 和 1000000 调换了位置, 而且二者的执行时间也几乎是相同的, 没有出现像楼主那么大的差别. 建议楼主多运行几次, 再比较结果.

当我将 a 改为 char 类型后，编译时加上-O 参数，汇编代码的确是用 inc 指令寻址的。 但不解的事情是：此时两个程序不加优化参数编译后的汇编代码是对称的，但执行时间差了 4 倍，而且比 int 的程序慢大约 300 倍。

int 型的 for1.c 的执行时间：  0.005s (real)
char 型的 for1.c 的执行时间：1.4s(real)
char 型的 for1.c 的执行时间：5.6s(real)

为什么 char 的比 int 的慢? 不明白......

指针++表示指向下一个类型单元，并不是地址简单地+1。
因为字节对齐关系，访问int比char快。

woolzey

char没有对齐问题吧

int需要4字节对齐，char本身就只有1个字节，按理说没有对齐问题。

Post by 自然平衡
指针++表示指向下一个类型单元，并不是地址简单地+1。
因为字节对齐关系，访问int比char快。

自然平衡

Post by woolzey
char没有对齐问题吧

int需要4字节对齐，char本身就只有1个字节，按理说没有对齐问题。

嗯，应该是和CPU字长对齐有关，和CPU字长相等的类型比不相等的类型效率要高。

biinn

Post by 自然平衡
指针++表示指向下一个类型单元，并不是地址简单地+1。

我说的是汇编代码，不是 c...