Как кеш процессора решает судьбу вашего цикла ещё до его выполнения

MAATRIX

Два цикла делают одну и ту же работу с одними и теми же данными — суммируют миллион чисел — но один заметно быстрее другого. Алгоритм одинаковый, сложность одинаковая, «Big O» одинаковый. Разница не в логике, а в том, в каком порядке цикл обращается к памяти. Это решается не в вашем коде, а на уровне кеша процессора — и решается ещё до того, как выполнилась первая инструкция цикла. Разберём, как это работает и почему порядок обхода данных иногда важнее, чем сам алгоритм.

Почему между процессором и оперативной памятью нужна прокладка

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

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

Здесь и кроется идея этой статьи: кеш — не пассивное хранилище «что уже спросили», а активный механизм, который пытается угадать наперёд. И насколько успешно он угадывает — зависит не от него самого, а от того, в каком порядке ваш код читает память.

Три этажа кеша: L1, L2, L3 — и зачем их несколько

Кеш процессора не один — их обычно три уровня, и у них разная роль.

• L1 — самый маленький (обычно десятки килобайт на ядро) и самый быстрый, физически ближе всего к вычислительным блокам ядра. Он разделён на кеш инструкций (что выполнять) и кеш данных (с чем работать). Отклик — единицы тактов.
• L2 — крупнее (обычно от пары сотен килобайт до нескольких мегабайт на ядро), чуть медленнее L1, часто тоже приватный для каждого ядра.
• L3 — самый крупный (десятки мегабайт), общий для всех ядер процессора, и самый медленный из трёх — но всё равно на порядки быстрее RAM.

Почему нельзя сделать один большой и быстрый кеш вместо трёх уровней? Потому что скорость и объём — это компромисс физики: чем больше ячеек памяти нужно опросить, чтобы найти нужный адрес, тем дольше сигнал идёт по кристаллу. Маленький L1 успевает ответить за один-два такта именно потому, что он маленький. Сделать L1 размером с L3 означало бы, что каждое обращение к нему стало бы таким же медленным, как к L3 — то есть весь смысл многоуровневости пропал бы.

Поэтому иерархия работает как воронка: данные, к которым обращаются чаще всего, стремятся осесть в L1; то, что нужно было недавно, но не «горячее» — в L2 и L3. Когда нужных данных нет ни в одном уровне кеша, это называется промах кеша (cache miss), и процессор идёт за данными в RAM — с полной задержкой похода в память.

Для задач с базами данных или с числодробилками выбор конкретного процессора — не абстракция: у разных линеек разный объём и топология L2/L3. Если вы подбираете сервер под тяжёлые вычисления, стоит заранее посмотреть сравнение AMD EPYC и Intel Xeon и общий разбор выбора процессора для баз данных — там кеш процессора один из ключевых параметров сравнения.

Кеш работает не байтами, а строками

Важная деталь, которая многое объясняет дальше: процессор никогда не запрашивает у памяти один байт или даже одно число. Он всегда забирает данные блоком фиксированного размера — этот блок называется строкой кеша (cache line), и на большинстве современных процессоров она равна 64 байтам.

Это значит: если вашему циклу понадобилось прочитать int (4 байта) по адресу X, процессор на самом деле подтягивает в кеш все 64 байта вокруг этого адреса — то есть ещё 15 соседних int, о которых вы, может, и не просили. Логика простая и статистически оправданная: если вы обратились к байту X, очень вероятно, что скоро обратитесь и к соседним байтам — так устроено большинство реальных программ (обход массива, чтение полей структуры, разбор строки посимвольно).

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

Prefetcher: как процессор угадывает ваш следующий шаг

Строка кеша решает проблему «взять с запасом», но у процессора есть механизм ещё активнее — аппаратный prefetcher (блок предвыборки). Это отдельная логика внутри процессора, которая следит за тем, к каким адресам памяти обращается выполняющийся код, ищет в этой последовательности обращений закономерность (паттерн) и, если находит её, начинает заранее, ещё до того как код реально попросит эти данные, подгружать следующие строки кеша из RAM в кеш.

Самый простой и самый надёжно распознаваемый паттерн — это последовательный доступ: адрес 100, потом 164, потом 228 (шаг в 64 байта, то есть строка за строкой). Prefetcher такую закономерность видит буквально за пару обращений и дальше начинает грузить строки кеша с опережением — пока процессор ещё считает предыдущий элемент, следующий уже едет из RAM в L2 или L1. К моменту, когда цикл реально дойдёт до этого элемента, ждать почти не приходится: промах кеша превратился в попадание, потому что данные подготовили заранее.

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

Важная оговорка: prefetcher — это эвристика, а не телепат. Он умеет уверенно распознавать простые регулярные паттерны (последовательный проход, проход с постоянным шагом-«страйдом», иногда — несколько параллельных потоков доступа). Сложные паттерны с точки зрения prefetcher неотличимы от случайности, даже если для вашей задачи в них есть смысл. Поэтому граница «предсказуемо / непредсказуемо» — это не про то, разумна ли логика вашего кода, а про то, видна ли эта логика в чистой последовательности адресов памяти.

Почему проход по массиву в разы приятнее прохода по случайным адресам

Соберём это в конкретный пример. Допустим, у вас есть миллион чисел, и вам нужно посчитать их сумму. Два способа хранения дадут принципиально разное поведение кеша при одинаковой логике «пройти и просуммировать».

Способ первый — непрерывный массив:

int sum = 0;
for (int i = 0; i < N; i++) {
    sum += array[i];   // адреса идут подряд: i, i+4, i+8, ...
}

Каждое обращение — соседний адрес. Prefetcher распознаёт паттерн со второго-третьего шага и начинает подгружать данные с опережением. Большая часть обращений после разогрева цикла обслуживается из L1/L2, а не из RAM.

Способ второй — связный список с теми же числами:

struct Node { int value; Node* next; };
int sum = 0;
Node* cur = head;
while (cur) {
    sum += cur->value;   // адрес следующего узла непредсказуем
    cur = cur->next;
}

Здесь адрес следующего узла — это указатель, полученный из предыдущего узла, а узлы были выделены аллокатором в произвольном порядке (тем более если список долго жил и в него что-то добавляли и удаляли — узлы разбросаны по куче фрагментами). Prefetcher не видит закономерности: следующий адрес известен только после того, как прочитан текущий узел. Каждый переход по next рискует быть промахом кеша.

Логическая сложность у обоих циклов одинаковая — O(n), одно сложение на элемент. Но у массива это преимущественно работа с кешем, а у списка — преимущественно ожидание памяти. Насколько именно это заметно на конкретном железе — зависит от объёма данных, от того, помещается ли массив в L2/L3 целиком, от конкретного процессора; точных цифр без замера на своём стенде я приводить не буду. Но качественная разница — «поток из кеша» против «череда промахов» — устойчиво воспроизводится и хорошо задокументирована как общее свойство архитектуры кеша, а не особенность одного языка или компилятора.

Тот же эффект проявляется в обходе двумерных массивов (матриц) — если хранение по строкам (row-major, как в C/C++/Python/NumPy по умолчанию), а обход идёт по столбцам, вы фактически превращаете последовательный по памяти паттерн в скачущий:

# Хорошо: внутренний цикл идёт по строке — адреса подряд
for i in range(n):
    for j in range(m):
        total += matrix[i][j]

# Плохо: внутренний цикл идёт по столбцу — каждый шаг прыгает на всю ширину строки
for j in range(m):
    for i in range(n):
        total += matrix[i][j]

Оба варианта считают одну и ту же сумму, но во втором каждый шаг внутреннего цикла перескакивает в памяти на целую строку матрицы вперёд — паттерн для prefetcher рвётся, и то, что должно было идти из L1, снова и снова уходит в RAM.

Как это применять на практике: структуры данных и порядок обхода

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

Предпочитайте непрерывные структуры указателям, когда это возможно. Массив или динамический вектор (Vec, ArrayList, обычный список Python поверх массива указателей) для последовательного обхода почти всегда выигрывает у связных списков и деревьев с разбросанными по куче узлами — именно за счёт кеша, а не за счёт меньшего числа операций.

Обходите данные в том порядке, в котором они физически лежат. Для двумерных массивов и матриц — это порядок хранения (row-major или column-major, в зависимости от языка). Для структур в БД или в файлах — порядок, в котором данные были записаны на диск, а не порядок, который логически удобен для вашей задачи.

Группируйте то, что читаете вместе. Если из структуры на 200 байт в горячем цикле используются только пара полей, а остальное — редко нужные метаданные, каждое обращение всё равно тянет за собой всю строку кеша, значительная часть которой пропадает впустую. Это соображение стоит за паттерном AoS vs SoA (array of structs vs structure of arrays): вместо массива объектов с полями {x, y, z, color, metadata} иногда выгоднее хранить отдельные массивы x[], y[], z[] — если горячий цикл использует только x и y, он будет читать плотный, ничем не разбавленный поток нужных чисел.

Не гонитесь за микрооптимизацией вслепую. Прежде чем переписывать структуры данных ради кеша, убедитесь измерением, что цикл действительно упирается в память, а не, например, в системные вызовы или сеть. Разобраться, где реально уходит время внутри вашего кода, помогает профилирование приложения прямо на проде — без этого шага легко «оптимизировать» то, что и так не было узким местом.

Помните про многопоточность. На серверах с несколькими сокетами память физически ближе к одному процессору и дальше от другого — это отдельный эффект NUMA поверх эффекта кеша, и он тоже завязан на то, откуда именно поток забирает данные. Если интересно, как это устроено и когда сервер с двумя CPU может оказаться медленнее одного — есть отдельный разбор о том, что такое NUMA и когда два процессора работают медленнее одного.

Всё это не отменяет важность алгоритмической сложности — O(n log n) не станет быстрее O(n²) за счёт удачного порядка обхода на сколько-нибудь больших n. Но при прочих равных, на данных, которые помещаются в кеш при удачном доступе и не помещаются при неудачном, разница в реальном времени выполнения может быть больше, чем от иной алгоритмической оптимизации — просто потому, что она решается не в «сложности», а в физике доступа к памяти.

Частые вопросы