Как оптимизировать программу по памяти

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

1、 Площадь стека： Пространство стека является непрерывным, и первый-последний-последний гарантирует, что фрагментация памяти не произойдет, и она будет расти от высокого адреса к низкому адресу. Компилятор автоматически выделяет и освобождает, Используется для хранения значений параметров функции, локальных переменных и т. Д. Операция аналогична стеку в структуре данных. Стек используется для поддержки контекста вызова функции и не может быть реализован без вызова функции стека.
2、 Область кучи (куча)： Кучи различны. Память кучи не обязательно является непрерывной. Метод выделения состоит в том, чтобы перемещаться к первому узлу в свободном связанном списке каждый раз, когда он превышает запрошенное пространство.

Размер выделенного пространства обычно не точно равен запрошенному размеру памяти, поэтому часто Новая операция должна породить много космического мусора. Память кучи обычно выделяется программистами, использующими malloc, new или распределитель в STL. Если программист не освобождает ее, операционная система может вернуть ее после завершения программы.

Максимальная оптимизация оперативной памяти для игр | Как оптимизировать оперативную память

3、 Глобальная зона (статическая): Здесь хранятся глобальные и статические переменные.
4、 Постоянная площадь: Здесь размещается постоянная строка, которая высвобождается системой после завершения программы.
5、 Область кода: Сохранить двоичный код тела функции.

Управление памятьюЕго можно разделить на три уровня, снизу вверх:

• Управление памятью ядра операционной системы
• glibc (1) Слой использует алгоритм управления памятью, поддерживаемый системными вызовами
• После того, как приложение динамически выделяет память из glibc, оно оптимизируется в соответствии с характеристиками программы самого приложения, такими как использование подсчета ссылок std :: shared_ptr, метод пула памяти apache и т. Д.

Jemalloc

Эта статья посвящена знакомству с jemalloc, используемым Facebook, и тому, как использовать jemalloc.Для этого принципа, пожалуйста, обратитесь к Приложению 2.

ptmalloc2 — это glibc, который мы сейчас используем (1) версия Malloc

1. После того, как выделенная память освобождается первой, она может быть не освобождена
2. Многопоточные замки стоят дорого
3. Если память, запрошенная потоком, не освобождается после окончания, другие потоки не могут использоваться, что приводит к потере
4. блок (блок) не менее 8 байт
5. Память с длительным жизненным циклом легко вызывает фрагментацию памяти, что не способствует переработке

1. jemalloc выделяет локальный ThreadCache для каждого потока, небольшие объекты (
2. Использование RB-Tree для поиска доступного пространства в логарифмическом времени
3. Увеличенный коэффициент попадания в кэш Увеличенный коэффициент попадания в кэш

Оптимизируй свою оперативную память и подними высокий FPS в ИГРАХ!

Для производительности приведите график из приложения 2:

Установить с помощью Jemalloc

git clone https://github.com/jemalloc/jemalloc/releases/download/5.1.0/jemalloc-5.1.0.tar.bz2 tar -jxvf jemalloc-5.1.0.tar.bz2 cd jemalloc-5.1.0/ ./configure make make install

2. Используйте динамические ссылки:
Добавьте -ljemalloc к параметрам ссылки
Например: g ++ -p test test.cpp -ljemalloc

После генерации исполняемого файла:

ldd test

Появляется вторая строка рисунка ниже, даже если она прошла успешно:

3. Используйте статическое связывание Если вы хотите использовать статическое связывание, вам нужно сбросить его при компиляции jemalloc

./configure —with-jemalloc-prefix make Скопируйте jemalloc.h и libjemalloc.a в подходящее место. В настоящее время макроопределение jemalloc.h будет немного отличаться от ранее скомпилированного jemalloc.h. Потому что в это время malloc освобождает realloc в файле libjemlloc.a становится yesmalloc, yesfree, yesrealloc. Это сделано для того, чтобы не дублировать имена malloc, free и realloc в glic, иначе он не скомпилируется.

В написанной вами программе вам нужно заменить malloc free realloc на je_malloc, je_free, je_realloc. (Jemalloc.h заменит je_malloc, je_free, je_realloc. На yesmalloc, yesfree, yesrealloc) Во время компиляции добавьте -DJEMALLOC_NO_DEMANGLE -static

Источник: russianblogs.com

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

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

Во вторых, при постоянном выделение-освобождение памяти идет ее фрагментация. Если в системе ограниченный объем памяти, то наступит момент, когда не удастся выделить новый кусок связной памяти. Причем у вас может быть свободно 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 parentTransform )

Что не так с этим кодом?

Посмотрите на функцию. Там находится проверка на валидность данных, которая должна оптимизировать. Но эта проверка занимает 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 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;

Источник: itw66.ru

Как оптимизировать программу по памяти?

Решаю задачу для контеста Яндекса, вылетает на одном тесте, пишет Memory Limited. Пытался делать решение через списки, но так получается что программа тратит еще больше памяти.

conf_num = int(input()) conf_dict = <> conf_list = [] m = 1 for i in range(conf_num): conf = input() conf_list.append(conf) for s in range(len(conf) — 2): if conf[s:s + 3] not in conf_dict: conf_dict[conf[s:s + 3]] = m m += 1 conf_table = [[0] * len(conf_dict) for i in range(len(conf_dict))] pairs_list = [] edge_num = 0 for i in conf_list: for s in range(len(i) — 3): conf_table[conf_dict[i[s:s + 3]] — 1][conf_dict[i[s + 1:s + 4]] — 1] += 1 if [i[s:s + 3], i[s + 1:s + 4]] not in pairs_list: pairs_list.append([i[s:s + 3], i[s + 1:s + 4]]) if conf_table[conf_dict[i[s:s + 3]] — 1][conf_dict[i[s + 1:s + 4]] — 1] == 1: edge_num += 1 # ВЫВОД print(len(conf_dict)) # Кол-во вершин графа print(edge_num) # Кол-во ребер графа for i in pairs_list: print(f’ ‘)

Отслеживать

задан 19 авг 2022 в 13:05

13 3 3 бронзовых знака

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Заметьте, что существует максимум 456976=26^4 рёбер, поскольку каждое ребро соответствует комбинации S[i]S[i+1]S[i+2]S[i+3] четырех латинских символов, и при использовании ребра в качестве ключа, памяти требуется всего несколько мегабайт (можно ещё уменьшить, сопоставив последовательности символов число в указанном диапазоне, но и так пройти должно)

Можно сделать всего один проход по строкам, беря 4 символа за раз

from collections import Counter s = ‘abcdcdcdabcd’ e = Counter() for i in range(len(s) — 3): t = s[i:i+4] e[t] += 1 for item in e: print(item[:3], item[1:], e[item]) abc bcd 2 bcd cdc 1 cdc dcd 2 dcd cdc 1 dcd cda 1 cda dab 1 dab abc 1

Источник: ru.stackoverflow.com