Попадания, промахи и политики записи

Урок разбирает, какими бывают промахи кэша и как кэш справляется с записью данных обратно в память.

Попадание (hit) — данные нашлись в кэше; промах (miss) — пришлось идти в нижний уровень. Политика записи определяет, когда изменённые данные попадут из кэша в память.

Три вида промахов (the 3 C's)

Понимание типа промаха подсказывает лечение: обязательные неизбежны при первом доступе, ёмкостные лечатся объёмом, конфликтные — ассоциативностью.

Политики записи

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

• Write-through (сквозная запись): пишем и в кэш, и в память сразу. Просто, память всегда актуальна, но медленно — каждая запись идёт в ОЗУ.
• Write-back (отложенная запись): пишем только в кэш, помечая строку «грязной» (dirty bit). В память её сбросят лишь при вытеснении. Быстро, но память временно «отстаёт».

WRITE-THROUGH:
  CPU --write--> [КЭШ] --сразу--> [ПАМЯТЬ]

WRITE-BACK:
  CPU --write--> [КЭШ: dirty=1]
                    │
        при вытеснении строки
                    ▼
                [ПАМЯТЬ]

Как работает под капотом: write-back с грязным битом

Смоделируем кэш с политикой write-back. Записи помечают строку грязной; реальный поход в память случается только когда грязную строку вытесняют. Посчитаем, сколько записей в ОЗУ сэкономлено:

class WriteBackLine:
    def __init__(self):
        self.dirty = False

mem_writes = 0
line = WriteBackLine()

# 5 записей в одну и ту же строку подряд
for i in range(5):
    line.dirty = True           # пишем только в кэш, метим грязной
print("после 5 записей: записей в ОЗУ =", mem_writes, "(всё ещё в кэше)")

# вытеснение грязной строки -> ОДНА запись в память
if line.dirty:
    mem_writes += 1
    line.dirty = False
print("при вытеснении: записей в ОЗУ =", mem_writes)
print("write-through сделал бы 5 записей в ОЗУ вместо 1")

Вывод:

после 5 записей: записей в ОЗУ = 0 (всё ещё в кэше)
при вытеснении: записей в ОЗУ = 1
write-through сделал бы 5 записей в ОЗУ вместо 1

Вытеснение: кого выгнать (LRU)

Когда в наборе нет места, какую строку выгнать? Популярная политика — LRU (Least Recently Used): выгоняем дольше всех не использовавшуюся, опираясь на временную локальность. Реализуем мини-LRU:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.store = OrderedDict()
        self.hits = self.misses = 0
    def access(self, key):
        if key in self.store:
            self.store.move_to_end(key)   # обновляем "свежесть"
            self.hits += 1
            return "hit"
        self.misses += 1
        if len(self.store) >= self.cap:
            evicted, _ = self.store.popitem(last=False)  # выгоняем самый старый
        self.store[key] = True
        return "miss"

c = LRUCache(2)
for k in ["A", "B", "A", "C", "B"]:
    print(f"доступ {k}: {c.access(k)} | в кэше: {list(c.store.keys())}")
print(f"попаданий {c.hits}, промахов {c.misses}")

Вывод:

доступ A: miss | в кэше: ['A']
доступ B: miss | в кэше: ['A', 'B']
доступ A: hit | в кэше: ['B', 'A']
доступ C: miss | в кэше: ['A', 'C']
доступ B: miss | в кэше: ['C', 'B']
попаданий 1, промахов 4

Глубже в тему

Классификация промахов на три вида (the 3 C's) ценна не сама по себе, а тем, что для каждого вида есть своё лекарство — и понимание типа промаха подсказывает, куда тратить усилия. Обязательные (compulsory) промахи неизбежны при самом первом обращении к блоку: данных просто ещё нигде нет в кэше, их обязательно надо подтянуть из памяти. С ними борются предвыборкой (prefetch) — аппаратура или компилятор угадывают, что скоро понадобится, и загружают заранее. Ёмкостные (capacity) промахи возникают, когда рабочий набор данных программы просто не влезает в кэш целиком; лечатся увеличением кэша или, что практичнее, переработкой алгоритма (например, блочной обработкой, чтобы рабочий набор уместился). Конфликтные (conflict) промахи — артефакт отображения, когда блоки бьются за одну ячейку при свободном кэше; их снимает повышение ассоциативности. Эта диагностика — рабочий инструмент: профилировщик показывает, каких промахов больше, и вы знаете, что чинить.

Выбор политики записи — это компромисс между простотой/согласованностью и скоростью/трафиком. Write-through (сквозная запись) обновляет и кэш, и память при каждой записи: память всегда актуальна, логика проста, но каждая запись платит полную цену похода в медленную память (обычно это смягчают буфером записи, чтобы процессор не ждал). Write-back (отложенная запись) пишет только в кэш, помечая строку «грязной» (dirty bit), и сбрасывает её в память лишь при вытеснении. Выигрыш огромен, когда в одну строку пишут многократно: расчёт из урока показывает, как пять записей подряд превращаются в одну-единственную запись в ОЗУ вместо пяти. Большинство современных кэшей используют именно write-back ради экономии пропускной способности памяти, которая в многоядерных системах является дефицитным ресурсом, делимым между всеми ядрами.

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

Политика вытеснения LRU опирается на временную локальность, но важно понимать и её слабости, иначе можно попасть в ловушку. Идея LRU проста и обычно хороша: раз к давно не использованной строке долго не обращались, вряд ли обратятся и скоро, — её и выгоняем. Но есть патологический случай — линейный проход по массиву, который больше кэша (стриминг). Тогда к моменту, когда мы захотим переиспользовать начало массива, LRU уже вытеснил его как «самое старое», и каждая итерация промахивается — LRU здесь работает строго против нас. Кроме того, честный LRU дорого реализовать при высокой ассоциативности (нужно хранить полный порядок использования всех строк набора), поэтому на практике применяют приближения: псевдо-LRU на дереве бит, или политики вроде «не использованный последним» (NRU). Современные процессоры идут дальше, применяя адаптивные политики, которые распознают стриминговые паттерны и не дают им вытеснять полезные данные. Вывод: даже такая «очевидная» эвристика, как LRU, — не панацея, и понимание её границ отличает грамотного оптимизатора от наивного.

Частые ошибки

• Считать write-back «опасным». Память отстаёт временно, но кэш гарантирует согласованность; в многоядерных системах это поддерживают протоколы когерентности.
• Путать типы промахов. Обязательный неизбежен, ёмкостный лечится размером, конфликтный — ассоциативностью.
• Думать, что LRU идеален. Он хорош для локальных паттернов, но при линейном проходе большого массива (стриминг) бесполезен.

Итог

• Промахи бывают обязательные, ёмкостные и конфликтные — каждый лечится по-своему.
• Write-through пишет в память сразу; write-back откладывает, экономя обращения (грязный бит).
• LRU вытесняет дольше всех неиспользованную строку, опираясь на временную локальность.