У меня есть ветка pbrt, которую я использую для проверки новых идей, реализации интересных мыслей из научных статей и в целом для исследования всего того, что в результате обычно оказывается в новой редакции книги Physically Based Rendering. В отличие от pbrt-v3, который мы стремимся сохранять как можно ближе к описанной в книге системе, в этой ветке мы можем менять что угодно. Сегодня мы увидим, как более радикальные изменения системы позволят значительно снизить использование памяти в сцене с островом из диснеевского мультфильма «Моана».

Примечание по методологии: в предыдущих трёх постах вся статистика измерялась для WIP-версии (Work In Progress) сцены, с которой я работал до её выпуска. В этой статье мы перейдём на окончательную версию, которая немного сложнее.

При рендеринге последней островной сцены из «Моаны» для хранения описания сцены pbrt-v3 использовал 81 ГБ ОЗУ. На текущий момент pbrt-next использует 41 ГБ — примерно в два раза меньше. Для получения такого результата достаточно было небольших изменений, вылившихся в несколько сотен строк кода.

Уменьшенные примитивы

Давайте вспомним, что в pbrt Primitive является сочетанием геометрии, её материала, функции излучения (если это источник освещения) и записи о среде внутри и снаружи поверхности. В pbrt-v3 GeometricPrimitive хранят следующее:

    std::shared_ptr<Shape> shape;
    std::shared_ptr<Material> material;
    std::shared_ptr<AreaLight> areaLight;
    MediumInterface mediumInterface;

Как сказано ранее, бОльшую часть времени areaLight является nullptr, а в MediumInterface содержится пара nullptr. Поэтому в pbrt-next я добавил вариант Primitive под названием SimplePrimitive, который хранит только указатели на геометрию и материал. Там, где это возможно, он по возможности используется вместо GeometricPrimitive:

class SimplePrimitive : public Primitive {
    // ...
    std::shared_ptr<Shape> shape;
    std::shared_ptr<Material> material;
};

Для неанимированных экземпляров объектов у нас теперь есть TransformedPrimitive, который хранит только указатель на примитив и преобразование, что экономит нам примерно 500 байт впустую тратившегося пространства, которые экземпляр AnimatedTransform добавлял в TransformedPrimitive рендерера pbrt-v3.

class TransformedPrimitive : public Primitive {
    // ...
    std::shared_ptr<Primitive> primitive;
    std::shared_ptr<Transform> PrimitiveToWorld;
};

(на случай необходимости анимированного преобразования в pbrt-next есть AnimatedPrimitive.)

После всех этих изменений статистика сообщает, что под Primitive используется всего 7,8 ГБ, вместо используемых в pbrt-v3 28,9 ГБ. Хотя здорово, что мы сэкономили 21 ГБ, это не так много, как то снижение, которого мы могли бы ожидать от предыдущих оценок; мы вернёмся к этому расхождению к концу этой части.

Уменьшенная геометрия

Также в pbrt-next значительно снижен объём памяти, занимаемой геометрией: пространство, используемое под меши треугольников, снизилось с 19,4 ГБ до 9,9 ГБ, а пространство для хранения кривых — с 1,4 до 1,1 ГБ. Чуть больше половины этой экономии возникло благодаря упрощению базового класса Shape.

В pbrt-v3 Shape несёт с собой несколько членов, которые переносятся во все реализации Shape — это те несколько аспектов, к которым удобно иметь доступ в реализациях Shape.

class Shape {
    // ....
    const Transform *ObjectToWorld, *WorldToObject;
    const bool reverseOrientation;
    const bool transformSwapsHandedness;
};

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

struct TriangleMesh {
    int nTriangles, nVertices;
    std::vector<int> vertexIndices;
    std::unique_ptr<Point3f[]> p;
    std::unique_ptr<Normal3f[]> n;
    // ...
};

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

class Triangle : public Shape {
    // ...
    std::shared_ptr<TriangleMesh> mesh;
    const int *v;
};

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

Проблема с Shape pbrt-v3 заключается в том, что хранимые в нём значения значения одинаковы для всех треугольников меша, поэтому лучше сохранять их из каждого целого меша в TriangleMesh, а затем предоставлять Triangle доступ к единой копии общих значений.

