Попадание в кэш и промах кэша
Когда процессору нужны данные, он сначала ищет их в кэше. Если они найдены, всё хорошо — но что, если нет?
Эта лекция поможет вам понять основную механику работы кэшей и ключевой принцип, делающий кэши эффективными, —принцип локальности。
Бытовая аналогия: стол в библиотеке
Вы пишете статью в библиотеке. На ваш стол помещается максимум 4 книги — это вашкэш, его ёмкость мала, но он всегда под рукой.
Когда вам нужна книга, сначала проверьте, лежит ли она на столе:
- На столе (попадание в кэш): просто откройте и используйте, ожидания ноль.
- Не на столе (промах кэша): встаньте и посмотрите на книжной полке, принесите её и положите на стол. Если стол заполнен, придётся положить обратно на полку книгу, к которой дольше всего не обращались.
Это простое правило и есть суть компьютерной кэш-системы —«Храни недавно использованное, вытесняй редко используемое»。
Если копнуть глубже, вы обнаружите: когда пишете статью, вы не перелистываете случайные, не относящиеся к делу книги. За определённый период времени вы раз за разом обращаетесь к одному и тому же набору справочных материалов. Из книг на тех тысячах полок в библиотеке тех, к которым вы действительно прикасались, может быть всего двадцать или тридцать. ЭтоПринцип локальностив действии.
Основная концепция: попадание в кэш и промах кэша
Основные термины
| Термин | Английский | Значение |
|---|---|---|
| Попадание в кэш | Попадание в кэш | Запрошенные процессором данные находятся прямо в кэше и используются напрямую |
| Промах кэша | Промах кэша | Запрошенные процессором данные отсутствуют в кэше, и их необходимо загрузить из следующего (более медленного) уровня памяти |
| коэффициент попаданий | Коэффициент попаданий | Число попаданий / общее число обращений, чем выше, тем лучше (в идеале близко к 100%) |
| Штраф за промах | Штраф за промах | Дополнительное время, затрачиваемое на загрузку данных из следующего уровня после промаха |
| Время попадания | Время попадания | Время, необходимое для чтения данных при попадании в кэш |
Простой пример
, arr
| Шаги | Адрес доступа | Состояние кэша (перед доступом) | Результат | Причина |
|---|---|---|---|---|
| 1 | 10 | [] | промах | Кэш пуст, адреса 10 в нём нет |
| 2 | 20 | [10] | промах | Адрес 20 отсутствует в кэше |
| 3 | 10 | [10, 20] | попадание | Адрес 10 находится в кэше! (временная локальность) |
| 4 | 30 | [10, 20] | промах | Адрес 30 отсутствует в кэше |
| 5 | 10 | [10, 20, 30] | попадание | Адрес 10 снова попадает в кэш |
2 попадания из 5 обращений, частота попаданий = 40%. Невысокая, но это уже демонстрирует принцип кэширования.
Почему кэши работают: принцип локальности
Если программа обращается к памяти совершенно случайно, кэш почти бесполезен — данные загружаются только для того, чтобы сразу же оказаться ненужными.
Но реальные программы не ведут себя случайно. Они обладают сильнойлокальностью, и именно это является фундаментальной причиной эффективности кэшей.
... Они расположены в памяти последовательно.
Если к фрагменту данных происходит обращение, вероятно, к нему обратятся снова в ближайшем будущем.
Типичный сценарий:
- Переменные в цикле：
for i in range(1000000): total += i— ПеременнаяiиtotalК ней обращаются 1 миллион раз за короткий период. - Горячий код функции: 20% кода программы отвечают за 80% времени её выполнения; к этим инструкциям часто обращаются повторно.
- Часто вызываемые параметры функции: Локальные переменные в рекурсивной функции накапливаются в стеке с каждым вызовом.
Пространственная локальность
Если происходит доступ к элементу данных, то, вероятно, будет осуществлён доступ и к соседним данным.
Типичный сценарий:
- Последовательный обход массива：
for i in range(len(arr)): sum += arr[i]—arr - Поля структуры/объекта: доступ
student.nameПосле [этого] весьма вероятно, что следующий доступ будет...student.age, они смежны в памяти. - Последовательно выполняемые инструкции: После того как процессор выполнит инструкцию по адресу 100, следующая инструкция, вероятно, находится по адресу 104.
Визуализация двух типов локальности
时间局部性示意图：
时间轴： t1 t2 t3 t4 t5 t6 t7 t8
访问地址： A B A C A D B A
|_____|_____|_____|
地址 A 在短时间内被多次访问——时间局部性
空间局部性示意图：
内存地址： 100 104 108 112 116 120 124 128
访问顺序： *1 *2 *3 *4 *5
|_____________________________|
连续访问相邻地址——空间局部性
Современные процессоры используют пространственную локальность для повышения производительности: при загрузке данных по адресу 100 из памяти они также загружают адреса 100~164 (целую строку кэша, обычно 64 байта) в кэш. Так, при обращении к адресу 104 данные уже находятся в кэше.
Политика замещения кэша: что делать, когда он заполнен
Слоты кэша ограничены; когда кэш заполнен и нужно принять новые данные, он долженвытеснить старый элемент данных. Решение о том, «кого вытеснить», и есть политика замещения кэша.
| Политика | Английский | Правила | оценка |
|---|---|---|---|
| Наименее недавно использованный | LRU (наименее недавно использованный) | Вытеснить данные, к которым дольше всего не было обращений | Наиболее часто используется, работает очень хорошо |
| первым пришёл — первым вышел | FIFO (первым пришёл — первым вышел) | Вытеснять данные, попавшие в кэш раньше всего | Просто, но средняя эффективность |
| Наименее часто используемые | LFU (наименее часто используемые) | Вытеснять данные с наименьшим числом обращений | Дружелюбен к горячим данным, но старые данные могут «отказываться уходить» |
| Случайное замещение | Случайный | Случайно выбирать один для вытеснения | Проще всего в реализации, работает хорошо |
LRU показывает лучшие результаты на практике, потому что напрямую использует временную локальность — «Если к данным не обращались недавно, вероятно, к ним не будут обращаться ещё некоторое время».
Реальные кэши CPU обычно используют приближённые варианты LRU (например, псевдо-LRU), чтобы снизить сложность аппаратной реализации.
Интерактивная демонстрация: симулятор LRU-кэша
Следующая программа на Python полностью моделирует работу LRU-кэша. Вы можете изменять последовательность обращений и объём кэша, чтобы наблюдать изменения коэффициента попаданий.
Пример
"""
Симулятор LRU-кэша (демонстрационный пример)
Функции:
1. Моделировать последовательность обращений процессора к адресам памяти
2. Использовать стратегию LRU для управления кэшем
3. Помечать каждое обращение в реальном времени как «попадание» или «промах»
4. Вычислять и отображать коэффициент попаданий
"""
from collections import OrderedDict
class LRUCache:
"""
Симулятор LRU-кэша (Least Recently Used)
Используйте OrderedDict для поддержания порядка доступа; чем ближе элемент к концу, тем позже к нему обращались.
"""
def __init__(self, capacity):
"""
Инициализировать кэш
:param capacity: ёмкость кэша (количество записей, которые можно сохранить)
"""
self.capacity = capacity
self.cache = OrderedDict() # Упорядоченный словарь: key=address, value=data
self.hits = 0 # Количество попаданий
self.misses = 0 # Количество промахов
self.evictions = 0 # Количество вытеснений
def access(self, address):
"""
Смоделировать доступ к памяти
:param address: адрес памяти для доступа
:return: (result_str, is_hit)
"""
if address in self.cache:
# Попадание в кэш!
self.hits += 1
# Политика LRU: переместить запись, вызвавшую попадание, в конец (отмечена как наиболее недавно использованная)
self.cache.move_to_end(address)
return "HIT", True
else:
# Промах кэша
self.misses += 1
evicted = None
if len(self.cache) >= self.capacity:
# Кэш заполнен, нужно вытеснить наименее недавно использованный элемент (первый элемент OrderedDict)
evicted_addr, _ = self.cache.popitem(last=False)
self.evictions += 1
evicted = evicted_addr
# Загрузить новые данные из 'хранилища следующего уровня' (имитируется как прямая выборка данных)
data = f"DATA_AT_{address}"
self.cache[address] = data
return "MISS", False
def hit_rate(self):
"""Рассчитать текущий коэффициент попаданий в кэш (в процентах)"""
total = self.hits + self.misses
if total == 0:
return 0.0
return (self.hits / total) * 100
def current_state(self):
"""Возвращает текущее кэшированное содержимое (от самого старого к самому новому)"""
return list(self.cache.keys())
def run_simulation(access_sequence, cache_capacity):
"""
Запустить полную симуляцию кэша
:param access_sequence: Последовательность обращений к памяти для симуляции (список целых чисел)
:param cache_capacity: емкость кэша
"""
cache = LRUCache(cache_capacity)
print("=" * 70)
print(f"ПРИМЕР Симулятор LRU-кэша")
print(fЕмкость кэша: {cache_capacity} слотов)
print(f"Последовательность обращений: {access_sequence}")
print("=" * 70)
print(f"{'шаг':<6} {'адрес':<8} {'результат':<8} {'состояние кэша (старые→новые)':<40}")
print("-" * 70)
for i, addr in enumerate(access_sequence, 1):
result, is_hit = cache.access(addr)
state = cache.current_state()
hit_mark = "ПОПАДАНИЕ [OK]" if is_hit else "ПРОМАХ X"
print(f"{i:<6} {addr:<8} {hit_mark:<8} {str(state):<40}")
# Статистика вывода
print("-" * 70)
print(f"\nРезультаты статистики:")
print(f" Количество попаданий (Hits) : {cache.hits}")
print(f" Количество промахов (Misses): {cache.misses}")
print(f" Количество вытеснений (Evictions): {cache.evictions}")
print(f" Процент попаданий : {cache.hit_rate():.1f}%")
print()
return cache
# ============================================================
# Демо 1: Базовое поведение LRU
# ============================================================
print("\n>>> Демо 1: Базовое поведение LRU-кэша")
print(Последовательность обращений демонстрирует временную локальность — к адресу 10 многократно обращаются\n")
run_simulation(
access_sequence=[10, 20, 10, 30, 40, 10, 20, 50, 10, 20],
cache_capacity=4
)
# ============================================================
# Демо 2: Влияние разных размеров кэша на долю попаданий
# ============================================================
print("\n>>> Демо 2: Влияние размера кэша на долю попаданий")
print("Производительность одной и той же последовательности обращений при разных размерах кэша\n")
test_sequence = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5,
1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7]
print(f"Длина последовательности обращений: {len(test_sequence)}")
print(f"{'ёмкость':<8} {'попадания':<8} {'промахи':<8} {'доля попаданий':<10}")
print("-" * 35)
for cap in [1, 2, 3, 4, 5, 8, 16]:
c = LRUCache(cap)
for addr in test_sequence:
c.access(addr)
print(f"{cap:<8} {c.hits:<8} {c.misses:<8} {c.hit_rate():<8.1f}%")
# ============================================================
# Демо 3: Сравнение 'случайного доступа' и 'доступа с локальностью'
# ============================================================
print("\n>>> 3: Доступ с локальностью против случайного доступа)
print("Одинаковая ёмкость кэша (8), процент попаданий при разных шаблонах доступа\n")
import random
random.seed(42)
# Шаблон A: Доступ с локальностью (имитация обхода массива в цикле)
local_access = []
for _ in range(20):
# На каждой итерации цикла обращаться последовательно в диапазоне 0-15, затем скачок
base = randint.randint(0, 50)
for offset in range(5):
local_access.append(base + offset)
# Режим B: полностью случайный доступ
random_access = [random.randint(0, 100) for _ in range(100)]
for label, seq in [("Доступ с локальностью", local_access), ("Случайный доступ", random_access)]:
c = LRUCache(8)
for addr in seq:
c.access(addr)
print(f" {label}: доля попаданий = {c.hit_rate():.1f}% (всего посещений {len(seq)} раз)")
Симулятор LRU-кэша (демонстрационный пример)
Функции:
1. Моделировать последовательность обращений процессора к адресам памяти
2. Использовать стратегию LRU для управления кэшем
3. Помечать каждое обращение в реальном времени как «попадание» или «промах»
4. Вычислять и отображать коэффициент попаданий
"""
from collections import OrderedDict
class LRUCache:
"""
Симулятор LRU-кэша (Least Recently Used)
Используйте OrderedDict для поддержания порядка доступа; чем ближе элемент к концу, тем позже к нему обращались.
"""
def __init__(self, capacity):
"""
Инициализировать кэш
:param capacity: ёмкость кэша (количество записей, которые можно сохранить)
"""
self.capacity = capacity
self.cache = OrderedDict() # Упорядоченный словарь: key=address, value=data
self.hits = 0 # Количество попаданий
self.misses = 0 # Количество промахов
self.evictions = 0 # Количество вытеснений
def access(self, address):
"""
Смоделировать доступ к памяти
:param address: адрес памяти для доступа
:return: (result_str, is_hit)
"""
if address in self.cache:
# Попадание в кэш!
self.hits += 1
# Политика LRU: переместить запись, вызвавшую попадание, в конец (отмечена как наиболее недавно использованная)
self.cache.move_to_end(address)
return "HIT", True
else:
# Промах кэша
self.misses += 1
evicted = None
if len(self.cache) >= self.capacity:
# Кэш заполнен, нужно вытеснить наименее недавно использованный элемент (первый элемент OrderedDict)
evicted_addr, _ = self.cache.popitem(last=False)
self.evictions += 1
evicted = evicted_addr
# Загрузить новые данные из 'хранилища следующего уровня' (имитируется как прямая выборка данных)
data = f"DATA_AT_{address}"
self.cache[address] = data
return "MISS", False
def hit_rate(self):
"""Рассчитать текущий коэффициент попаданий в кэш (в процентах)"""
total = self.hits + self.misses
if total == 0:
return 0.0
return (self.hits / total) * 100
def current_state(self):
"""Возвращает текущее кэшированное содержимое (от самого старого к самому новому)"""
return list(self.cache.keys())
def run_simulation(access_sequence, cache_capacity):
"""
Запустить полную симуляцию кэша
:param access_sequence: Последовательность обращений к памяти для симуляции (список целых чисел)
:param cache_capacity: емкость кэша
"""
cache = LRUCache(cache_capacity)
print("=" * 70)
print(f"ПРИМЕР Симулятор LRU-кэша")
print(fЕмкость кэша: {cache_capacity} слотов)
print(f"Последовательность обращений: {access_sequence}")
print("=" * 70)
print(f"{'шаг':<6} {'адрес':<8} {'результат':<8} {'состояние кэша (старые→новые)':<40}")
print("-" * 70)
for i, addr in enumerate(access_sequence, 1):
result, is_hit = cache.access(addr)
state = cache.current_state()
hit_mark = "ПОПАДАНИЕ [OK]" if is_hit else "ПРОМАХ X"
print(f"{i:<6} {addr:<8} {hit_mark:<8} {str(state):<40}")
# Статистика вывода
print("-" * 70)
print(f"\nРезультаты статистики:")
print(f" Количество попаданий (Hits) : {cache.hits}")
print(f" Количество промахов (Misses): {cache.misses}")
print(f" Количество вытеснений (Evictions): {cache.evictions}")
print(f" Процент попаданий : {cache.hit_rate():.1f}%")
print()
return cache
# ============================================================
# Демо 1: Базовое поведение LRU
# ============================================================
print("\n>>> Демо 1: Базовое поведение LRU-кэша")
print(Последовательность обращений демонстрирует временную локальность — к адресу 10 многократно обращаются\n")
run_simulation(
access_sequence=[10, 20, 10, 30, 40, 10, 20, 50, 10, 20],
cache_capacity=4
)
# ============================================================
# Демо 2: Влияние разных размеров кэша на долю попаданий
# ============================================================
print("\n>>> Демо 2: Влияние размера кэша на долю попаданий")
print("Производительность одной и той же последовательности обращений при разных размерах кэша\n")
test_sequence = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5,
1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7]
print(f"Длина последовательности обращений: {len(test_sequence)}")
print(f"{'ёмкость':<8} {'попадания':<8} {'промахи':<8} {'доля попаданий':<10}")
print("-" * 35)
for cap in [1, 2, 3, 4, 5, 8, 16]:
c = LRUCache(cap)
for addr in test_sequence:
c.access(addr)
print(f"{cap:<8} {c.hits:<8} {c.misses:<8} {c.hit_rate():<8.1f}%")
# ============================================================
# Демо 3: Сравнение 'случайного доступа' и 'доступа с локальностью'
# ============================================================
print("\n>>> 3: Доступ с локальностью против случайного доступа)
print("Одинаковая ёмкость кэша (8), процент попаданий при разных шаблонах доступа\n")
import random
random.seed(42)
# Шаблон A: Доступ с локальностью (имитация обхода массива в цикле)
local_access = []
for _ in range(20):
# На каждой итерации цикла обращаться последовательно в диапазоне 0-15, затем скачок
base = randint.randint(0, 50)
for offset in range(5):
local_access.append(base + offset)
# Режим B: полностью случайный доступ
random_access = [random.randint(0, 100) for _ in range(100)]
for label, seq in [("Доступ с локальностью", local_access), ("Случайный доступ", random_access)]:
c = LRUCache(8)
for addr in seq:
c.access(addr)
print(f" {label}: доля попаданий = {c.hit_rate():.1f}% (всего посещений {len(seq)} раз)")
Интерактивная демонстрация: симуляция попаданий/промахов кэша в реальном времени
Случайно сгенерировать последовательность обращений к памяти с локальностью (30 обращений), анимировать каждый процесс поиска в кэше, отслеживать долю попаданий в реальном времени и построить график изменения
Слева: область симуляции
Точки предпросмотра последовательности доступаТекущий адрес доступа
Кнопка управления
Справа: статистика + графикиТекущий адрес доступа:--
Индикатор результата попадания/промахаГотово
Сетка из 4 слотов кэшаСлот 1Пусто
Слот 2Пусто
Слот 3Пусто
Слот 4Пусто
Статистика попаданий/промахов/доли попаданий
Кривая изменения доли попаданий Chart.js
Количество попаданий0
Количество промахов0
коэффициент попаданий--
Запустите этот код, и вы обнаружите:
- Чем больше ёмкость кэша, тем выше доля попаданий — но улучшение постепенно уменьшается (предельный эффект)
- Паттерны доступа с локальностью имеют гораздо более высокую долю попаданий, чем случайный доступ—именно поэтому кэши эффективны
- При политике LRU адреса, к которым многократно обращаются, остаются в кэше и почти никогда не вытесняются
Три типа промахов кэша
Не все «промахи кэша» одинаковы. Инженеры по аппаратному обеспечению делят их на три типа:
| Type | Английский | Когда это происходит | Можно ли этого избежать? |
|---|---|---|---|
| Обязательный промах | Обязательный промах (холодный промах) | Когда к элементу данных обращаются впервые, его ещё нет в кэше | Неизбежен (первое обращение всегда холодное) |
| Промах по ёмкости | Промах по ёмкости | Рабочее множество (данные, активно используемые программой) больше ёмкости кэша | Увеличьте размер кэша или уменьшите рабочий набор |
| Конфликтный промах | Конфликтный промах | Разные адреса отображаются на одно и то же место в кэше (часто встречается в кэшах с прямым отображением) | Используйте множественно-ассоциативное или полностью ассоциативное отображение |
Для обычных программистов чаще приходится иметь дело с первыми двумя типами:
- Обязательный промах: неизбежен, но чем дольше работает ваша программа, тем меньше его влияние.
- Промах из-за нехватки ёмкости: его можно смягчить, оптимизировав размер структур данных и паттерны доступа. Например, используйте более компактные типы данных, обрабатывайте большие массивы блоками.
Понимание промахов кэша — ключ к написанию высокопроизводительного кода. Простое практическое правило: делайте паттерны доступа к данным дружественными к кэшу — обходите массивы в порядке их расположения в памяти, избегайте скачкообразного доступа и держите часто используемые вместе данные рядом в памяти.
Практика программирования: код, дружественный к кэшу
Вот классический пример: при обходе двумерного массива обход по строкам и по столбцам даёт огромную разницу в производительности.
Пример
"""
Дружественный и недружественный к кэшу обход массива (демонстрационный пример)
Продемонстрируйте, как различные шаблоны доступа к одним и тем же данным влияют на производительность кэша
"""
import time
# Хранение списков Python: двумерный массив = список списков
# В arr[i][j], arr[i] — целая строка, непрерывно расположенная в памяти.
# Итак, обход по строкам = дружественный к кэшу, обход по столбцам = недружественный к кэшу
def traverse_row_major(arr):
"""
Обход по строкам: сначала фиксируем индекс строки i, затем проходим по столбцам j
Шаблон доступа: arr[0][0], arr[0][1], arr[0][2]...
Расположение в памяти: эти элементы расположены непрерывно в памяти -- хорошая пространственная локальность!
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for i in range(rows):
for j in range(cols):
total += arr[i][j]
return total
def traverse_column_major(arr):
"""
Обход по столбцам: сначала фиксируем индекс столбца j, затем проходим по строкам i
Шаблон доступа: arr[0][0], arr[1][0], arr[2][0]...
Размещение в памяти: эти элементы разбросаны по памяти -- плохая пространственная локальность!
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for j in range(cols):
for i in range(rows):
total += arr[i][j]
return total
# Создаём большой массив (1000 x 1000)
SIZE = 1000
print(f"Создаём двумерный массив {SIZE}x{SIZE}...")
arr = [[i * SIZE + j for j in range(SIZE)] for i in range(SIZE)]
# Сначала выполняем предварительный прогрев, чтобы избежать смещения из-за холодного старта
traverse_row_major(arr)
traverse_column_major(arr)
# Формальный тест
print("\nНачало сравнения производительности (3 запуска, берётся среднее):")
print("-" * 50)
def benchmark(func, arr, trials=3):
Среднее время по нескольким запускам
times = []
for _ in range(trials):
start = time.perf_counter()
func(arr)
elapsed = time.perf_counter() - start
times.append(elapsed)
return sum(times) / len(times)
row_time = benchmark(traverse_row_major, arr)
col_time = benchmark(traverse_column_major, arr)
print(f"Обход по строкам (дружественный к кэшу): {row_time:.4f} секунд")
print(fОбход по столбцам (недружественный к кэшу): {col_time:.4f} секунд)
print(fОбход по столбцам медленнее, чем по строкам: {col_time / row_time:.1f} раз)
print()
print("Анализ причин:")
print(При обходе по строкам arr[i][0], arr[i][1], arr[i][2]... хранятся в памяти непрерывно)
print(При первом обращении к arr[i][0] CPU загружает в кэш сразу несколько последующих элементов)
print(" Последующее обращение к arr[i][1], arr[i][2] будет напрямую попадать в кэш")
print()
print(" При обходе по столбцам arr[0][j], arr[1][j], arr[2][j]... отделены друг от друга целой строкой в памяти.")
print(Почти каждое обращение требует загрузки из памяти, что приводит к крайне низкой доле попаданий в кэш)
# Дополнение: простой тест — используйте id() в Python для проверки адреса памяти
print("\nПроверка расположения в памяти (демонстрация с небольшим массивом):")
малый = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(fid элемента arr[0][0]: {id(small[0][0])})
print(f"arr[0][1] id: {id(small[0][1])} (PoorValue: {id(small[0][1]) - id(small[0][0])})")
print(fid элемента arr[0][2]: {id(small[0][2])} (смежно с [0][0]))
print(f"id элемента arr[1][0]: {id(small[1][0])} (не смежно с [0][2], потому что переходит через строку)")
Дружественный и недружественный к кэшу обход массива (демонстрационный пример)
Продемонстрируйте, как различные шаблоны доступа к одним и тем же данным влияют на производительность кэша
"""
import time
# Хранение списков Python: двумерный массив = список списков
# В arr[i][j], arr[i] — целая строка, непрерывно расположенная в памяти.
# Итак, обход по строкам = дружественный к кэшу, обход по столбцам = недружественный к кэшу
def traverse_row_major(arr):
"""
Обход по строкам: сначала фиксируем индекс строки i, затем проходим по столбцам j
Шаблон доступа: arr[0][0], arr[0][1], arr[0][2]...
Расположение в памяти: эти элементы расположены непрерывно в памяти -- хорошая пространственная локальность!
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for i in range(rows):
for j in range(cols):
total += arr[i][j]
return total
def traverse_column_major(arr):
"""
Обход по столбцам: сначала фиксируем индекс столбца j, затем проходим по строкам i
Шаблон доступа: arr[0][0], arr[1][0], arr[2][0]...
Размещение в памяти: эти элементы разбросаны по памяти -- плохая пространственная локальность!
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for j in range(cols):
for i in range(rows):
total += arr[i][j]
return total
# Создаём большой массив (1000 x 1000)
SIZE = 1000
print(f"Создаём двумерный массив {SIZE}x{SIZE}...")
arr = [[i * SIZE + j for j in range(SIZE)] for i in range(SIZE)]
# Сначала выполняем предварительный прогрев, чтобы избежать смещения из-за холодного старта
traverse_row_major(arr)
traverse_column_major(arr)
# Формальный тест
print("\nНачало сравнения производительности (3 запуска, берётся среднее):")
print("-" * 50)
def benchmark(func, arr, trials=3):
Среднее время по нескольким запускам
times = []
for _ in range(trials):
start = time.perf_counter()
func(arr)
elapsed = time.perf_counter() - start
times.append(elapsed)
return sum(times) / len(times)
row_time = benchmark(traverse_row_major, arr)
col_time = benchmark(traverse_column_major, arr)
print(f"Обход по строкам (дружественный к кэшу): {row_time:.4f} секунд")
print(fОбход по столбцам (недружественный к кэшу): {col_time:.4f} секунд)
print(fОбход по столбцам медленнее, чем по строкам: {col_time / row_time:.1f} раз)
print()
print("Анализ причин:")
print(При обходе по строкам arr[i][0], arr[i][1], arr[i][2]... хранятся в памяти непрерывно)
print(При первом обращении к arr[i][0] CPU загружает в кэш сразу несколько последующих элементов)
print(" Последующее обращение к arr[i][1], arr[i][2] будет напрямую попадать в кэш")
print()
print(" При обходе по столбцам arr[0][j], arr[1][j], arr[2][j]... отделены друг от друга целой строкой в памяти.")
print(Почти каждое обращение требует загрузки из памяти, что приводит к крайне низкой доле попаданий в кэш)
# Дополнение: простой тест — используйте id() в Python для проверки адреса памяти
print("\nПроверка расположения в памяти (демонстрация с небольшим массивом):")
малый = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(fid элемента arr[0][0]: {id(small[0][0])})
print(f"arr[0][1] id: {id(small[0][1])} (PoorValue: {id(small[0][1]) - id(small[0][0])})")
print(fid элемента arr[0][2]: {id(small[0][2])} (смежно с [0][0]))
print(f"id элемента arr[1][0]: {id(small[1][0])} (не смежно с [0][2], потому что переходит через строку)")