循环中的空间位置

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

这个循环具有非常差的空间局部性.它正在访问整个内存的随机位置.每次循环迭代,您可能都希望它反弹到不同的缓存行.这将导致各种缓存未命中,并且缓存基本上变得无用.