Модуль 1 ⏱ ~33 мин чтения 📐 1 Mermaid диаграмм

19. Ассоциативность кэша, Prefetching и Cache Miss

В предыдущей главе (18. Кэши CPU. L1, L2, L3 и Cache Line) мы выяснили, что оперативная память и процессор общаются строго 64-байтными порциями — кэш-линиями. Но мы намеренно оставили за скобками главный архитектурный ребус.

Взгляните на цифры: объем кэша первого уровня L1 составляет скромные 32 КБ. Объем оперативной памяти на сервере — 64 Гигабайта (а то и терабайт).
Разделив 32 КБ на 64 байта, мы получим ровно 512 слотов для кэш-линий.

Когда ядро запрашивает блок памяти по произвольному 64-битному адресу из бескрайней RAM, по какому правилу контроллер определяет, в какой именно из 512 слотов положить приехавшие байты? И что еще важнее: когда эти данные понадобятся снова, как процессор за долю наносекунды находит нужную кэш-линию среди остальных 511, не перебирая их по очереди?

Эта фундаментальная задача называется Архитектурой маппинга (отображения) кэша.

Ассоциативность кэша: Проблема парковки

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

Как организовать правила въезда и размещения машин? В истории вычислительной техники было опробовано три подхода.

DIAGRAM

Анатомия 64-битного адреса памяти при поиске в кэше:
┌───────────────────────────────┬──────────────┬───────────────┐
│           Tag (Тег)           │  Set (Индекс)│ Offset (Смещение)
│            52 бита            │    6 бит     │     6 бит     │
└───────────────────────────────┴──────────────┴───────────────┘
                                 (выбирает 1    (выбирает байт
                                  из 64 сетов)   внутри 64B линии)

1. Direct-Mapped (Кэш прямого отображения)

Самое прямолинейное решение: жесткая привязка. Номер парковочного места однозначно вычисляется из адреса автомобиля по формуле деления с остатком: Место = Адрес % 512.
$$\text{Место} = \text{Адрес} \pmod{512}$$

Плюсы: Невероятная аппаратная простота и дешевизна. Время поиска — строго $\mathcal{O}(1)$: берем биты адреса и сразу смотрим в нужную ячейку.
Минусы: Чудовищные коллизии. Представьте, что в вашей Go-программе два активных массива лежат по адресам 0 и 32768. Оба этих адреса при делении на 512 дают один и тот же остаток — 0! Они претендуют на одно-единственное Место №0.
Процессор будет циклически вытеснять одну кэш-линию другой на каждой итерации цикла. Это явление называется Thrashing (кэш-буксование). Скорость работы падает до уровня медленной DRAM, несмотря на то что остальные 511 мест на парковке стоят абсолютно пустыми!

2. Fully Associative (Полностью ассоциативный кэш)

Противоположная крайность: полная свобода. Любая кэш-линия может занять вообще любое свободное место из 512.

Плюсы: Коллизий мест нет в принципе. Кэш заполняется со 100% эффективностью.
Минусы: Катастрофа при поиске. Чтобы узнать, есть ли нужный адрес в кэше, контроллер обязан параллельно сравнить теги всех 512 ячеек за один такт! Для этого требуется разместить 512 аппаратных компараторов на кристалле. Это приводит к дикому расходу транзисторов, высокому энергопотреблению и перегреву. В кэшах данных L1/L2 такой подход физически не реализуем (он применяется лишь в крошечных специализированных буферах на 32–64 записи, например, в TLB).

3. N-Way Set Associative (N-канальный множественно-ассоциативный)

Гениальный инженерный компромисс, на котором сегодня построены 99.9% процессоров в мире.

Парковка делится на несколько отдельных «секторов» или «наборов» (Sets). Внутри каждого сета выделяется строго фиксированное число парковочных мест (Ways, каналы ассоциативности).

Например, классический 8-Way кэш объемом 32 КБ:

Всего слотов: 512 линий.
В каждом сете: 8 мест (Ways).
Всего сетов: $512 / 8 = 64$ сета.

