Warning: session_start(): open(/var/lib/php5/sess_72hkutbmpflanqlmipldtgahq2, O_RDWR) failed: No space left on device (28) in /opt/www/itw66.ru/engine/modules/session/Session.class.php on line 76
Методы оптимизации памяти (Memory optimization) / C++ / it works!
C++

Методы оптимизации памяти (Memory optimization)

1. Минимизируйте количество выделений памяти


Динамическое выделение памяти для систем с ее дефицитом — это зло. Во первых, при выделение памяти в куче ее местоположение случайно, а значит если выделить память два раза для двух объектов, то они вряд ли будут лежать в соседней памяти. Поэтому работа с такими объектами будет медленнее.

Во вторых, при постоянном выделение-освобождение памяти идет ее фрагментация. Если в системе ограниченный объем памяти, то наступит момент, когда не удастся выделить новый кусок связной памяти. Причем у вас может быть свободно 50 мегабайт, а выделить не удастся даже 10.

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


2. Используйте хранилища данных


Храните объекты вместе в одном куске памяти. Особенно если у вас есть коллекция объектов, с которыми вы будете работать одновременно. Пробегаться по такой коллекции будет значительно эффективнее, если все объекты будут последовательно в памяти.

Получение данных из памяти идет блоком в 64 байта. Это значит что нельзя получить меньше. Когда вы идете по коллекции объектов, то при получении первого объекта, получаются 64 байта начиная с первого байта объекта (это не всегда так, но в данном случае это не важно).

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

Обращение к L1 — 20 тактов.
Обращение к L2 — 100 тактов.
Обращение к общей памяти — 600 тактов.

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

Понятно, что вы не сможете выделять память под каждый объект в отдельности. Стоит иметь менеджер памяти, у которого можно запросить требуемый кусок памяти. В статье Placement new, или как создать объект в выделенной памяти я описывал как создать такой менеджер.

3. Храните одинаковые данные вместе


Допустим у вас есть некий класс. Он сложный, с большим количеством переменных. Есть так же иерархия объектов данного класса.

// Класс для некоторого графического объекта
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 тактов. Т.е. эта «оптимизация» совершенна не нужна.

Ну и конечно где нибудь будет коллекция таких объектов, например такая:

std::vector< SomeObject* > m_objects;


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

Решением является хранение однотипных данных в общих хранилищах. Создаем массив для Matrix4x4 и для BoundingSphere, где будут находиться данные от всех объектов. Каждый объект будет содержать указатель на свои данные. Наш объект изменится таким образом:

// Класс для некоторого графического объекта
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.


class Ball
{
   Matrix4x4*       m_transform;
   Matrix4x4*       m_warldTransform;
   bool             m_life;
};
class Balls
{
  std::vector< Ball* >  m_balls;
}


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

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. Поблочное выделение памяти


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

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.

struct Data
{
   int              id;
   int              matrixCount;    // количество элементов в массиве 1
   int              boundingsCount; // количество элементов в массиве 2
   Matrix4x4*       matrixes;       // 1 массив данных
   BoundingSphere*  boundings;      // 2 массив данных
}


Неправильный вариант выделения памяти:

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. Посчитать, сколько всего будет матриц и баундингов.
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.

Пример:

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.

// 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.

Смотрите так же статьи по смежной тематике:
Оптимизация кода на С++.
Эффективный код на С++.

Похожие записи




Комментарии (3) свернуть  |  развернуть

0
Объяснение 4-го пункта:

Когда идет постоянная работа с объектами и их иерархиями, например в бизнесс логике, то 4-й пункт будет практически не применим. Он применим тогда, когда проектируется некая система с большим количеством данных.

Пример: вы собираетесь делать систему частиц. Понятно что внешнему коду не нужно работать с конкретной частицей в отдельности (никогда не нужно). Из вне придет команда — обновить/отрисовать систему частиц. Этот процесс будет значительно ускорен, если частицы будут идти в памяти подряд (будет меньше обращений к памяти).

Как выглядит обновление частиц:
1. нужно для всех частиц изменить позицию
2. нужно для всех частиц изменить вращение
… цвет и прочие параметры.

Если данные будут представлены в виде последовательности частиц то: размер частицы 64 байта. Из памяти берется за раз 64 байта. Это значит что при обновление на каждую частицу будет по запросу к памяти (который 600 тактов, в то время как вычисления будут 12-15 тактов, т.е. будет тормозить доступ к памяти, а не математика).

Если же организовать все как в пункте 4-е, т.е. раcположить сначала все позиции в памяти, затем все повороты и т.д., то за раз будет получено 64/16=4 позиции для 4-х партиклов (тут 16 байт это размер структуры float x,y,z,w). т.е. для расчета всех партиклов будет в 4-е раза меньше запросов к памяти, скорость выполнения увеличится более чем в 3-и раза.
комментарий был удален
0
4-й метод актуален когда расчеты часто проводятся по какому то параметру структуры. Например найти объект по индексу. Это будет значительно быстрее если индексы будут в отдельном массиве.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.

Warning: Unknown: open(/var/lib/php5/sess_72hkutbmpflanqlmipldtgahq2, O_RDWR) failed: No space left on device (28) in Unknown on line 0

Warning: Unknown: Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php5) in Unknown on line 0