break;

assertCanocchunk != 0); assertCanocchunk ->blocksAvailable > 0); return аПоссИипк ->АПocateCblocksize ) ;

Придерживаясь этой стратегии, класс FixedAllocator удовлетворяет большинство запросов за одно и то же время. При этом могут возникать некоторые задержки, обусловленные поиском и добавлением новых блоков. Иногда эта схема может работать неэффективно. Однако на практике такие случаи встречаются редко. Не забывайте, что у каждого механизма распределения памяти есть своя ахиллесова пята.

Освобождение памяти - более сложная задача, поскольку определенная часть информации отсутствует. У нас есть лишь указатель на освобождаемую область памяти, и нам неизвестно, какому именно объекту типа chunk он принадлежит. Мы можем просмотреть содержимое вектора chunks , проверяя, лежит ли данный указатель в диапазоне от pData до pData + blockSize * numBlocks . Если да, то указатель следует передать функции-члену Deallocate соответствующего объекта класса chunk. Очевидно, что этот поиск требует затрат времени. Несмотря на то что операция выделения памяти выполняется быстро, процедура удаления занимает линейное время. Итак, нужно как-то ускорить этот процесс.

Для этого можно применить вспомогательный кэш (cache memory). Когда пользователь освобождает блок, используя вызов FixedAllocator::Deal 1 ocate(р), объект класса FixedAllocator не передает указатель р обратно соответствующему объекту класса Chunk, а записывает указатель р во внутреннюю память - кэш, в котором хранятся свободные блоки. При поступлении нового запроса объект класса FixedAllocator сначала просматривает кэш. Если он не пуст, объект извлекает из кэша последний доступный указатель и немедленно возвращает его обратно. Это очень быстрая операция. Только когда кэш опустошен, объект класса FixedAllocator вынужден выполнить стандартную процедуру распределения памяти для объекта класса chunk. Эта многообещающая стратегия в некоторых достаточно распространенных случаях работает плохо.

При распределении памяти для небольших объектов возможны такие ситуации.

• Распределение памяти для большого массива данных. В памяти одновременно размешается большое количество мелких объектов. Это происходит, например, при инициализации набора указателей на маленькие объекты.

• Удаление в том же порядке. Большое количество мелких объектов удаляется в том же порядке, в котором они были размещены в памяти. Это происходит при разрушении большинства контейнеров из стандартной библиотеки шаблонов STL.

• Удаление в обратном порядке. Большое количество небольших объектов удаляется в порядке, обратном порядку их размещения в памяти. Для профамм, напи-

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

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

• Произвольное размещение и удаление. Объекты создаются и удаляются без определенного порядка. Это происходит, когда при выполнении программы время от времени возникает необходимость в небольших объектах.

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

Лучше всего применять стратегию удаления объектов, совпадающую со стратегией их размещения в памяти. Переменная-член FixedAnocator: :deanocChunk указывает на последний объект класса chunk, который был использован для удаления из памяти. Как только поступает запрос на удаление, эта переменная проверяется первой. Затем, если она ссылается на неверный объект типа Chunk, функция Deallocate начинает линейный поиск, обнаруживает требуемый объект и обновляет переменную deallocChunk .

Есть два важных приема, позволяющих ускорить работу функции Deallocate в указанных выше ситуациях. Во-первых, функция Deallocate выполняет поиск подходящего объекта класса chunk, начиная с окрестности указателя deanocChunk . Это значит, что вектор chunks просматривается, начиная с переменной deanocChunk , а следующими проверяются итераторы, находящиеся выше и ниже. Это значительно повышает скорость удаления большого массива данных при любом порядке удаления (прямом или обратном). Во время размещения большого массива данных функция Allocate добавляет объекты класса Chunk по порядку. Во время удаления либо указатель deal locChunk сразу попадает в точку, либо правильный объект будет обнаружен на следующем шаге.

Во втором трюке следует избегать крайних вариантов. Допустим, оба указателя al-locChunk и deallocChunk ссылаются на последний объект в векторе, и свободного места в этом множестве не осталось. Представьте, что произойдет, если будет выполняться следующий код.

for (...)

некоторые интеллектуальные указатели используют свой механизм распределения памяти для небольших объектов (глава 7) SmartPtr р;

... используется указатель р ...

При каждом проходе цикла создается и уничтожается объект класса SmartPtr. При создании объекта, поскольку памяти больше нет, функция FixedAllocator: :Anocate создает новый объект класса chunk и заносит его в вектор chunks . При разрушении объекта функция FixedAllocator: :Deallocate обнаруживает пус-

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

той блок и освобождает его. Эти затратные процедуры повторяются на каждой итерации цикла for.

Такая неэффективная работа недопустима. Следовательно, во время удаления объект класса Chunk должен освобождаться, только если есть два пустых объекта этого класса. При наличии только одного пустого участка он быстро перемешается в конец вектора chunks . Таким образом мы избегаем выполнения затратных операций vec-tor<Chunk>:: erase, всегда удаляя лишь последний элемент.

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

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

Итак, у нас есть класс FixedAllocator, достаточно эффективно удовлетворяющий запросы на распределение памяти фиксированного размера как с точки зрения затрачиваемого времени, так и с точки зрения использования памяти. Класс FixedAllocator оптимизирован для работы с небольшими объектами.

4.6. Класс SmaliObjAllocator

Третий уровень нашей архитектуры механизма распределения памяти состоит из класса SmanobjAllocator, позволяющего размещать в памяти объекты любого размера, объединяя в одно целое несколько объектов класса FixedAllocator. Получив запрос на распределение памяти, объект класса small Obj Allocator либо переадресует его наиболее подходящему объекту класса FixedAllocator, либо передаст его оператору ::operator new.

Ниже приведено краткое описание класса SmaliObjAllocator. Объяснения даются после кода.

class SmaliObjAllocator

public:

SmallobjAllocatorC

std::size t chunksize,

std::size t maxobjectsize); void* Allocate(std::size t numBytes); void Deal1ocate(void* p, std::size t size);

private:

std::vector<FixedAl1ocator> poo1 ;

Конструктор получает два параметра, определяющих конфигурацию объекта класса SmaliObjAllocator. Параметр Size задает размер участка памяти, принятый по умолчанию (длина каждого объекта класса chunk, выраженная в байтах), а параметр maxobjectsize задает максимально возможный размер объектов, которые еще могут