live13 (live13) wrote,
live13
live13

Category:

Шаблоны игрового программирования. Локальность данных

Локальность данных( Data Locality)


Оглавление


Задача



Ускорение доступа к памяти с помощью более удобного для кэширования процессором размещения данных.

Мотивация



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

Чипы становятся быстрее(хотя сейчас мы приближаемся к плато на графике), но производители железа кое-что утаивают. Мы конечно можем теперь обрабатывать данные быстрее, но мы не можем ускорить сами данные.

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

    Данные взяты из Computer Architecture: A Quantitative Approach Джона Л. Хеннеси, Девида А. Паттерсона, Андре С.Арчи-Дюссо по мотивам презентации Тони Альбрехта “Pitfalls of Object-Oriented Programming”.




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

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

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

    И в конце концов вы не должны. Как мы сейчас увидим, оперативная память совсем не настолько хорошо обеспечивает случайный доступ.


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

Хранилище данных



Представьте себе что вы клерк в маленьком офисе. Ваша работа заключается в запросе коробок с бумагами и выполнении с ними какой-то бухгалтерской работы - складывать всякие числа или что-то в таком духе. Вы работаете с коробками подписанными специальным сакральным образом, понятным другим бухгалтерам.

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


Благодаря тяжелой работе, врожденным способностям и стимуляторам, вы можете справиться с одной коробкой скажем за минуту. Но есть одна проблема. Все коробки хранятся в хранилище, расположенном в соседнем здании. Чтобы взять коробку, вам нужно попросить кладовщика принести ее вам. Он идет на склад, садится в грузоподъемник и едет по проходам между стойками, пока не доберется до нужной коробки.

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

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


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

      Технически это называется локальность ссылок ( locality of reference).


  • Использовать погрузчик для перевозки всего одной коробки с бумагами - довольно глупая затея.

  • У вас в офисе есть никем не используемый угол.



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

Нагруженный паллет он привозит вам. Игнорируя технику безопасности, он заезжает на погрузчике в офис и оставляет паллет в углу офиса.

Когда вам понадобится новая коробка, вы теперь первым делом должны проверить, не находится ли она уже на паллете в вашем офисе. Если, да - то это просто отлично! Вам придется потратить всего несколько секунд чтобы взять ее и продолжить работу с цифрами. Если на паллете окажется пятьдесят коробок и они все вам нужны - значит в этот день вы сделаете в пятьдесят раз больше работы.

Но вот если вам нужна коробка, которой на паллете нет, вы возвращаетесь к старому сценарию. Так как у вас в офисе помещается только один паллет, вашему приятелю со склада придется забрать тот что лежит у вас в офисе и привезти новый.

Паллет для процессора



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

Если бы эта глава писалась тридцать лет назад, на этом аналогия и заканчивалась бы. Но как только чипы начали стремительно становиться быстрее, а память - нет, разработчики аппаратного обеспечения начали искать решение проблемы. Решение, которое они предложили - это кэш процессора.

Современные компьютеры имеют небольшую память, размещенную прямо в процессоре. Процессор может получать из нее данные гораздо быстрее чем из основной памяти. Она не слишком большая по объему потому что много в чип не поместится и к тому же быстрая статическая память (static RAM или SRAM) гораздо дороже обычной.

    В современном железе обычно присутствует кэш нескольких уровней. Вы наверняка слышали как их называют “L1”, “L2”, “L3” и т.д. Каждый уровень больше и медленнее предыдущего. В этой главе мы не будем вспоминать о том что память организована в такую иерархию, но вам все равно стоит об этом знать.


Эта маленькая порция памяти называется кэш (точнее говоря, находящийся на чипе кэш первого уровня) и в нашей аналогии работает как паллет с коробками. И когда вашему процессору потребуется байт данных из памяти, он автоматически извлекает последовательную порцию данных из памяти - обычно 64 или 128 байт и помещает ее в кэш. Эта порция данных называется блок данных или строка кэша(cache line).



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

    В аналогии я приукрасил одну деталь (по крайней мере). В вашем офисе есть место только для одного паллета, т.е. одна строка кэша. Настоящий кэш содержит несколько строк кэша. Детали реализации выходят за рамки рассмотрения книги, но если вам интересно - советую погуглить по запросу "ассоциативность кэша" ("cache associativity").


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


for (int i = 0; i < NUM_THINGS; i++)
{
sleepFor500Cycles();
things[i].doStuff();
}


