rorikstr/hyperion
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
hyperion/10-linux/30-computer-arch/Кэш, регистры, кэш-линия.md

19 KiB
Raw Permalink Blame History

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

1. Регистры (Registers)

Это самая быстрая память, которая находится прямо в ядре процессора.

  • Аналогия: Это твои руки. Данные здесь — это то, что ты держишь прямо сейчас.
  • Объем: Крошечный. Регистров всего несколько десятков штук (например, 16 регистров общего назначения в x86-64).
  • Размер: В архитектуре x86-64 (64-битной) один регистр вмещает ровно 64 бита (8 байт).
  • Скорость: 0 тактов (мгновенно). Арифметические операции (сложение, умножение) процессор может делать только над значениями, которые уже лежат в регистрах.
  • SIMD-регистры: Это особые широкие регистры (128, 256 или 512 бит), в которые можно положить сразу пачку чисел (например, четыре float32) и обработать их одной инструкцией. Именно их использует Rust-компилятор для векторизации.

2. Кэш процессора (CPU Cache)

Это сверхоперативная память типа SRAM (Static RAM), расположенная на кристалле процессора. Она нужна, чтобы процессор не простаивал, ожидая данные из медленной оперативной памяти (RAM).

  • Аналогия: Это верстак или рабочий стол. Данные здесь лежат "под рукой".
  • Уровни (L1, L2, L3):
    • L1 (Level 1): Самый маленький (например, 32 КБ для команд + 32 КБ для данных на ядро), но самый быстрый. Доступ занимает ~3-4 такта.
    • L2: Побольше (256 КБ - 1 МБ на ядро), чуть медленнее (~10-12 тактов).
    • L3: Общий для всех ядер (десятки МБ), еще медленнее (~40-50 тактов), но все равно намного быстрее RAM.

3. Кэш-линия (Cache Line)

Это минимальная единица обмена данными между RAM и кэшем.

  • Размер: Стандарт индустрии — 64 байта.
  • Суть: Процессор не умеет читать из памяти "один байт". Если твой код просит переменную типа u8 (1 байт), процессор всё равно загрузит из RAM целую линию (64 байта), в которой лежит этот байт, и поместит её в кэш.
  • Почему это важно для структур данных:
    • Если у тебя массив (или Vec), данные лежат плотно. Загрузив одну кэш-линию, процессор получает сразу 16 чисел i32 (так как 16 * 4 байта = 64). Следующие 15 обращений к массиву будут мгновенными (взяты из L1 кэша).
    • Если у тебя связный список, каждый элемент может лежать в памяти далеко друг от друга. Чтобы прочитать 16 элементов, процессору придется 16 раз сходить в медленную RAM, загружая 16 разных кэш-линий, из которых полезными будут только по 4-8 байт. Это называется Cache Miss (промах кэша), и это убивает производительность.

Итог

  1. Процессор загружает данные из RAM кэш-линиями (по 64 байта) в кэш.
  2. Из кэша данные попадают в регистры (по 8 байт).
  3. АЛУ (арифметико-логическое устройство) выполняет операции над регистрами.

В B-Tree мы храним ключи массивом, поэтому одна загрузка кэш-линии дает нам сразу много ключей для сравнения, и мы максимально эффективно используем эту механику.

1 2 3 4 5 6 7 8 9 10

Помимо иерархии памяти (Регистры → Кэш → RAM), для написания высокопроизводительного кода (особенно на Rust/C++) критически важно понимать еще три концепции. Они объясняют, почему "наивный" код часто работает медленнее, чем мог бы.

1. Конвейер (Pipeline) и Предсказание ветвлений (Branch Prediction)

