Оптимизация геометрии для 64-битной платформы

Сейчас мы работаем над библиотеками серверной обработки геометрии (нахождение пути, проверка видимости и пр.). В тестовом проекте проявилась интересная проблема: геометрия, особенно со вспомогательными данными, занимала много памяти на платформе х86 и очень много на х64. На первый взгляд все было спроектировано верно, но на диске данные занимали около 100МБ, а в памяти – больше гигабайта.
Геометрия описывается треугольниками, каждый треугольник содержит координаты трех вершин и некоторые вспомогательные данные (нормаль, коэффициенты для расчета пересечения и пр.). Треугольники каждой модели упорядочены в дерево, каждый лист дерева хранит набор треугольников, причем один и тот же треугольник может присутствовать в разных листьях.

Сначала система была прототипирована без различных оптимизаций. Затем было решено отказаться от хранения координат в треугольнике – создан общий пул вершин для каждой модели и в треугольниках хранились только ссылки. Вторым шагом мы сделали то же самое для листьев дерева – заменили треугольники ссылками на общий пул. Именно в этот момент и было замечено чрезмерное потребление памяти, особенно в x64 режиме.
В упрощенной модели можно сказать, что дерево представляло собой массив массивов указателей на треугольники, каждый из которых – массив из трех указателей на вершины. В С++ это упрощенно можно записать так:

typedef Vertex** Triangle;
typedef Triangle** Leaf;
typedef Leaf* Tree;

Запись

Tree m_tree;

эквивалентна

Vertex ***** m_tree;

Выглядит достаточно страшно :). Для визуальности можно воспользоваться STL и придуманным шаблоном stdext::triplet и написать так:

typedef stdext::triplet<Vertex*, Vertex*, Vertex*> Triangle;
typedef std::vector<Triangle*> Leaf;
typedef std::vector<Leaf> Tree;

Запись

Tree m_tree;

эквивалентна

std::vector<
    std::vector<
        stdext::triplet<Vertex*, Vertex*, Vertex*>* > >
           m_tree;

Конечно же, в реальной ситуации треугольник, лист и дерево – отдельные классы с различными свойствами и методами, но сейчас нам важна именно схема их вложенности, иерархия. Не трудно догадаться, что каждый указатель в архитектуре x86 занимает 4 байта, а в x64 – 8 байт. У нас же указателей вышло много, что и вылилось в существенное потребление памяти.
Для серверной геометрии нередко используются упрощенные модели – нет особой разницы, выделяется ли оконная рама для просчета пути NPC, количество полигонов ствола дерева почти не влияет на расчет линии видимости возле него. Это обуславливает небольшой размер моделей – редко когда модель имеет несколько тысяч вершин. Выходит, что для адресации вершин и треугольников можно было бы использовать 16-битовые индексы, в то время как мы используем на х64 системе 64-битовые указатели.

Дальнейшее развитие оптимизации достаточно предсказуемо – мы заменили наиболее используемые ссылки индексами unsigned short, что уменьшило потребляемую иерархией память в 2 раза на х86 системах и в 4 раза на архитектуре х64. Следующим шагом были созданы шаблонные классы, которые позволяют использовать любой тип в качестве индексов: в зависимости от сложности модели создается Tree либо Tree. Более сложные модели удобнее разбивать на части, чем хранить с 32-битными индексами. Более 50% моделей из нашего тестового проекта попали в категорию с 8-битными индексами. По сравнению с изначальным вариантом с указателями разница получилась огромная.

А теперь немного цифр:

8-bit: models 5140, leafs 157489, leaf references 899038, triangles 409962
16-bit: models 4376, leafs 2950551, leaf references 13938081, triangles 6774482

Это значит, что ранее у нас было 21553332 указателей на вершины и 14837119 указателей на треугольники, что в 64-битах означает 291123608 байт ~= 277 мегабайт данных.
После оптимизации получилось 1229886 8-битных индексов вершин, 20323446 16-битных, 899038 8-битных указателей на треугольники, 13938081 16-битных. В сумме это 70651978 байт ~= 67 мегабайт данных. Выигрыш более чем в 4 раза на 64-битной архитектуре.

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