Данные, удобные кэшу

Фото нужно повернуть на 90°. Программа — два цикла: взять пиксель (y, x), положить его в повёрнутую картинку на место (x, h − 1 − y). Сколько ни переставляй циклы, копирований ровно столько, сколько пикселей. А время отличается в разы, потому что память приходит в кэш строками по 64 байта, и важно, сколько раз каждую строку придётся везти заново. Ниже — поворот на модели кэша размером 4 КБ: слева картинку читают, справа пишут, а то, что сейчас лежит в кэше, подсвечено.

При обходе по строкам чтение идёт подряд — каждая строка памяти исходника загружается один раз. Зато запись идёт вниз по столбцу результата: каждый следующий пиксель — в новую строку памяти, и пока программа вернётся к ней со следующим пикселем, кэш уже давно её выбросил. Переключите слой на «сколько раз грузили»: правая картинка красная, каждая её строка памяти загружена по 16 раз — по разу на каждый пиксель. Всего промахов 34 000 при минимуме 4 000. Блоки 16 × 16 доводят их до 5 792.

А теперь выберите высоту 256. Картинка выше всего на шесть пикселей, но блоки перестают помогать: промахов снова 34 816, как при обходе по строкам. Добавьте строкам запас — и промахов ровно 4 096, минимум. Как это получается, разберём ниже, а сначала — общее правило.

Идея

Кэш помогает программе, которая трогает память подряд, возвращается к данным, пока они ещё в кэше, и держит рядом то, что нужно вместе. Каждому из трёх правил соответствует приём: порядок обхода, обход блоками, раскладка данных. Ни один из них не меняет O-большое — число операций то же. Меняется число походов в память, а поход в память стоит в сотню раз дороже операции.

Как устроены кэш, его строки и наборы, рассказано в главе курса «Близко и далеко», а сколько стоит каждый уровень памяти — в статье «Числа, которые стоит знать». Здесь — что с этим делать в коде.

Обход блоками

Почему обход по строкам плох при повороте? Чтобы строка памяти результата пригодилась повторно, она должна дожить в кэше до следующей строки исходника. А за это время программа успевает записать по пикселю в каждую строку результата — их столько, какова ширина картинки. У фото шириной 2000 пикселей это 2000 строк памяти, 128 КБ: больше, чем кэш первого уровня.

Блоки меняют счёт. Возьмём квадрат 32 × 32 пикселя исходника и повернём его целиком, прежде чем идти дальше. Строка квадрата — 32 пикселя по 4 байта, две строки кэша, так что квадрат исходника занимает 64 строки кэша и квадрат результата столько же: всего 8 КБ, а в кэше первого уровня обычно 32–48 КБ. Пока квадрат не закончен, ни одна его строка не вылетает, и каждая загружается один раз. Размер блока подбирают так, чтобы оба квадрата с запасом помещались в кэш; для пикселей по 4 байта это 16–32, иногда 64. Тот же приём лежит в основе быстрого умножения матриц: библиотеки линейной алгебры перемножают блоками, подобранными под размеры кэшей.

Есть и способ, которому размер кэша знать не нужно. Разрежем картинку пополам по длинной стороне и повернём каждую половину, разрезая её дальше, пока куски не станут маленькими. На каком-то уровне деления куски поместятся в кэш, какого бы размера он ни был, — и дальше всё работает как с блоками. Такие алгоритмы называют не зависящими от кэша; их предложили Маттео Фриго, Чарльз Лейзерсон, Харальд Прокоп и Шридхар Рамачандран в 1999 году.

Ловушка: строка длиной 4 КБ

Теперь высота 256. Кэш делит строки памяти на наборы, и строка может лечь только в свой набор — его номер берётся из адреса. В модели наборов 16 по 4 места, и адреса, отстоящие на 1 КБ, попадают в один набор. Строка повёрнутой картинки — это h пикселей по 4 байта. При высоте 250 это 1000 байт, и строки результата расходятся по разным наборам. При 256 — ровно 1024 байта, и все 16 строк результата из блока попадают в один набор с четырьмя местами. Они выталкивают друг друга, и каждая запись — промах.

