image

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

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

Память
BVH-дерево 9,01 ГиБ
Кривые 1,44 ГиБ
MIP-текстуры 2,00 ГиБ
Меши треугольников 11,02 ГиБ


Что касается времени выполнения, то встроенная статистика оказалась краткой и выдала отчёт только о выделении памяти под известные объекты размером в 24 ГБ. top сообщил, что на самом деле использовано около 70 ГБ памяти, то есть в статистике не учтено 45 ГБ. Небольшие отклонения вполне объяснимы: распределителям динамической памяти требуется дополнительное место для регистрации использования ресурсов, часть теряется из-за фрагментации, и так далее. Но 45 ГБ? Здесь определённо скрывается что-то нехорошее.

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

Примитивы


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

Primitives 24,67 ГиБ

Ой-ёй. Так что же такое примитив, и зачем вся эта память?

pbrt различает Shape, который является чистой геометрией (сферой, треугольником и т.д.) и Primitive, который является сочетанием геометрии, материала, иногда функции излучения и задействованной среды находящейся внутри и снаружи поверхности геометрии.

Существует несколько вариантов базового класса Primitive: GeometricPrimitive, который является стандартным случаем: «ванильным» сочетанием геометрии, материала и т.д., а также TransformedPrimitive, который представляет собой примитив с применёнными к нему преобразованиями, или как экземпляр объекта, или для подвижных примитивов с преобразованиями, изменяющимися во времени. Оказывается, что в этой сцене оба этих типа являются пустой тратой пространства.

GeometricPrimitive: 50% лишнего пространства


Примечание: в этом анализе сделаны некоторые ошибочные допущения; они пересмотрены в четвёртом посте серии.

4,3 ГБ использовано на GeometricPrimitive. Забавно жить в мире, где 4,3 ГБ использованной ОЗУ — это не самая большая твоя проблема, но давайте тем не менее посмотрим, откуда у нас 4,3 ГБ GeometricPrimitive. Вот соответствующие части определения класса:

class GeometricPrimitive : public Primitive {
    std::shared_ptr<Shape> shape;
    std::shared_ptr<Material> material;
    std::shared_ptr<AreaLight> areaLight;
    MediumInterface mediumInterface;
};

У нас есть указатель на vtable, ещё три указателя, а затем MediumInterface, содержащий ещё два указателя общим размером 48 байтов. В этой сцене всего несколько излучающих освещение мешей, поэтому areaLight почти всегда является нулевым указателем, а влияющей на сцену среды нет, поэтому оба указателя mediumInterface также являются null. Таким образом, если бы у нас была специализированная реализация класса Primitive, которую можно было использовать при отсутствии функции излучения и среды, то мы бы сэкономили почти половину места на диске, занимаемого GeometricPrimitive — в нашем случае примерно 2 ГБ.

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

Прежде чем двигаться дальше, выполним проверочный рендеринг:


Пляж с острова из фильма «Моана», отрендеренный pbrt-v3 с разрешением 2048x858 и 256 сэмплами на пиксель. Общее время рендеринга на 12-ядерном/24-поточном инстансе Google Compute Engine с частотой 2 ГГц с последней версией pbrt-v3 составило 2 ч 25 мин 43 с.

TransformedPrimitives: 95% потраченного впустую пространства


Память, выделенная под 4,3 ГБ GeometricPrimitive, была довольно болезненным ударом, но как насчёт 17,4 ГБ под TransformedPrimitive?

Как сказано выше, TransformedPrimitive используется как для преобразований с изменением во времени, так и для экземпляров объектов. В обоих случаях нам нужно применить дополнительное преобразование к существующему Primitive. В классе TransformedPrimitive есть только два члена:

    std::shared_ptr<Primitive> primitive;
    const AnimatedTransform PrimitiveToWorld;

Пока всё хорошо: указатель на примитив и изменяющееся со временем преобразование. Но что на самом деле хранится в AnimatedTransform?

    const Transform *startTransform, *endTransform;
    const Float startTime, endTime;
    const bool actuallyAnimated;
    Vector3f T[2];
    Quaternion R[2];
    Matrix4x4 S[2];
    bool hasRotation;
    struct DerivativeTerm {
        // ...
        Float kc, kx, ky, kz;
    };
    DerivativeTerm c1[3], c2[3], c3[3], c4[3], c5[3];

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

Но в этой сцене ничего не движется. С точки зрения преобразований для экземпляров объектов нам необходим один указатель на преобразование, а значения для разложения и подвижных ограничивающих параллелепипедов не нужны. (То есть всего нужно 8 байт). Если создать отдельную реализацию Primitive для неподвижных экземпляров объектов, 17,4 ГБ сжимаются всего до 900 МБ (!).

