c - 循环的执行速度随变量位置而变化

Question

版本 A:

#include<time.h>
#include<stdio.h>
int main()
{

time_t start = time(0); //denote start time
int i,j; // initialize ints
static double dst[4096][4096]; //initialize arrays
static double src[4096][4096]; //
for(i=0; i<4096; ++i){
    for(j=0; j<4096; ++j){
        dst[i][j] = src[i][j];
}
    }
time_t end = time(0); //denote end time


double time = difftime(end, start); //take difference of start and end time to determine elapsed time
printf("Test One: %fms\n",time);

}

版本 B:

#include<time.h>
#include<stdio.h>
int main()
{

time_t start = time(0); //denote start time
int i,j; // initialize ints
static double dst[4096][4096]; //initialize arrays
static double src[4096][4096]; //
for(i=0; i<4096; ++i){
    for(j=0; j<4096; ++j){
        dst[j][i] = src[j][i];
}
    }
time_t end = time(0); //denote end time


double time = difftime(end, start); //take difference of start and end time to determine elapsed time
printf("Test One: %fms\n",time);

}

使用这个程序，我已经确定，如果将数组中 i 和 j 的位置颠倒，则执行时间会延长 1 秒。

为什么会这样？

Answer 1

在您的代码中，循环意味着“逐一遍历同一行中的地址，然后转到下一行”。但是如果把i和j的位置颠倒，就是“把同一列的地址，一个一个的遍历，到下一列”。

在C语言中，多维数组放在线性地址空间中，逐字节，逐行，所以dst[i][j] = src[i][j]你的情况意味着 *(dst + 4096 * i + j) = *(src + 4096 * i + j):

*(dst + 4096 * 0 + 0) = *(src + 4096 * 0 + 0);
*(dst + 4096 * 0 + 1) = *(src + 4096 * 0 + 1);
*(dst + 4096 * 0 + 2) = *(src + 4096 * 0 + 2);
//...

将 i 和 j 颠倒意味着:

*(dst + 4096 * 0 + 0) = *(src + 4096 * 0 + 0);
*(dst + 4096 * 1 + 0) = *(src + 4096 * 1 + 0);
*(dst + 4096 * 2 + 0) = *(src + 4096 * 2 + 0);
//...

所以在第二种情况下额外的 1 秒是由于以非连续方式访问内存造成的。

您不需要自己计算时间，因为您可以在 linux/UNIX 上使用“time”命令运行您的程序:

$ time ./loop

这两种情况在我的 linux 机器上的结果:

$ time ./loop_i_j

real    0m0.244s
user    0m0.062s
sys     0m0.180s

$ time ./loop_j_i

real    0m1.072s
user    0m0.995s
sys     0m0.073s