CPU·IV Машина Глава 34 из 65
Близко и далеко
Если такт процессора растянуть до секунды, за числом в оперативную память придётся идти пять минут, к жёсткому диску — год, а ответа из-за океана ждать шестнадцать лет. Эта глава — прогулка по такой масштабной модели: от регистра до другого континента и обратно, с замерами на сервере курса.
Машина
- 28 Биты
- 29 Вентили
- 30 Сумматор и АЛУ
- 31 Память
- 32 Процессор
- 33 Ниже Python
- 34 Кэши вы здесь
- 35 Конвейер
Опирается на: 33 · Рентген Python 14 · Как список лежит в памяти
Что вы унесёте из главы
- прикидывать порядок задержек от регистра до сети и понимать, во что обходится промах
- объяснять, почему одинаковый по сложности код работает с разной скоростью, и обходить данные в порядке памяти
- устроить кэш с вытеснением LRU и понимать, где он помогает, а где нет
Глава 33 кончилась загадкой. Сумма матрицы по строкам и по столбцам — одна и та же работа: те же шестнадцать миллионов сложений, те же машинные команды, только два цикла поменялись местами. А обход по столбцам оказался медленнее в разы. Раз команды одинаковые, дело в том, откуда они берут числа: какие-то лежат близко, какие-то далеко.
Почувствовать эти расстояния трудно: обращение к памяти занимает меньше микросекунды, а микросекунда для человека — ничто. Так бывает и с Солнечной системой: в километрах она непредставима, зато если Солнце — мяч, а Земля — горошина в двадцати шагах от него, картинка встаёт перед глазами. Сделаем такую же масштабную модель для памяти. Растянем время так, чтобы один такт процессора длился секунду, и пройдёмся по этой шкале от регистра до другого континента. По дороге выяснится, почему столбцы медленнее строк и как программы прячут далёкое поближе.
Если такт — секунда
Процессор с частотой 3,3 гигагерца делает такт за 0,3 наносекунды. Это и будет наша секунда. Числа в модели ниже — типичные порядки величин: их собирали Питер Норвиг в таблице к своему эссе «Научитесь программировать за десять лет» (2001) и Джефф Дин из Google в докладах около 2010 года. У каждой конкретной машины они свои и с годами меняются, но порядок держится десятилетиями, и для прикидок нужен именно он.
Регистр — секунда: число уже в руке. Кэш первого уровня, L1, — три секунды: протянуть руку к столу. L2 — около десяти секунд, L3 — меньше минуты: встать и дойти до полки в соседней комнате. Оперативная память — пять с половиной минут: спуститься к соседям за солью. Это ещё быстро. Прочитать кусочек SSD — четыре дня. Спросить сервер в соседней стойке дата-центра — почти три недели. Жёсткому диску, чтобы подвести головку к нужной дорожке, нужен целый год. А пакет через океан и обратно идёт шестнадцать лет: за это время успевают вырасти дети.
Переключите модель на шаги, и получится та же прогулка в пространстве. До L1 — три шага, до оперативной памяти — двести пятьдесят метров, до SSD — двести пятьдесят километров, до жёсткого диска — больше половины экватора, а пакет через океан — почти дорога до Луны.
Калькулятор внизу виджета показывает, что из этого следует. Почти любая программа ходит в память миллиарды раз. Если данные чаще всего находятся рядом, в L1, среднее время обращения близко к наносекунде. Если хотя бы одно обращение из двадцати уходит в оперативную память, среднее вырастает в несколько раз, а если промахов большинство, процессор почти всё время стоит и ждёт. Считается среднее так: $t = h \cdot t_{\text{L1}} + (1 - h) \cdot t_{\text{ОЗУ}}$, где $h$ — доля обращений, нашедших данные рядом. Из-за множителя 100 у второго слагаемого даже маленькая доля промахов решает всё. Кнопки «по строкам» и «по столбцам» подставляют $h$ для обходов матрицы из главы 33; откуда взялось «15 из 16», станет ясно через раздел.
Наносекунда в кармане
Переключите модель на «сколько пролетит свет». За один такт — девять сантиметров, за обращение к L1 — как раз провод Хоппер. Чтобы сигнал успел сходить к памяти и обратно за несколько тактов, память должна лежать в сантиметрах от вычислителя, а сигнал в проводе бежит медленнее света в пустоте. Поэтому самые быстрые уровни памяти живут прямо на кристалле процессора, рядом с АЛУ.
Оперативная память медленна не только из-за расстояния: за её сто наносекунд свет пролетел бы тридцать метров. Ячейку ещё надо найти по адресу, прочитать, усилить слабый сигнал. Большую память быстрой не сделаешь: чем больше ящиков, тем длиннее путь к каждому. Зато для сети расстояние — главный и неустранимый предел. От Москвы до Нью-Йорка около 7500 километров по прямой, а свет в оптоволокне бежит примерно 200 000 километров в секунду. Значит, туда и обратно — не меньше 75 миллисекунд, сколько ни ускоряй серверы. Об этом пределе Хоппер и напоминала своими проводками.
Лестница памяти
Сделать всю память такой же быстрой, как регистры, нельзя: быстрая память бывает только маленькой и дорогой. Регистров у процессора сотни байт, L1 — десятки килобайт на ядро, L2 — от сотен килобайт до нескольких мегабайт, L3 — десятки мегабайт на все ядра, оперативной памяти — гигабайты, диска — терабайты. Каждая ступенька в десятки, а то и в тысячи раз больше предыдущей. Медленнее она в несколько раз, пока мы внутри процессора и оперативной памяти, и в сотни и тысячи раз, когда спускаемся к дискам. Такую лестницу называют иерархией памяти, а время от вопроса до ответа — задержкой.
Ступеньки L1, L2 и L3 — это кэши: маленькие быстрые хранилища копий из большой медленной памяти. Программа о них не знает и ничего у них не просит. Она обращается по адресу, а процессор сам ищет нужный байт сначала в L1, потом в L2, потом в L3 и только потом идёт в оперативную память, оставляя по дороге копии. Узнать, какие кэши у машины, на которой работает песочница курса, можно у самой системы.
Цифры зависят от процессора. Есть способ увидеть лестницу и без справки — измерить её. Возьмём массив и превратим его в один большой круг: в каждой ячейке записан номер следующей, и номера перемешаны случайно. Это связный список из главы 14, узлы которого разбросаны по памяти. Пройти по нему можно только шаг за шагом: пока не прочитаешь ячейку, не знаешь, куда идти дальше. Поэтому время одного шага показывает задержку памяти в чистом виде. Будем увеличивать массив и смотреть, когда он перестанет помещаться в очередную ступеньку.
Линия идёт ступеньками. Пока массив помещается в L1, шаг стоит пару наносекунд (большая часть из них — сам цикл). Когда массив перерастает L1, время прыгает в несколько раз, потом ещё раз на границе L2 и L3, а за пределами кэшей уходит за сотню наносекунд — это оперативная память. У нас на сервере вышло около 2 наносекунд в начале и больше 200 в конце: разница в сто раз, как и обещала модель. На вашем запуске границы ступенек могут сдвинуться — они покажут размеры кэшей той машины, где работает песочница.
Строка кэша
Теперь можно разгадать матрицу. Память ходит в кэш не по байту, а кусками. Кусок называют строкой кэша, на большинстве процессоров это 64 байта подряд (у процессоров Apple — 128; ячейка выше показала размер строки на нашем сервере). Когда нужного байта в кэше нет, случается промах: процессор ждёт, пока из памяти приедет вся строка. Зато следующие обращения к её соседям — попадания, почти бесплатные.
Матрица из главы 33 лежит в памяти строка за строкой, по четыре байта на число. Обход по строкам идёт вдоль памяти: один промах привозит шестнадцать чисел, и пятнадцать следующих обращений — попадания. Вот откуда «15 из 16» в калькуляторе модели. Обход по столбцам прыгает через целую строку матрицы, 4096 чисел, то есть 16 килобайт. Каждое обращение попадает в новую строку кэша. Та же строка кэша понадобится соседнему столбцу уже на следующем круге внешнего цикла, но за один столбец обход задел 4096 разных строк кэша, это 256 килобайт, и к возвращению наша строка давно вытеснена из L1. Промах на каждом шаге.
В маленьком масштабе это видно глазами. Ниже матрица проходит через кэш на несколько строк: красная точка — промах, зелёная — попадание, подкрашены клетки, чьи строки сейчас лежат в кэше.
Сравните три обхода на матрице 8 × 8 со строками по 4 числа и кэшем на 4 строки. По строкам — 16 промахов из 64, меньше не бывает: каждая строка кэша загружена один раз. По столбцам — 64 промаха из 64. Теперь, не меняя обхода по столбцам, увеличьте кэш до 8 строк. Промахов снова 16: первый столбец загрузил 8 строк кэша, и следующим трём столбцам всё уже под рукой. Значит, обход по столбцам плох только тогда, когда столбец не помещается в кэш. Третий способ, «квадратами», обходит матрицу блоками размером со строку кэша, причём внутри блока — по столбцам, и тоже даёт минимум. Так устроены быстрые программы умножения и транспонирования матриц, и так вы решите одну из задач в конце главы.
Тот же опыт можно поставить и в Python. В песочнице есть модуль cs.cachesim: матрица в нём лежит, как в памяти, строка за строкой, а каждое обращение проходит через модель кэша и считается.
512 промахов против 4096 — ровно в восемь раз, по числу элементов в строке кэша. На железе время отличается меньше чем в восемь раз: процессор замечает, что программа идёт по памяти подряд, и сам подкачивает следующие строки заранее. Но и эта хитрость работает только для предсказуемого обхода.
Близость во времени и в пространстве
Кэш размером в доли процента от памяти помогает почти любой программе, и дело в свойстве самих программ, которое называют локальностью. Локальность во времени: то, к чему обращались недавно, скорее всего понадобится снова — счётчик цикла, сумма, верхушка стека. Локальность в пространстве: после адреса $x$ скорее всего понадобится $x + 8$ — следующий элемент массива, следующая команда программы. Строки кэша зарабатывают на втором, вытеснение давно не нужного — на первом.
С этой точки зрения по-новому выглядят структуры данных из второй части курса. Список Python — массив ссылок, лежащих подряд: проход по нему дружит с кэшем. Связный список из главы 14 — цепочка узлов, разбросанных по памяти: каждый переход — потенциальный промах, и опыт со ступеньками показал, во что это обходится. Хеш-таблица из главы 16 нарочно раскидывает ключи как можно случайнее, поэтому каждый поиск — скорее всего промах, и всё равно это одна-две строки кэша вместо двадцати переходов по дереву. Оценка $O(n)$ не видит этих различий: она считает шаги, а не расстояния. Два алгоритма с одной асимптотикой могут отличаться по скорости в разы — смотря как они ходят по памяти.
Обходите данные в том порядке, в каком они лежат в памяти, и возвращайтесь к ним, пока они ещё в кэше. Порядок циклов — бесплатная оптимизация: то же число операций, но меньше ожидания.
Замер на трёх языках
В главе 33 обход матрицы по столбцам на C оказался медленнее примерно в шесть раз. Повторим опыт на чистом Python и на numpy.
У чистого Python разница скромнее, чем у C, и сильно скачет от запуска к запуску: у нас выходило от десяти процентов до двух раз. Причина в главе 33: на каждое сложение интерпретатор тратит десятки наносекунд собственной работы, и ожидание памяти тонет в ней. К тому же список списков хранит ссылки на объекты, разбросанные по памяти, так что промахов хватает в обоих порядках. У numpy числа лежат вплотную, по восемь байт, своей работы почти нет, и разница выходит большой: у нас от десяти до пятнадцати раз. Атрибут strides показывает, на сколько байт надо шагнуть в памяти, чтобы сдвинуться на одну клетку вдоль каждой оси: вдоль строки — 8, вдоль столбца — 24 000. Чем меньше у языка собственной работы, тем заметнее в нём ожидание памяти.
Куда положить строку
До сих пор кэш у нас мог положить любую строку на любое место. Кэши процессора так почти не устроены. Найти строку в кэше — значит сравнить её адрес со всеми, что там лежат, а сравнивать тысячи адресов за такт дорого. Поэтому кэш процессора делят на наборы. Номер набора вычисляется из адреса строки, например как остаток от деления на число наборов, и строка может лечь только в свой набор, на одно из нескольких мест. Если место в наборе одно, кэш называют кэшем с прямым отображением, если мест восемь — восьмиканальным, а если набор один на весь кэш — полностью ассоциативным.
У наборов есть цена: два адреса, которые попадают в один набор, могут выталкивать друг друга, даже когда остальной кэш пуст. Вот два массива по 32 числа, один сразу за другим, и программа складывает их поэлементно.
При прямом отображении a[i] и b[i] всегда попадают в один набор: их адреса отличаются на 32, а это как раз восемь наборов по четыре числа. Каждое обращение выбивает строку, которая понадобится следующей, и попаданий ноль. Два места в наборе уже спасают положение. Поэтому кэши процессоров делают многоканальными, а программисты, которые борются за скорость, избегают массивов, чей размер — большая степень двойки: такие массивы чаще наступают друг другу на наборы. В задаче «Симулятор кэша» вы напишете такой кэш сами.
Кого выселить
Кэш всегда полон: как только программа поработала немного, все места заняты. Каждый промах заставляет решать, чью строку выбросить, чтобы освободить место. Правило напрашивается: выбросить ту, которой дольше всех не пользовались. Если локальность во времени есть, давно забытое, скорее всего, и дальше не понадобится. Это правило называют LRU, от английского least recently used. Есть и другие: выбросить того, кто пришёл первым (FIFO), или случайного.
Правило, лучше которого не бывает, описал в 1966 году Ласло Белади из IBM, изучая вытеснение в виртуальной памяти: выбрасывать того, кто понадобится позже всех остальных. Беда в том, что для этого надо знать будущее. На практике правило Белади служит линейкой: с ним сравнивают выполнимые правила, прогоняя через них одни и те же записанные запросы.
Начните с «любимчика»: A спрашивают через раз. LRU держит его в кэше всё время, и промахов 7 из 12, а FIFO однажды выбрасывает A только потому, что тот пришёл первым, и платит лишним промахом. Теперь выберите «круг» с тремя местами: четыре буквы по кругу. LRU промахивается на каждом запросе — к моменту, когда буква нужна снова, она самая давняя и её только что выбросили. Случайное правило здесь выигрывает у LRU почти вдвое. Это слабое место LRU, и его стоит помнить: если программа ходит по кругу по данным чуть больше кэша, LRU выбрасывает как раз то, что понадобится следующим. Так ведёт себя и обход матрицы по столбцам, с которого началась глава. Поставьте четыре места — и все правила сравняются: круг поместился.
В Python есть готовый кэш с вытеснением LRU — декоратор functools.lru_cache. Он запоминает ответы функции, как мемоизация из главы 22, но хранит не больше maxsize последних, выбрасывая давние.
Семь промахов и пять попаданий, как у LRU в виджете на «любимчике» с тремя местами. Последняя строка показывает, что @cache из главы 22 — тот же lru_cache, только с maxsize=None: он ничего не выбрасывает и растёт без предела. Для рекурсии с памятью это то, что нужно. Для сервера, который запоминает ответы на запросы пользователей, — утечка памяти: через месяц работы кэш съест всю оперативку. Там нужен предел и правило вытеснения.
Кэш как общая идея
Держать копию далёкого поближе — идея, которая работает на каждой ступеньке нашей шкалы, а не только внутри процессора. Мемоизация из главы 22 держит под рукой результаты вычислений, и «далеко» здесь — это время, которое заново ушло бы на подсчёт. Операционная система держит в оперативной памяти недавно прочитанные куски диска, поэтому файл, открытый второй раз, читается мгновенно (подробнее — в главах 38 и 40). Браузер хранит на вашем диске картинки и скрипты сайтов, которые вы уже открывали.
Этот сайт — тоже пример. Фотографии и тяжёлые материалы курсов лежат в хранилище DigitalOcean Spaces в дата-центре во Франкфурте, а страницы ссылаются на них через адрес cdn.legost.in. Это сеть доставки содержимого, CDN: её серверы стоят во многих городах и держат копии файлов, так что ответ приходит из ближайшего, а не из Франкфурта. Когда мы проверяли заголовки ответа для одной из фотографий блога, в них было cache-control: max-age=3600 — браузеру разрешено час не спрашивать картинку заново — и cf-cache-status: HIT: копия нашлась на узле сети доставки, до хранилища запрос не дошёл. Посмотреть такие заголовки можно в инструментах разработчика браузера, на вкладке «Сеть».
У всех этих кэшей одна и та же трудность — копия может устареть. Если фотографию в хранилище заменили, браузер ещё час будет показывать старую, а узлы сети доставки — до тех пор, пока не проверят оригинал. Недаром программисту Филу Карлтону приписывают присловье: в computer science есть только две трудные вещи — инвалидация кэша и придумывание имён.
Задачи
Напишите класс LRUCache. Конструктор принимает вместимость capacity (не меньше 1). Метод get(key) возвращает значение по ключу или None, если ключа нет. Метод put(key, value) кладёт значение или обновляет старое; если ключей стало больше capacity, выбрасывает тот, к которому дольше всех не обращались. Обращением считаются и get, и put.
Каждая операция должна работать за $O(1)$ в среднем: в последнем тесте кэш на 50 000 ключей выдерживает 300 000 операций за три секунды.
Нужны две вещи сразу: найти ключ за $O(1)$ — это словарь, и знать порядок обращений — это очередь, из которой можно вынуть элемент из середины. Список не годится: remove из середины — $O(n)$, как вы видели в главе 14.
Словарь Python помнит порядок вставки. Если при каждом обращении удалять ключ и вставлять заново, он окажется в конце, а самый давний — в начале: next(iter(d)). Ещё удобнее collections.OrderedDict с методами move_to_end(key) и popitem(last=False).
OrderedDict внутри — словарь плюс двусвязный список из главы 14: словарь находит узел, список хранит порядок, и перенос узла в конец — пара переприсваиваний ссылок. Это классическое устройство кэша LRU. Подвох задачи — обновление: put существующего ключа не должен никого выбрасывать, но должен сделать ключ свежим.
Напишите функцию count_misses(trace, line, sets, ways), которая считает промахи кэша на трассе обращений. trace — список адресов в байтах. Строка кэша — line байт: адрес a лежит в строке номер a // line. Кэш состоит из sets наборов, строка номер $k$ может лежать только в наборе k % sets, в наборе ways мест; если набор полон, из него выбрасывается строка, к которой дольше всех не обращались. В начале кэш пуст.
Модулем cs.cachesim пользоваться нельзя — его вы и пишете. В последнем тесте трасса из миллиона адресов, на неё дано четыре секунды.
Сначала переведите адрес в номер строки, потом номер строки — в номер набора. Каждый набор — маленький кэш LRU на ways мест, совсем как в прошлой задаче, только без значений.
Во втором примере строки 0 и 4 попадают в один набор ($0 \bmod 4 = 4 \bmod 4 = 0$), а места в наборе одно — они выбивают друг друга. С ways=2 промахов было бы два.
Полтора десятка строк, и у вас в руках инструмент, которым пользуются архитекторы процессоров: прежде чем делать кэш в кремнии, его проверяют на записанных трассах реальных программ. Меняя line, sets и ways при одном и том же объёме, можно увидеть, как растут промахи от тесноты в наборах, а прогнав трассу с правилом Белади, — сколько теряет LRU по сравнению с идеалом.
Матрицы Matrix из модуля cs.cachesim лежат в памяти строка за строкой, а каждый get и set проходит через общий кэш на 32 строки по 8 чисел. Напишите две функции, которые обходятся минимумом промахов:
col_sums(m, n)— список сумм столбцов матрицыmразмером $n \times n$; для $n = 64$ — не больше 600 промахов;transpose(a, b, n)— записать вbтранспонированнуюa, то естьb[j][i] = a[i][j]; обе матрицы ходят через один кэш; для $n = 64$ — не больше 1200 промахов.
Функции должны работать при любом $n$, не только кратном восьми: тесты проверяют ещё транспонирование при $n = 128$ (не больше 4600 промахов) и при $n = 100$ (не больше 3600). Читать содержимое матриц можно только через get и set. В заготовке — прямолинейные версии: ответы верные, но промахов слишком много.
col_sums: заведите сразу все $n$ сумм и идите по матрице строками, добавляя каждое число в сумму его столбца. Сумм столько же, сколько столбцов, а обход — в порядке памяти.
transpose так не спасти: если читать a по строкам, то писать b приходится по столбцам, и наоборот. Поменяйте циклы местами: промахов столько же. Выход — квадраты, как в виджете с сеткой: обработать блок $8 \times 8$ целиком, пока его строки в кэше и у a, и у b.
Четыре цикла: два внешних идут по углам блоков с шагом 8, два внутренних — по клеткам блока. Края при $n$, не кратном восьми, — через min(start + 8, n).
При $n = 64$ суммы столбцов по строкам дают 512 промахов — по одному на строку кэша, меньше нельзя. Транспонирование блоками — 1024: каждую строку кэша у a и у b загружаем один раз, а прямолинейная версия делает 4608. Блок $8 \times 8$ трогает восемь строк кэша в a и восемь в b, всего 16 из 32 мест, и всё, что ему нужно, лежит рядом до конца его работы. С блоками $4 \times 4$ промахов было бы 1536: каждая строка кэша у b заполняется за два захода и успевает вылететь между ними. Так же, блоками, работают быстрые библиотеки линейной алгебры вроде BLAS, которой numpy поручает произведение матриц.
Куда дальше
Прогулка закончилась там, где началась, у регистров. Процессор, как выяснилось, большую часть времени ждёт данных, и весь его кэш держится на предсказуемости программ: раз программа обратилась сюда, скоро обратится и к соседям. Он и сам подстраивается под программу: замечает последовательный обход и подкачивает строки заранее, не дожидаясь просьбы.
Он делает и больше. Чтобы не стоять без дела, пока данные едут из памяти, процессор угадывает, в какую сторону свернёт ближайший if, и начинает выполнять команды наперёд. Когда угадал — выигрыш, когда нет — результаты выбрасываются, будто ничего не было. Почти ничего: в кэше остаются следы. А мы только что видели, что время обращения выдаёт, лежат данные рядом или далеко. Так процессор, угадывая будущее, иногда выдаёт чужие секреты. Как это устроено и как из этого получилась одна из самых громких уязвимостей в истории, — в главе 35.