Современный процессор — это фабрика. Он не делает одну инструкцию за раз; он выполняет их параллельно на разных стадиях (чтение, декодирование, выполнение, запись).

  • Проблема: Когда процессор видит условный переход if (ветвление), он не знает, куда пойдет код дальше, пока условие не вычислится.
  • Решение: Процессор угадывает (Branch Prediction). Он начинает выполнять ветку true заранее (спекулятивное выполнение).
  • Цена ошибки: Если процессор не угадал (Branch Misprediction), он должен выбросить все вычисления и начать заново с правильной ветки. Это огромная потеря времени (10-20 тактов).
  • Для разработчика:
    • Отсортированные массивы обрабатываются быстрее (паттерн ветвлений предсказуем: TTTTFFFF).
    • В B-Tree поиск внутри узла часто делают линейным (без ветвлений, через SIMD) или оптимизированным бинарным, чтобы не сбивать предсказатель.

2. Виртуальная память и TLB (Translation Lookaside Buffer)

Адреса, которые видит твоя программа (например, указатель 0x7ff...), — ненастоящие. Это виртуальные адреса. Процессор должен каждый раз переводить их в физические адреса RAM.

  • TLB: Это специальный маленький "кэш для адресов". Он помнит последние переводы страниц памяти.
  • TLB Miss: Если ты прыгаешь по памяти слишком хаотично (например, в огромном графе или HashMap), TLB не находит перевод, и процессору приходится лезть в "таблицы страниц" (Page Walk), что очень дорого.
  • Почему это важно: Локальность данных (B-Tree, массивы) спасает не только кэш данных (L1/L2), но и TLB. Меньше прыжков по страницам — быстрее работа.

3. Суперскалярность и Зависимость по данным (Data Dependency)

Ядро процессора имеет несколько исполнительных блоков (ALU). Оно может выполнить, например, 4 сложения за один такт, если они независимы.

  • Плохо: a = b + 1; c = a + 2; (Второе действие ждет первого).
  • Хорошо: a = b + 1; c = d + 2; (Процессор сделает это одновременно).
  • Для разработчика: Иногда развертывание циклов (loop unrolling) или обработка данных независимыми блоками дает ускорение именно за счет загрузки всех ALU ядра.

ИТОГ: Ключевые элементы процессора для программиста

Чтобы писать эффективный код (особенно структуры данных), нужно держать в голове эту "карту железа":

Элемент Что это Почему важно понимать
Регистры Рабочая зона ядра (мгновенно) Данные должны быть здесь для вычислений. Компилятор пытается держать "горячие" переменные тут.
Кэш-линия 64 байта данных (транспорт) Читаем память блоками. Массивы (Vec) — короли, связные списки — зло. B-Tree выигрывает за счет плотности данных.
Кэш (L1/L2/L3) Быстрая память (на кристалле) Cache Miss — главный враг производительности. Чем компактнее твои данные, тем больше их влезет в кэш.
Branch Predictor Предсказатель if'ов Непредсказуемые условия (рандомные if) сбрасывают конвейер. Иногда лучше вычислить лишнее, чем ветвиться.
SIMD Векторные инструкции Обработка 4-8 чисел одной командой. Rust делает это сам, если ты используешь итераторы и простые циклы.
TLB Кэш адресов памяти Хаотичные прыжки по памяти (Pointer Chasing) забивают не только кэш данных, но и TLB.

Главный вывод для Rust-разработчика: Думай о памяти как о ленте, которую нужно читать подряд. Любой указатель (Box, ссылка, узел графа) — это разрыв ленты, который стоит дорого. Структуры данных, которые минимизируют эти разрывы (как B-Tree или Vec), всегда будут побеждать на современном железе.

Это отличный вопрос. Твоя ментальная модель ("загружается в L1, потом копируется в L2") немного перевернута. В реальности все происходит ровно наоборот по направлению, но гораздо интереснее в деталях.

Давай разберем анатомию клонирования (например, строки или вектора) на уровне железа. Представим, что мы делаем let b = a.clone();.

1. Иерархия: Путь еды (данных)

