Готовый перевод Game Programming Patterns / Паттерны программирования в играх: 5.1 Data Locality

Цель

Ускорить доступ к памяти при помощи кэширования обращений к процессору.

Мотивация

Нас обманывали.

Нам показывают графики где частота процессора растет каждый год, словно закон Мура не просто историческое наблюдение, а какое-то божественное правило.

Не пошевелив и пальцем, мы, ребята из ПО, видим как наши прораммы ускоряются на новом "железе".

Микросхемы становятся быстрее (хотя этот процесс замедлился)

но владельцы заводов "железа" забывают сказать нам кое-что.

Конечно, мы можем обработать данные быстрее, чем когда-либо, но мы не можем их быстрее получить.

Частота процессора и памяти по сравнению со значениями в 1980г. Как видите, процессор "подрос" семимильными шагами, но память еле тащиться вслед за ним.

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

Как видите, память не поспевает за увеличивающейся частотой процессоров.

Совсем не поспевает.

Сегодня, может потребоваться сотни циклов, чтобы получиь байт данных из ОЗУ.

Так если для большинства машинных команд нужны данные, и чтобы их получить, нужно выполнить сотни циклов, как же получается, что процессор не простаивает 99% времени в ожидании данных?

Вообще-то, он и правда простаивает изумительно большое количество времени в наши дни, но, все же, все не так уж плохо, как могло бы быть.

Оперативное Запоминующее Устройство назвали так потому, что в теории, можно получить доступ к любому его участку одинаково быстро.

Вам не нужно беспокоиться о том, надо ли считывать последовательно, как, например, при работе с диском.

Теперь нужно.

Как мы увидим, доступ к ОЗУ по-разному "оперативен".

Склад данных.

Представьте, что вы - бухгалтер в небольшом офисе.

Ваша работа состоит в том, чтобы брать коробки с бумагами и "бухгалтерить" над ними, например, выдавать каждому листу номер.

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

Наверное, мне не следует использовать в качестве аналогии работу, в которой я ничего не смыслю.

Благодаря упорной работе, естественной предрасположенности и стимулянтам, вы можете обработать целую коробку за минуту.

Вот тут и возникает небольшая проблемка.

Все эти коробки находятся на складе в разных зданиях.

Чтобы получить коробку, вам нужно попросить кладовщика вам ее принести.

Он идет, берет грузоподъемник и едет на нем между пролетами, пока не найдет нужную вам коробку.

И у него это занимает, кроме шуток, целый день.

В отличие от вас, ему статус "работника месяца" в ближайшее время не светит.

Значит, как бы быстро вы ни работали, вы получаете по коробке в день.

Остаток времени, вы просто сидите и думаете, как же вас занесло на такую отстойную работу.

Однажды, появляется группа промышленных инженеров.

Их работа состоит в увеличении эффективности операций - вроде ускорения конвеерной обработки.

Понаблюдав за вашей работой два дня, они заметили следующее:

Весьма часто, когда вы закончили одну коробку, следующая коробка лежит неподалеку на той же полке в складу.

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

В углу вашего офиса есть немного свободного места.

"Принцип локальности" означает: "применяется там, где только что, что-то использовалось".

Они применили умное решение.

Когда бы вы не попросили у кладовщика коробку, он хватает их на целую палету.

Он берет нужную вам коробку, а также еще несколько коробок рядом с ней.

Нужны ли они вам, он этого не знает (да его это и не волнует).

; он просто берет столько, сколько влезает на одну палету.

Загружает целую палету и едет с ней к вам.

Пренебрегая безопасностью рабочего пространства, он заезжает в офис и выгружает палету прямо в свободный угол.

Как только вам понадобится новая коробка, первым делом вам надо посмотреть, не лежит ли она на палете в вашем офисе.

Если - да, прекрасно!

У вас займет секунду, чтобы ее подхватить, и вот вы снова обрабатываете числа.

Если палета вместит 50 коробок и вам повезет настолько, что все нужные коробки окажутся на ней, вы сможете обработать в 50 раз больше, чем раньше.

Но если вам понадобится коробка, которой нет на палете - вы вернулись к тому, с чего начинали.

Поскольку у вас в офисе помещается лишь одна палета, ваш друг со склада должен будет забрать ее и привезти взамен полностью новую.

Палету для вашего "процессора".

Как ни странно, это очень похоже на то, как работают процессоры в современных компьютерах.

Если вы еще не поняли, в этом примере вы - процессор.

Ваш стол - это регистры процессора, а коробки с бумагами - это данные, которые можно туда разместить.

Склад - это память вашего компьютера, а этот раздражающий кладовщик - шина, которая подтягивает данные из оперативной памяти в регистры.

Если бы я писал эту книгу 30 лет назад, мой пример бы на этом закончился.

Но, так как процы стали быстрее, а память, так скажем, почти нет, инженеры-электронщики начали искать решения.

Они пришли к идее кэшировать процессор.

У современных компьютеров есть немного памяти прямо на чипе.

Процессор может подтянуть данные оттуда намного быстрее чем из оперативной памяти.

Ее немного, потому что она должна еще влезть на чип, а также потому, что хотя она и более скоростная (SRAM), но и намного более дорогостоящая.

В современном "железо" на самом деле несколько уровней кэша, это как раз и имеется ввиду, когда вы слышите "L1", "L2", "L3" и т.д.

Каждый следующий уровень больше, но при этом медленнее, чем предыдущий.

В этой главе, нас не будет волновать тот факт, что эта память иерархична, но важно об этом знать.

Этот маленький участок памяти называется кэшем ( в частности, участок, расположенный прямо на чипе - это кэш первого уровня)

и в моей аналогии, его роль выполняла палета с коробками.

Каждый раз, как чипу понадобится байт данных с ОЗУ, он автоматически получает порцию последовательных данных - обычно размером от 64 до 128 байтов - и кладет их в кэш.

Эта порция памяти называется кэш-линией.

Когда следующий нужный вам байт данных оказывается в этой порции, ЦП считывает его прямо из кэша, что намного быстрее обращений к ОЗУ.

Успешное нахождение участка данных в кэше называется попаданием в кэш (cache hit).

Если данные там не найти, и приходится лезть за ними в основную память - это промах кэша (cache miss).

Я пропустил, как мининмум,

одну деталь в моем примере.

У вас в офисе нашлось место лишь для одной палеты, т.е. одной кэш-линии.

Реальный кэш содержит набор кэш-линий.

Здесь детально принцип их работы рассматриваться не будет, но чтобы потренировать мозг, ищите "ассоциативность кэша" (“cache associativity”).

При промахах кэша ЦП простаивает - ему нужны данные, чтобы выполнить следующую инструкцию.

Он сидит, сходя с ума от скуки, несколько сот тактов, пока данные не подтянутся.

Наша миссия - избежать этого.

Представьте, вы пытаетесь оптимизировать вот такой, критичный с точки зрения производительности, участок игры:

Переведено на Нотабеноиде
http://notabenoid.org/book/51192/215230

Переводчики: Deo, fragmentic