Memory Management - Why certain initializations order are faster?

Question

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

float timedifference_msec(struct timeval t0, struct timeval t1) {
    return (t1.tv_sec - t0.tv_sec) * 1000.0f + (t1.tv_usec - t0.tv_usec) / 1000.0f;
}

int main()
{
    struct timeval t0;
    struct timeval t1;
    float elapsed;

    int ** a = malloc(10000*sizeof(int*));
    for(int i = 0; i < 10000; i++){
        a[i] = malloc(10000*sizeof(int));
    }

    gettimeofday(&t0, 0);
    for(int i = 0; i < 10000; i++){
        for(int j = 0; j< 10000; j++){
            a[j][i] = 0;
        }
    }
    gettimeofday(&t1, 0);

    elapsed = timedifference_msec(t0, t1);
    printf("%f\n", elapsed);


    gettimeofday(&t0, 0);
    for(int i = 0; i < 10000; i++){
        for(int j = 0; j< 10000; j++){
            a[i][j] = 0;
        }
    }
    gettimeofday(&t1, 0);
    elapsed = timedifference_msec(t0, t1);
    printf("%f", elapsed);

    return 0;
}

Why exactly is the first implementation faster than the other?

Edit: Why would I be faster, when I substitute:

int (*a)[num]  = malloc(num*num*sizeof(int));
memset(&a, 0, 10000*10000*sizeof(int));

Answer 1

Such an effect happens because of how the data of the int** a is stored in memory (as per C/C++). This question on StackOverflow has answers with some more details (in particular, a difference between int** and int[][] that many users noted in the comments), and how it

looks like an array of arrays - it's just laid out contiguously in memory.

It's worth to mention, that since several mallocs are used, the whole array might not be stored completely contiguously in memory; however, each individual row – will. Here comes the catch: to take full advantage of the "partial" contiguous layout of the array in memory, you want to access the elements (if possible) in the order they are stored. That makes the code cache-friendly. This question on making the code cache-friendly has many good advices, but here, the memory layout is the important one.

Looking inside the memory of how the array is stored is very useful: this StackOverflow answer illustrates that on a concrete example for a static array. In C/C++, the layout is row-major (as opposed to Matlab and Fortran); therefore, accessing the array row-wise is advantageous:

a[0][0] = 0.;
a[0][1] = 0.;
a[0][2] = 0.;
...
a[0][N-1] = 0.;
a[1][0] = 0.;
a[1][1] = 0.;
a[1][2] = 0.;
...
a[N-1][0] = 0.;
a[N-1][1] = 0.;
...
a[N-1][N-1] = 0.;

where N is the size of the array (assuming row-size == column-size).

Now, this piece corresponds to the "unwrapped" second implementation:

for(int i = 0; i < 10000; i++){
    for(int j = 0; j< 10000; j++){
        a[i][j] = 0;
    }
}

which is much faster on my machine (gcc -O3): 1577.997070 ms (for the first variant) vs 45.952000 ms (for the second one). The actual numbers are not accurate and not important, it's the qualitative comparison that matters.

It's important to note, that mallocs don't have to do (but can) the next allocation contiguously (thanks to @Brian Borcher's comment). Therefore, with your way of allocating the int ** a array, you are prone to not walk fully contiguously in memory with the aforementioned loop; however, you still are taking much more advantage of the code cache-friendliness with the second implementation.

To make the code even faster, consider:

• allocating the whole array a at once with one malloc of the appropriate size
• treating a matrix as a 1-D array using a[i+j*numRows] indexing
• read the best practices of correctly allocating multi-dimensional arrays
• use an allocator that gives you data aligned in memory. mkl_malloc is one example; however, there are many other possibilities, and you might already have one available based on the libraries already used in your application. Choose an appropriate alignment.

So, it's the second implementation that is faster.

Answer 2

Noting correctly that this is an array of pointers to arrays of ints:

In the first version, the code is accessing element 0 of each successive array of ints, then element 1, etc. That means it is changing which pointer (to an array of ints) is being dereferenced on each inner iteration.

In the second version, the code is accessing each element of the 0'th array of ints, then each element of the 1'th array of ints, etc. That means it is changing which pointer (to an array of ints) is being dereferenced on each outer iteration.

This means the second version may cache the pointer (i.e in a register) for each outer iteration, and reuse it for each inner iteration. So the second version will make many fewer pointer dereferences, saving time.