Машина направляется в свой сет по формуле: Зона = Адрес % 64 (где номер кэш-линии делится по модулю числа сетов).
$$\text{Зона (Set)} = (\text{Адрес} / 64) \pmod{64}$$
А вот внутри выделенного сета она может занять любое из 8 свободных мест!

Когда процессору нужно проверить наличие адреса, он активирует всего 8 компараторов одновременно (вместо 512). Это работает молниеносно, потребляет минимум энергии и защищает от коллизий. Если все 8 мест в сете заняты, специальный алгоритм вытеснения (обычно LRU — Least Recently Used или его аппаратное приближение Tree-PLRU) выбрасывает кэш-линию, к которой дольше всего не обращались.

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    Addr["64-битный адрес памяти"]:::data --> Split["Разбиение адреса:<br>[Tag | Set Index (6 бит) | Offset (6 бит)]"]
    Split --> SetSelect["Выбор Set (от 0 до 63)"]

    subgraph SetK["Выбранный Set K (8-Way Associative)"]
        direction TB
        W0["Way 0: [Tag0 | 64B Data]"]
        W1["Way 1: [Tag1 | 64B Data]"]
        W2["Way 2: [Tag2 | 64B Data]"]
        W3["Way 3: [Tag3 | 64B Data]"]
        W4["Way 4: [Tag4 | 64B Data]"]
        W5["Way 5: [Tag5 | 64B Data]"]
        W6["Way 6: [Tag6 | 64B Data]"]
        W7["Way 7: [Tag7 | 64B Data]"]
    end

    SetSelect --> SetK
    SetK --> Compare{"Параллельное сравнение<br>Тега с 8 слотами"}
    Compare -->|"Совпадение найдено"| Hit["КЭШ-ХИТ (Hit)<br>Отдача байта за 1 ns"]
    Compare -->|"Совпадений нет"| Miss["КЭШ-ПРОМАХ (Miss)<br>Запрос в L2/L3/DRAM + вытеснение LRU"]

В современных процессорах кэш L1d обычно 8-way или 12-way (например, 48 КБ и 12-way в Golden Cove, 32 КБ и 8-way в более ранних ядрах), кэш L2 — 8-way или 16-way, а огромный L3 — 12-way, 16-way или даже 24-way.

Правило Трех C: Анатомия Cache Miss

Когда процессор пытается прочитать данные и не находит нужный тег в выбранном сете, происходит Cache Miss (промах кэша).

