为什么像这样遍历数组在 C 语言中效率低下？

Question

我正在看一本书，里面有这段话：

Arrays in C can be seen as a contiguous chunk of memory. More precisely, the last dimension of the array is the contiguous part. We call this the row-major order. Understanding this and the fact that a cache fault loads a complete cache line into the cache when accessing uncached data to prevent subsequent cache faults, we can see why accessing an array of dimension 10000x10000 with array[0][0] would potentially load array[0][1] in cache, but accessing array[1][0] right after would generate a second cache fault, since it is sizeof(type)*10000 bytes away from array[0][0], and therefore certainly not on the same cache line. Which is why iterating like this is inefficient:

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

你能向我解释一下他们在本段中试图解释的内容以及他们正在谈论的“缓存错误”是什么吗？

Answer 1

将数组想象成书中的页面。如果每页包含 1024 个字符，则声明为 a[100][1024] 的数组就像一本 100 页的书。通过阅读每一页来提高阅读本书的效率。也就是说，您按照 a[0][0]、a[0][1]、...、a[0][1023]、a[1][0] 的顺序进行迭代。即，您阅读整页，然后翻页。如果你遍历最左边的索引，就像从每一页读一个字符，读完一个字符后翻页，然后当你读到书的末尾时回到第 1 页阅读第二个字符。翻页是缓存错误。

为什么像这样遍历数组在 C 语言中效率低下？

Why iterating through an array like this is inefficient in C?

arrays

c

iteration

row-major-order