Developer Tales or everything about everything

25Авг/120

Оптимизация C++ в играх

Введение

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

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

Создание и удаление объектов

Создание и удаление объектов – это основная концепция, используемая в C++, и это главная часть, где компилятор создает код «за вашей спиной». Плохо спроектированные программы могут использовать огромное количество времени из-за вызова конструкторов, копирования объектов и дорогой генерации временных объектов. Однако, внимание и несколько простых правил могут помочь добиться скорости выполнения, сравнимой с кодом на C.

  • Создавайте объекты только тогда, когда они действительно необходимы и будут использоваться

Наиболее быстрый код – код, который никогда не будет выполняться, поэтому не следует создавать объект, если вы его не будете использовать (или исходя из каких-либо условий, он используется не всегда). Например:

Если (arg*) нуль, то мы ничего не выполняем в функции, однако, будут вызваны конструктор и деструктор для объекта Object.
Если (arg*) принимает значение нуль очень часто, а Object требует выделения памяти, это обойдется очень дорого. Решение проблемы – конечно же, поместить декларацию объекта после условия.

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

  • Использование списков инициализации

Рассмотрим следующий класс:

Поскольку конструкторы членов класса вызываются до того, как вызывается конструктор класса, то в примере сначала будет вызван конструктор для mName, а затем оператор = для копирования объекта. Самое плохое в этом примере то, что конструктор для строки может выделить память большую, чем необходимо для передаваемого значения. Следующий пример показывает, как избежать вызова operator=. Конструктор для строки, с задаваемым значением может оказаться намного более эффективным, т.к. в этом случае компилятор имеет возможность оптимизировать код вызова пустого конструктора класса:

  • Используйте пре-инкремент (++i) вместо пост-инкремента (i++)

Основная проблема в пост-инкременте x = y++ в том, что компилятор должен будет создать копию значния y, увеличить y и вернуть исходно значение. Т.е. пост-инкремент требует создания временного объекта, в то время, как для операции пре-инкремента этого не требуется. Конечно, для целых типов нет существенной разницы, но для пользовательских типов она может стать колоссальной. Поэтому следует использовать пре-инкремент, если есть возможность выбора.

  • Избегайте операторов, возвращающих результат по значению

Очень удобно использовать в C++ следующую операцию для класса векторов:

Эта операция должна вернуть новый объект вектора и, более того, она вернет его по значению. Конечно, это позволяет использовать удобную запись сложения векторов вида v = v1 + v2. Однако, цена вызова дополнительного конструктора и создания копии объекта вектора обычно очень высока. Иногда компилятору удается оптимизировать код создания временных объектов (это называется оптимизация возврата по значению [return value optimization]), но будет лучше, если вы переборете свою гордость и напишете более уродливый код, похожий на этот:

Стоит заметить, что operator+= лишен данной проблемы, потому что он изменяет первое передаваемое значение и не обязан создавать временный объект. Поэтому, если возможно, используйте оператор += вместо обычного сложения.

  • Используйте легковесные конструкторы

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

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

Обычно, дешевле использовать копирующий конструктор, вместо operator=, поэтому предпочтительнее использовать vehice v1(v2);, вместо (vehicle v1; v1 = v2;). Если вы хотите избежать копирования объектов, то сделайте operator= закрытым. В таком случае, любая попытка скопировать объект приведет к ошибке времени компиляции. Также, следует взять за привычку помечать одноаргументные конструкторы директивой explicit, подразумевая, что вы используете их в качестве преобразователей типов. Это исключает возможность создания компилятором временных объектов при преобразовании типов.

  • Выделение памяти и кэширование объектов

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

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

Управление памятью

При написании программ на C++ необходимо быть более осведомленным в деталях управления памятью, нежели для программ, написанных на C. В языке C распределение памяти управляется функциями malloc() и free(), в то время, как в C++ может потребоваться дополнительная память для конструирования объектов и членов классов. Большинство игр,
написанных на C++ (так же, как и большинство игр, написанных на C) требуют собственного менеджера памяти. Поскольку C++ требует многократного выделения памяти, необходимо заботиться о фрагментации кучи. Один из традиционных подходов: не выделять память вообще после того, как игра начнется, либо зарезервировать непрерывный блок памяти, который будет периодически очищаться (к примеру, между уровнями). На современных компьютерах такие суровые методы не столь необходимы, если вы будете следить за распределением памяти.

