Работа с динамической памятью зачастую является узким местом во многих алгоритмах, если не применять специальные ухищрения.
В статье я рассмотрю парочку таких техник. Примеры в статье отличаются (например, от этого) тем, что используется перегрузка операторов new и delete и за счёт этого синтаксические конструкции будут минималистичными, а переделка программы — простой. Также описаны подводные камни, найденные в процессе (конечно, гуру, читавшие стандарт от корки до корки, не удивятся).
В первую очередь проверим, насколько умный аллокатор может ускорить работу с памятью.
Напишем простые тесты для C++ и C# (C# известен прекрасным менеджером памяти, который делит объекты по поколениям, использует разные пулы для объектов разных размеров и т.п.).
Несмотря на всю «сферично-вакуумность» примера, разница по времени получилась в 10 раз (62 ms против 650 ms). Кроме того, c#-пример закончен, а по правилам хорошего тона в c++ выделенные объекты надо удалить, что ещё больше увеличит отрыв (до 2580 ms).
Очевидное решение — забрать у ОС большой блок памяти и разбить его на равные блоки размера sizeof(Node), при выделении памяти брать блок из пула, при освобождении — возвращать в пул. Пул проще всего организовать с помощью односвязного списка (стека).
Поскольку стоит задача минимального вмешательства в программу, всё что можно будет сделать, это добавить примесь BlockAlloc к классу Node:
Прежде всего нам понадобится пул больших блоков (страниц), которые забираем у ОС или C-runtime. Его можно организовать поверх функций malloc и free, но для большей эффективности (чтобы пропустить лишний уровень абстракции), используем VirtualAlloc/VirtualFree. Эти функции выделяют память блоками, кратными 4K, а также резервируют адресное пространство процесса блоками, кратными 64K. Одновременно указывая опции commit и reserve, мы перескакиваем ещё один уровень абстракции, резервируя адресное пространство и выделяя страницы памяти одним вызовом.
Затем организуем пул блоков заданного размера
Комментарием // todo: lock(this) помечены места, которые требуют межпоточной синхронизации (например, используйте EnterCriticalSection или boost::mutex).
Объясню, почему при «форматировании» страницы не ипользуется абстракция FreeBlock для добавления блока в пул. Если бы было написано что-то вроде
То страница по принципу FIFO оказалась бы размеченной «наоборот»:
Несколько блоков, затребованных из пула подряд, имели бы убывающие адреса. А процессор не любит ходить назад, от этого у него ломается Prefetch (UPD: Не актуально для современных процессоров). Если же делать разметку в цикле
то цикл разметки ходил бы по адресам назад.
Теперь, когда приготовления сделаны, можно описать класс-примесь.
Объясню, зачем нужны проверки if (s != sizeof(T))
Когда они срабатывают? Тогда, когда создаётся/удаляется класс, отнаследованный от базового T.
Наследники будут пользоваться обычными new/delete, но к ним также можно примешать BlockAlloc. Таким образом, мы легко и безопасно определяем, какие классы должны пользоваться пулами, не боясь сломать что-то в программе. Множественное наследование также прекрасно работает с этой примесью.
Готово. Наследуем Node от BlockAlloc и заново проводим тест.
Время теста теперь — 120 ms. В 5 раз быстрее. Но в c# аллокатор всё же лучше. Наверное, там не просто связный список. (Если же сразу после new сразу вызывать delete, и тем самым не тратить много памяти, умещая данные в кеш, получим 62 ms. Странно. В точности, как у .NET CLR, как будто он возвращает освободившиеся локальные переменные сразу в соответствующий пул, не дожидаясь GC)
Часто ли попадаются классы, которые хранят в себе массу различных дочерних объектов, таких, что время жизни последних не дольше времени жизни родителя?
Например, это может быть класс XmlDocument, наполненный классами Node и Attribute, а также c-строками (char*), взятыми из текста внутри нод. Или список файлов и каталогов в файловом менеджере, загружаемых один раз при перечитывании каталога и больше не меняющихся.
Как было показано во введении, delete обходится дороже, чем new. Идея второй части статьи в том, чтобы память под дочерние объекты выделять в большом блоке, связанном с Parent-объектом. При удалении parent-объекта у дочерних будут, как обычно, вызваны деструкторы, но память возвращать не потребуется — она освободиться одним большим блоком.
Создадим класс PointerBumpAllocator, который умеет откусывать от большого блока куски разных размеров и выделять новый большой блок, когда старый будет исчерпан.
Наконец, опишем примесь ChildObject с перегруженными new и delete, обращающимися к заданному аллокатору:
В этом случае кроме добавления примеси в child-класс необходимо будет также исправить все вызовы new (или воспользоваться паттерном «фабрика»). Синтаксис оператора new будет следующим:
new (… параметры для оператора… ) ChildObject (… параметры конструктора… )
Для удобства я задал два оператора new, принимающих A& или A*.
Если аллокатор добавлен в parent-класс как член, удобнее первый вариант:
Если аллокатор добавлен как предок (примесь), удобнее второй:
Понятно, что указатель и ссылка взаимно конвертируются, разделение этих случаев — избавления от лишних значков.
Для вызова delete не предусмотрен специальный синтаксис, компилятор вызовет стандартный delete (отмеченный *1), независимо от того, какой из операторов new был использован для создания объекта. То есть, синтаксис delete обычный:
Если же в конструкторе ChildObject (или его наследника) происходит исключение, вызывается delete с сигнатурой, соответствующей сигнатуре оператора new, использованном при создании этого объекта (первый параметр size_t будет заменён на void*).
Размешение оператора new в секции private защищает от вызова new без указания аллокатора.
Приведу законченный пример использования пары Allocator-ChildObject:
Заключение. Статья была написана 1.5 года назад для песочницы, но увы, не понравилась модератору.
В статье я рассмотрю парочку таких техник. Примеры в статье отличаются (например, от этого) тем, что используется перегрузка операторов 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 года назад для песочницы, но увы, не понравилась модератору.
