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

Question

Я понимаю определения терминов, но у меня возникают проблемы с применением их концепций к коду. Для упражнения нас просят описать, является ли следующий код пространственным или временным:

for (int i=0; i<10; i++) {
    printf(some_array[i]);
}

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

Answer 1

Это немного глупое упражнение, правда. Код не является временным или пространственным.

Но временная локальность подразумевает, что вы собираетесь обращаться к одному и тому же адресу несколько раз, относительно близко во времени. Здесь вы этого не делаете (если не считаете доступ к i, я полагаю), поэтому в процессе исключения вы можете заключить, что это должна быть пространственная локальность.

Точнее, вы получаете доступ к some_array[0], затем some_array[1] и т. Д. И т. Д. Они расположены близко друг к другу в адресном пространстве, так что да, это может быть "опора" на пространственную локальность.

Answer 2

В контексте аппаратной кеш-памяти, в которой обычно возникают эти понятия, анализ, как правило, не проводится на основе адреса памяти. Локальность анализируется по доступу к блокам памяти, которые передаются между кешем и основной памятью.

Если вы думаете об этом таким образом, ваш код имеет как временную, так и пространственную локальность. Когда ваш код читает some_array[0], если его адрес не найден в кеше, он читается из основной памяти, и весь содержащий его блок копируется в кеш. Он заменяет некоторый другой блок, следуя определенной политике: например, MRU.

Затем, когда вы получаете доступ к some_array[1] через некоторое время, его блок уже находится в кеше, поэтому время чтения будет меньше. Обратите внимание, что вы получили доступ к тому же блоку, и в течение небольшого количества времени. Таким образом, у вас есть как пространственная, так и временная локализация.

Кэш-память использует пространственную и временную локальность для обеспечения более быстрого доступа к памяти. С другой стороны, может ли ваш код воспользоваться этим - это совсем другой вопрос. Тем не менее, компилятор выполнит большинство оптимизаций за вас, поэтому вам следует позаботиться об этом только после обнаружения узкого места в профильной сессии. В средах Linux отлично подходит Cachegrind .

Answer 3

Этот код имеет временную локальность в кэше инструкций, потому что вы повторяете код с каждым циклом (при условии, что ваш оптимизатор не развернул цикл). Он также имеет пространственную локальность в кэше данных, потому что, если вы получите доступ к элементу массива i, вы скоро получите доступ к элементам i + 1, i + 2 и т. Д. Если размер строки кэша данных составляет 16 байтов, а массив - 32-разрядные целые числа, тогда ваш кеш данных также загружал элементы 1, 2 и 3, когда вы запрашивали элемент 0 (при условии, что наш массив начинался с границы строки кэша).

Answer 4

Код имеет только пространственную локальность, но не временную локальность - в контексте обращений к кеш-памяти.

При загрузке данных в кеш загружается целая строка / блок - следовательно, последующие обращения к точно такой жеРасположение в памяти, а также адреса, которые также являются частью одного и того же блока в кеше, будут иметь быстрое время доступа.

Есть способы оптимизировать ваш код так, чтобы столько же чтений было из кеша, а не напрямуюиз основной памяти: 1. Если вы можете получить доступ ко всем близлежащим адресам памяти, просто воспользовавшись первым отсутствием кэша, и до того, как этот блок будет удален из кэша, - тогда вы используете пространственную локальность.2. Если вы обращаетесь к одной и той же ячейке памяти столько раз, сколько требуется вашей программе до выселения блока в кеше, - тогда вы используете временную локализацию.

Примеры, такие как умножение матриц, будут иметь как временную, так и пространственнуюместонахождение.