Cache Misses on a two dimensional array

Question

I have a doubt on how the machines stores a two dimensional array in memory. I'll present you my code in order to be clearer. I'm defining a two dimensional array in this way, in my main loop:

int main()
{
    int i;
    internalNode**tab =(internalNode **)malloc(sizeof(internalNode *)* DIM);
    for (i=0; i<DIM ; i++)
        tab[i] = (internalNode *)malloc(sizeof(internalNode) * DIM);

    //CODE

    CalculusOnGrid(tab,DIM);
}

Where DIM is a user defined variable and internalNode is a structure. In the function CalculusOnGrid i'm going to do this calculus on the grid ( my two dimensional array):

for(i=1;i<DIM-1;i++)
    for(j=1;j<DIM-j;i++)
        tab[i][j].temperature_new = 0.25*tab[i+1][j].temperature+tab[i-1][j].temperature + tab[i][j+1].temperature + tab[i][j-1].temperature);

So i'm going to search for the 4 neighbors of my current point (i,j) of the grid.

Here there is my question: I'm going to do a Cache Miss on the upper and below element ( that's to say tab[i+1][] and tab[i-1][]) or on the right and left elements? (that's to say tab[][j+1] and tab[][j-1])

What's your suggestion for speeding up my code and reduce the number of Cache misses?

I hope that the question is proposed in a clear way. If this is not the case, ask me whatever you want!

Thank you!

Alessandro

differency between array of arrays and 2 dimentional array http://www.c-faq.com/aryptr/dynmuldimary.html — Boiethios, Apr 13 '16 at 11:34

Lundin · Accepted Answer · 2016-04-13T11:43:42.357

1

Cache misses is one of many reasons why you should avoid using pointer-based lookup tables to emulate dynamic arrays.

Instead, use a 2D array:

internalNode (*tab)[DIM] = malloc( sizeof(internalNode[DIM][DIM]) );

free(tab);

Now the memory will be adjacent and performance should be much better.

edited Apr 13 '16 at 11:43

answered Apr 13 '16 at 11:35

Lundin

195,001
40
254
396

As long as DIM isn't too big, I think that should be mentioned. – 2501 Apr 13 '16 at 11:59
Thank you! So in this way i emulare a 2D array using 1D array? – Alessandro Bertini Apr 13 '16 at 13:16
@AlessandroBertini No, emulating a 2D array would have been `type* ptr = malloc (x*y*sizeof(*ptr))`, aka a "mangled array". This is a true 2D array, I just simplified the syntax a bit to allow you to do `tab[x][y]` rather than the ugly `(*tab)[x][y]`. [Long-winded explanation of why the above works](http://stackoverflow.com/a/32050859/584518). – Lundin Apr 13 '16 at 13:25
Ok, so if i want to pass this 2D array to a function, let's say an Initialization function, in the main loop, what's the best way to do it? – Alessandro Bertini Apr 13 '16 at 14:38
@AlessandroBertini Probably `void func (size_t x, size_t y, int array[x][y])`. The array parameter will decay into a pointer to the first element, that is an array pointer `int(*)[y]`, the same type as you have in the caller. – Lundin Apr 14 '16 at 07:48

Cache Misses on a two dimensional array

1 Answers1