Эта проблема устранена в pbrt-next: базовый класс Shape в pbrt-next не содержит таких членов, а потому каждый Triangle на 24 байта меньше. Геометрия Curve использует похожую стратегию и тоже выигрывает от использования более компактного Shape.

Общие буферы треугольников

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

Я написал небольшой класс, хэширующий эти буферы при получении и сохраняющий их в кэш, и изменил TriangleMesh так, чтобы он проверял кэш и использовал уже сохранённую версию любого нужного ему избыточного буфера. Выигрыш оказался очень хорошим: удалось избавиться от 4,7 ГБ избыточного объёма, что гораздо больше того, что я ожидал.

Катастрофа с std::shared_ptr

После всех этих изменений статистика сообщает о примерно 36 ГБ известной выделенной памяти, а в начале рендеринга top говорит об использовании 53 ГБ. Дела.

Я боялся ещё одной серии медленных прогонов massif для выяснения того, какая выделенная память отсутствует в статистике, но тут в моих входящих появилось письмо от Арсения Капулкина. Арсений объяснил мне, что мои предыдущие оценки использования памяти GeometricPrimitive были сильно ошибочными. Мне пришлось долго разбираться, но потом я понял; огромное спасибо Арсению за указание на ошибку и подробные объяснения.

До письма Арсения я мысленно представлял себе реализацию std::shared_ptr следующим образом: в этих строках существует общий дескриптор, хранящий счётчик ссылок и указатель на сам размещённый объект:

template <typename T> class shared_ptr_info {
    std::atomic<int> refCount;
    T *ptr;
};

Затем я предположил, что экземпляр shared_ptr просто указывает на него и использует его:

template <typename T> class shared_ptr {
    // ...
    T *operator->() { return info->ptr; }
    shared_ptr_info<T> *info;
};

Если вкратце, то я предполагал, что sizeof(shared_ptr<>) — это то же самое, что и размер указателя, и что на каждый общий указатель впустую занимается 16 байт лишнего места.

Но это не так.

В реализации моей системы общий дескриптор имеет размер 32 байта, а sizeof(shared_ptr<>) — 16 байт. Следовательно GeometricPrimitive, который в основном состоит из std::shared_ptr, примерно в два раза больше моих оценок. Если вам интересно, почему так получилось, то в этих двух постах на Stack Overflow очень подробно объясняются причины: 1 и 2.

Почти во всех случаях использования std::shared_ptr в pbrt-next они не обязаны быть общими указателями. Занимаясь безумным хакингом, я заменил всё, что мог, на std::unique_ptr, который на самом деле имеет тот же размер, что и обычный указатель. Например, вот как теперь выглядит SimplePrimitive:

class SimplePrimitive : public Primitive {
    // ...
    std::unique_ptr<Shape> shape;
    const Material *material;
};

Награда оказалась большей, чем я ожидал: использование памяти в начале рендеринга снизилось с 53 ГБ до 41 ГБ — экономия в 12 ГБ, совершенно неожиданная ещё несколько дней назад, а общий объём почти в два раза меньше, чем используемый pbrt-v3. Отлично!

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

Часть 5.

Чтобы подвести итог этой серии статей, мы начнём с изучения скорости рендеринга островной сцены из диснеевского мультфильма «Моана» в pbrt-next — ветке pbrt, которую я использую для проверки новых идей. Мы внесём более радикальные изменения, чем это возможно в pbrt-v3, который должен придерживаться системы, описанной в нашей книге. Закончим мы обсуждением направлений дальнейших усовершенствований, от самых простейших до немного экстремальных.

Время рендеринга

В pbrt-next внесено много изменений в алгоритмы переноса света, в том числе изменения в сэмплировании BSDF и усовершенствования алгоритмов русской рулетки. В результате для рендеринга этой сцены он трассирует больше лучей, чем pbrt-v3, поэтому невозможно напрямую сравнить время выполнения этих двух рендереров. Скорость в общем близка, за одним важным исключением: при рендеринге островной сцены из «Моаны», показанной ниже, pbrt-v3 тратит 14,5% времени выполнения на выполнение поисков текстур ptex. Раньше это казалось мне вполне нормальным, но pbrt-next тратит всего 2,2% времени выполнения. Всё это ужасно интересно.

После изучения статистики мы получаем¹:

pbrt-v3:
Считывания блоков Ptex 20828624
Поиски Ptex 712324767

pbrt-next:
Считывания блоков Ptex 3378524
Поиски Ptex 825826507

