Временная локальность

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

Сущность явления

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

Например, в цикле, который суммирует элементы массива, переменная-аккумулятор (например, sum) многократно считывается и записывается на каждой итерации. Это классический случай временной локальности. Аналогично, код самого цикла (инструкции) многократно выполняется, что также демонстрирует временную локальность на уровне команд.

Отличие от пространственной локальности

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

Вместе эти два принципа образуют основу локальности ссылок (англ. locality of reference), которая описывает предсказуемость доступа к памяти в типичных программах.

Роль в архитектуре компьютеров

Кэш-память

Временная локальность является ключевым фактором, определяющим эффективность кэш-памяти. Кэш — это небольшой, быстрый буфер, который хранит копии часто используемых данных из основной памяти (ОЗУ). Когда процессор обращается к данным, контроллер кэша сначала проверяет, есть ли они в кэше. Если данные там присутствуют (кэш-попадание, англ. cache hit), доступ происходит быстро. Если нет (кэш-промах, англ. cache miss), данные загружаются из медленной основной памяти, и их копия помещается в кэш.

Благодаря временной локальности, после того как данные были загружены в кэш при первом обращении, последующие обращения к ним будут удовлетворяться из кэша, что значительно ускоряет выполнение программы. Если бы временной локальности не было, каждое обращение к памяти требовало бы загрузки данных из ОЗУ, что привело бы к резкому падению производительности.

Стратегии вытеснения

Алгоритмы вытеснения данных из кэша (например, LRU — Least Recently Used, «наименее используемый») также основаны на принципе временной локальности. LRU вытесняет те данные, к которым дольше всего не было обращений, предполагая, что они с наименьшей вероятностью понадобятся в ближайшем будущем. Это прямое следствие временной локальности: данные, к которым обращались недавно, скорее всего, будут нужны снова, а те, к которым не обращались долго — нет.

Виртуальная память

Временная локальность также используется в системах виртуальной памяти. Когда операционная система подкачивает страницы памяти между ОЗУ и диском (файл подкачки или раздел подкачки), она опирается на то, что недавно использованные страницы с высокой вероятностью будут использованы снова. Алгоритмы замещения страниц, такие как LRU и его приближения, также эксплуатируют временную локальность.

Примеры в программировании

Циклы

Наиболее яркий пример временной локальности — это работа с переменными внутри цикла. Рассмотрим код на языке C:

``c int sum = 0; for (int i = 0; i < 1000000; i++) { sum += i; } ``

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

Повторные вызовы функций

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

Обработка данных в реальном времени

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

Влияние на производительность

Положительное влияние

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

Отрицательное влияние (проблемы)

Если программа не демонстрирует временной локальности (например, при случайном доступе к большим объёмам данных, которые не помещаются в кэш), производительность может резко упасть. Это явление называется «кэш-промахи» и может привести к тому, что процессор будет тратить большую часть времени на ожидание данных из памяти. В таких случаях говорят о «плохой локальности» или «отсутствии временной локальности».

Оптимизация кода

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

• Использования локальных переменных (вместо глобальных) — они хранятся в стеке и часто остаются в кэше.
• Разбиения больших циклов на меньшие блоки (блокинг, англ. loop tiling) — чтобы данные помещались в кэш.
• Избегания излишних повторных вычислений — кэширование результатов.
• Использования структур данных, которые поддерживают локальность (например, массивы вместо связных списков).

Измерение временной локальности

Временную локальность можно измерить с помощью профилировщиков производительности (например, perf, Valgrind, Intel VTune). Они показывают количество кэш-промахов и попаданий, что косвенно отражает степень локальности. Также существуют метрики, такие как «рабочее множество» (working set) — набор страниц памяти, к которым программа обращается в течение определённого интервала времени. Чем меньше рабочее множество, тем выше временная локальность.

Временная локальность в разных архитектурах

Многоядерные процессоры

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

Векторные процессоры и GPU

Векторные процессоры и графические процессоры (GPU) также используют временную локальность, но в меньшей степени, чем пространственную. В GPU, где тысячи потоков обрабатывают данные параллельно, временная локальность может быть менее выражена, так как каждый поток может работать с разными данными. Однако, в некоторых задачах (например, в свёрточных нейронных сетях) временная локальность всё же важна.

Встраиваемые системы

В микроконтроллерах с ограниченным объёмом кэша временная локальность критична. Программисты для встраиваемых систем часто вручную оптимизируют код, чтобы минимизировать кэш-промахи, используя временную локальность.

Критика и ограничения

Временная локальность не является универсальным свойством всех программ. Некоторые алгоритмы, особенно те, что работают с большими наборами данных в случайном порядке (например, хеш-таблицы с плохой хеш-функцией или графовые алгоритмы с нерегулярным доступом), могут демонстрировать низкую временную локальность. В таких случаях для повышения производительности приходится использовать другие методы, такие как предварительная выборка данных (prefetching) или изменение структуры данных.

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

Источники

• Хеннесси Дж., Паттерсон Д. «Архитектура компьютера и проектирование компьютерных систем». — 5-е изд. — СПб.: Питер, 2014. — 784 с.
• Танейбаум Э., Остин Т. «Архитектура компьютера». — 6-е изд. — СПб.: Питер, 2013. — 816 с.
• Intel Corporation. «Intel 64 and IA-32 Architectures Optimization Reference Manual». — 2023.
• Документация к инструменту профилирования perf (Linux kernel).