Управління пам'яттю у C++

Робота з динамічною пам'яттю найчастіше є вузьким місцем у багатьох алгоритмах, якщо не застосовувати спеціальні хитрощі.

У статті я розгляну кілька таких технік. Приклади у статті відрізняються (наприклад, від цього) тим, що використовується перевантаження операторів new і delete і за рахунок цього синтаксичні конструкції будуть мінімалістичними, а переробка програми простий. Також описані підводні камені, знайдені в процесі (звичайно, гуру, які читали стандарт від кірки до кірки, не здивуються).

0. А чи потрібна нам ручна робота з пам'яттю?

Насамперед перевіримо, наскільки розумний аллокатор може прискорити роботу з пам'яттю.

Напишемо прості тести для C++ та C# (C# відомий чудовим менеджером пам'яті, який ділить об'єкти по поколінням, використовує різні пули для об'єктів різних розмірів тощо).

class Node < public: Node* next; >; //. for (int i = 0; i

class Node < public Node next; >//. for (int l = 0; l

Незважаючи на всю «сферично-вакуумність» прикладу, різниця в часі вийшла в 10 разів (62 ms проти 650 ms). Крім того, c#-приклад закінчено, а за правилами гарного тону c++ виділені об'єкти треба видалити, що ще більше збільшить відрив (до 2580 ms).

1. Пул об'єктів

Очевидне рішення - забрати в ОС великий блок пам'яті і розбити його на рівні блоки розміру sizeof(Node), при виділенні пам'яті брати блок із пулу, при звільненні - повертати в пул. Пул найпростіше організувати за допомогою списку (стека).

Оскільки стоїть завдання мінімального втручання в програму, все, що можна буде зробити, це додати домішку BlockAlloc до класу Node:

class Node : public BlockAlloc

Насамперед нам знадобиться пул великих блоків (сторінок), які забираємо у ОС чи C-runtime. Його можна організувати поверх функцій malloc і free, але для більшої ефективності (щоб пропустити зайвий рівень абстракції) використовуємо VirtualAlloc/VirtualFree.Ці функції виділяють пам'ять блоками, кратними 4K, а також резервують адресний простір процесу блоками, кратними 64K. Одночасно вказуючи опції commit та reserve, ми перескакуємо ще один рівень абстракції, резервуючи адресний простір та виділяючи сторінки пам'яті одним викликом.

inline size_t align(size_t x, size_ta) < return ((x-1) | (a-1)) + 1; >//#define align(x, a) ((((x)-1) | ((a)-1)) + 1) class class PagePool < public: void* GetPage() < void* page = VirtualAlloc( NULL, PageSize, MEM_COMMIT | MEM_RESERVE; pages.push_back(page); return page; >~PagePool() < for (vector::iterator i = pages.begin(); i != pages.end(); ++i) < VirtualFree(*i, 0, MEM_RELEASE); >> private: vector pages; >;

Потім організуємо пул блоків заданого розміру

template class BlockPool : PagePool < public: BlockPool() : head(NULL) < BlockSize = align(sizeof(T), Alignment); count = PageSize/BlockSize; >void* AllocBlock() < // todo: lock(this) if (!head) FormatNewPage(); void * tmp = head; head = * (void **) head; return tmp; >void FreeBlock(void* tmp) < // todo: lock(this) *(void**)tmp = head; head = tmp; >private: void* head; size_t BlockSize; size_t count; void FormatNewPage() < void* tmp = GetPage(); head = tmp; for(size_t i = 0; i < count-1; i++) < void * next = (char *) tmp + BlockSize; *(void**)tmp = next; tmp = next; >*(void**)tmp = NULL; > >;

коментарем // todo: lock(this) позначені місця, які потребують міжпотокової синхронізації (наприклад, використовуйте EnterCriticalSection або boost::mutex).

Поясню, чому під час «форматування» сторінки не використовується абстракція FreeBlock для додавання блоку в пул. Якби було написано щось на зразок

То сторінка за принципом FIFO виявилася б розміченою «навпаки»:

Кілька блоків, що вимагаються з пулу поспіль, мали б спадні адреси. А процесор не любить ходити назад, від цього у нього ламається Prefetch (UPD: Не актуально для сучасних процесорів). Якщо ж робити розмітку у циклі

for (size_t i = PageSize-(BlockSize-(PageSize%BlockSize)); i != 0; i -= BlockSize) FreeBlock.

то цикл розмітки ходив за адресами назад.

Тепер, коли приготування зроблено, можна описати клас-домішка.

