Под катом собраны полезные советы по оптимизации использования памяти
1. Минимизируйте количество выделений памяти
Динамическое выделение памяти для систем с ее дефицитом - это зло. Во первых, при выделение памяти в куче ее местоположение случайно, а значит если выделить память два раза для двух объектов, то они вряд ли будут лежать в соседней памяти. Поэтому работа с такими объектами будет медленнее.
Во вторых, при постоянном выделение-освобождение памяти идет ее фрагментация. Если в системе ограниченный объем памяти, то наступит момент, когда не удастся выделить новый кусок связной памяти. Причем у вас может быть свободно 50 мегабайт, а выделить не удастся даже 10.
В третьих есть риски утечек памяти. Конечно, для их поиска и устранения вы напишите крутой менеджер памяти, но лучше выделить память один раз и дальше в ней работать, чем постоянно ее выделять динамически.
2. Используйте хранилища данных
Храните объекты вместе в одном куске памяти. Особенно если у вас есть коллекция объектов, с которыми вы будете работать одновременно. Пробегаться по такой коллекции будет значительно эффективнее, если все объекты будут последовательно в памяти.
Получение данных из памяти идет блоком в 64 байта. Это значит что нельзя получить меньше. Когда вы идете по коллекции объектов, то при получении первого объекта, получаются 64 байта начиная с первого байта объекта (это не всегда так, но в данном случае это не важно).
Если все объекты будут последовательно лежать в памяти, то при обращении ко второму объекту данные уже будут в кэше процессора и будет начата работа с ними. Если же объекты будут разбросаны в памяти, то при обращение к каждому из них придется заново обращаться к оперативной памяти.
Обращение к L1 - 20 тактов. Обращение к L2 - 100 тактов. Обращение к общей памяти - 600 тактов.
Поэтому нужно стремиться к написанию кода и такой организации данных, чтобы минимизировать кэшмисы, ибо они дорого обходятся если будут происходить каждый раз при работе к большими коллекциями.
Понятно, что вы не сможете выделять память под каждый объект в отдельности. Стоит иметь менеджер памяти, у которого можно запросить требуемый кусок памяти. В статье Placement new, или как создать объект в выделенной памяти я описывал как создать такой менеджер.
3. Храните одинаковые данные вместе
Допустим у вас есть некий класс. Он сложный, с большим количеством переменных. Есть так же иерархия объектов данного класса.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Класс для некоторого графического объекта
class SomeObject
{
...
Matrix4x4 m_transform; - матрица трансформации объекта (позиция, поворот, масштабирование)
Matrix4x4 m_warldTransform; - мировая матрица трансформации
BoundingSphere m_boundingSphere; - сфера вокруг объекта (нужна для вычисления столкновений)
BoundingSphere m_worldBoundingSphere; - сфера вокруг объекта в пространстве мира
const char* m_name; - имя объекта
bool m_dirty; - флаг того, валидные данные или нет
bool m_life; - флаг того, что объект жив
};
// функция получения окружности описывающей объект
const BoundingSphere& SomeObject::GetBoundingSphere( const Matrix4x4& parentTransform )
{
if( m_dirty )
m_worldBoundingSphere = m_boundingSphere.Transform( parentTransform );
return m_worldBoundingSphere;
}
Что не так с этим кодом? Посмотрите на функцию. Там находится проверка на валидность данных, которая должна оптимизировать. Но эта проверка занимает 23-24 (указаны для процессора Cell, PS3) цикла процессора, в то время как вычисление выполнится за 12 тактов. Т.е. эта “оптимизация” совершенна не нужна.
Ну и конечно где нибудь будет коллекция таких объектов, например такая:
1
std::vector< SomeObject* > m_objects;
При проходе по такой коллекции для получения каждого нового элемента будет обращение к памяти. Более того, если нужно будет всего лишь найти объекты у которых m_life == false, то нужно будет грузить в память все целиком.
Решением является хранение однотипных данных в общих хранилищах. Создаем массив для Matrix4x4 и для BoundingSphere, где будут находиться данные от всех объектов. Каждый объект будет содержать указатель на свои данные. Наш объект изменится таким образом:
1
2
3
4
5
6
7
8
9
10
11
// Класс для некоторого графического объекта
class SomeObject
{
...
Matrix4x4* m_transform;
Matrix4x4* m_warldTransform;
BoundingSphere* m_boundingSphere;
BoundingSphere* m_worldBoundingSphere;
const char* m_name;
bool m_life;
};
Одна только эта реорганизация ускорила выполнение GetBoundingSphere для всех объектов на 30 процентов. Это произошло не только потому, что размер объекта стал меньше (больше влазит в кеш) и математические данные лежат в смежной памяти, поэтому и проводить вычисления с ними значительно быстрее.
4. Работайте не с объектами а с коллекциями объектов
При работе с некоторыми коллекциями объектов нет нужды работать с объектами в отдельности. В этом случае лучше реорганизовать внутреннее устройство коллекции таким образом, чтобы вообще устранить сам объект. Допустим есть объект Ball и его коллекция Balls.
1
2
3
4
5
6
7
8
9
10
class Ball
{
Matrix4x4* m_transform;
Matrix4x4* m_warldTransform;
bool m_life;
};
class Balls
{
std::vector< Ball* > m_balls;
}
Это лучше реорганизовать так, чтобы вообще избавиться от класса Ball. Это наиболее эффективно с точки зрения использования памяти, когда однотипные данные находятся последовательно в памяти. Это значительно ускорит работу с такой коллекцией. Если иногда внешнему миру нужен экземпляр такой коллекции, то можно предусмотреть функцию GetBall.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Ball
{
Matrix4x4 m_transform;
Matrix4x4 m_warldTransform;
bool m_life;
};
class Balls
{
// хранит данные вместо самих объектов
std::vector< Matrix4x4 > m_transform;
std::vector< Matrix4x4 > m_warldTransform;
std::vector< bool > m_life;
const Ball& GetBall( int index ) const
{
return Ball( m_transform[ index ], m_warldTransform[ index ], m_life[ index ] );
}
}
5. Поблочное выделение памяти
Выделяйте память большими блоками, а не под каждый элемент в отдельности. Допустим вам нужно выделить память под массив таких структур и заполнить его данными (допустим из файла). Предполагается, что данные после загрузки не будут меняться:
1
2
3
4
5
6
7
8
9
10
11
struct Data
{
int id;
int matrixCount; // количество элементов в массиве 1
int boundingsCount; // количество элементов в массиве 2
Matrix4x4 matrixes[ MAX_SIZE ]; // 1 массив данных
BoundingSphere boundings[ MAX_SIZE ]; // 2 массив данных
}
int m_count;// размер массива
Data* m_data; // массив данных
Для начала реорганизуем структуру в соответствии с пунктом 3.
1
2
3
4
5
6
7
8
struct Data
{
int id;
int matrixCount; // количество элементов в массиве 1
int boundingsCount; // количество элементов в массиве 2
Matrix4x4* matrixes; // 1 массив данных
BoundingSphere* boundings; // 2 массив данных
}
Неправильный вариант выделения памяти:
1
2
3
4
5
6
7
8
m_data = new Data[ m_count ];
for( int i = 0; i < m_count; ++i )
{
...
m_data[ i ].matrixes = new Matrix4x4[ matrixCount ];
m_data[ i ].boundings = new BoundingSphere[ boundingsCount ];
// заполняем массивы данными
}
Правильный вариант:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1. Посчитать, сколько всего будет матриц и баундингов.
totalMatrixes = ..;
totalBoundings = ..;
2. // выделяем память подо все разом.
// сначала в памяти будут идти структуры, а затем сами данные
typedef unsigned char u8;
u8* dataPtr = (Data*) new u8[ sizeof( Data )*m_count +
sizeof( Matrix4x4 )*totalMatrixes +
sizeof( BoundingSphere )*totalBoundings ];
m_data = dataStart;
dataPtr += sizeof( Data ) * m_count;
for( int i = 0; i < m_count; ++i )
{
m_data[ i ].id = ..;
m_data[ i ].matrixCount = ..;
m_data[ i ].boundingsCount = ..;
// устанавливаем указатели на данные
m_data[ i ].matrixes = dataPtr; dataPtr += sizeof( Matrix4x4 ) * m_data[ i ].matrixCount;
m_data[ i ].boundings = dataPtr; dataPtr += sizeof( BoundingSphere ) * m_data[ i ].boundingsCount;
// заполняем массивы данными
}
- Как видно, мы выделили память только один раз, сразу большим куском. Это уменьшает ее фрагментацию и улучшает эффективность по работе с данными.
- Проходить по массиву таких структур будет достаточно быстро (например чтобы найти элемент с нужным id), т.к. размер структуры маленький будет меньше кэшмисов.
- Проводить вычисления над данными будет так же эффективно, т.к. все данные в одном месте.
6. Учитывайте выравнивание
Учитывайте выравнивание типов. Располагайте наиболее большие типы вначале структуры. Группируйте типы с равным размером, располагая переменные подряд. Помните, что double выравнивается минимум по 8.
Пример:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct s1
{
short int a;
double b;
int d;
}
sizeof(s1[ 10 ]) == 24 * 10
struct s2
{
double b;
int d;
short int a;
}
sizeof(s1[ 10 ]) == 16 * 10
7. Знайте размер типов
Заведите себе подобные типы и всегда учитывайте, сколько занимают ваши переменные в памяти. Это поможет легче учитывать пункт 6.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 8 bit
typedef unsigned char u8;
typedef signed char i8;
// 16 bit
typedef unsigned short u16;
typedef signed short i16;
// 32 bit
typedef unsigned int u32;
typedef signed int i32;
// 64 bit
typedef unsigned long long u64;
typedef signed long long i64;
// floats
typedef float f32;
typedef double f64;
Данные методы имеют отношение к технике, называемой Data oriented design. Можете почитать про это более подробно тут: Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf.
Смотрите так же статьи по смежной тематике: Оптимизация кода на С++. Эффективный код на С++.
Комментарии
FiloXSee, 8 июля 2011, 16:32
Объяснение 4-го пункта:
Когда идет постоянная работа с объектами и их иерархиями, например в бизнесс логике, то 4-й пункт будет практически не применим. Он применим тогда, когда проектируется некая система с большим количеством данных.
Пример: вы собираетесь делать систему частиц. Понятно что внешнему коду не нужно работать с конкретной частицей в отдельности (никогда не нужно). Из вне придет команда — обновить/отрисовать систему частиц. Этот процесс будет значительно ускорен, если частицы будут идти в памяти подряд (будет меньше обращений к памяти).
Как выглядит обновление частиц:
- нужно для всех частиц изменить позицию
- нужно для всех частиц изменить вращение … цвет и прочие параметры.
Если данные будут представлены в виде последовательности частиц то: размер частицы 64 байта. Из памяти берется за раз 64 байта. Это значит что при обновление на каждую частицу будет по запросу к памяти (который 600 тактов, в то время как вычисления будут 12-15 тактов, т.е. будет тормозить доступ к памяти, а не математика).
Если же организовать все как в пункте 4-е, т.е. раcположить сначала все позиции в памяти, затем все повороты и т.д., то за раз будет получено 64/16=4 позиции для 4-х партиклов (тут 16 байт это размер структуры float x,y,z,w). т.е. для расчета всех партиклов будет в 4-е раза меньше запросов к памяти, скорость выполнения увеличится более чем в 3-и раза.
FiloXSee, 8 июля 2011, 16:32
Объяснение 4-го пункта:
Когда идет постоянная работа с объектами и их иерархиями, например в бизнесс логике, то 4-й пункт будет практически не применим. Он применим тогда, когда проектируется некая система с большим количеством данных.
Пример: вы собираетесь делать систему частиц. Понятно что внешнему коду не нужно работать с конкретной частицей в отдельности (никогда не нужно). Из вне придет команда — обновить/отрисовать систему частиц. Этот процесс будет значительно ускорен, если частицы будут идти в памяти подряд (будет меньше обращений к памяти).
Как выглядит обновление частиц:
- нужно для всех частиц изменить позицию
- нужно для всех частиц изменить вращение … цвет и прочие параметры.
Если данные будут представлены в виде последовательности частиц то: размер частицы 64 байта. Из памяти берется за раз 64 байта. Это значит что при обновление на каждую частицу будет по запросу к памяти (который 600 тактов, в то время как вычисления будут 12-15 тактов, т.е. будет тормозить доступ к памяти, а не математика).
Если же организовать все как в пункте 4-е, т.е. раcположить сначала все позиции в памяти, затем все повороты и т.д., то за раз будет получено 64/16=4 позиции для 4-х партиклов (тут 16 байт это размер структуры float x,y,z,w). т.е. для расчета всех партиклов будет в 4-е раза меньше запросов к памяти, скорость выполнения увеличится более чем в 3-и раза.
4-й метод актуален когда расчеты часто проводятся по какому то параметру структуры. Например найти объект по индексу. Это будет значительно быстрее если индексы будут в отдельном массиве.
FiloXSee, 8 июля 2011, 16:32
4-й метод актуален когда расчеты часто проводятся по какому то параметру структуры. Например найти объект по индексу. Это будет значительно быстрее если индексы будут в отдельном массиве.