Пространственное и временное расположение
Я понимаю определения терминов, но у меня возникают проблемы с применением их концепций к коду. Для упражнения нас просят описать, является ли следующий код пространственным или временным:
for (int i=0; i<10; i++) {
printf(some_array[i]);
}
Я чувствую, что это пространственная локальность, потому что при доступе к одному индексу массива, следующая ячейка памяти индекса будет доступна, как только цикл будет повторяться. Это правильный взгляд на это? Что определяет, является ли код временным или пространственным? Больше примеров было бы здорово.
4 ответа
Это немного глупо, правда. Код не является временным или пространственным.
Но временная локальность подразумевает, что вы собираетесь обращаться к одному и тому же адресу несколько раз, относительно близко во времени. Вы не делаете это здесь (если вы не считаете доступ i(Я полагаю), поэтому в процессе исключения вы можете сделать вывод, что это должна быть пространственная локализация.
Точнее, вы получаете доступ some_array[0], затем some_array[1]и т. д. и т. д. Они расположены близко друг к другу в адресном пространстве, так что, да, это может быть "опора" на пространственную локальность.
В контексте аппаратной кеш-памяти, в которой обычно возникают эти понятия, анализ, как правило, не проводится на основе адреса памяти. Локальность анализируется по доступу к блокам памяти, которые передаются между кешем и основной памятью.
Если вы думаете об этом таким образом, ваш код имеет как временную, так и пространственную локальность. Когда ваш код читает some_array[0]Если его адрес не найден в кэше, он считывается из основной памяти, и весь блок, который содержит его, копируется в кэш. Он заменяет некоторый другой блок, следуя определенной политике: например, MRU.
Затем, когда вы получаете доступ some_array[1] через некоторое время его блок уже находится в кеше, поэтому время чтения будет меньше. Обратите внимание, что вы получили доступ к тому же блоку, и в течение небольшого количества времени. Таким образом, у вас есть как пространственная, так и временная местность.
Кэш-память использует преимущества пространственной и временной локализации для обеспечения более быстрого доступа к памяти. С другой стороны, может ли ваш код воспользоваться этим - это совсем другой вопрос. Тем не менее, компилятор выполнит большинство оптимизаций за вас, поэтому вам следует позаботиться об этом только после обнаружения узкого места в профильной сессии. В средах Linux Cachegrind отлично подходит для этого.
Этот код имеет временную локальность в кэше инструкций, потому что вы повторяете код с каждым циклом (при условии, что ваш оптимизатор не развернул цикл). Он также имеет пространственную локальность в кэше данных, потому что, если вы получите доступ к элементу массива i, вы скоро получите доступ к элементам i+1, i+2 и т. Д. Если размер строки кэша данных составляет 16 байтов, а массив - 32-разрядные целые числа, то ваш кеш данных также загружал элементы 1, 2 и 3, когда вы запрашивали элемент 0 (при условии, что наш массив начинался на границе строки кэша).
Код имеет только пространственную локальность, но не имеет временной локализации - в контексте доступа к кэш-памяти.
При загрузке данных в кеш загружается целая строка / блок - следовательно, последующие обращения к точно такой же ячейке памяти, а также к адресам, которые также являются частью того же блока в кеше, будут иметь быстрое время доступа.
Есть способы оптимизировать ваш код так, чтобы столько же считывалось из кеша, а не напрямую из основной памяти: 1. Если вы можете получить доступ ко всем адресам близлежащей памяти, просто воспользовавшись первым промахом кэша, и до этого блок выгружается из кеша - тогда вы используете пространственную локализацию. 2. Если вы обращаетесь к одной и той же ячейке памяти столько раз, сколько требуется вашей программе до того, как блок в кэше будет выселен, - тогда вы воспользуетесь временной локализацией.
Примеры, такие как матричное умножение, будут иметь как временную, так и пространственную локальность.