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

Цель

Deo 21.08.14 в 18:35

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

Deo 21.08.14 в 18:36

Мотивация

fragmentic 17.07.14 в 16:57

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

Deo 21.08.14 в 18:58

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

Deo 21.08.14 в 18:38

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

Deo 21.08.14 в 18:40

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

Deo 21.08.14 в 18:42

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

Deo 21.08.14 в 18:43

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

Deo 21.08.14 в 18:44

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

Deo 21.08.14 в 18:46

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

Deo 21.08.14 в 18:51

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

Deo 21.08.14 в 18:52

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

Deo 21.08.14 в 18:52

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

Deo 21.08.14 в 18:54

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

Deo 21.08.14 в 18:56

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

Deo 21.08.14 в 19:00

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

Deo 21.08.14 в 19:03

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

Deo 21.08.14 в 19:06

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

Deo 21.08.14 в 19:09

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

Deo 21.08.14 в 19:10

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

Deo 21.08.14 в 19:10

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

Deo 21.08.14 в 19:11

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

Deo 21.08.14 в 19:12

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

Deo 21.08.14 в 19:18

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

Deo 21.08.14 в 19:19

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

Deo 21.08.14 в 19:22

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

Deo 21.08.14 в 19:22

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

Deo 21.08.14 в 19:24

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

Deo 21.08.14 в 19:26

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

Deo 21.08.14 в 19:27

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

Deo 21.08.14 в 19:28

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

Deo 21.08.14 в 19:28

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

Deo 21.08.14 в 19:29

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

Deo 21.08.14 в 19:30

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

Deo 21.08.14 в 19:31

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

Deo 21.08.14 в 19:34

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

Deo 21.08.14 в 19:35

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

Deo 21.08.14 в 19:36

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

Deo 21.08.14 в 19:37

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

Deo 21.08.14 в 19:59

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

Deo 21.08.14 в 20:04

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

Deo 21.08.14 в 20:06

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

Deo 21.08.14 в 20:08

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

Deo 21.08.14 в 20:08

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

Deo 21.08.14 в 20:10