c -循环中的空间局部性

Question

据我所知，空间局部性与附近将来使用的附近内存有关。然而，我想知道如果一个循环被执行了很多次，这是否会导致良好的空间局部性?提前感谢，如果我的话让你难以理解，我很抱歉。

Answer 1

循环的迭代次数不一定影响空间局部性。所做的循环所做的

在实践中，空间局部性的关键确实与缓存行有关。简单地说，一个程序将其访问限制在少量的不同的缓存行，将显示更多的缓存命中，从而获得更好的性能。访问大量不同缓存线的程序将遇到更多的缓存丢失，从而降低性能。

非常好的空间局部性:

uint8_t g_array[2];
void test(void) {
    int i, a=0;
    for (i=0; i<10000000; i++) {
        a += g_array[i % 2];      // Only ever accesses [0] or [1]
    }
}

这个循环具有很好的空间局部性。数组很小，循环只访问下标0或1。

---

仍然是良好的空间局部性:

uint8_t g_array[CACHELINE_SIZE] __attribute__ ((aligned (CACHELINE_SIZE)));
void test(void) {
    int i, a=0;
    for (i=0; i<10000000; i++) {
        a += g_array[i % CACHELINE_SIZE];
    }
}

这里我们有一个数组，它正好与一条缓存行对齐。由于循环只访问该数组中的元素，因此我们可以说它具有良好的空间局部性——访问只会触及该缓存行。

---

空间局部性差:

uint8_t g_array[RAND_MAX * CACHELINE_SIZE]
    __attribute__ ((aligned (CACHELINE_SIZE)));
void test(void) {
    int i, a=0;
    for (i=0; i<10000000; i++) {
        int r = rand();
        a += g_array[(r*CACHELINE_SIZE) + (i%CACHELINE_SIZE)];
    }
}

这个循环的空间局部性非常差。它访问内存中的随机位置。每次循环迭代，您都可能期望它跳转到不同的缓存行。这将导致各种类型的缓存丢失，并且缓存实际上变得无用。