Пространственное расположение в петлях

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

Этот цикл имеет удивительно плохую пространственную локализацию. Это доступ к случайным местам по всей памяти. На каждой итерации цикла вы, вероятно, можете ожидать, что она отскочит к другой строке кэша. Это вызовет все виды кеша, и кеш по сути станет бесполезным.