Что вам хочется изменить в этом коде в первую очередь? Совершенно верно. Убрать этот бесполезный и затратный вызов функции. Этот вызов эквивалентен цене кеш-промаха для производительности. Каждый раз когда вас выкидывает в основную память, вы вставляете в свой код задержку.

Что? Производительность данных?



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

Когда примеры заработали, я был крайне удивлен. Я предполагал что разница будет заметна, но даже не предполагал насколько она велика, пока не увидел это своими глазами. Я написал две программы, выполняющие одинаковые вычисления. Единственное отличие заключалось в количестве допускаемых кэш-промахов. Более медленная программа работала в пятьдесят раз медленнее.

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

    Так что оценка может варьироваться.


Это просто открыло мне глаза. Я привык думать о производительности категориями кода, а не данных. Сами байты не бывают быстрыми или медленными - это просто статичные состояния. Но из-за того что у нас есть кэш, способ организации данных напрямую влияет на производительность.

Сложность заключается в том чтобы подать это таким образом чтобы нам хватило одной главы. Оптимизация для кэша - тема обширная. А я ведь даже еще ничего не рассказал о кэшировании инструкций(instruction caching). Вы ведь помните, что код тоже находится в памяти и должен быть загружен в процессор перед тем как будет выполнен. Кто-то более сведующий в теме мог бы написать об этом целую книгу.

    И такая книга действительно существует: Data-Oriented Design Ричарда Фабиана.


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

Все сводится к одной простой мысли: когда чип выполняет чтение из памяти, он считывает целую строку кэша. Чем больше вы уместите в эту строку кэша, тем большую скорость получите. Так что наша цель заключается в том, чтобы организовать структуры данных таким образом, чтобы обрабатываемые вами вещи находились в памяти одна за другой.

    Здесь есть одно существенное допущение: один поток. Если вы изменяете близкорасположенные данные в разных потоках - вам выгоднее иметь их в разных строках кэша. Если два потока пытаются изменить данные в одной строке кэша, обеим ядрам придется заниматься дорогостоящей синхронизацией их кэша.


Другими словами, если код перемалывает сначала Thing, потом Another, и потом Also, вам желательно расположить их в памяти таким образом:



Обратите внимание что это не указатели на Thing, Another, и Also. Это сами находящиеся в них данные, расположенные одни за другими. Как только процессор считывает Thing, он начинает считывание Another и потом Also (в зависимости от размера данных и размера нашей строки кэша). Когда вы начинаете работать над следующим объектом, он уже находится в кэше. Чип счастлив и вы счастливы.

Шаблон



Современные процессоры обладают кэшем для ускорения доступа к памяти. Доступ к памяти, находящейся рядом с той, к которой мы только что обращались - значительно быстрее. Используйте это свойство для ускорения работы с помощью увеличения локальности данных - размещение данных в памяти последовательно, в порядке их обработки.

Когда использовать



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

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

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

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

    К сожалению большинство из этих инструментов совсем не дешевы. Но если вы работаете в команде консольных разработчиков, у вас наверняка уже есть лицензия.

    Если нет - я могу порекомендовать отличную альтернативу - cachegrind. Он запускает вашу программу на симуляторе процессора с иерархией кэша и потом показывает что происходило с кэшем.


Как было сказано выше, кэш-промахи влияют на производительность игры. И хотя вам не стоит впустую тратить время на предварительную оптимизацию для работы с кэшем, не забывайте о кэше, когда будете проектировать свои структуры данных.

Имейте в виду



Одним из отличительных признаков архитектуры программного обеспечения является абстракция. Большая часть этой книги посвящена шаблонам, снижающим связность между отдельными частями кода, так чтобы их было проще изменять по отдельности. В объектно-ориентированных языках это обычно подразумевает использование интерфейсов.

В C++ использование интерфейсов включает в себя доступ к объектам через указатели или ссылки. Но переход по указателю означает прыжок в памяти, что в свою очередь приводит к кэш-промаху, которые этот шаблон призывает избегать.

    Вторая часть интерфейса - это виртуальный вызов методов. Это требует от процессора заглядывать в виртуальную таблицу и искать там указатель на настоящий вызываемый метод. И опять мы сталкиваемся с указателем, что приводит к кэш-промахам.


Для того чтобы применить этот шаблон, вам нужно пожертвовать частью вашей драгоценной абстракции. Чем больше вы будете подчинять свою архитектуру локальности данных, тем больше вам придется пожертвовать наследованием и интерфейсами и предоставляемым ими удобством. Это не серебрянная пуля, а разумный обмен. И в этом и заключается весь интерес!

