Память и кеш

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 30 · страница 30.3
Память и кеш
Как работает ОЗУ, что такое указатель, как массивы лежат в памяти — и почему кеш процессора делает код быстрее в 100 раз.
Процессор не работает напрямую с ОЗУ — между ними
три уровня кеша
. Понять это значит понять, почему
for i for j
и
for j for i
могут отличаться по скорости в 5 раз.
ФГОС
ФОП
углубл.
01
ОЗУ: адреса и ячейки
Оперативная память (RAM)
— это огромный массив пронумерованных ячеек. Каждая ячейка хранит 1 байт (8 бит) и имеет уникальный
адрес
— целое число.
Процессор читает память командой
LOAD адрес → регистр
и записывает командой
STORE регистр → адрес
. Всё в компьютере — переменные, массивы, объекты — это просто диапазоны ячеек памяти.
🔬
Симулятор ячеек ОЗУ
Нажми на ячейку, чтобы изменить её значение (0–255).
Указатель
Массив
Данные
Что хранится в ячейке?
— зависит от типа переменной:
char c = 'A'
→ 1 байт → ASCII-код 65 =
0100 0001
int n = 300
→ 4 байта → записан в дополнительном коде по 1 байту
double x = 3.14
→ 8 байт → IEEE 754 double
int* p
→ 4 или 8 байт →
адрес
другой ячейки памяти
02
Указатели
Указатель (pointer)
— переменная, которая хранит
адрес
другой переменной в памяти.
int x = 42;
— переменная в ячейке, например, по адресу
0x1000
int* p = &x;
— указатель
p
хранит значение
0x1000
*p
— операция разыменования: читаем значение по адресу, хранящемуся в p → получаем
42
👉
Симулятор цепочки указателей
Нажимай «Следующий шаг», чтобы пройти по цепочке разыменований.
Зачем нужны указатели?
Передача по ссылке
Функция меняет переменную вызывающего кода, не копируя большой объект целиком.
Динамическая память
malloc
/
new
возвращает указатель на выделенный блок. Размер известен только в рантайме.
Структуры данных
Связные списки, деревья, графы — узлы хранят указатели на соседей.
Массивы
Имя массива в C/C++ — это указатель на его первый элемент.
03
Массивы в памяти
Массив — это
непрерывный блок памяти
. Все элементы расположены подряд, вплотную друг к другу.
Для массива
int arr[5]
(каждый
int
= 4 байта) с начальным адресом
0x2000
:
arr[0]
→ 0x2000,
arr[1]
→ 0x2004,
arr[2]
→ 0x2008, …
Адрес элемента i:
base + i × sizeof(тип)
📦
Массив в памяти: визуализатор адресации
Тип элемента
Размер массива
Базовый адрес (hex)
Двумерный массив:
хранится как одномерный, строка за строкой (row-major order в C).
a[i][j]
→
base + (i*cols + j) * sizeof(тип)
. Именно поэтому проход по строкам быстрее прохода по столбцам — данные соседних элементов одной строки находятся рядом в памяти (и вместе попадают в кеш).
04
Иерархия памяти и кеш процессора
Процессор работает с тактовой частотой ~3–5 ГГц. За одну команду — 0.3 нс. Но ОЗУ отвечает за
60–100 нс
. Чтобы не ждать, между процессором и ОЗУ стоит несколько уровней быстрой
кеш-памяти (SRAM)
:
L1 кеш
32–64 КБ · 1–4 цикла (~0.5 нс) · в каждом ядре
↕
L2 кеш
256 КБ – 1 МБ · 10–20 циклов (~5 нс) · в каждом ядре
↕
L3 кеш
8–32 МБ · 30–50 циклов (~15 нс) · общий для ядер
↕
ОЗУ (DRAM)
4–64 ГБ · 200–300 циклов (~80 нс) · медленно!
Аналогия:
процессор — повар, L1 — то, что лежит прямо перед ним на разделочной доске (мгновенный доступ), L2 — на кухонном столе, L3 — в холодильнике рядом, ОЗУ — в кладовке за дверью. Если нужного нет на доске — идёшь дальше, тратишь время.
Принцип работы:
1. Процессор запрашивает данные по адресу
A
.
2. Проверяется L1: нашли? →
cache hit
, данные за ~0.5 нс.
3. Нет в L1? Проверяется L2. Нет? L3. Нет? →
cache miss
, идём в ОЗУ.
4. Данные загружаются из ОЗУ в L3 → L2 → L1
кеш-линией
(64 байта сразу).
5. Следующий доступ к соседним адресам — уже cache hit!
05
Симулятор кеша (прямое отображение)
Кеш с прямым отображением (direct-mapped cache):
каждому адресу ОЗУ соответствует ровно одна строка кеша. Строка определяется по формуле:
строка = адрес mod N
, где N — количество строк кеша.
⚡
Симулятор: direct-mapped cache (8 строк)
Процессор обращается к адресам по очереди. Смотри: hit (зелёный) или miss (красный).
Состояние кеша (8 строк):
Последовательность адресов:
Нажми «Запустить» для начала симуляции.
Обращений
0
Hit
0
Miss
0
Hit rate
—
Задание для самопроверки:
Измени последовательность на
0,8,0,8,0,8
и запусти. Почему hit rate = 0%? (Адреса 0 и 8 конфликтуют — оба отображаются на строку 0 при N=8.) Это называется
cache thrashing
.
06
Мини-тест
🧠
Мини-тест: 5 вопросов