二维数组上的缓存未命中

Question

我对机器如何在内存中存储二维数组有疑问。为了更清楚，我将向您展示我的代码。我在主循环中以这种方式定义一个二维数组:

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);
}

其中 DIM 是用户定义的变量，internalNode 是一个结构体。在函数 CalculusOnGrid 中，我将在网格(我的二维数组)上进行微积分:

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);

所以我要搜索网格当前点 (i,j) 的 4 个邻居。

这是我的问题:我将在上部和下部元素(即 tab[i+1][] 和 tab[i-1][])或右侧执行缓存未命中和左边的元素？ (也就是说tab[][j+1]和tab[][j-1])

您对加快我的代码速度并减少缓存未命中次数有何建议？

我希望以明确的方式提出这个问题。如果不是这样，请问我任何你想要的!

谢谢!

亚历山德罗

Answer 1

缓存未命中是您应避免使用基于指针的查找表来模拟动态数组的众多原因之一。

相反，使用二维数组:

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

free(tab);

现在内存将是相邻的，性能应该会好得多。