Как мы видим в pbrt-v3, текстура ptex считывается с диска в среднем через каждые 34 поиска текстуры. В pbrt-next она считывается всего через каждые 244 поиска — то есть ввод-вывод с диска снизился примерно в 7 раз. Я предположил, что так происходит потому, что pbrt-next вычисляет разности лучей для непрямых лучей, а это приводит к тому, что осуществляется доступ к более высоким MIP-уровням текстур, что в свою очередь создаёт более целостную серию доступов к кэшу текстур ptex, снижает количество промахов кэша, а значит, и количество операций ввода-вывода². Краткая проверка подтвердила мою догадку: при отключении разности лучей скорость ptex становилась намного хуже.

Увеличение скорости ptex повлияло не только на экономию вычислений и ввода-вывода. В системе с 32 ЦП pbrt-v3 имел ускорение всего в 14,9 раза после завершения парсинга описания сцены. pbrt обычно демонстрирует близкое к линейному параллельное масштабирование, поэтому это довольно сильно разочаровало меня. Благодаря гораздо меньшему количеству конфликтов при блокировках в ptex, версия pbrt-next была в 29,2 раза быстрее в системе с 32 ЦП, и в 94,9 раза быстрее в системе с 96 ЦП — мы снова вернулись к устраивающим нас показателям.


Корни из островной сцены «Моаны», отрендеренные pbrt с разрешением 2048x858 при 256 сэмплах на пиксель. Общее время рендеринга на инстансе Google Compute Engine с 96 виртуальных ЦП с частотой 2 ГГц в pbrt-next — 41 мин 22 с. Ускорение благодаря mulithreading при рендеринге составило 94,9 раза. (Я не совсем понимаю, что здесь происходит с bump mapping.)

Работа на будущее

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

Дальнейшее уменьшение памяти буфера треугольников

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

Тип	Память
Позиции	2,5 ГБ
Нормали	2,5 ГБ
UV	98 МБ
Индексы	252 МБ

Я понимаю, что с передаваемыми позициями вершин сделать ничего нельзя, но для других данных есть возможности экономии. Существует множество типов представления векторов нормалей в эффективном с точки зрения памяти виде, обеспечивающее различные компромиссы между объёмом памяти/количеством вычислений. Использование одного из 24-битных или 32-битных представлений позволит снизить занимаемое нормалями место до 663 МБ и 864 МБ, что сэкономит нам больше 1,5 ГБ ОЗУ.

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

Для других сцен возможно вполне подойдёт дискретизация UV-координат текстур в 16 бит или использование значений float половинной точности, в зависимости от их диапазона значений. Похоже, что в этой сцене все значения координат текстур равны нулю или единице, а значит, могут быть представлены одним битом — то есть возможна снижение объёма занимаемой памяти в 32 раза. Такое состояние дел вероятно возникло благодаря использованию для текстурирования формата ptex, устраняющего необходимость UV-атласов. С учётом малого объёма, занимаемого сейчас координатами текстур, реализация этой оптимизации не особо необходима.

pbrt всегда использует для буферов индексов 32-битные целые числа. Для небольших мешей из менее чем 256 вершин достаточно всего 8 битов на индекс, а для мешей меньше чем из 65 536 вершин можно использовать 16 бит. Изменить pbrt, чтобы приспособить его к такому формату, будет не очень сложно. Если бы мы хотели оптимизировать по максимуму, то могли бы выделять ровно столько бит, сколько необходимо для представления в индексах требуемого диапазона, при этом ценой бы стало повышение сложности поиска их значений. При том, что сейчас под индексы вершин используется всего четверть гигабайта памяти, эта задача по сравнению с другими выглядит не очень интересной.

Пик использования памяти построения BVH

Ранее мы не обсуждали ещё одну подробность использования памяти: непосредственно перед рендерингом возникает кратковременный пик в 10 ГБ дополнительно используемой памяти. Это случается, когда строится (большой) BVH всей сцены. Код построения BVH рендерера pbrt написан так, чтобы выполняться в две фазы: сначала он создаёт BVH с традиционным представлением: по два дочерних указателя на каждый узел. После построения дерева оно преобразуется в схему с эффективным использованием памяти, в которой первый дочерний элемент узла находится в памяти непосредственно за ним, а смещение ко второму дочернему узлу хранится как целое число.