Сначала важно понять: процессор (ядро) слеповат. Он может работать только с тем, что лежит у него "в руках" — в регистрах (крошечная память прямо внутри ядра).

  • RAM (Оперативная память): Это "склад" в соседнем здании. Огромный, но медленный.
  • L3 Кэш: Это "разгрузочная зона" на этаже. Общая для всех ядер.
  • L2 Кэш: Это "холодильник" на кухне конкретного ядра.
  • L1 Кэш: Это "разделочная доска" прямо перед руками повара. Самая быстрая.

2. Процесс клонирования (пошагово)

Когда ты вызываешь clone(), происходит операция Read (чтение источника) + Write (запись копии).

Этап А: Чтение (Read) — "Доставка на кухню"

Процессор говорит: "Мне нужны данные по адресу A (источник)".

  1. Поиск: Он ищет их в L1. Если нет — в L2. Если нет — в L3. Если нет — идет в RAM.
  2. Cache Line Fill: Данные никогда не ходят по одному байту. Они ходят "пачками" по 64 байта (Cache Line). Даже если тебе нужен 1 байт, из RAM вытащится вся линия (64 байта) и по цепочке RAM -> L3 -> L2 -> L1 приедет к ядру.
  3. Регистры: Наконец, данные (или их часть) попадают в регистры процессора (например, в 256-битные регистры AVX, если копируем быстро).

Этап Б: Запись (Write) — "Создание клона"

Теперь процессор должен записать эти данные по новому адресу B (куда мы клонируем).

  1. Allocation: Сначала Rust (аллокатор) находит свободное место в памяти для B.
  2. Store (Запись): Процессор пишет данные из регистров в L1 кэш по адресу B.
    • Важный нюанс: Он не пишет сразу в RAM! Это было бы безумно медленно.
    • Он пишет в L1 и помечает эту строку как Dirty (Грязная). Это значит: "Эта версия новее, чем то, что лежит в RAM. Не потеряй".

Этап В: Вытеснение (Eviction) — "Уборка"

Вот тут рушится твое предположение про "копируется в L2". Данные попадают в L2 не потому что они "нужны там для работы", а потому что в L1 закончилось место.

  1. Когда L1 переполняется, старые или "грязные" данные вытесняются вниз — в L2.
  2. Когда L2 переполняется — в L3.
  3. И только когда L3 переполняется или процессор явно командует (сброс кэша), данные улетают в RAM.

3. "Кишечные" оптимизации (SIMD и Prefetching)

Если бы процессор копировал байт за байтом через обычные регистры (по 64 бита), это было бы медленно. В Rust (и в libc memcpy) клонирование оптимизировано жестко:

  1. SIMD (Single Instruction, Multiple Data): Процессор использует широкие регистры (AVX/SSE). За один такт он может "вдохнуть" 32 или 64 байта данных источника в регистр и "выдохнуть" их в новое место в L1. Это как переносить воду ведрами, а не ложками.

  2. Non-Temporal Stores (Обход кэша): Это хардкорная тема. Если ты клонируешь гигантский массив (больше размера кэша, например 100 МБ), процессор понимает: "Если я сейчас запихну эти 100 МБ в L1, я вытесню оттуда все полезные данные моей программы, а этот массив мне сейчас не нужен для вычислений, я просто копирую". В этом случае используются специальные инструкции (например, movntdq в x86), которые пишут данные мимо L1 и L2, сразу в буфер записи (Write Combining Buffer) и оттуда в RAM. Это называется "не засорять кэш" (cache pollution).

Итог для Rust-разработчика

Когда ты делаешь clone():

  1. CPU: Читает кусок памяти A в регистры (протаскивая через все кэши вверх).
  2. CPU: Пишет из регистров в L1 по адресу B.
  3. Кэш-контроллер: Асинхронно, в фоновом режиме, когда-нибудь потом спускает эти данные из L1 вниз до RAM.

Взаимодействие с оперативной памятью есть, но оно отложено во времени (Write-Back), чтобы твой код не тормозил, ожидая записи в медленную RAM.