Как стать автором
Обновить

Управление памятью в C++

Время на прочтение 6 мин
Количество просмотров 147K
Работа с динамической памятью зачастую является узким местом во многих алгоритмах, если не применять специальные ухищрения.

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



0. А нужна ли нам ручная работа с памятью?


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

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

class Node {
public:
        Node* next;
};
// ...
for (int i = 0; i < 10000000; i++) {
        Node* v = new Node();
}


class Node
{
    public Node next;
}
// ...
for (int l = 0; l < 10000000; l++)
{
    var v = new Node();
}


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

1. Пул объектов


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

Поскольку стоит задача минимального вмешательства в программу, всё что можно будет сделать, это добавить примесь BlockAlloc к классу Node:
class Node : public BlockAlloc<Node>


Прежде всего нам понадобится пул больших блоков (страниц), которые забираем у ОС или C-runtime. Его можно организовать поверх функций malloc и free, но для большей эффективности (чтобы пропустить лишний уровень абстракции), используем VirtualAlloc/VirtualFree. Эти функции выделяют память блоками, кратными 4K, а также резервируют адресное пространство процесса блоками, кратными 64K. Одновременно указывая опции commit и reserve, мы перескакиваем ещё один уровень абстракции, резервируя адресное пространство и выделяя страницы памяти одним вызовом.

Класс PagePool
inline size_t align(size_t x, size_t a) { return ((x-1) | (a-1)) + 1; }
//#define align(x, a) ((((x)-1) | ((a)-1)) + 1)

template<size_t PageSize = 65536>
class PagePool
{
public:
        void* GetPage() {
                void* page = VirtualAlloc(NULL, PageSize, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
                pages.push_back(page);
                return page;
        }

        ~PagePool() {
                for (vector<void*>::iterator i = pages.begin(); i != pages.end(); ++i) {
                        VirtualFree(*i, 0, MEM_RELEASE);
                }
        }
private:
        vector<void*> pages;
};


Затем организуем пул блоков заданного размера

Класс BlockPool
template<class T, size_t PageSize = 65536, size_t Alignment = 8 /* sizeof(void*) */>
class BlockPool : PagePool<PageSize>
{
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 для добавления блока в пул. Если бы было написано что-то вроде

for (size_t i = 0; i < PageSize; i += BlockSize) FreeBlock((char*)tmp+i);


То страница по принципу FIFO оказалась бы размеченной «наоборот»:


Несколько блоков, затребованных из пула подряд, имели бы убывающие адреса. А процессор не любит ходить назад, от этого у него ломается Prefetch (UPD: Не актуально для современных процессоров). Если же делать разметку в цикле
for (size_t i = PageSize-(BlockSize-(PageSize%BlockSize)); i != 0; i -= BlockSize) FreeBlock...

то цикл разметки ходил бы по адресам назад.

Теперь, когда приготовления сделаны, можно описать класс-примесь.
template<class T>
class BlockAlloc
{
public:
        static void* operator new(size_t s) {
                if (s != sizeof(T)) {
                        return ::operator new(s);
                }
                return pool.AllocBlock();
        }
        static void operator delete(void* m, size_t s) {
                if (s != sizeof(T)) {
                        ::operator delete(m);
                } else if (m != NULL) {
                        pool.FreeBlock(m);
                }
        }

        // todo: implement nothrow_t overloads, according to 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 the warning about missing placement delete...
        static void operator delete(void*, void*) {
        }

private:
        static BlockPool<T> pool;
};
template<class T> BlockPool<T> BlockAlloc<T>::pool;


Объясню, зачем нужны проверки if (s != sizeof(T))
Когда они срабатывают? Тогда, когда создаётся/удаляется класс, отнаследованный от базового T.
Наследники будут пользоваться обычными new/delete, но к ним также можно примешать BlockAlloc. Таким образом, мы легко и безопасно определяем, какие классы должны пользоваться пулами, не боясь сломать что-то в программе. Множественное наследование также прекрасно работает с этой примесью.

Готово. Наследуем Node от BlockAlloc и заново проводим тест.
Время теста теперь — 120 ms. В 5 раз быстрее. Но в c# аллокатор всё же лучше. Наверное, там не просто связный список. (Если же сразу после new сразу вызывать delete, и тем самым не тратить много памяти, умещая данные в кеш, получим 62 ms. Странно. В точности, как у .NET CLR, как будто он возвращает освободившиеся локальные переменные сразу в соответствующий пул, не дожидаясь GC)

2. Контейнер и его пёстрое содержимое



Часто ли попадаются классы, которые хранят в себе массу различных дочерних объектов, таких, что время жизни последних не дольше времени жизни родителя?

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

Как было показано во введении, delete обходится дороже, чем new. Идея второй части статьи в том, чтобы память под дочерние объекты выделять в большом блоке, связанном с Parent-объектом. При удалении parent-объекта у дочерних будут, как обычно, вызваны деструкторы, но память возвращать не потребуется — она освободиться одним большим блоком.

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

Класс PointerBumpAllocator
template<size_t PageSize = 65536, size_t Alignment = 8 /* sizeof(void*) */>
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<void*>::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<void*> pages;
        void* head;
        size_t free;
};
typedef PointerBumpAllocator<> DefaultAllocator;


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

template<class T, class A = DefaultAllocator>
struct ChildObject
{
        static void* operator new(size_t s, A& allocator) {
                return allocator.AllocBlock(s);
        }
        static void* operator new(size_t s, 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 обычный:
delete node;


Если же в конструкторе ChildObject (или его наследника) происходит исключение, вызывается delete с сигнатурой, соответствующей сигнатуре оператора new, использованном при создании этого объекта (первый параметр size_t будет заменён на void*).

Размешение оператора new в секции private защищает от вызова new без указания аллокатора.

Приведу законченный пример использования пары Allocator-ChildObject:
Пример
class XmlDocument : public DefaultAllocator
{
public:
        ~XmlDocument() {
                for (vector<XmlNode*>::iterator i = nodes.begin(); i != nodes.end(); ++i) {
                        delete (*i);
                }
        }

        void AddNode(char* content, char* name) {
                char* c = (char*)AllocBlock(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<XmlNode, XmlDocument>
        {
        public:
                XmlNode(char* _content, char* _name) : content(_content), name(_name) { }
        private:
                char* content;
                char* name;
        };

private:
        vector<XmlNode*> nodes;
};


Заключение. Статья была написана 1.5 года назад для песочницы, но увы, не понравилась модератору.
Теги:
Хабы:
+54
Комментарии 53
Комментарии Комментарии 53

Публикации

Истории

Работа

QT разработчик
13 вакансий
Программист C++
121 вакансия

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн
PG Bootcamp 2024
Дата 16 апреля
Время 09:30 – 21:00
Место
Минск Онлайн
EvaConf 2024
Дата 16 апреля
Время 11:00 – 16:00
Место
Москва Онлайн