считаться "небольшими". Объект класса SmallObjAllocator переадресовывает запросы на выделение блоков, размер которых превышает величину maxobjectsize, непосредственно оператору ::operator new.

Довольно необычно, что функция Deallocate получает размер объекта, подлежа-шего удалению, в качестве аргумента. Дело в том, что это позволяет ускорить процесс освобождения памяти. В противном случае функция SmallObjAllocator: : Deal locate должна была бы искать среди всех объектов класса FixedAllocator тот, которому принадлежит данный указатель. Это слишком затратная процедура, поэтому объекту класса SmallObjAllocator нужно передавать размер удаляемого блока. Как мы увидим в следуюшей главе, эта задача изяшно решается самим компилятором.

Какое отображение сушествует между размером блока в объекте FixedAllocator и вектором роо1 ? Иными словами, как по заданному размеру отыскать соответствую-ший объект класса FixedAllocator, который выполняет распределение памяти и ее освобождение?

Простая и эффективная идея заключается в том, чтобы элемент pool [i] обрабатывал объекты размера i. Вектор роо1 инициализируется с размером maxobjectsize, а затем инициализируются все объекты класса FixedAllocator, содержащиеся в нем. Если поступает запрос на выделение памяти размером numBytes, объект класса SmallObjAllocator передает его либо элементу pool [numBytes] (эта операция имеет постоянное время выполнения), либо оператору : :operator new.

Однако это решение не настолько удачное, как кажется на первый взгляд. В конкретных ситуациях нам могут понадобиться распределители памяти только одного определенного размера, например 4 байт, и никакие другие объекты не нужны. В этом случае придется распределять память для 64 и большего количества элементов вектора роо1 , хотя на самом деле используются только два элемента.

Выравнивание размеров и заполнение пустот еше больше снижают эффективное использование памяти. Например, многие компиляторы дополняют все типы, определенные пользователем, до размера, кратного заданному числу (2, 4 и т.д.). Например, если компилятор дополняет все структуры до размера, кратного 4, то используется только 25% элементов вектора роо1 , остальные представляют собой балласт.

Намного лучше пожертвовать скоростью просмотра, но сэкономить память. Мы будем хранить объекты класса FixedAllocator только для тех размеров памяти, которые требуются хотя бы один раз. Таким образом, вектор роо1 может содержать много объектов разного размера, не слишком увеличиваясь. Для того чтобы ускорить просмотр, вектор роо1 хранится отсортированным по размерам блоков.

Кроме того, ускорить просмотр можно с помошью стратегии, которая уже применялась в классе FixedAllocator. Объект класса SmallObjAllocator хранит указатель на последний объект класса FixedAllocator, использованный при освобождении памяти. Ниже приведен полный список переменных-членов класса SmallAllocator.

class SmallObjAllocator {

private:

std::vector<FixedAllocator> pool ; FixedAllocator* pLastAlloc ;

Фактически в современных системах экономия памяти ведет к ускорению работы. Это происходит благодаря огромной разнице между скоростью работы основной памяти (большой и медленной) и кэш-памяти (маленькой и быстрой).

FixedAllocator* pLastDealloc ;

При поступлении запроса на выделение памяти сначала проверяется указатель pLastAnoc . Если его размер не соответствует ожидаемому, функция SmaliObjAllocator: :Allocate выполняет бинарный поиск в массиве роо1 . Освобождение памяти осуществляется примерно так же. Единственное отличие заключается в том, что функция SmaliObjAllocator: :а1 locate может закончить свою работу, вставив в массив роо1 новый объект класса FixedAllocator.

Как уже отмечалось при обсуждении класса FixedAllocator, эта простая схема кэширования предназначена для многократного создания и удаления объектов за постоянное время.

4.7. Трюк

На последнем уровне нашей архитектуры расположен класс Small Object, базовый класс, инкапсулирующий функциональные возможности, предоставленные классом SmaliObjAllocator.

Класс SmallObject перефужает операторы new и delete. Таким образом, при создании объекта класса, производного от класса SmallObject, в действие вступает перегрузка, направляющая запрос объекту класса FixedAllocator.

Определение класса SmallObject довольно простое, но интересное.

class SmallObject {

public:

static void* operator new(std::si2e t size);

static void operator delete(void* p, std::size t size);

virtual -SmallobjectO {}

Класс SmallObject выглядит вполне нормально, за исключением одной маленькой детали. Во многих книгах, посвященных языку С++, например, в учебнике Sutter (2000), говорится, что при перефузке оператора delete его единственным аргументом должен быть указатель типа void.

В языке С++ есть одна лазейка, которая нас очень интересует. (Напомним, что мы разработали класс SmaliObjAllocator так, чтобы размер освобождаемого блока передавался как аргумент.) В стандартном варианте оператор delete можно перефузить двумя способами. Первый из них выглядит так.

void operator delete(void* р); Второй способ таков.

void operator delete(void* р, std::size t size);

Эта тема очень подробно изложена в книге Sutter (2000).

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

Как заставить компилятор автоматически определять размер блока? На первый взгляд кажется, что для этого понадобится дополнительная память для каждого объекта, хотя именно этого мы и стремились избежать.

Однако на самом деле никакой дополнительной памяти не требуется. Рассмотрим следующий код.

class Base {

int a [100]; public:

virtual ~BaseC) {}

class Derived : public Base {

int b [200]; public:

virtual ~Derived() {}

Base* p = new Derived; delete p;

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

1. Деструктору передается булевский признак: "Вызывать/не вызывать оператор delete после разрушения объекта". Деструктор класса Base виртуален, поэтому в нашем примере оператор delete р относится к правильному объекту класса Derived. В этом случае размер объекта известен уже на этапе компиляции - он равен sizeof (Derived) - и компилятор просто передает эту константу оператору delete.

2. Деструктор возврашает размер объекта. Мы можем сделать так (ведь мы сами написали компилятор, не правда ли?), чтобы каждый деструктор после разрушения объекта возвращал величину sizeof (Class). Эта схема также вполне работоспособна, поскольку деструктор класса Base виртуален. После его вызова система поддержки выполнения программ вызовет оператор delete, передавая ему результат работы деструктора.

3. Реализуется скрытая виртуальная функция-член, получающая размер объекта в качестве аргумента. Назовем ее Size(), например. В этом случае система поддержки выполнения программ вызовет эту функцию, сохранит результат ее работы, уничтожит объект и вызовет оператор delete. Такая реализация может показаться неэффективной, но ее преимущество заключается в том, что компилятор может использовать функцию 5ize() и для других целей.

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

(Окончен бал, погасли свечи, и мы из разработчиков компилятора разжалованы в рядовые программисты.) Как видим, для того чтобы передать оператору delete правильный размер блока, компръаятор должен выполнить довольно много работы. Зачем же нам терять эту информацию и выполнять при каждом удалении объекта поиск, расходуя время?

Ведь все так хорошо складывается! Объекту класса Smal 1а1 locator нужен размер удаляемого блока. Компилятор передает ему этот размер, а объект класса SmallObject переадресовывает его объекту класса FixedAllocator.