CODEWITHSUNDEEP
carrayscaching
Alessandro Bertini
Alessandro Bertini

Reputation: 23

Cache Misses on a two dimensional array

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

Upvotes: 0

Views: 1171

Answers (1)

Lundin
Lundin

Reputation: 214840

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.

Upvotes: 1

Related Questions