Такое разделение необходимо было с точки зрения обучения студентов — гораздо проще понять алгоритмы построения BVH без хаоса, связанного с необходимостью преобразования дерева в компактную форму в процессе построения. Однако в результате получается этот пик использования памяти; с учётом его влияния на сцену устранение этой проблемы видится привлекательным.

Преобразование указателей в целые числа

В различных структурах данных есть множество 64-битных указателей, которые можно представить в виде 32-битных целых чисел. Например, каждый SimplePrimitive содержит указатель на Material. Большинство экземпляров Material являются общими для множества примитивов сцены и их никогда не бывает больше нескольких тысяч; поэтому мы можем хранить единый глобальный вектор vector всех материалов:

std::vector<Material *> allMaterials;

и просто хранить 32-битные целочисленные смещения на этот вектор в SimplePrimitive, что сэкономит нам 4 байта. Тот же трюк можно использовать с указателем на TriangleMesh в каждом Triangle, а также во множестве других мест.

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

Размещение на основе арен (областей)

Для каждого отдельного Triangle и примитива осуществляется отдельный вызов new (на самом деле make_unique, но это то же самое). Такие размещения памяти приводят к использованию дополнительного учёта ресурсов, занимающего около пяти гигабайт памяти, неучтённой в статистике. Поскольку срок жизни всех таких размещений одинаков — до завершения рендеринга — мы можем избавиться от этого дополнительного учёта, выделив их из арены памяти (memory arena).

Хаки vtable

Моя последняя идея ужасна, и я прошу за неё прощения, но меня она заинтриговала.

Каждый треугольник в сцене имеет дополнительную нагрузку в виде по крайней мере двух указателей vtable: один для Triangle, и ещё один для SimplePrimitive. Это 16 байт. В островной сцене «Моаны» в целом 146 162 124 уникальных треугольников, что добавляет почти 2,2 ГБ избыточных указателей vtable.

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

Оказывается, что на современных ЦП x86 на самом деле используется только 48 бит из 64-битных указателей. Поэтому есть лишние 16 бит, которые мы можем позаимствовать для хранения какой-нибудь информации… например, типа геометрии, на которую мы указываем. В свою очередь, добавив немного работы, мы можем совершить путь назад, к возможности создания аналога вызовов виртуальных функций.

Вот, как это будет происходить: сначала мы определяем структуру ShapeMethods, которая содержит указатели на функции, например так³:

struct ShapeMethods {
   Bounds3f (*WorldBound)(void *);
   // Intersect, etc. ...
};

Каждая реализация геометрии будет реализовывать функцию ограничения, функцию пересечения, и так далее, получая в качестве первого аргумента аналог указателя this:

Bounds3f TriangleWorldBound(void *t) {
    // Этой функции передаются только указатели на Triangle.
    Triangle *tri = (Triangle *)t;
    // ...

У нас была бы глобальная таблица структур ShapeMethods, в которой n-ный элемент был бы для типа геометрии с индексом n:

ShapeMethods shapeMethods[] = {
  { TriangleWorldBound, /*...*/ },
  { CurveWorldBound, /*...*/ };
  // ...
};

При создании геометрии мы кодируем его тип в какие-то из неиспользуемых битов возвращаемого указателя. Затем с учётом указателя на геометрию, конкретный вызов которой мы хотим выполнить, мы бы извлекали этот индекс типа из указателя и использовали как индекс в shapeMethods для нахождения соответствующего указателя функции. По сути, мы реализовывали бы vtable вручную, обрабатывая dispatch самостоятельно. Если бы мы делали это и для геометрии, и для примитивов, то экономили бы по 16 байт на Triangle, однако проделав при этом довольно тяжёлый путь.

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

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

Примечания

1. В конце концов pbrt-next трассирует больше лучей в этой сцене, чем pbrt-v3, что вероятно объясняет увеличение количества операций поиска.
2. Разности лучей для непрямых лучей в pbrt-next вычисляются с помощью того же хака, использованного в расширении кэша текстур для pbrt-v3. Похоже, что он работает достаточно хорошо, но его принципы кажутся мне не особо проверенными.
3. Именно так Rayshade обрабатывает назначение методов. Такой подход используется, когда в C необходим аналог виртуальных методов. Однако Rayshade не делает ничего особенного для устранения указателей на каждый объект.