有效地迭代数组和行主要顺序

C 中的数组可以看作是一块连续的内存。更准确地说，数组的最后一个维度是连续的部分。我们称之为行主要订单。了解这一点以及缓存故障在访问未缓存数据时将完整缓存行加载到缓存中以防止后续缓存故障的事实，我们可以看到为什么使用 array[0][0] 访问维度 10000x10000 的数组可能会在缓存中加载 array[0][1]，但是访问 array[1][0] 是正确的之后会产生第二个缓存故障，因为它距离 array[0][0] 只有 4 个字节，因此肯定不会在同一个缓存线上。这就是为什么像这样迭代是低效的：

#define ARRLEN 10000
int array[ARRLEN][ARRLEN];

size_t i, j;
for (i = 0; i < ARRLEN; ++i)
{
    for(j = 0; j < ARRLEN; ++j)
    {
        array[j][i] = 0;
    }
}

像这样迭代更有效：

#define ARRLEN 10000
int array[ARRLEN][ARRLEN];

size_t i, j;
for (i = 0; i < ARRLEN; ++i)
{
    for(j = 0; j < ARRLEN; ++j)
    {
        array[i][j] = 0;
    }
}

同样，这就是为什么在处理具有一维和多个索引的数组时（为了简单起见，使用索引 i 和 j，这里说 2 维）重要的是迭代遍历数组，如下所示：

#define DIM_X 10
#define DIM_Y 20

int array[DIM_X*DIM_Y];

size_t i, j;
for (i = 0; i < DIM_X; ++i)
{
    for(j = 0; j < DIM_Y; ++j)
    {
        array[i*DIM_Y+j] = 0;
    }
}

或者使用 3 维和索引 i，j 和 k：

#define DIM_X 10
#define DIM_Y 20
#define DIM_Z 30

int array[DIM_X*DIM_Y*DIM_Z];

size_t i, j, k;
for (i = 0; i < DIM_X; ++i)
{
    for(j = 0; j < DIM_Y; ++j)
    {
        for (k = 0; k < DIM_Z; ++k)
        {
            array[i*DIM_Y*DIM_Z+j*DIM_Z+k] = 0;
        }
    }
}

或者以更通用的方式，当我们有一个 N1 x N2 x … x Nd 元素的数组时， d 维度和索引标记为 n1，n2，…，nd 偏移量计算如下

图片/公式取自： https ： //en.wikipedia.org/wiki/Row-major_order