Первый шаг – переопределить глобальные операторы new и delete. Используйте собственный код в этих операторах, чтобы избежать вызова функции malloc() в процессе выделения памяти и использовать заранее выделенные блоки. К примеру, если вы знаете, что вам необходимо 10,000 4-байтовых ячеек, то можно запросто выделить 40,000 байт заранее и использовать этот блок памяти при необходимости (вместо того, чтобы каждый раз выделять по 4 байта). Чтобы определить, какия части блока памяти остаются свободными, следует определить freeList, который будет содержать указатели на каждый свободный блок.

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

Виртуальные функции

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

Если функция func() критическая по времени выполнения функция, то следует избавиться от использования виртуальной функции. Один из способов сделать это – добавить новый защищенный член класса к baseClass, который будет возвращаться с помощью новой быстрой функции getPointer():

Более суровый способ – изменить классовую иерархию. Если class1 & class2 имеют незначительные отличия, то возможно стоит объединить их в один класс с флагом определяющим тип объекта. При таких изменениях, функция getPointer() можно декларировать, как встроенную. Все эти способы выглядят не очень элегантно, но на машинах с маленьких кэшем это играет важную роль.
Хотя виртуальные функции всего лишь добавляют указатели на функции, однако, каждая виртуальная функция требует собственного указателя в таблице виртуальных функций. Поэтому в небольших, часто используемых классах следует отказаться от их использования.

Размер кода

Компиляторы имеют заслуженную плохую репутацию из-за того, что генерируют «раздутый код» C++. Так как память ограничена и чем меньше программа, тем она быстрее, нужно стараться делать исполняемые файлы настолько маленькими, насколько это вообще возможно. Первое, что нужно сделать для этого – переманить компилятор на свою сторону :). Если компилятор помещает информацию отладки, то отключить отладку (Microsoft Visual C++ размещаем отладочную информацию отдельно от исполняемого файла, поэтому для этой среды нет такой необходимости). Обработка и использование исключений порождает дополнительный код, поэтому необходимо избегать этого механизма. Убедитесь, что компоновщик настроен на удаление неиспользуемых функций и классов. Включите самый высокий уровень оптимизации кода в компиляторе. Иногда также следует попытаться настроить оптимизатор кода на размер, а не на скорость – порой это улучшает когерентность кэша инструкций. Избавьтесь от всех инструкций отображения отладочной информации, а также, объедините по возможности разделенные константные строки в одну.

Встраивание зачастую является причиной необычайно громоздких функций. Компиляторы с легкостью могут проигнорировать ваши директивы inline, не сказав об этом ни слова. Более того, компилятор самостоятельно может сделать некоторые функции встраиваемыми. Это еще одна причина, по которой не стоит нагружать конструкторы большим количеством кода. Также, следует быть очень осторожным при использовании перегруженных операторов. К примеру, простая операция m1 = m2 * m3 может служить причиной генерации огромного кода, если m1, m2 и m3 – матрицы.
Использование RTTI (Run Time Type Information) требует от компилятора генерации некоторой статической информации для каждого класса вашей программы. RTTI по умолчанию включен и в программе возможно использование dynamic_cast и получать информацию об объектах (dynamic_cast оказывается чрезвычайно дорогой функцией в некоторых реализациях). И все же, если вас необходимо, чтобы объект вел себя иначе, добавьте виртуальную функцию, которая определит это поведение. Это, в любом случае, более лучший подход. Также, следует заметить, что static_cast не относится к проблемным функциям, т.к. использует кастинг в C-стиле.

Библиотека STL

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

