Row-major or column-major order?

Row-major order is used in C/C++/Objective-C (for C-style arrays) Column-major order is used in MATLAB, GNU Octave. So accessing them in a same way we store should increase cache hits.

To test it, I wrote two simple program.

Test1:

#define SIZE_X 10000
#define SIZE_Y 10000
int main()
{
 int i,j;
 int b = 0;
 int a[SIZE_X][SIZE_Y];
 
 for(i = 0; i < SIZE_X; i++){
  for(j = 0; j < SIZE_Y; j++){
   b = a[i][j];   // Difference 
  } 
 }
 return 0;
}

test2:

#define SIZE_X 10000
#define SIZE_Y 10000
int main()
{
 int i,j;
 int b = 0;
 int a[SIZE_X][SIZE_Y];
 
 for(i = 0; i < SIZE_X; i++){
  for(j = 0; j < SIZE_Y; j++){
   b = a[j][i];    // Difference
  } 
 }
 return 0;
}

Difference between two program is in 12th row. Typically, caches are designed so that if a value is read in from memory, that value, plus a block of values near that, are brought into the cache. That way, when you iterate over an array, most probably you will find adjacent values in the cache.

Default stack size for Ubuntu 18.04 is 8192 kbytes. You can check it with “ulimit -all” . Lets change it for current session to emphasize time difference between two code. Follow and do below:

• sudo su
• ulimit -s 819200
• gcc test1.c -o test1
• gcc test2.c -o test2

Lets see test results: