как высокопроизводительное приложение

В этом году, силами команды Intel Software Network, был организован и проведен конкурс для разработчиков игр Intel® Game Demo contest. Мы очень рады, что почетное 3е место в номинации «Лучшая многопоточная игра» было присуждено российской разработке! Лев Дымченко, автор компьютерной игры AntiPlanet, рассказал нам о своей игре и секретах оптимизации.

 Лев Дымченко, Virtualray

AntiPlanet – это игра в жанре 3D шутер от первого лица. Её отличительной особенностью является нестандартное графическое решение. Для визуализации был применен VirtualRay Spherical Engine – трехмерный движок, использующий сферы в качестве базовых примитивов, из которых состоят все уровни и модели. Кроме того, движок способен рассчитывать освещение всей сцены в реальном времени, причем, сцена может произвольно изменяться перед отрисовкой каждого кадра. Эти две особенности, - сферическое решение геометрии игрового мира и полностью динамическое попиксельное освещение с мягкими тенями от всех объектов, выделяют AntiPlanet среди большого количества однообразных 3D игр.

AntiPlanet стала первой игрой (в жанре FPS) с высокореалистичным освещением, не использующей предварительный статический расчет освещения сцены. Это радикально «оживляет» игровые уровни с точки зрения графики. 

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

На новых процессорах Intel® Core™ Duo AntiPlanet идет полностью плавно. В зависимости от сцены и количества противников частота кадров составляет 30-50 кадров в разрешении 1024x768x32. Причем, игра оптимизирована с точки зрения более важного для игрока параметра – минимального fps, что дает дополнительную плавность даже при сильно нагруженной объектами сцене. 
 

Трассировка лучей – очень требовательная к вычислительным ресурсам задача. Современные методы трассировки, в частности, обратная трассировка, применяются в графических редакторах для рендеринга реалистичных изображений, но в редакторах нет необходимости «мгновенной» отрисовки сцены. Использование данного метода в играх для персональных компьютеров стало возможным как благодаря невероятному росту вычислительной мощности процессоров, так и глубокой оптимизации алгоритмов под архитектуру современных CPU.

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

Сразу отметим, что метод замечательно ложится на многопроцессорную архитектуру, ибо задача имеет естественную декомпозицию по данным, так как лучи можно трассировать независимо друг от друга, и выдавать каждому процессорному ядру свой кусочек изображения для рендеринга. Это определяет перспективность метода в свете нынешней тенденции к многоядерности. Впрочем, программа демонстрировала неплохой прирост производительности (~30%) и на процессорах с технологией Hyperthreading.

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

Более конкретно, чтобы программа использовала всю мощь процессора, должно соблюдаться два главных условия: программа должна использовать SSE (если она производит вычисления с плавающей точкой) и скорость подсистемы памяти не должна быть ограничением. Ибо скорость памяти значительно меньше скорости процессорного ядра. К второстепенным условиям можно отнести отсутствие большого количества случайных ветвлений, неудобных сочетаний инструкций. Ну и, конечно, средства языка программирования и вызовы ОС также не должны быть ограничением. Такие мелочи, как использование оптимизирующего компилятора с оптимальной генерацией инструкций из программного кода можно и не упоминать. На языке С++ с применением виртуальных функций и так далее невозможно написать приложение, полностью использующие потенциал CPU. Не говоря уже о различных интерпретаторах. Но достаточно большой проект затруднительно и экономически не выгодно писать на ассемблере. Поэтому движок VirtualRay построен так, что основная часть работы производится в относительно небольшой функции, которая занимает малый объем кода.  Это, собственно, цикл трассировки лучей. Он написан на ассемблере и полностью в инструкциях упакованного SSE. То есть, практически все используемые инструкции работают с четверками пар операндов, а не с одной. Там используются различные нехитрые приемы специфической оптимизации, описанные в оптимизационном документе к архитектуре IA. Например, замена точных вычислений приближенными, замена ветвлений уловными инструкциями, хранение часто используемых данных в регистрах процессора и так далее прелести низкоуровневого программирования, доступного через ассемблер или использование intrinsics.  

Перед собственно отрисовкой пикселей (Rendering) при помощи трассировки соответствующих лучей есть обширная стадия (PreRendering) обработки сцены целиком, построение базы данных примитивов, удобной для поиска пересечений лучей с объектами сцены. Она формально написана на С++, фактически на С, использует изощренные геометрические алгоритмы, занимает большой объем кода и не имеет оптимизаций под SSE, и ассемблер там не используется, ибо это неоправданно с точки зрения модификации кода и временных затрат. Общий объем вычислений там невелик (по сравнению с собственно циклом трассировки лучей).

База данных примитивов строится как Structure of Arrays, а не Array of Structures, что позволяет легко использовать инструкции SSE для работы с упакованными данными и поднять производительность в 4 раза, так как операции осуществляются сразу с 4 парами чисел, а не с одной.

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

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

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

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

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

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

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

Справка.
Использование упакованного SSE в вычислениях с вещественными числами типа float (4 байта на число) – почти четырех кратное ускорение в критической части кода. Оптимизация под четырехядерность – тоже четырехкратное ускорение. Оптимизация работы с памятью бесценна, ибо плохо оптимизированная с точки зрения доступа к памяти программа не способна загрузить ядро процессора работой, и все другие оптимизации пойдут прахом. И того, вместо разрешения 400x300 программа работает с той же скоростью в 16 раз большем разрешении 1600x1200. 
 

Дымченко Лев, родился в Москве, окончил математическую школу, далее - механико-математический факультет МГУ, далее работал над проектами в области программирования. Кроме AntiPlanet/VirtualRay можно также отметить, например, ixbt CPU RightMark. Автор одного из тестов SPEC CPU 2006. Любимые внекомпьютерные увлечения - футбол, шахматы и музыка.

Желающие более подробно узнать об оптимизации, могут задать вопрос здесь или на форуме antiplanet.freeforums.org. Вы также можете задать свой вопрос автору статьи - Льву Дымченко по почте dev (собака) virtualray.ru

 * Приведенные расчеты сделаны автором статьи. Корпорации Intel за точность приведенных данных ответственности не несет.