Скрытая информация

Многие менеджеры памяти выделяют несколько дополнительных байт в операторе new, чтобы при вызове оператора delete был использован правильный размер независимо от того, является деструктор виртуальным или нет.

void* Foo::operator new(size t bytes)

size t rea1 bytes = bytes + sizeof(size t);

unsigned char* space = (unsigned char*)::operator new(rea1 bytes); ((size t)space) = rea1 bytes; return space + sizeof(size t);

Теперь информацию о размере можно использовать в операторе delete или в любом другом месте, где вам захочется узнать настоящий размер. Тем не менее, при этой стратегии необходимо учесть ряд обстоятельств.

Лишние затраты

В зависимости от компилятора и операционной системы эта методика уже может использоваться незаметно для вас. Если вы самостоятельно добавите информацию о размере, она может продублировать уже хранящиеся сведения. Скорее всего, это произойдет при делегировании ::operator new на уровне объектов (см. выше). Такая методика приносит наибольшую пользу в сочетании с блочными схемами выделения памяти, она сокращает затраты ::operator new или calloc для блока, а не для отдельного объекта.

Оптимизация размера кванта

Большое преимущество этой методики заключается в том, что вы можете выделить больше места, чем было запрошено. Как это? Может ли принести пользу выделение лишней неиспользуемой памяти? На самом деле может, если подойти к этому разумно. Один из возможных вариантов - всегда выделять память с приращением в n байт, где минимальное значение n равно 4. При это повышается вероятность того, что после удаления 17-байтового объекта занимаемое им место удастся использовать, скажем, для 18- или 19-байтового объекта. Более изощренный подход состоит в выделении памяти по степеням 2, или, если вы относитесь к числу истинных гурманов управления памятью, - по числам Фибоначчи. Такие системы называются системами напарников (buddy systems), поскольку для каждого выделенного блока вы сможете найти его напарника (то есть другую половинку большого блока, из которого он был выделен) исключительно по размеру и начальному адресу. Появляется возможность эффективного воссоединения соседних освобожденных блоков. Если вы интересуетесь подобными вещами, в главе 16 рассматриваются основы системы напарников для степеней 2 в контексте автоматической сборки мусора.

Другая информация

Кроме размера блока может сохраняться и другая информация, например:

• адрес объекта класса для данного объекта;

• флаги блока (например, «флаг зомби», о котором будет рассказано ниже);

• статистическая информация - например, время создания объекта.

Списки свободных блоков

Упрощенный список свободных блоков, приведенный в предыдущей главе, может использоваться только для объектов постоянного размера. Например, он не будет нормально работать с производными классами, в которых добавляются новые переменные, поскольку они будут иметь другой размер. Сам список тоже ограничивался одним размером; для передачи оператору delete правильного размера требовались виртуальные деструкторы. Впрочем, создать более универсальные списки уже не так уж трудно.

Одно из несложных усовершенствований заключается в том, чтобы хранить в каждом узле списка не только адрес следующего указателя в списке, но и размер блока. Это позволит хранить в одном списке блоки разных размеров. При выделении памяти мы просматриваем список, пока не находим блок, размеры которого достаточны для наших целей. Для этого придется хранить скрытую информацию о размере блока даже после его выделения, чтобы при уничтожении объекта восстанавливать весь блок. Стратегия, прямо скажем, тупая и подходит разве что для очень маленьких списков, поскольку время поиска возрастает линейно с размером списка. Впрочем, она послужит отправной точкой для нашего обсуждения.

Более эффективное представление - коллекция списков свободной памяти, в которой каждый список представляет блоки определенного размера. Ниже показана урощенная, но полезная реализация.

class MemManager { private:

struct FreeList { Список с блоками определенного размера FreeList* next; Следующий FreeList

void* top of 1ist; Верх текущего списка size t chunk size; Размер каждого свободного блока FreeList(FreeList* successor, size t size) : next(successor), top of 1ist(NULL), chunk size(size) {}

FreeList* a11 1ists; Список всех FreeList public:

MemManager() : a11 1ists(NULL) {}

void* Al1ocate(size t bytes);

void Dea11ocate(void* space, size t bytes);

void* MemManager::Al1ocate(size t bytes)

for (FreeList* f1 = a11 1ists;

f1 != NULL && f1->chunk size != bytes; f1 = f1->next)

if (f1->top of 1ist != NULL) {

void* space = f1->top of 1ist;

f1->top of 1ist = *((void**)(f1->top of 1ist));

return space;

return ::operator new(bytes); Пустой список

return ::operator new(bytes); Такого списка нет

void MemManager::Dea11ocate(void* space, size t bytes)

FreeList* f1 = NULL;

for (f1 = a11 1ists; f1 != NULL; f1 = f1->next)

if (f1->chunk size == bytes) break; if (f1 == NULL) Списка для такого размера нет

f1 = new FreeList(a11 1ists, bytes); a11 1ists = f1;

*((void**)space) = f1->top of 1ist; f1->top of 1ist = space;

Функции Al1ocate() и Dea11ocate() вызываются из перегруженных операторов new и delete соответственно. Такой подход предельно упрощен, но работает он неплохо. Вы можете воспользоваться им для любого сочетания классов, и он будет работать с производными классами, в которых добавились новые переменные. Он также может использоваться в схеме управления памятью на базе ведущих указателей. Существуют многочисленные усовершенствования, которые можно внести в показанную основу:

• Ограничить размеры блоков числами, кратными некоторому числу байт, степенями 2 или числами Фибоначчи.

• Воспользоваться более эффективной структурой данных, чем связанный список списков - возможно, бинарным деревом или даже массивом, если диапазон размеров невелик.

• Предоставить функцию Flush(), которая при нехватке памяти удаляет все содержимое списков.

• В функции Al1ocate() при отсутствии в списке свободного места заданного размера выделить память под массив блоков этого размера вместо одного блока.

Подсчет ссылок

Подсчет ссылок основан на простой идее - мы следим за количеством указателей, ссылающихся на объект. Когда счетчик становится равным 0, объект удаляется. Звучит просто, не правда ли? В определенных условиях все действительно просто, но подсчет ссылок обладает довольно жесткими ограничениями, которые снижают его практическую ценность.

Базовый класс с подсчетом ссылок

Начнем с абстрактного базового класса, от которого можно создать производный класс с подсчетом ссылок. Базовый класс содержит переменную, в которой хранится количество вызовов функции Grab() за вычетом количества вызовов функции Re1ease().

class RefCount { private:

unsigned long count; Счетчик ссылок public:

RefCount() : count(0) {} RefCount(const RefCount&) : count(0) {} RefCount& operator=(const RefCount&)

{ return *this; } Не изменяет счетчик virtual ~RefCount() {} Заготовка void Grab() { count++; } void Re1ease()

if (count > 0) count -- ;

if (count == 0) delete this;

Пока клиентский код правильно вызывает функции Grab() и Re1ease(), все работает абсолютно надежно. Каждый раз, когда клиент получает или копирует адрес объекта, производного от RefCount, он вызывает Grab(). Когда клиент гарантирует, что адрес больше не используется, он вызывает Re1ease(). Если счетчик падает до 0 - бац! Нет больше объекта!