4
$\begingroup$
#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));
$\endgroup$
  • $\begingroup$ This question brings me back to the 1980s, and how some languages store arrays in row order and some in column order. Except that you're making an array or pointers to arrays, instead of a 2D array. Thus, I'd ask why aren't you making a 2D array? $\endgroup$ – RonJohn Jan 20 at 17:04
  • $\begingroup$ go for it 🙂 I edited... $\endgroup$ – TVSuchty Jan 20 at 17:33
  • $\begingroup$ You should make it this instead: int a[10000][10000] = malloc(10000*10000*sizeof(int)); memset(&a, 0, 10000*10000*sizeof(int)); $\endgroup$ – RonJohn Jan 20 at 17:43
  • 1
    $\begingroup$ I did not found a way to compile your multidimensional array. I edited a compiling version... $\endgroup$ – TVSuchty Jan 20 at 18:00
  • 1
    $\begingroup$ @RonJohn : malloc(...);memset(...,0,...);? You mean calloc()? $\endgroup$ – Eric Towers Jan 21 at 0:14
11
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Actually, given the strange way in which the storage is allocated, the rows may not actually be contiguous (malloc() doesn't have to do the next allocation immediately after the previous allocation and won't if you're using one of the many memory allocators that do alignment on a cache block boundary for performance or isolate blocks in pages to prevent code from writing beyond the end of a malloc block.) $\endgroup$ – Brian Borchers Jan 19 at 22:53
  • $\begingroup$ @BrianBorchers true. But I would say the topic of proper allocators (preferably with aligned) is, I would say, outside the realm of this particular question. $\endgroup$ – Anton Menshov Jan 19 at 22:59
  • 2
    $\begingroup$ You can simply malloc the whole array at once to avoid this problem. The code might run faster in that case. $\endgroup$ – Brian Borchers Jan 19 at 23:53
  • $\begingroup$ This is not an array of arrays. It's an array of pointers. Brian is right; you can allocate a single contiguous block of memory and treat that as an array of arrays. $\endgroup$ – MSalters Jan 20 at 9:19
  • 1
    $\begingroup$ This a is not a two-dimensional array. $\endgroup$ – user253751 Jan 20 at 10:37
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.