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

Архитектурные решения

Знаменитая статья Ноэля Ллописа заставила многих людей задуматься об архитектуре игры с точки зрения использования кэша и получила название "ориентированная на данные архитектура (data-oriented design)".

Что вы будете делать с полиморфизмом

• Не используйте:
  
  Проще всего ответить так: не используете подклассы или по крайней мере избегайте их применения, там где имеет смысл применять оптимизацию работы с кэшем. Культура программирования и так уже постепенно отходит от массированного применения наследования.
  
  
  Одним из способов использовать гибкость полиморфизма без использования подклассов является шаблон Объект тип( Type Object).
  
  
  
  
  
  • Это просто и безопасно. Вы всегда знаете с каким классом работают все ваши объекты одного размера.
  
  
  • Это быстро. Динамическая диспетчеризация подразумевает поиск метода в виртуальной таблице методов и переход по указателю к самому методу. Несмотря на то что стоимость этой операции на различном оборудовании серьезно варьируется, вам все равно придется платить за динамическую диспетчеризацию.
    
    Как обычно с абсолютной уверенностью можно утверждать только о том что ничего абсолютного нет. В большинстве случаев компилятор C++ требует косвенности для вызова виртуального метода. Но в некоторых случаях компилятор может выполнить развиртуализацию (devirtualization) и вызвать нужный метод статически, если знает конкретный тип получателя. Развиртуализация встречается еще чаще в языках с компиляцией на лету, таких как Java или JavaScript.
  
  
  • Это гибкий подход. На самом деле динамическая диспетчеризация применяется потому что она дает нам мощный инструмент настройки поведения между объектами. Если вы хотите, чтобы разные сущности в вашей игре имели собственные стили рендеринга или обладали собственными специальными движениями и атаками, вам в этом помогут именно виртуальные методы. Попытка реализовать нечто подобное с помощью кода без виртуальных методов, у вас образуется громадное месиво конструкций типа switch.
  
  
  
  


• Используйте отдельный массив для каждого типа:
  
  Мы используем полиморфизм чтобы активизировать поведение объекта, тип которого нам неизвестен. Другими словами у нас есть мешок с разными штуками и мы хотим чтобы каждый из этих объектов делал что-то свое, когда мы ему прикажем.
  
  Но в таком случае сразу возникает вопрос - зачем складывать все в один мешок? Почему не организовать вместо этого отдельные гомогенные коллекции для каждого типа?
  
  
  
  
  • Наши объекты будут плотно упакованы. Так как все объекты в массиве одного типа - у нас не будет подбивки(padding) и других странностей.
  
  
  • Мы можем применять статическую диспетчеризацию. Как только ваши объекты будут разделены по типу, полиморфизм вам больше не понадобится. Вы можете использовать простые невиртуальные вызовы методов.
  
  
  • Вы можете поддерживать множество коллекций. Если у вас есть много разных типов объектов, поддерживать для каждого типа отдельный массив может быть сложно и накладно.
  
  
  • Вам нужно заботиться о каждом из типов. Так как у вас для каждого типа имеется отдельная коллекция, вы не сможете убрать связность от набора классов. Часть магии полиморфизма заключается в открытости: код, работающий с наследниками может быть полностью несвязан с потенциально большим набором типов, реализующих данный интерфейс.
  
  
  
  


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

Как определять игровые сущности?

• Если игровые сущности - это классы с указателями на свои компоненты:
  
  Именно так выглядел наш первый пример. Это самое традиционное ООП решение. У вас есть класс для GameEntity и у него есть указатели на свои компоненты. Так как все это просто указатели - остается только догадываться где и как на самом деле размещаются эти компоненты в памяти.
  
  
  
  
  • Вы можете хранить компоненты в последовательном массиве. Так как игровой сущности все равно где находятся ее компоненты, вы можете организовать их в хорошо упакованный массив для оптимизации из обхода.
  
  
  • Получив сущность, вы легко можете добраться до ее компонентов. Для этого нужно просто перейти по указателю.
  
  
  • Перемещать компоненты в памяти сложно. Когда компоненты включаются или выключаются, вы можете попробовать перемещать их внутри массива так что активные будут находиться вначале, а неактивные в конце. Но если вы будете перемещать компонент, на который ссылается сущность - вы разрушите эту связь если не будете действовать осторожно. Вам нужно будет обязательно обновить при этом и указатель на компонент внутри сущности.
  
  
  
  


• Если игровые сущности - это классы с ID своих компонентов:
  
  Сложность работы с указателями на компоненты заключается в том что при этом их становится сложнее перемещать в памяти. Вы можете применить более абстрактную адресацию: ID или индекс, который можно использовать для поиска компонента.
  
  Семантику ID и реализацию поиска я оставляю на ваше усмотрение. Это может быть простой ID, хранимый внутри компонента и обход массива или более сложное решение с применением хеш таблиц, связывающих ID с индексом компонента в массиве.
  
  
  
  
  • Это сложно. Конечно ваша система ID не сравнится по сложности с ракетостроением, но работы явно больше чем при использовании обычных указателей. Вам нужно будет ее реализовать и отладить. А еще у вас появятся накладные расходы на бухгалтерию.
  
  
  • Это медленное решение. Сложно тягаться с сырыми указателями. Для того чтобы получить компонент сущности нам нужно будет выполнять поиск или какую-то операцию с хешированием.
  
  
  • Вам потребуется доступ к "менеджеру" компонентов. Основная идея заключается в том что у вас есть абстрактный ID, идентифицирующий компонент. И вы можете использовать его чтобы получить указатель на сам компонент. Но чтобы это сделать вам нужен кто-то, кто может найти компонент по его ID. Это будет класс - обертка над сырым последовательным массивом компонентов наших объектов.
    
    При работе с сырыми указателями, если у вас есть сущность - значит вы можете получить и ее компоненты. В этом случае вам потребуется не только сама сущность но и предварительная регистрация компонентов.
    
    
    Вы можете подумать" Так я применю синглтон! И проблема решена!" Ну как бы да. Только советую сначала заглянуть в эту главу.
    
    
  
  
  
  


• Если игровые сущности представляют из себя всего лишь ID.
  
  Это сравнительно новый способ, который применяется в некоторых игровых движках. Как только вы перенесете все поведение и состояние сущности из главного класса в компоненты, то что останется? Немного на самом деле. Единственное что делает сущность - это связывает вместе набор компонентов. Она нужна только для того чтобы сообщать нам что этот AI компонент, этот физический компонент и этот компонент рендеринга образуют игровую сущность в нашем мире.
  
  Важно здесь то как компоненты взаимодействуют. Компоненту рендеринга нужно знать где находится сущность. А эта информация может храниться в физическом компоненте. Компонент AI хочет перемещать сущность и для этого ему нужно приложить силу к физическому компоненту. Каждому компоненту нужно иметь возможность получить доступ к родственному компоненту, вместе с которыми они образуют сущность.
  
  Думаю некоторые уже догадались что все что нам нужно - это ID. Вместо того чтобы сущность знала о своих компонентах, компоненты могут знать о своей сущности. Каждый компонент может знать ID сущности, которой он принадлежит. Когда AI компоненту потребуется физический компонент своей сущности, он просто запросит физический компонент с таким же ID как и у него.
  
  Ваши классы сущностей полностью исчезают, заменяемые удобной оболочкой над числами.
  
  
  
  
  • Сущности занимают мало места. Если вам нужно передать ссылку на игровую сущность - вы просто передаете число.
  
  
  • Сущности пустые. Логично что недостатком такого решения является, то что вам придется убрать из сущностей все. У вас больше нет места для хранения не компонентно-специфического состояния или поведения. Эти функции тоже возлагаются на шаблон компонентов.
  
  
  • Вам не нужно управлять временем жизни. Так как сущности - это значения простых типов, их не нужно явно создавать или удалять. Сущность "умирает", когда уничтожаются все ее компоненты.
  
  
  • Поиск компонентов сущности может быть достаточно медленным. Это та же самая проблема как и в предыдущем решении, но немного с другой точки зрения. Чтобы найти компонент какой-либо сущности, вам нужно найти объект по ID. Этот процесс может быть достаточно затратным.
    
    На этот раз поиск является критически важным для производительности. Компоненты часто взаимодействуют со своими родственниками во врем обновления, так что искать их придется часто. В качестве решения можно сделать "ID" сущности индексом компонентов в массивах.
    
    Если у каждой сущности будет одинаковый набор компонентов, то все ваши массивы с компонентами будут полностью параллельными. Компонент в слоте три в массиве AI компонентов будет принадлежать той же сущности, что и физический компонент в массиве три в соответствующем массиве.
    
    Имейте ввиду, что вам придется затрачивать усилия для сохранения параллельности массивов. Это может быть сложным, если вам захочется сортировать или упаковывать их по разным критериям. У вас могут быть сущности с выключенной физикой и другие - невидимые. Поэтому не получится отсортировать физические и рендер компоненты таким образом, чтобы массивы остались синхронизированными друг с другом.
    
  
  
  
  

Смотрите также

• Большая часть этой главы вращается вокруг шаблона Компонент ( Component) и это определенно одна из наиболее часто используемых структур данных для оптимизации работы с кэшем. И действительно, применение компонентов этому способствует. Так как сущности обновляются по одной "области" (AI, физика и т.д.) за раз, разбиение их на компоненты позволяет поделить сущности на более удобные в плане работы с кэшем кусочки.
  
  Но это не значит что вы можете использовать этот шаблон только с компонентами! Каждый раз, когда у вас встречается код критический в плане производительности, работающий с большим объемом данных - подумайте о локальности данных.
  


• "Ловушки объектно-ориентированного программирования( Pitfalls of Object-Oriented Programming)" Тони Альбрехта - это наверное самое лучшее чтиво на тему организации структур данных в игре в максимально кэш-дружественном виде. Я встречал много людей (включая меня самого), кому эта книга помогла с улучшением производительности.


• Примерно в то же время Ноэль Ллопис написал хороший пост в своем блоге на ту же тему.


• Этот шаблон практически полностью основан на использовании последовательного массива гомогенных объектов. Время от времени вам наверняка придется добавлять или удалять из него объекты. Шаблон Пул объектов ( Object Pool) как раз этому и посвящен.


• Игровой движок Artemis - один из первых и наверное самый известный из фреймворков, использующих ID в качестве игровой сущности.