Пример кода



Если вы все таки решитесь спуститься в кроличью нору оптимизации для обеспечения локальности данных, вы обнаружите что нарезать ваши данные и структуры так, чтобы процессору было их легче считывать можно бесчисленным количеством способов. Для начала я покажу вам пример каждого из наиболее часто используемых способов организации данных. Мы рассмотрим их в контексте определенной части игрового движка, но (как и в случае с любым другим шаблоном) имейте в виду что общий принцип применим везде, где он уместен.

Последовательные массивы



Начнем с Игрового цикла ( Game Loop), обрабатывающего множество игровых сущностей. Эти сущности подразделяются на различные области - AI, физику и рендеринг с помощью шаблона Компонент ( Component). Вот класс сущности:


class GameEntity
{
public:
GameEntity(AIComponent* ai,
PhysicsComponent* physics,
RenderComponent* render)
: ai_(ai), physics_(physics), render_(render)
{}

AIComponent* ai() { return ai_; }
PhysicsComponent* physics() { return physics_; }
RenderComponent* render() { return render_; }

private:
AIComponent* ai_;
PhysicsComponent* physics_;
RenderComponent* render_;
};


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

    Как следует из имени, это пример шаблона Метод обновления ( Update Method). Даже render() реализует этот шаблон, просто с другим именем.



class AIComponent
{
public:
void update() { /* Обработка и изменение состояния... */ }

private:
// Цели, настроение, и т.д.. ...
};

class PhysicsComponent
{
public:
void update() { /* Обработка и изменение состояния... */ }

private:
// твердое тело, скорость, масса, и т.д. ...
};

class RenderComponent
{
public:
void render() { /* Обработка и изменение состояния... */ }

private:
// Сетка, текстуры, шейдеры, и т.д....
};


Игра поддерживает большой массив указателей на все сущности в игровом мире. На каждом обороте игрового цикла мы вынуждены делать следующее в определенном порядке:

1. Обновлять компоненты AI для всех сущностей.

2. Обновлять для них физические компоненты.

3. Выполнять их рендеринг с помощью компонентов рендерингга.

Многие игры реализуют это следующим образом:


while (!gameOver)
{
// Обрабатываем AI.
for (int i = 0; i < numEntities; i++)
{
entities[i]->ai()->update();
}

// Обновляем физику.
for (int i = 0; i < numEntities; i++)
{
entities[i]->physics()->update();
}

// Рисуем на экране.
for (int i = 0; i < numEntities; i++)
{
entities[i]->render()->render();
}

// Остальные задачи игрового цикла...
}


До того как вы познакомились с процессорным кэшем, это выглядит совершенно безобидно. Но теперь вы наверняка видите что что-то здесь не так. Этот код не просто ломает кэш, он просто захоти к нему со спины и избивает до полусмерти. Смотрите что делается:

1. Массив игровых сущностей указывает на них, так что к каждому элементу мы должны переходить через указатель. Это кэш-промах.

2. Сама игровая сущность содержит указатели на компоненты. Еще один кэш-промах.

3. Далее мы обновляем компонент.

4. И теперь возвращаемся к шагу один и повторяем для каждого компонента каждой сущности в игре.

Самое же страшное заключается в том что мы не имеем ни малейшего представления о том как эти объекты располагаются в памяти. МЫ полностью полагаемся на милость менеджера памяти. А так как сущности постоянно создаются и удаляются, они скорее всего будут размещаться совершенно хаотично.

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




Если вашей целью является организация дешевого безумного тура переходов по адресному пространству игру с названием в духе "256 мегабайт за четыре ночи!" - это отличная идея. Но нашей целью является ускорение работы игры и бесцельное брожение по всей памяти- не тот способ, который нам в этом поможет. Помните функцию sleepFor500Cycles()? Так вот в этом коде она вызывается постоянно.

    Существует специальный термин для бесполезных переходов по указателям - "гонка указателей (pointer chasing)" и в отличие от названия само это явление совсем не веселое.


Поступим умнее. Нашим первым наблюдением станет то, что единственная причина, по который мы переходим по указателю к сущности - это немедленный переход еще по одному указателю чтобы получить компонент. Сама GameEntity не имеет интересных состояний и полезных методов. Ваш игровой цикл занимается исключительно компонентами.

Вместо громадного созвездия раскиданных по всему адресному пространству сущностей и компонентов, мы попробуем вернуться на Землю. У нас будет большой массив для каждого типа компонентов: плоский массив AI компонентов, еще один для физики и еще один для рендеринга.

