c - 循环中的空间局部性

据我了解，空间局部性与在不久的将来使用的附近内存有关。但是我想知道循环是否执行多次，这是否会导致良好的空间局部性？提前致谢，如果我难以理解，请见谅。

最佳答案

循环的迭代次数不一定会影响空间局部性。循环正在做什么。

实际上，空间局部性的关键确实与缓存行有关。简单来说，将访问限制为少量不同缓存行的程序将展示更多缓存命中，从而获得更好的性能。访问大量不同缓存行的程序将遇到更多缓存未命中，从而降低性能。

非常好的空间局部性:

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

这个循环的空间局部性非常差。它正在访问整个内存中的随机位置。每次循环迭代您可能会期望它反弹到不同的缓存行。这会导致各种缓存未命中，缓存本质上变得毫无用处。

关于c - 循环中的空间局部性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23486608/