Работа с динамической памятью зачастую является узким местом во многих алгоритмах, если не применять специальные ухищрения.
В статье я рассмотрю парочку таких техник. Примеры в статье отличаются (например, от этого) тем, что используется перегрузка операторов 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, мы перескакиваем ещё один уровень абстракции, резервируя адресное пространство и выделяя страницы памяти одним вызовом.
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;
};Затем организуем пул блоков заданного размера
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 оказалась бы размеченной «наоборот»:
Несколько блоков, затребованных из пула подряд, имели бы убывающие адреса. А процессор не любит ходить назад, от этого у него ломается 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, который умеет откусывать от большого блока куски разных размеров и выделять новый большой блок, когда старый будет исчерпан.
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 года назад для песочницы, но увы, не понравилась модератору.
Автор: qw1
