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

в 18:08, , рубрики: c++, memory management, Программирование, системное программирование, метки:

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

В статье я рассмотрю парочку таких техник. Примеры в статье отличаются (например, от этого) тем, что используется перегрузка операторов 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<typename T, size_t PageSize = 65536, size_t Alignment = 8 /* sizeof(void*) */>
class BlockPool : PagePool<PageSize>
{
public:
        BlockPool() : head(NULL), BlockSize(align(sizeof(T), Alignment)) { }

        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;

        void FormatNewPage() {
                size_t count = PageSize / BlockSize;
                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;
        }
};

Переменные BlockSize и count можно вычислить во время компиляции и оформить в виде static const, но победить компилятор у меня не получилось.

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

Объясню, почему я не воспользовался абстракцией FreeBlock для добавления блока в пул.
Если бы я написал что-то вроде

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

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

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

Теперь, когда приготовления сделаны, можно описать класс-примесь.

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);
                }
        }

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

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

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

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

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

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

Класс DataPool

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

        DataPool() : free(0) { }

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

        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;
        }

private:
        vector<void*> pages;
        void* head;
        size_t free;
};
typedef DataPool<> DefaultDataPool;

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

template<class T, class P = DefaultDataPool>
struct ChildObject {
        static void* operator new(size_t s, P& pool) {
                return pool.AllocBlock(s);
        }
        static void* operator new(size_t s, P* pool) {
                return pool->AllocBlock(s);
        }

        static void operator delete(void*, P*) { }
        static void operator delete(void*, P&) { }
        static void operator delete(void*, size_t) { }
private:
        static void* operator new(size_t s);
};

В этом случае кроме добавления примеси в child-класс необходимо будет также исправить все вызовы new (или воспользоваться паттерном «фабрика»). Синтаксис оператора new будет следующим:

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

Для удобства я задал два оператора new, принимающих P& или P*.
Если DataPool добавлен в объект как член класса-контейнера, удобнее первый вариант:

xmlNode = new(pool) XmlNode(nodename);

Если DataPool добавлен как предок, удобнее второй:

xmlNode = new(this) XmlNode(nodename);

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

Для вызова delete не нужно специального синтаксиса, компилятор сам вызовет delete с той же сигнатурой, что и new, при обычном синтаксисе

delete xmlNode;

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

Вопрос знатокам: зачем я добавил третий оператор delete? (ответ в конце статьи)

Приведу законченный пример использования этой пары:

Пример

class XmlDocument : public DefaultDataPool
{
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 года назад для песочницы, но увы, не понравилась модератору.

А теперь ответ на заковыристый вопрос

Этот оператор delete вызывается, если в конструкторе ChildObject (или его наследника) происходит исключение. Безжалостный c++, зачем мне попадать в метод, если я не смогу вернуть память, потому что в параметре нет ссылки на пул?

Автор: qw1

* - обязательные к заполнению поля