template class BlockAlloc < public: static void* operator new(size_ts) < if (s != sizeof(T)) < return ::operator new(s); >return pool.AllocBlock(); > static void operator delete (void * m, size_ts) < if (s! = sizeof (T)) < :: operator delete (m); >else if (m != NULL) < pool.FreeBlock(m); >> // todo: implement nothrow_t overloads, згідно з borisko' comment // http://habrahabr.ru/post/148657/#comment_5020297 // Avoid hiding placement new that's needed by the stl containers. static void* operator new(size_t, void* m) < return m; >//. and warning про missing placement delete. static void operator delete(void*, void*)< >private: static BlockPool pool; >; template BlockPool BlockAlloc::pool;

Поясню, навіщо потрібні перевірки if (s! = sizeof(T))
Коли вони спрацьовують? Тоді, коли створюється/видаляється клас, успадкований від базового T.
Спадкоємці будуть користуватися звичайними new/delete, але до них також можна додати BlockAlloc. Таким чином, ми легко та безпечно визначаємо, які класи мають користуватися пулами, не боячись зламати щось у програмі. Множинне успадкування також чудово працює з цією домішкою.

Готово. Наслідуємо Node від BlockAlloc і заново проводимо тест.
Час тесту тепер – 120 ms. Вп'ятеро швидше. Але в c # аллокатор все ж таки краще. Напевно, там не просто зв'язковий перелік. (Якщо відразу після new відразу викликати delete, і тим самим не витрачати багато пам'яті, вміщуючи дані в кеш, отримаємо 62 ms. Дивно. В точності, як у .NET CLR, ніби він повертає локальні змінні, що звільнилися, відразу у відповідний пул, не чекаючи GC)

2. Контейнер та його строкатий вміст

Чи часто трапляються класи, які зберігають у собі масу різних дочірніх об'єктів, таких, що час життя останніх не довший за час життя батька?

Наприклад, це може бути клас XmlDocument, наповнений класами Node та Attribute, а також c-рядками (char*), взятими з тексту всередині нод. Або список файлів і каталогів у файловому менеджері, що завантажуються один раз при перечитуванні каталогу і більше не змінюються.

Як було показано у вступі, delete обходиться дорожче, ніж new. Ідея другої частини статті полягає в тому, щоб пам'ять під дочірні об'єкти виділяти у великому блоці, пов'язаному з Parent-об'єктом. При видаленні parent-об'єкта у дочірніх будуть, як завжди, викликані деструктори, але пам'ять повертати не потрібно - вона звільнитися одним великим блоком.

Створимо клас PointerBumpAllocator, який вміє відкушувати від великого блоку шматки різних розмірів та виділяти новий великий блок, коли старий буде вичерпаний.

template class PointerBumpAllocator < public: PointerBumpAllocator() : free(0) < >void* AllocBlock(size_t block) < // todo: lock(this) block = align(block, Alignment); if (block > free) < free = align (block, PageSize); head = GetPage (free); >void* tmp = head; head = (char *) head + block; free -= block; return tmp; > ~PointerBumpAllocator() < for (vector::iterator i = pages.begin(); i != pages.end(); ++i) < VirtualFree(*i, 0, MEM_RELEASE); >> private: void* GetPage(size_t size) < void* page = VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE); pages.push_back(page); return page; >vector pages; void * head; size_t free; >; typedef PointerBumpAllocator<> DefaultAllocator;

Нарешті опишемо домішка ChildObject з перевантаженими new і delete, що звертаються до заданого аллокатора:

template struct ChildObject < static void* operator new(size_ts, A& allocator) < return allocator.AllocBlock(s); >static void* operator new(size_ts, A* allocator) < return allocator->AllocBlock(s); > static void operator delete(void*, size_t) < >// *1 static void operator delete(void*, A*) < >static void operator delete(void*, A&) < >private: static void* operator new( size_t s); >;

У цьому випадку крім додавання домішки до child-класу необхідно буде також виправити всі виклики new (або скористатися патерном «фабрика»). Синтаксис оператора new буде наступним:

new (… параметри для оператора… ) ChildObject (… параметри конструктора… )

Для зручності я поставив два оператори new, які приймають A& або A*.
Якщо аллокатор доданий до parent-класу як член, зручніше перший варіант:

node = new(allocator) XmlNode(nodename);

node = new(this) XmlNode(nodename);

Зрозуміло, що покажчик та посилання взаємно конвертуються, поділ цих випадків — позбавлення зайвих значків.

Для виклику delete не передбачено спеціального синтаксису, компілятор викличе стандартний delete (позначений *1), незалежно від того, який з операторів new був використаний для створення об'єкта. Тобто синтаксис delete звичайний:

Якщо ж у конструкторі ChildObject (або його спадкоємця) відбувається виняток, викликається delete з сигнатурою, що відповідає сигнатурі оператора new, використаному під час створення цього об'єкта (перший параметр size_t буде замінено на void*).

Розміщення оператора new у секції private захищає від виклику new без вказівки аллокатора.

Наведу закінчений приклад використання пари Allocator-ChildObject:

class XmlDocument : public DefaultAllocator < public: ~XmlDocument() < for (vector::iterator i = nodes.begin(); i != nodes.end(); ++i) < delete (*i); >> void AddNode (char * content, char * name) < char * c = (char *) AlllockBlock (strlen (content) + 1); strcpy(c, content); char* n = (char*)AllocBlock(strlen(name)+1); strcpy(n, content); nodes.push_back(new(this) XmlNode(c, n)); >class XmlNode : public ChildObject < public: XmlNode(char* _content, char* _name) : content(_content), name(_name) < >private: char* content; char * name; >; private: vector nodes; >;

Висновок. Стаття була написана 1.5 роки тому для пісочниці, але, на жаль, не сподобалася модератору.

Як правильно звільнити пам'ять зайняту елементами

І в кінці програми я хочу, щоб деструктор класу, який зберігає в собі vector видалив всі його елементи, і якщо чесно не виходить, може хтось підкаже?

class Order; class Company < public: Company(std::string name); < delete OrderVector[*it]; >> void makeOrder(const char* name, const float price); removeOrdersByProductName(const char* name); void fire(const char* name); :ostream&out, const Company&company); private: std::string name_;EmployeeList; EmployeeList employees_; vector OrderVector;