Что касается GeometricPrimitive, то его исправление — это нетривиальное изменение по сравнению с описанным в книге, поэтому мы тоже отложим его на следующую версию pbrt. По крайней мере, мы теперь понимаем, что происходит с хаосом из 24,7 ГБ памяти Primitive.

Неприятность с кэшем преобразований


Следующим по размеру блоком неучтённой памяти, определённым massif, был TransformCache, который занимал примерно 16 ГБ. (Вот ссылка на исходную реализацию.) Идея заключается в том, что одна и та же матрица преобразований часто используется в сцене несколько раз, поэтому лучше всего иметь в памяти её единственную копию, чтобы все использующие её элементы просто хранили указатель на одно и то же преобразование.

Для хранения кэша TransformCache использовал std::map, а massif сообщил, что 6 из 16 ГБ использовалось для узлов чёрно-красного дерева в std::map. Это ужасно много: 60% процентов этого объёма используется для самих преобразований. Давайте посмотрим на объявление для этого распределения:

std::map<Transform, std::pair<Transform *, Transform *>> cache;

Здесь работа выполнена на отлично: Transform целиком используются как ключи для распределения. Ещё лучше то, что в pbrt Transform хранит две матрицы 4x4 (матрицу преобразования и её обратную матрицу), что приводит хранению в каждом узле дерева 128 байт. Всё это абсолютно излишне для хранимого для него значения.

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

Кроме того, что пространство впустую тратится на ключи, с поиском в std::map для обхода красно-чёрного дерева связано много операций переходов по указателям, поэтому кажется логичным попробовать что-то совершенно новое. К счастью, о TransformCache мало написано в книге, поэтому вполне допустимо полностью переписать его.

И последнее, прежде чем мы приступим: после исследования сигнатуры метода Lookup() становится очевидной ещё одна проблема:

void Lookup(const Transform &t, Transform **tCached,
            Transform **tCachedInverse)

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

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

В новой реализации добавлены следующие улучшения:

  • Она использует хэш-таблицу, позволяющую ускорить поиск, и не требует хранения ничего, кроме массива Transform *, что, по сути, снижает объём используемой памяти до величины, действительно необходимой для хранения всех Transform.
  • Сигнатура метода поиска теперь имеет вид Transform *Lookup(const Transform
    &t)
    ; в одном месте, где вызывающая функция хочет получить из кэша обратную матрицу, он просто вызывает Lookup() дважды.

Для хэширования я использовал хэш-функцию FNV1a. После её реализации я обнаружил пост Араса о хэш-функциях; возможно, мне просто стоило использовать xxHash или CityHash, потому что их производительность выше; возможно, когда-нибудь мой стыд победит и я исправлю это.

Благодаря новой реализации TransformCache значительно снизилось общее время запуска системы, — до 21 мин 42 с. То есть мы сэкономили ещё 5 мин 7 с, или ускорились в 1,27 раза. Более того, более эффективное использование памяти снизило занимаемое матрицами преобразования место с 16 до 5,7 ГБ, что почти равно объёму хранящихся данных. Это позволило нам не пытаться воспользоваться тем, что на самом деле они не проективные, и хранить матрицы 3x4 вместо 4x4. (В обычном случае я бы скептически отнёсся к значимости такого рода оптимизации, но здесь она бы сэкономила нам больше гигабайта — куча памяти! Это определённо стоит сделать в рендерере продакшена.)

Небольшая оптимизация производительности для завершения


Слишком обобщённая структура TransformedPrimitive стоит нам и памяти, и времени: профайлер сообщил, что солидная часть времени при запуске тратилась в функции AnimatedTransform::Decompose(), которая разлагает преобразования матрицы в поворот кватерниона, перенос и масштаб. Поскольку в этой сцене ничего не движется, эта работа не нужна, и тщательная проверка реализации AnimatedTransform показала, что ни к одному из этих значений доступ не осуществляется, если две матрицы преобразования на самом деле идентичны.

Добавив к конструктору две строки, чтобы разложения преобразований не выполнялись, когда они не требуются, мы сэкономили ещё 1 мин 31 с времени запуска: в результате мы пришли к 20 мин 9 с, то есть в целом ускорились в 1,73 раза.

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

Комментарии (4)


  1. iPilot
    21.07.2018 20:17

    Читаю и в каждом абзаце, как соль на рану: «Преждевременные оптимизации — зло», «Труд программиста дорог, а докупить памяти или новый процессор — дешевле».
    Скупой платит дважды?


    1. bjornd
      21.07.2018 20:22
      +2

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


    1. ToSHiC
      22.07.2018 00:47

      В исходниках pbrt v1 есть ченджлог, и там упоминается 2005 год, тогда 70ГБ было размером приличного жёсткого диска для ноутбука, топовые 3.5" диски были объёмом 500ГБ.


    1. RomanArzumanyan
      24.07.2018 12:41

      В статье оптимизируют достаточно зрелый продукт, не так ли?