Классическая теория архитектуры ЭВМ (сформулированная Марком Хиллом и популяризированная Джоном Хеннесси и Дэвидом Паттерсоном) делит промахи на три фундаментальные категории — «Три C» (The 3 C's):

Compulsory Miss (Обязательный, или «холодный» промах):
Самое первое обращение программы к данной области памяти. Данных физически еще никогда не было в кэше. Этот промах неизбежен при холодном старте сервиса.
Capacity Miss (Промах по вместимости):
Рабочий набор данных вашей программы (Working Set) превышает физический объем кэша (например, хэш-таблица на миллион ключей занимает 100 МБ, а весь кэш L3 — 32 МБ). Данные постоянно сменяют друг друга, потому что кэш банально мал.
Conflict Miss (Конфликтный промах):
Самый обидный и коварный промах. Суммарный объем данных невелик и легко поместился бы в кэш (кэш занят всего на 15%), но структура адресов такова, что все обращения конкурируют за один и тот же Set, переполняя его 8 каналов.

(В многоядерных системах к ним добавляется четвертое «C» — Coherence Miss, вызванный аннулированием строк из-за записи на соседнем ядре. Мы разберем его в следующей главе).

Ловушка / Gotcha: Проклятие степеней двойки

Конфликтные промахи породили одну из самых печально известных аппаратных ловушек в инженерной практике.

Если вы выделите в Go двумерную матрицу, размерность которой является точной степенью двойки — например, [4096][4096]byte, — и начнете наивно обходить её по столбцам, вы рискуете обрушить производительность в 10–20 раз даже по сравнению с обычным промахом.

Почему это происходит?
Элементы первого столбца matrix[0][0], matrix[1][0] и matrix[2][0] отстоят друг от друга в памяти с шагом ровно 4096 байт ($2^{12}$).
Для 8-канального кэша L1 размером 32 КБ с 64 сетами размер одного периода повторения сетов составляет:
$$64\text{ сета} \times 64\text{ байта} = 4096\text{ байт}$$

Это означает, что все элементы столбца имеют одинаковый Set Index и попадают в один и тот же Set кэша! Емкость сета исчерпывается на 8-м элементе. С девятой строки процессор начинает непрерывно выбивать свои же свежие кэш-линии из этого злополучного сета, в то время как остальные 63 сета кэша остаются кристально чистыми!

Лекарство (Padding):
Добавьте к размеру строки фиктивное смещение, нарушающее кратность степени двойки: например, выделите [4096][4160]byte. Сдвиг адресов рассеет обращения по разным сетам кэша, коллизии исчезнут, и пропускная способность восстановится. (Подробнее эту технику мы разберем в 25. Выравнивание данных, Padding и Struct Layout).

Prefetching: Железо предсказывает будущее

Казалось бы, если Compulsory Miss (первое чтение) неизбежен, то при последовательном обходе массива мы обречены получать штраф памяти на каждой новой кэш-линии.

Но создатели процессоров научили кремний предугадывать намерения программиста. За это отвечает Hardware Prefetcher (Аппаратный блок предвыборки).

Prefetcher работает как скрытый аналитический радар в составе кэш-контроллера. Он непрерывно отслеживает последовательность адресов, которые запрашивают инструкции MOVQ.

DIAGRAM

Ваш код запрашивает:
Линия 1: 0x1000  (Miss, чтение из DRAM)
Линия 2: 0x1040  (+64 байта)  ──► Prefetcher фиксирует: Stride = +64
Линия 3: 0x1080  (+64 байта)  ──► Шаблон подтвержден!

Prefetcher самостоятельно (на опережение) отправляет запрос:
        0x10C0  (затягивается в L1/L2 фоном, пока вы считаете 0x1080!)

Если контроллер замечает устойчивый шаг:

Кэш-линия 0x1000
Затем кэш-линия 0x1040 (+64 байта)
Затем кэш-линия 0x1080 (+64 байта)

Prefetcher делает вывод: код выполняет последовательный обход непрерывного массива с шагом в одну кэш-линию (Stride = 1).
Не дожидаясь, пока процессор завершит работу с текущими байтами и запросит адрес 0x10C0, Prefetcher в фоновом режиме отправляет упреждающий запрос по шине памяти в DRAM.

К тому моменту, когда счетчик цикла доберется до адреса 0x10C0, данные уже будут заботливо лежать в кэше L1 или L2! Задержка доступа в 80–100 нс оказывается полностью замаскирована, превращаясь в 1 наносекунду.

Под капотом: Границы страниц и Prefetcher

Аппаратный предвыборщик спроектирован предельно осторожным: он никогда не переступает границу физической страницы памяти (размером 4 КБ).
Если массив подходит к концу страницы (например, к адресу 0x1FFF), предвыборщик немедленно останавливается. Дело в том, что предвыборщик оперирует физическими адресами и не знает, как устроена виртуальная память: следующая страница может оказаться не отображенной на память или принадлежать совсем другому месту. Важно: сам аппаратный префетч не вызывает Page Fault — если трансляция не удалась, запрос на предвыборку просто молча отбрасывается, программа не падает. Поэтому он и не пытается шагать за границу страницы: это либо бесполезно, либо небезопасно. (Современные ядра, начиная примерно с Intel Ivy Bridge, имеют дополнительный «next-page prefetcher», который угадывает переход на следующую страницу.) О том, как устроены эти страницы, мы поговорим в 27. Виртуальная память. Взгляд со стороны железа.

Mechanical Sympathy: Помогаем Prefetcher'у на Go

С точки зрения кремния, идеальный высокопроизводительный код на Go — это код, в котором Prefetcher угадывает 100% обращений к памяти.

Чтобы достичь этой гармонии, разработчик должен знать, какие паттерны помогают блоку предвыборки, а какие сбивают его с толку.

1. Pointer Chasing (Погоня за указателями)

Слайс указателей []*User или узлы связного списка container/list — злейшие враги предвыборщика.

Когда вы обходите слайс указателей:

Вы последовательно читаете адрес 0x9000 из самого слайса.
Процессор совершает переход и читает данные структуры в куче по адресу 0x9000.
На следующем шаге из слайса читается адрес 0x7500.
Процессор вынужден прыгать по адресу 0x7500.

Для кремниевого контроллера цепочка 0x9000 -> 0x7500 выглядит как абсолютно хаотичный белый шум. Аппаратный Prefetcher не видит никакой закономерности и отключается. В итоге программа собирает полный штраф DRAM на каждом элементе! Классические структуры данных вроде связных списков, бинарных деревьев поиска и графов на указателях аппаратно работают в десятки раз медленнее массивов именно по этой причине.

2. Шаг итерации больше размера кэш-линии

Даже если данные лежат в едином непрерывном куске памяти, неоптимальный размер структуры может дезориентировать контроллер:

package main

type BigStruct struct {
    UsefulData int64     // 8 байт полезной нагрузки
    Padding    [248]byte // Мусор для раздутия размера (структура ровно 256 байт)
}

func sumUsefulData(items []BigStruct) int64 {
    var sum int64
    for i := range items {
        sum += items[i].UsefulData
    }
    return sum
}

В данном примере срез items монолитен. Однако полезное поле UsefulData запрашивается с огромным шагом в 256 байт (прыжок через 4 кэш-линии за одну итерацию!).
Многие аппаратные детекторы шага (IP-stride prefetcher) отслеживают ограниченные шаги — порядка до 2 КБ, но их эффективность падает с ростом шага, а соседние линии могут подтягиваться и без детектора. Главное здесь иное: шина памяти загружается не полезными данными — на каждые 8 прочитанных байт загружается целая 64-байтная кэш-линия (в 8 раз больше нужного), хотя «прыжок» через 256 байт на каждый элемент означает, что из каждых 4 линий полезна лишь одна.

Собеседование

Вопрос: Если мы знаем, что указатели и связные списки парализуют работу Prefetcher'а, но архитектура системы требует дерева или графа с миллионами динамических узлов, как выжать максимум производительности в Go?

Ответ: Использовать паттерн Arena Allocation (или пул на основе монолитного слайса).

Вместо того чтобы создавать каждый узел через индивидуальный вызов new(Node) (который раскидывает объекты по разным страницам кучи), мы заранее аллоцируем непрерывный буфер:

arena := make([]Node, 10000)

Новые элементы графа берутся из этой арены последовательно. Теперь указатели *Node внутри структуры ссылаются на соседние ячейки памяти внутри непрерывного массива. При обходе графа смежные вершины с высокой вероятностью окажутся в одной и той же кэш-линии или будут своевременно захвачены аппаратным Prefetcher'ом!

Итог

Чтобы связать гигантскую память и компактный кэш без взрывного роста числа транзисторов, применяется N-Way Set Associative архитектура. Кэш делится на наборы (Sets), каждый из которых содержит $N$ параллельных линий (Ways).
Промахи кэша подчиняются Правилу Трех C: Compulsory (первое обращение), Capacity (нехватка объема) и Conflict (конфликт за слоты одного сета).
Многомерные массивы с размерностями степени двойки чреваты Conflict Miss: данные многократно выбивают друг друга из одного сета кэша при пустующих соседних. Лекарство — добавление искусственного отступа (Padding).
Аппаратный Prefetcher распознает линейные шаблоны чтения памяти и фоном затягивает кэш-линии из медленной DRAM в быстрый кэш L1, нивелируя задержки.
Для максимальной дружбы с «железом» предпочитайте плоские слайсы значений []struct. Избегайте развесистых графов на неструктурированных указателях или собирайте их узлы внутри монолитных арен памяти.

Мы детально изучили, как работает подсистема памяти в пределах одного процессорного ядра. Но в наших серверах трудятся десятки ядер!
Что произойдет, если горутина на Ядре №1 обновит переменную в своем локальном кэше L1, а горутина на Ядре №2 в ту же наносекунду попытается её прочитать? Как процессоры синхронизируют локальные кэши без хаоса и гонок данных?

Об этом мы поговорим в следующей фундаментальной главе: 20. Многоядерные процессоры и Cache Coherence.