Almost identical code with different runtimes - Why?

Question

I am testing two almost identical codes with a slight difference in one of the for loops. The first uses three cycles to repeat the indices y , z , x , and the second repeated x , z , y .

My question is, why is there a difference in user time and wall clock? Is it because of the location of the memory in one code and another?

test_1.c:

 #define N 1000 // Matrix definition long long int A[N][N],B[N][N],R[N][N]; int main() { int x,y,z; char str[100]; /*Matrix initialization*/ for(y=0;y<N;y++) for(x=0;x<N;x++) { A[y][x]=x; B[y][x]=y; R[y][x]=0; } /*Matrix multiplication*/ for(y=0;y<N;y++) for(z=0;z<N;z++) for(x=0;x<N;x++) { R[y][x]+= A[y][z] * B[z][x]; } exit(0); } 

The difference in the second code (test_2.c) in the last loop:

 for(x=0;x<N;x++) for(z=0;z<N;z++) for(y=0;y<N;y++) { R[y][x]+= A[y][z] * B[z][x]; } 

If I type / user / bin / time -v./test_1, I get the following statistics:

 Command being timed: "./test_1" User time (seconds): 5.19 System time (seconds): 0.01 Percent of CPU this job got: 99% Elapsed (wall clock) time (h:mm:ss or m:ss): 0:05.22 

So far, / user / bin / time -v./test_2 gives the following statistics:

 Command being timed: "./test_2" User time (seconds): 7.75 System time (seconds): 0.00 Percent of CPU this job got: 99% Elapsed (wall clock) time (h:mm:ss or m:ss): 0:07.76 

Answer 1

Basically, you access memory in a different pattern - your first approach is much friendlier to the memory cache, because you get access to a lot of data in one area, and then move on to the next piece of memory, etc.

If you need a real analogy in the world, imagine that you are delivering leaflets to 10 different roads (AJ), each of which has house numbers 1-10. You can deliver A1, A2, A3 ... A10, B1, B2, B3 ... B10, etc. Or you can deliver A1, B1, C1 ... J1, A2, B2, C2 ... etc. Obviously, the first method will be more effective. This is exactly the same as in the computer’s memory - it’s more efficient for accessing the “near” memory that you recently accessed than a jump.