Путаница между временной и пространственной локализацией в коде реальной жизни

Во-первых, ссылки на var могут быть локальными во времени или локальными в пространстве, а не локальными во времени, что является неправильной грамматикой. Незначительный момент.

Теперь к вашим вопросам.

1. Принцип Местность во времени гласит, что две инструкции ссылаются на одно и то же место в пределах относительно короткого промежутка времени. Например, в приведенном коде часто упоминается a[i], а такие инструкции, как a[i] = a[i] * 2 и a[i] = a[i] * 3, выполняются очень близко друг к другу. Если мы посмотрим на эту область, мы можем сказать, что ссылки на j и a[i] являются локальными во времени. Ссылки на i также локальны во времени, потому что i упоминается каждый раз, когда есть a[i]. Однако если последняя строка данного кода читается как a[j] = a[j] * j, то ссылки на i не будут локальными во времени, по крайней мере, в рамках внутреннего цикла^[1].

2. Принцип пространственной локальности гласит, что две инструкции ссылаются на смежные области памяти. Ссылки на a[i] являются хорошим примером этого, так как можно предположить (в большинстве случаев), что a[0] и a[1] будут в памяти рядом друг с другом.

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

[1] - Как правило, когда вы говорите о локальности, это будет в контексте данного уровня в иерархии памяти, будь то ОЗУ, кэш L1 или что-то еще. Во всех смыслах, кроме самого ограниченного, ссылки как на i, так и на j являются локальными во времени.

Написание этого ответа, поскольку я не получил его даже после прочтения других ответов на этот вопрос, нескольких других вопросов и википедии (это более запутанно).

Я думаю, что мы тратим много времени и энергии, чтобы понять терминологию, которая в данном случае немного запутанна/сложна. Мне было легче понять, когда я не обращал внимания на термины «пространственный» и «временной».

Начнем с основ.

Давайте попробуем понять, что такое кэш — место, доступ к которому осуществляется быстрее, чем к основной памяти. Это классно. Но это место ограничено и дорого, поэтому нужно использовать его с умом. Но как бы вы (или ОС) решили, что помещать в кеш, а что нет? Должен быть какой-то способ узнать, что нам понадобится в будущем… ах, предсказания будущего! (Отчет меньшинства! Звоните в колокольчики?).

Должен быть какой-то способ определить, что понадобится программе в будущем. Используя здравый смысл и код, мы можем сказать, что некоторые части кода повторяются по своей природе — например, циклы! Если внутри цикла есть переменная i, вы знаете, что в ближайшем будущем к ней будут обращаться снова и снова. Это принцип временной локальности. я могу быть внесен в кеш, так как он временно локальный.

В другой области, если код использует любую линейную структуру данных (пример: массив) и это тоже в цикле с приращением в индексе, то легко увидеть, что, хотя в настоящее время требуется только 3-е место (например) этой структуры данных, очень скоро также потребуются следующие местоположения, потому что индекс увеличивается на 1 для этой линейной структуры данных. Так что было бы здорово, если бы мы добавили данные и из следующих нескольких местоположений. Это принцип пространственной локальности. Следующие несколько местоположений могут быть помещены в кеш, поскольку они пространственно локальны.

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

Внешняя петля является примером пространственной локализации. Он последовательно увеличивает адрес, который вызывает внутренний цикл for.

Внутренняя петля демонстрирует временную локальность. К одному и тому же адресу памяти обращаются десять раз подряд и каждый раз умножают на j.

Что касается ваших первых двух вопросов, то и i, и j (счетчики циклов) являются очень хорошими примерами временной локальности.

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

Давайте начнем с определения как временной, так и пространственной локализации.

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

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

sum = 0;
for (i = 0; i < arr.length; i++)
  sum += arr[i];
return sum;

Теперь, глядя на этот пример, здесь переменная sum используется снова и снова, что показывает временную местность, а затем значения массива arr доступны в порядке, т.е. arr[0], arr[1], arr [2] ,... и т. д., и который показывает Пространственное местоположение, так как массивы являются непрерывными (смежными) блоками памяти, поэтому данные извлекаются рядом с текущим местоположением памяти.

Теперь, глядя на этот пример

for(i = 0; i < 20; i++)
    for(j = 0; j < 10; j++)
        a[i] = a[i]*j;

Здесь мы видим временную локальность, поскольку a[i] во втором цикле используется снова и снова, а затем доступ к переменной j осуществляется в порядке, который показывает пространственную локальность.