Примерно так:

    Моя наименее любимая часть использования компонентов - это то что слово "компонент" такое длинное.



AIComponent* aiComponents =
new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponents =
new PhysicsComponent[MAX_ENTITIES];
RenderComponent* renderComponents =
new RenderComponent[MAX_ENTITIES];


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

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



while (!gameOver)
{
// Обработка AI.
for (int i = 0; i < numEntities; i++)
{
aiComponents[i].update();
}

// Обработка физики.
for (int i = 0; i < numEntities; i++)
{
physicsComponents[i].update();
}

// Отрисовка на экране.
for (int i = 0; i < numEntities; i++)
{
renderComponents[i].render();
}

// Остальные задачи игрового цикла...
}


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



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

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

Это совсем не значит что мы полностью избавились от GameEntity. Мы можем их оставить в качестве наборов указателей на компоненты. Они просто указывают на элементы этих массивов. В других частях игры, куда вам потребуется передать концептуальную "игровую сущность", это все равно полезно. Главное что критичный в плане производительности игровой цикл может этим не заниматься и переходит к данным напрямую.

Упакованные данные



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

    Класс ParticleSystem - это пример Пула объектов( Object Pool), специально построенного для одного типа объектов.



class Particle
{
public:
void update() { /* Гравитация, и т.д. ... */ }
// Позиция, скорость, и т.д. ...
};

class ParticleSystem
{
public:
ParticleSystem()
: numParticles_(0)
{}

void update();
private:
static const int MAX_PARTICLES = 100000;

int numParticles_;
Particle particles_[MAX_PARTICLES];
};


Рудиментарный метод обновления для системы выглядит следующим образом:


void ParticleSystem::update()
{
for (int i = 0; i < numParticles_; i++)
{
particles_[i].update();
}
}


Но нам в свою очередь не нужно обновлять все частицы на каждом кадре. Система частиц имеет пул объектов фиксированного размера, но они не обязательно разбросаны по экрану в полном объеме. Проще всего поступить примерно так:


for (int i = 0; i < numParticles_; i++)
{
if (particles_[i].isActive())
{
particles_[i].update();
}
}


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

    Смекалистые низкоуровневые программисты наверняка заметили еще одну проблему. Выполняя if для каждой частицы, мы рискуем получить ошибку предсказания переходов (branch misprediction) и остановки конвейера(pipeline stall). На современных процессорах одна "инструкция" обычно занимает несколько циклов. Для того чтобы процессор постоянно был занят, инструкции попадают на конвейер (pipeline), так что следующая инструкция начинает выполняться прежде чем закончится предыдущая.

    Чтобы это стало возможным, процессору приходится угадывать какая из инструкций будет выполняться следующей. Для последовательно выполняющегося кода это сделать элементарно, но если у нас есть управление потоком, все становится сложнее. Когда мы выполняем инструкции if, нам нужно угадать - активна ли частица и нужно ли будет вызывать для нее update() или нет.

    Чтобы ответить на этот вопрос, чип выполняет предсказание переходов (branch prediction): он смотрит, какие переходы выполнялись до этого и пытается угадать сделаете ли вы это снова. А когда ваш цикл постоянно попадает на неактивные частицы, такое предсказание будет неверным.

    Когда предсказание оказывается неверным, процессору приходится выбросить инструкции, которые он уже начал обрабатывать (очистка конвейера(pipeline flush)) и начинает заново. Влияние на производительность на разных машинах может отличаться, но оно все равно достаточно велико для того чтобы некоторые разработчики вообще старались отказываться от ветвления кода в самых горячих участках кода.


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

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

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

Мы можем посчитать количество активных частиц. И тогда наш цикл обновления превратится в такую замечательную конструкцию:


for (int i = 0; i < numActive_; i++)
{
particles[i].update();
}


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

Конечно я не утверждаю что нам нужно применять quicksort ко всей коллекции объектов на каждом кадре. Это уничтожит результаты всего чего мы добились. Все что мы хотим - так это сохранить массив отсортированным.

Предполагая что массив уже отсортирован - и он таким является когда все наши частицы неактивны - единственный момент когда он может стать неотсортированным - это тогда, когда частица становится активной или неактивной. Мы можем довольно легко отследить эти два случая. Когда частица становится неактивной, мы переходим в конец активных частиц и меняем ее с первой неактивной:


void ParticleSystem::activateParticle(int index)
{
// Не должна быть активной!
assert(index >= numActive_);

// Меняем ее на первую неактивную частицу
// следующую сразу за активной.
Particle temp = particles_[numActive_];
particles_[numActive_] = particles_[index];
particles_[index] = temp;

// Теперь активных на одну больше.
numActive_++;
}


Чтобы сделать частицу неактивной, поступаем наоборот:


void ParticleSystem::deactivateParticle(int index)
{
// Не должна быть неактивной!
assert(index < numActive_);

// Теперь активных на одну меньше.
numActive_--;

// Меняем ее на последнюю активную частицу
// находящуюся сразу перед неактивной.
Particle temp = particles_[numActive_];
particles_[numActive_] = particles_[index];
particles_[index] = temp;
}


Многие программисты (включая меня) выработали аллергию на перемещение объектов в памяти. Перемещение порции байт по сравнению с перемещением указателя ощущается более тяжеловесным. Но когда сюда добавляется стоимость переходов по указателю, оказывается что интуиция нас здесь подводит. В некоторых случаях дешевле переместить данные в памяти и обеспечить тем самым наполнение кэша.

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


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

К сожалению не все так радужно. Как вы можете видеть из API, мы потеряли на этом частичку объектно-ориентированности. Класс Particle больше не управляет собственным состоянием. Вы больше не можете вызывать его метод activate(), потому что теперь он даже не знает свой индекс. Вместо этого любой код, который хочет изменить активность частицы должен обращаться к системе частиц.

В данном случае меня вполне устраивает тот факт что ParticleSystem и Particle крепко связаны между собой. Я думаю о них как о единой концепции, распределенной между двумя физическими классами. Таким образом мы соглашаемся с фактом, что частицы имеют смысл только в контексте системы частиц. Также в этом случае порождать и уничтожать частицы будет именно сама система частиц.

Горячее/холодное разделение



Итак, вот еще один пример того, простая техника позволит нам улучшить работу с кэшем. Представим себе AI компонент для некоей игровой сущности. У нее есть несколько состояний: текущая проигрываемая анимация, точка назначения куда она движется, уровень энергии и т.д. - все что проверяется и изменяется на каждом кадре игры. Примерно так:


class AIComponent
{
public:
void update() { /* ... */ }

private:
Animation* animation_;
double energy_;
Vector goalPos_;
};


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


class AIComponent
{
public:
void update() { /* ... */ }

private:
// Предыдущие поля...
LootType drop_;
int minDrops_;
int maxDrops_;
double chanceOfDrop_;
};


Предположим что мы следовали предыдущему шаблону и во время обновления AI, выполняли проход по аккуратно упакованному линейному массиву данных. Но в перечень этих данных входят и данные о луте. В результате каждый компонент увеличивается, а количество помещающихся в строку кэша компонентов уменьшается. У нас будет больше кэш-промахов, потому что нам придется обходить больший участок памяти. Данные о луте будут попадать в кэш для каждого компонента на каждом кадре, даже если мы и не будем их касаться.

Решение этой проблемы называется " Горячее/холодное разделение (hot/cold splitting)". Идея заключается в разделении данных на две части. Первая хранит "горячие" данные: состояния, которые мы используем на каждом кадре. Вторая хранит "холодные" данные: все остальное, что используется значительно реже.

Горячая часть - это основа AI компонента. Это то что мы используем настолько часто, что не хотим допускать гонки указателей для их поиска. Холодную часть компонента можно хранить в стороне, но она все равно будет нам нужна. И поэтому мы помещаем на нее указатель в горячей части данных следующим образом:


class AIComponent
{
public:
// Методы...
private:
Animation* animation_;
double energy_;
Vector goalPos_;

LootDrop* loot_;
};

class LootDrop
{
friend class AIComponent;
LootType drop_;
int minDrops_;
int maxDrops_;
double chanceOfDrop_;
};


Теперь когда мы выполняем обход AI компонентов на каждом кадре, единственными данными, загружаемыми в кэш являются те что мы активно используем (за исключением маленького указателя на холодные данные).

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


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

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

Вторая часть главы
Tags: c++, design patterns, game programming, programming, игры, книги, перевод, программирование, шаблоны, шаблоны проектирования
Subscribe

promo live13 may 11, 2014 17:58 46
Buy for 50 tokens
Примерно неделю назад я писал, что заинтересовался этой online-книжкой http://gameprogrammingpatterns.com/ и решил сделать ее перевод. Сам я мог бы ограничиться и английским вариантом, но думаю многим перевод пригодится. В прошлом я уже занимался переводом книг. Не как основной работой. Так,…
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments