Класс VoidPtrPool идентичен тому, который использовался в алгоритме Бейкера, с добавлением связанного списка активных VoidPtr.

Итератор ведущих указателей

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

class VoidPtrPoollterator : public VoidPtrlterator { private:

VoidPtr* next; public:

VoidPtrIterator(VoidPtr* first) : next(first) {} virtual bool More() { return next != NULL; } virtual VoidPtr* Next()

VoidPtr* vp = next; next = next->next; return vp;

VoidPtrIterator* VoidPtrPoo1::iterator()

return new VoidPtrPoolIterator(&head.next);

Алгоритм уплотнения

Алгоритм уплотнения выглядит так просто, что его можно было бы и не приводить. class Space { private:

unsigned long next byte;

unsigned char bytes[SPACESIZE]; public:

Space() : next byte(0) {}

void* Al1ocate(size t size);

void Compact();

void* Space::Al1ocate(size t size)

Выровнять на границу слова

size = ROUNDUP(size);

if (next byte + size > SPACESIZE)

Compact();

if (next byte + size > SPACESIZE)

Исключение - нехватка памяти

void* space = &bytes[next byte]; next byte += size; return space;

void Space::Compact()

next byte = 0;

VoidPtrIterator* iterator = VoidPtrPoo1::iterator(); while (iterator->More())

VoidPtr* vp = iterator->Next(); void* space = Al1ocate(vp->size);

if (space < vp->address) Проверить, что объект поместится

delete iterator;

Оптимизация

Существует много возможностей повысить эффективность этой схемы для рядовых классов. Один из простейших видов оптимизации - хранение нижнего уровня, который определяет самый нижний удаленный объект. Нижний уровень представляет собой самый нижний VoidPtr из активного списка, ниже которого удаленных объектов нет. Он хранится в виде переменной класса VoidPtr* вместе с началом и концом списка. Деструктор VoidPtr проверяет, находится ли адрес указываемого объекта ниже текущего нижнего уровня; если да, он заменяет нижний уровень новым значением. Уплотнение начинается с нижнего уровня, поскольку ниже него перемещать ничего не требуется. Иначе говоря, мы начинаем не с начала списка, а где-то с середины - с нижнего уровня.

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

Другой прием оптимизации - объединять несколько смежных объектов в одной операции перемещения. Экономия не так уж велика, но несколько тактов все же удается сэкономить.

Последовательное уплотнение на месте

Алгоритм уплотнения на месте нетрудно приспособить для условий последовательного уплотнения в фоновом режиме. Все просто: мы сохраняем VoidPtrIterator в виде переменной класса Space и используем его, чтобы смещать вниз один объект при каждом вызове функции Copy1(). Реализация проста и прямолинейна, необходимо лишь соблюдать осторожность с удалением во время уплотнения. Помните, что в процессе перебора списка VoidPtr удаляется один из его элементов. Это простой частный случай проблемы надежности итераторов, которую мы обсуждали в главе 8.

Все, что говорилось об алгоритме Бейкера в контексте внешних объектов, в равной степени относится и к уплотнению на месте. Адреса, на которые ссылаются VoidPtr, следует проверять по интервалам адресов в пространстве уплотнения, и объекты могут свободно перемещаться из пространства памяти и в него.

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

Перспективы

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

В следующей главе мы вернемся к стратегии «дескрипторов повсюду». Конечно, организовать универсально уплотнение памятью для производных коммерческих классов невозможно. Но по крайней мере вы увидите, как далеко можно зайти в С++, прежде чем поднять руки, сведенные судорогой от долгого сидения за клавиатурой.