А. Александреску - Современное проектирование на C++ (1119444), страница 25
Текст из файла (страница 25)
Если бы в классе сЬипк была предусмотрена переменная- шен Ыос~ьзхе, это было бы пустой тратой времени и памяти. Не забывайте, что мы находимся на самом дне структуры — здесь все имеет значение. По соображениям эффективности в классе СЬипк не определены ни конструкторы, ни деструктор, ни оператор присваивания.
Попытка определить семантику копирования на этом уровне снизила бы эффективность работы верхних уровней структуры, на которых объекты класса СЬипк хранятся внутри векторов. Структура СЬипк демонстрирует важные ограничения. Поскольку переменные Ыоскзлиаз1аЫе и Нгзтлчаз1аЫев1ос1~ имеют тип ипззйпед сЬаг, порция не может содержать больше 255 блоков (на компьютерах, где символы состоят из 8 бит).
Как мы вскоре убедимся, это решение вполне удачно и позволяет избежать многих неприятностей. Перейдем теперь к более интересной теме. Блок может быль занят или свободен. Все, что необходимо сохранить, записывается в свободные блоки. В первом байте свободного блока хранится индекс следуюшего свободного блока. Поскольку первый доступный индекс хранится в переменной тзгзтяча11аЫев1осК, мы получаем полноценный одно- связный список свободных блоков, не используя дополнительной памяти.
В момент инициализации объект класса сЬипк выглядит, как показано на рис. 4.4. Код его инициализации приведен ниже. ио14 сЬипк::тпзт(зто::ззхе т Ыоскьзхе, ипззйпед сЬаг Ыоскз) ( рпата =пеи ипзздпед сЬаг[Ыоскь(хе * Ыосйз]; Н гзтяиаз!аЫев1осй = О; Ыосйзяча)1аЫе = Ыосйз; ипМйпеб сЬаг 5 = О; ипззйпеб сЬаг" р = Рцата гог (; 1 != ЫосЬз; р += Ыоск5зхе) ( ~-~ 1; Этот односвязный список, встроенный в структуру данных, представляет собой большое достижение.
Он позволяет быстро и эффективно находить свободный блок внутри порции без дополнительных затрат памяти, причем на размешение и удаление блока тратится постоянное время, что исключительно важно. Часть Ь Методы 104 Рис. 4.4. Обьект класса Сйиай, состоящий из 255 блоков ио 4 блока каждый Посмотрим теперь, почему количество блоков ограничено величиной, соответствующей максимальному значению переменной типа ипзздпеб сваг. Допустим, что мы используем переменную более широкого типа, например цпзздпеб з1зогт, которая на многих компьютерах занимает 2 байт.
В этом случае перел нами возникают две проблемы — большая и маленькая. ° Мы не можем размещать блоки, размер которых меньше величины збаеоФ(ипз1дпеб зпогс), что очень неудобно, поскольку мы разрабатываем механизм распределения памяти для небольших объектов. Это маленькая проблема. ° Мы сталкиваемся с вопросами выравнивания участков памяти. Вообразите, что мы создали механизм распределения для 5-байтовых блоков. В этом случае приведение указателя, ссылающегося на 5-байтовый блок, к типу ипзбдпеб 1пт приведет к непредсказуемым последствиям. Это большая проблема.
Решить эти проблемы довольно просто — нужно использовать тип ипз1дпеб спаг в качестве типа для "тайного индекса" ("ззеа1Ф )пбех'*). Символьный тип по определению имеет размер, равный 1 байт, поэтому никаких проблем, связанных с выравниванием участков памяти не возникает, поскольку даже указатель на отдельную ячейку памяти ссылается на переменную типа ипз1дпеб сйаг. Это приводит к ограничению максимального количества блоков в объекте класса Спмпк, поскольку в нем не может быть больше, чем ОНСНД МЛХ блоков (в большинстве систем эта величина равна 255).
Это вполне приемлемо, даже если размер блока действительно мал, например, от 1 до 4 байт. Это относится и к более крупным блокам, поскольку в любом случае объекты класса спмпк по определению должны быть маленькими. Функпия распределения памяти извлекает блок, на который ссылается переменная Нгзтдча41аЫев1оск и устанавливает ее на следующий свободный блок — типичная операпия над списками. чодб= с1зипк:сд11осате(зсб::ззхе т Ыоскв1хе) тФ (!Ыоскздча11аЫе ) гегигп 0; ипзз'дпеб сваг ряези1с = роаса + (Нгзсдчаз1аЫев1оск * Ыоскя1ге); // присвоение переменной Н гзсдча11аЫев1оск // указателя на следующий свободный блок Н гзсдча11аЫев1оск = *ряеьм1т; --Ы оскздча11аЫ е 105 Глава 4.
Размещение в памяти небольших обьектов гетцгп ркевц1т ) Итак, функция Спцпк::л11осате состоит из одной операции сравнения, одной операции доступа по индексу, двух операций вычитания, присваивания и оператора декрементации — вполне приемлемо. Еше более важно то, что в этой функции не выполняется операция поиска. На рис.
4.5 показано состояние объекта класса спцпк после выполнения первой операции распределения памяти. Рис. 4.5. Сттояние ооьекта класса Сйипя после емполнения период операции распределения памяти. Занятая память еыделена серылс цестом Функция освобождения памяти работает в точности наоборот. Она возврашает блок в список свободных блоков и увеличивает значение переменной Ыосйвлча11- аЫе . Не забудьте о необходимости передавать размер блока в качестве параметра функции оеа11осате, поскольку объекту класса Спцпк он неизвестен.
чо1д спцпк::пеа11осате(ио1д* р, втд::взхе т Ыоск>зле) ( аьвегт(р >= рпата ); цов1спед сваг* тояе1еаве = втат1с савт<цпв1спед спагн>(р); // Проверка выравнивания аввегт((тояе1еаве — рпата ) Ж Ыосйвйае == 0); *тояе1еаве = т1гвтлиаз1аЫев1оск ; т1гвтлиаз1аЫев1оск = втатзс савт<цпв1спед сваг>( (токе1еаве - ровса ) / Ыосйвзхе); // проверка усечения аввегт(т1гвтлиаз1аЫев1оск (тояе1еаэе - рпата ) / ЫосМВзге)„. ++Ыосквлиа41аЫ е Функция освобождения памяти небогата содержанием, однако в ней содержится довольно много диагностических высказываний (которые по-прежнему не перехватывают все ошибочные ситуации).
Структура спцпк вполне соответствует традиционным механизмам распределения памяти, принятым в языках С и С++. Если вы передадите функции споив::оеа11осате неверный указатель, приготовьтесь к худшему. 4.5. Класс НхебАПоса1ог На следуюшем уровне механизма распределения памяти для небольших объектов находится класс рйхедл11осатог. Этот класс предназначен для распределения памяти Часть й Методы при работе с блоками фиксированного размера, причем этот размер не обязан соответствовать размеру порции. Для этого объект класса рзхедд11осатаг образует вектор объектов типа СЬип)с.
При поступлении запроса на распределение памяти объект класса кзхедд11осасог отыскивает подходящий объект класса СЬипй. Если все порции заняты, объект класса рзхедд11осасог создает новый объект класса СЬипй. Вот как выглядит эта часть определения класса. с1ааа язхедд11осатог ( рг(часе: зсб:."з1ге т. Ыосйв(зе ; ипзздпед сЬаг пиев1осйз СуредеУ зтд::честогсСЬипй> СЬипМз; СЬипкз сЬипйз СЬипй* а11осСЬипК СЬипк* деа11осСЬип1с; Чтобы ускорить работу, класс г1хедд11осатог не перебирает элементы вектора сЬипМз в поисках подходящего участка памяти при каждом запросе. Вместо этого в объекте хранится указатель на последний объект класса Сйип)с, который использовался при распределении памяти (переменная а11осСЬипМ ). При поступлении нового запроса функция гзхедд11осасе сначала проверяет, достаточно ли памяти в порции, на которую ссылается указатель а11осСЬипй .
Если этот объект удовлетворяет требованиям запроса, то используется именно он, Если нет, выполняется линейный поиск (и, возможно, в вектор сЬип1сз записывается новый объект класса СЬипй), В любом случае указатель а11осСЬипМ устанавливается на найденный или вновь созданный объект класса СЬипЬ. Такой подход повышает вероятность того, что в следующий раз распределение памяти будет выполнено быстро. Вот как выглядит код этого алгоритма. чоИ* язхедд11осасог::411осатеО ( 1г (а11осСЬипй == 0 1~ а11осСЬипй ->Ыосйздчаз1аЫе == О) ( // в данном объекте памяти недостаточна.
// попробуйте найти другой. сЬипМз::)сегасог 1 = сЬипйз .ЬедзпО; бог (;; +=1) ( 1б (1 == сЬипйз .епдО) ( // все объекты заполнены -- добавляем новый. СЬипкз . гезегче(сйипйз .ззгеО+1); СЬипй пепСЬипк; пепсЬипй.тпз'с(Ыосйвзге , пивв1осйз ); сЬипйз .ризЬ Ьасй(пепСЬипй); а11осСЬипЬ = бсЬипМз .ЬасМО; деа11осСЬипЬ = йсЬипКз .ЬасМ() Ьгеак; ) зб (1->Ыос)сздчаз1аЫе > О) ( // объект найден а11осСЬипЬ 6*з; 107 Глава 4. Размещение в памяти небольших объектов Ьгеай; аьвегт(а11оссйцпЫ != О); аввегс(а11оссйцпй ->Ыоскздча11аЫе > О); гетцгп а11оссйцпК,->д11осате(Ыосйбзхе ); Придерживаясь этой стратегии, класс рзхеда11осатог удовлетворяет большинство запросов за одно и то же время.
При этом могут возникать некоторые задержки, обусловленные поиском и добавлением новых блоков. Иногда эта схема может работать неэффективно. Однако на практике такие случаи встречаются редко. Не забывайте, что у каждого механизма распределения памяти есть своя ахиллесова пята. Освобождение памяти — более сложная задача, поскольку определенная часть информации отсутствует.
У нас есть лишь указатель на освобождаемую область памяти, и нам неизвестно, какому именно объекту типа сйцпк он принадлежит. Мы можем просмотреть содержимое вектора сйипкз, проверяя, лежит ли данный указатель в диапазоне от роата до рпата + Ыосйбйхе " пипв1осйз .
Если да, то указатель следует передать функции-члену пеа11осате соответствующего объекта класса Сйцпк. Очевидно, что этот поиск требует затрат времени. Несмотря на то что операция выделения памяти выполняется быстро, процедура удаления занимает линейное время. Итак, нужно как-то ускорить этот процесс. Для этого люжно применить вспомогательный кэш (сас1зе тешозу). Когда пользователь освобождает блок, используя вызов яз хедд11осасог:: оеа11осате(р), объект класса гйхедд11осасог не передает указатель р обратно соответствующему объекту класса сйцпк, а записывает указатель р во внутреннюю память — кэш, в котором хранятся свободные блоки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
