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?

possible duplicate of Time taken:Row major sum Column major sum — Raymond Chen
– Raymond Chen, Commented Nov 19, 2013 at 6:19
The rather formal explanation you provide suggests that this is a homework assignment rather than a practical programming problem. (Don't forget to credit SO when you turn in your assignment.) — Raymond Chen
– Raymond Chen, Commented Nov 19, 2013 at 6:55
It is actually part of my learning program, not a classroom assignment. It is for my personal knowledge and future application. I have no issue crediting SO for the answer, I am just puzzled as to what a clear explanation would be. — Curseive
– Curseive, Commented Nov 19, 2013 at 6:56

raof01 · Accepted Answer · 2013-11-19 11:54:54Z

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

Vinay Shukla · Accepted Answer · 2013-11-19 06:46:07Z

0

#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.

edited Nov 19, 2013 at 6:46

answered Nov 19, 2013 at 6:40

Vinay Shukla

1,84213 silver badges43 bronze badges

4 Comments

Curseive Over a year ago

I actually do have stdio.h included in my code. I must have missed it in copying it over. It would appear that it has to do with my cache size as well, which is 3 MB. Any value smaller than 4096 will return a 0.00... result for both equations.

alk Over a year ago

How does this answer the question, please? And btw, this "Maybe the issue is that you have not included stdio.h." is nonsense.

Siyuan Ren Over a year ago

@Curseive: You know it is about cache. What else do you want to know?

Curseive Over a year ago

@C.R. I'm trying to determine the behavior once the array is too large for cache.

Collectives™ on Stack Overflow

Execution speed of loops varies with variable position

2 Answers 2

Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related