4 відповіді 4

delete OrderVector[*it];

не має сенсу. OrderVector - це ім'я типу.

Все можна зробити без будь-якого написання вручну циклу за допомогою стандартного алгоритму std::for_each та стандартного функціонального об'єкта std::default_delete.

Ось демонстраційна програма.

#include #include #include #include struct Order < ~Order() < std::cout >; vector OrderVector; () >; std::for_each( orders.begin(), orders.end(), std::default_delete() );

Її виведення на консоль

Order::~Order() Order::~Order() Order::~Order()

Якщо хочете використовувати цикл замість алгоритму, достатньо написати

for (auto order: orders) delete order;

#include #include struct Order < ~Order() < std::cout >; typedef std::vector OrderVector; for ( auto order : orders ) delete order;

Результат буде такий самий, що і для програми, наведеної вище.

Що стосується вашого власного циклу, то правильно його записати так:

for ( auto it = orders_.begin(); it != orders_.end(); ++it )

Зверніть увагу, що замість даного оголошення конструктора

Company(std::string name);

краще записати

Company( const std::string &name );

Також через те, що ви використовуєте вектор покажчиків, вам слід або заборонити копіювання об'єктів класу, як, наприклад, у визначенні класу записати

Company(const Company &) = delete; Company & operator = (const Company &) = delete;

Або визначити їх очевидно.

Company.h: In destructor 'virtual Company::~Company()': Company.h:26:13: error: 'default_delete' is not a member of 'std' std::default_delete(); ^ Company.h:26:38: error: expected primary-expression before ‘>’ token std::default_delete(); ^ Company.h:26:40: error: expected primary-expression before ‘)’ token std::default_delete();

@AntonBarinov Ви повинні включити заголовок , де визначено функціональний об'єкт std::default_delete, Якщо ваш компілятор не підтримує цей засіб, то використовуйте цикл for на основі діапазону. як я показав. У крайньому випадку можете використовувати виправлений цикл.:)

Якщо ви хочете, щоб при видаленні елементів автоматично виконувався їх деструктор, то вам потрібно або загорнути вказівники в "розумні покажчики", або зберігати у векторі не вказівники, а самі об'єкти.

Для першого варіанта можна (і потрібно!) використати std::shared_ptr . Однак у цьому випадку деструктор Order буде викликатися не обов'язково, коли видаляється вектор. Він буде викликатись коли вилучиться останній розумний покажчик на його об'єкт:

#include #include typedef std::shared_ptr OrderPtr ; typedef std::vector OrderVector; OrderVector orders_; void Company::makeOrder(const char* name, const float price) < // безпечно створюємо розумний покажчик auto new_order = std::make_shared(name, price); orders_.push_back(new_order); >

Другий варіант, деструктор вектора автоматично викличе деструктори для кожного елемента:

#include typedef std::vector OrderVector; OrderVector orders_; void Company::makeOrder(const char* name, const float price) < auto new_order = Order(name, price); orders_.push_back(new_order); >// краще так void Company::emplaceOrder(const char* name, const float price)