STL умалчивает о распределении памяти при использовании ее компонентов. Каждая часть библиотеки дает некоторые гарантии по производительности. К примеру, операции вставки, удаления и поиска в множествах имеют сложность O(logn) – идеальный выбор, не правда ли?:).
Возможно. По крайней мере, до тех пор, пока операции над множествами действительно имеют заявленную сложность. Вне зависимости от того, что написано в документации, производительность STL напрямую зависит от методов ее разработки на разных платформах. Многие реализации основаны на красно-черных деревьях, в которых каждый узел дерева содержит элемент коллекции. Это обычно для дерева каждый раз выделять память при помещении элемента в узел, и очищать память при его удалении. В зависимости от того, насколько часто вы добавляете и удаляете элементы множества, зависит и производительность используемого вами инструмента.

Альтернативное решение – использовать векторы для размещения элементов. Реализация вектора гарантирует константное время вставки элемента в конец. Это говорит о том, что вектор перераспределяет память только при необходимости, к примеру, удваивает свой размер при достижении лимита. При использовании вектора в качестве контейнера для элементов, первое, что вы сделаете – проверите, нет ли в векторе данного элемента. Поиск по вектору займет O(n) времени. Поэтому все элементы вектора располагаются последовательно в памяти и использования векторов становится дружественным по отношению к кэшу. А проверка всего множества (set<>) может замусорить кэш, так как элементы красно-черного дерева могут быть разбросаны в памяти. Также стоит отметить, что множества требуют дополнительных расходов, чтобы создать дерево. Если все элементы множества – ссылки на объекты, то множеству может потребоваться в 3-4 раза больше памяти для размещения объектов.
Удаление из множества – операция, занимающая O(logn) времени. Это выглядит заманчиво. Операция удаления из вектора занимает O(n) времени, потому как необходимо сместить все элементы, следующие за удаляемым элементом. Однако, если вектор расположен в непрерывном блоке памяти, то осуществить перемещение можно с использованием команды memcpy(), которая выполняется очень быстро (также, это является одной из главных причин, почему в STL коллекциях стоит хранить только указатели на объекты, а не сами объекты. Если вы помещаете сам объект, то потребуется вызов большого числа конструкторов при выполнении таких операций, как удаление).
Если вы все еще не убедились в том, что использование множеств и хэша может стать большой проблемой, то посмотрите на цикл обхода коллекции:

Если контейнер – это вектор, то инкремент итератора – одна машинная инструкция. Но, если контейнер это множество или хэш, то ++it означает переход к следующему узлу дерева – довольно дорогой операции, которая иногда приводит к потере производительности кэша, потому как узлы деревьев могут быть разбросаны в памяти.
Конечно, если вы помещаете в контейнер большое количество элементов, то сложность O(logn) множества может с легкостью оплатить потерю памяти. Также, если вы используете контейнер редко, то разница в производительности может быть совершенно незначительной. Но вы можете быть удивлены тем, что вектора опережают множества практически для всех типов структур, которые вы храните в контейнерах :).

Однако, это не последнее слово об использовании памяти STL. Важно знать, когда контейнер действительно освобождает выделенную память при вызове clear(). Если это не так, то может возникнуть фрагментация памяти. К примеру, если вы регистрируете пустой вектор в начале игры и по мере необходимости добавляете туда элементы, а затем вызываете clear(), когд игрок перезапустил игру, то вектор, в действительности, может не очистить память. Память вектора все еще может быть расположена где-то в куче. Если два способа избежать этой проблемы. Пепвый – использовать функцию reserve() при создании вектора и зарезервировать таким образом память для максимального количества элементов вектора. Если это не подходит, то можно принудительно очистить память таким образом:

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

Дополнительные возможности

Если в языке есть некоторая возможность, почему нам ее не использовать? :)
С одной стороны, простые возможности могут на деле оказаться малопроизводительными, а сложные и непонятный – наоборот. Самые темные уголки мира C++ сильно зависимы от реализации компиляторов, поэтому убедитесь в плате за использование возможности.
Использование C++ строк std::string выглядит очень удобным на бумаге. Однако, их использования нужно избегать в местах, где важна производительность. Рассмотрим код:

Вызов функции требует вызова конструктора для std::string с параметром const char*. В одной коммерческой реализации этот конструктор вызывал malloc(), strlen() & memcpy(). Также, деструктор выполнял некоторую нетривиальную работу после вызова free(). В таком случае, выделенная память перерасходуется понапрасну, потому как строка «Hello» уже находится в программном сегменте данных, а мы в дополнение сделаем ее копию в памяти. Если бы функция принимала значение const char*, то этого бы не произошло. Это, надо заметить, очень высокая цена за использование класса строк C++.
Шаблоны – пример обратной стороны эффективности. В соответствии с языком C++, код генерируется для шаблона только когда шаблон определяется конкретными типами. В теории это звучит, как качественная замена одним определением шаблона, вместо тонны схожего кода. Если вы имеете вектор указателей на объекты типа class1 и вектор указателей на объекты типа class2, то получите две копии класса vector в исполняемом файле.
Настоящая ситуация в отношении компиляторов обычно намного лучше. Во-первых, только те функции, который непосредственно вызываются в коде имеют место в исполняемом файле. Во-вторых, компилятор сгенерирует только одну копию кода, если поведение объекта предопределено. Вы можете заметить, что в предыдущем примере, будет сгенерирована только одна копия (возможно, vector) шаблона. Используя хороший компилятор, шаблоны дадут вам возможность высокой эффективности разработки, обеспечивая настолько же высокую производительность.

Итоги

  • Не объявляйте объекты тогда, когда они возможно не будут использованы;
  • Используйте списки инициализации в конструкторах, вместо operator= для инициализации членов класса;
  •  Используйте операцию пре-инкремента (++i) вместо операции пост-инкремента (i++), чтобы избежать создания временных объектов;
  • Избегайте операторов, возвращающих результат по значению (например, operator=);
  • Не помещайте в конструкторы большой код и избегайте инициализации членов класса внутри конструкторов (лучше сделать замену этим возможностям, путем создания дополнительных методов, типа setName());
  • Используйте кэш в непрерывном блоке памяти для хранения и использования объектов;
  • При разработке игры, если необходимо, переопределите операции new & delete, а еще лучше – напишите собственный менеджер памяти;
  • При выделении памяти часто оказывается проще выделить сразу n * count байт, чем выделить count байт n раз;
  • Избегайте использования виртуальных функций;
  • Отключайте директивы отладчика при создании исполняемого файла;
  • Избегайте использования большого количества исключений;
  • Настройте компоновщик так, чтобы он удалял неиспользуемые функции и классы;
  • При создании исполняемых файлов включайте наивысший уровень оптимизации;
  • Не делайте встраиваемыми большие функции;
  • Будьте осторожны с использованием контейнеров из библиотеки STL. Предпочтительнее для хранения элементов лучше использовать вектора, а вместо std::string использовать C-строки;
  •  Современные компиляторы хорошо оптимизируют код шаблонов классов, поэтому использование шаблонов может повысить производительность за счет удаления похожего кода.

Заключение

Некоторые возможности C++, такие как списки инициализации или пре-инкрмент, увеличивают производительность, а некоторые, такие как перегруженные операторы, RTTI, снижают. Библиотека STL демонстрирует, что нельзя слепо доверяться стандартным алгоритмам. Избегайте потенциально слабых мест языка и библиотек и потратьте немного времени на изучение настроек вашего компилятора и профайлера. Тогда вам удастся быстро понять, как организовать программу и сделать из нее хорошую игру!

Источник: Game Gems 2, Optimization for C++ Games, Andrew Kirmse, Lucas Arts Entartaiment
Перевод и коррекция: Yorie (aka Deft).

Просмотров: 2946
Комментарии (0) Пинги (0)

Пока нет комментариев.


Leave a comment


− один = 7

http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_bye.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_good.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_negative.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_scratch.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_wacko.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_yahoo.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_cool.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_heart.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_rose.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_smile.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_whistle3.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_yes.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_cry.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_mail.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_sad.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_unsure.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_wink.gif 
 

Trackbacks are disabled.