Execution speed of loops varies with variable position

Question

Version 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);

}

Version 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);

}

Using this program, I have determined that if you reverse the positions of i and j in the arrays, it takes 1 second longer to execute.

Why is this happening?

Answer 1

In your code, the loop means that "traverse the address in the same row, one by one, then go to next line". But if you reverse the positions of i and j, this means that "traverse the address in the same column, one by one, the go to next column".

In C, multi-dimensional array are put on linear address space, byte by byte, then line by line, so dst[i][j] = src[i][j] in your case means *(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);
//...

while reversed i and j means:

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

So the extra 1 second in second case is cause by accessing memory in a non-contigous manner.

You don't need to do time calculation yourself, because you can run your program with "time" command on linux/UNIX:

$ time ./loop

The results on my linux box for the 2 cases:

$ 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

Answer 2

#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(j=0; j<4096; ++j){
    for(i=0; i<4096; ++i){
        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 tested and it is giving me this o/p Test One: 0.000000ms in both cases after reversing and normal. I used gcc compiler.

Maybe the issue is that you have not included stdio.h .I experienced the same behavior once when I did not include stdio.h.

Something related to memory(in stack) allocation during compile time could be possible reason.