В настоящем процессоре то же самое, только в масштабе: в кэше первого уровня обычно 64 набора, и адреса через каждые 4 КБ попадают в один набор. Опасна строка, длина которой кратна 4 КБ, то есть картинка с высотой, кратной 1024 пикселям: 2048, 3072, 4096. Вот поворот настоящей картинки шириной 2000 пикселей при высотах около 3072:

Этот замер сделан на компьютере автора: пик зависит от того, как устроен кэш конкретного процессора, и на сервере сайта его не видно. На высоте 3072 и обход по строкам, и обход блоками на Go в несколько раз медленнее, чем на соседних высотах, — пик торчит над графиком. Лечится это запасом: строка результата в памяти делается чуть длиннее, чем нужно, и неиспользуемые пиксели в конце просто пропускаются. Графические библиотеки так и хранят картинки — с длиной строки в памяти (stride) отдельно от ширины. Правило запаса: строка должна занимать нечётное число строк кэша. Просто прибавить 16 пикселей недостаточно: при высоте 3056 это даст как раз 3072.

В numpy пика нет: поворот функцией rot90 с копированием проходит эти высоты ровно. А блоки, написанные вручную на Python, медленнее готовой функции — каждый блок стоит нескольких вызовов из интерпретатора. Для numpy вывод простой: не изобретать, а пользоваться готовым.

Раскладка: массив структур и структура массивов

Третье правило — держать рядом то, что нужно вместе. Модель частиц: у каждой координаты, скорости, масса и номер — восемь полей по 8 байт, 64 байта, ровно строка кэша. Нужна сумма масс. Если частицы лежат массивом структур, каждая строка кэша приносит одну массу и семь ненужных полей. Если массы лежат отдельным массивом, одна строка приносит восемь масс.

Пока частиц тысяча, все они помещаются в кэш, и разница невелика. С сотен тысяч массив структур отстаёт — на Go в 7–11 раз, в numpy, где структурный массив сравнивается с обычным, в 7–16 раз. Так устроены колоночные базы данных и форматы вроде Parquet: аналитический запрос читает два столбца из сорока, и хранить таблицу по столбцам выгоднее, чем по строкам. Обратный случай тоже бывает: если код почти всегда берёт все поля объекта сразу, массив структур лучше — одна строка кэша приносит всё нужное.

Хуже обеих раскладок — объекты, разбросанные по памяти и связанные указателями: каждый переход — погоня за адресом, как в замере из статьи о задержках. Поэтому массив почти всегда обходится быстрее связного списка, а B-дерево, у которого в узле много ключей подряд, часто обгоняет двоичное дерево поиска даже в памяти.

Код

Модель из сцены: тот же кэш, те же порядки, те же числа.

Обход по строкам и по столбцам стоят одинаково — 8,5 минимума: в одном случае каждый раз промахивается запись, в другом — чтение. Блоки 8 × 8 хуже блоков 16 × 16: в строке кэша 16 пикселей, и блок шириной 8 использует строку наполовину, а за второй половиной приходится возвращаться. При высоте 256 не спасают никакие блоки, а запас в 16 пикселей даёт ровно минимум — каждая строка памяти загружена один раз.

А это настоящий поворот из замера: блоки и строка результата с запасом.

Сколько это стоит

O-большое не меняется: поворот картинки из N пикселей — N копирований при любом порядке. Чтобы увидеть разницу, нужна другая мера — число переносов блоков между уровнями памяти. Такую модель, модель внешней памяти, предложили Алок Аггарвал и Джеффри Виттер в 1988 году: память быстрая, но маленькая, на M элементов, обмен с медленной идёт блоками по B элементов, и считаются только обмены. Пройти массив из N элементов стоит N/B обменов. Поворот по строкам — почти N: каждая запись в новый блок. Поворот блоками — около 2N/B, если блок картинки помещается в быструю память. Та же модель объясняет внешнюю сортировку и B-деревья, только вместо кэша и памяти там память и диск.

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

Задачи

Задача — та же модель кэша, но на матрице и с настоящими параметрами: обход по строкам, по столбцам и блоками, и матрицы, у которых строка ровно 2 КБ.