Spacial Locality in loops

问题:

From what I understand, spacial locality has to do with nearby memory being used in the nearby future. However I was wondering if a loop is executed many times, does this lead to good spacial locality? Thanks in advance, and sorry if I'm hard to understand.

回答1:

The number of iterations of a loop doesn't necessarily affect spatial locality. What the loop is doing does.

In practice, the key to spatial locality really has to do with cache lines. In simple terms, a program that limits its accesses to a small number of different cache lines will exhibit more cache hits, and thus better performance. A program that accesses a large number of different cache lines will encounter more cache misses, and thus lower peformance.

Very good spatial locality:

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

This loop has very good spatial locality. The array is tiny, and the loop only ever accesses indices 0 or 1.

---

Still good spatial locality:

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

Here we have an array that is aligned to exactly one cache line. Since the loop only accesses elements in that array, we can say it has good spatial locality - accesses will only ever touch that one cache line.

---

Poor spatial locality:

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

This loop has remarkably poor spatial locality. It is accessing random locations all over memory. Every loop iteration you can probably expect it to bounce to a different cache line. This will cause all kinds of cache misses, and the cache essentially becomes useless.