Книга: Эффективное использование STL

Совет 10. Помните о правилах и ограничениях распределителей памяти

Совет 10. Помните о правилах и ограничениях распределителей памяти

Распределители памяти первоначально разрабатывались как абстракция для моделей памяти, позволяющих разработчикам библиотек игнорировать различия между near- и far-указателями в некоторых 16-разрядных операционных системах (например, DOS и ее зловредных потомках), однако эта попытка провалилась. Распределители также должны были упростить разработку объектных диспетчеров памяти, но вскоре выяснилось, что такой подход снижает эффективность работы некоторых компонентов STL. Чтобы избежать снижения быстродействия. Комитет по стандартизации C++ включил в Стандарт положение, которое практически выхолостило объектные распределители памяти, но одновременно выражало надежду, что от этой операции их потенциальные возможности не пострадают.

Но это еще не все. Распределители памяти STL, как и operator new с operator new[], отвечают за выделение (и освобождение) физической памяти, однако их клиентский интерфейс имеет мало общего с клиентским интерфейсом operator new, operator new[] и даже malloc. Наконец, большинство стандартных контейнеров никогда не запрашивает память у своих распределителей. Еще раз подчеркиваю — никогда. В результате распределители производят довольно странное впечатление.

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

Перечень особенностей распределителей начинается с рудиментарных определений типов для указателей и ссылок. Как упоминалось выше, распределители изначально были задуманы как абстракции для моделей памяти, поэтому казалось вполне логичным возложить на них обеспечение определения типов (typedef) для указателей и ссылок в определяемой модели. В стандарте C++ стандартный распределитель объектов типа T(allocator<T>) предоставляет определения allocator<T>::pointer и allocator<T>::reference, поэтому предполагается, что пользовательские распределители также будут предоставлять эти определения.

Ветераны C++ немедленно почуют неладное, поскольку в C++ не существует средств для имитации ссылок. Для этого пришлось бы перегрузить operator. (оператор «точка»), а это запрещено. Кроме того, объекты, работающие как ссылки, являются примером промежуточных объектов (proxy objects), а использование промежуточных объектов приводит к целому ряду проблем, одна из которых описана в совете 18. Подробное описание промежуточных объектов приведено в совете 30 книги «More Effective C++».

В случае распределителей STL бессмысленность определений типов для указателей и ссылок объясняется не техническими недостатками промежуточных объектов, а следующим фактом: Стандарт разрешает считать, что определение типа pointer любого распределителя является синонимом T*, а определение типа reference — синонимом T&. Да, все верно, разработчики библиотек могут игнорировать определения и использовать указатели и ссылки напрямую! Таким образом, даже если вам удастся написать распределитель с новыми определениями для указателей и ссылок, никакой пользы от этого не будет, поскольку используемая реализация STL запросто сможет эти определения проигнорировать. Интересно, не правда ли?

Пока вы не успели осмыслить этот пример странностей стандартизации, я приведу следующий. Распределители являются объектами, из чего следует, что они могут обладать собственными функциями, вложенными типами и определениями типов (такими как pointer и reference). Однако в соответствии со Стандартом реализация STL может предполагать, что все однотипные объекты распределителей эквивалентны и почти всегда равны. Разумеется, это обстоятельство объяснялось вескими причинами. Рассмотрим следующий фрагмент:

template<typename T> // Шаблон пользовательского
                     // распределителя памяти
class SpecialAllocator{...};
typedef SpecialAllocator<Widget> SAW; // SAW = "SpecialAllocator
                                      //for Widgets"
list<Widget.SAW> L1;
list<Widget.SAW> L2;
L1.splice(L1.begin(), L2);

Вспомните: при перемещении элементов из одного контейнера listв другой функцией splice данные не копируются. Стоит изменить значения нескольких указателей, и узлы, которые раньше находились в одном списке, оказываются в другом, поэтому операция врезки выполняется быстро и защищена от исключений. В приведенном примере узлы, ранее находившиеся в L2, после вызова splice перемещаются в L1.

Разумеется, при уничтожении контейнера L1 должны быть уничтожены все его узлы (с освобождением занимаемой ими памяти). А поскольку контейнер теперь содержит узлы, ранее входившие в L2, распределитель памяти L1 должен освободить память, ранее выделенную распределителем L2. Становится ясно, почему Стандарт разрешает программистам STL допускать эквивалентность однотипных распределителей. Это сделано для того, чтобы память, выделенная одним объектом-распределителем (таким как L2), могла безопасно освобождаться другим объектом-распределителем (таким как L1). Отсутствие подобного допущения привое бы к значительному усложнению реализации врезки и к снижению ее эффективности (кстати, операции врезки влияют и на другие компоненты STL, один из примеров приведен в совете 4).

Все это, конечно, хорошо, но чем больше размышляешь на эту тему, тем лучше понимаешь, какие жесткие ограничения накладывает предположение об эквивалентности однотипных распределителей. Из него следует, что переносимые объекты распределителей — то есть распределители памяти, правильно работающие в разных реализациях STL, — не могут обладать состоянием. Другими совами, это означает, что переносимые распределители не могут содержать нестатических переменных (по крайней мере таких, которые бы влияли на их работу). В частности, отсюда следует, что вы не сможете создать два распределителя SpecialAllocator<int>, выделяющих память из разных куч (heap). Такие распределители не были бы эквивалентными, и в некоторых реализациях STL попытки использования обоих распределителей привели бы к порче структур данных во время выполнения программы.

Обратите внимание: эта проблема возникает на стадии выполнения. Распределители, обладающие состоянием, компилируются вполне нормально — просто они не работают так, как предполагалось. За эквивалентностью всех однотипных распределителей вы должны следить сами. Не рассчитывайте на то, что компилятор предупредит о нарушении этого ограничения.

Справедливости ради стоит отметить, что сразу же за положением об эквивалентности однотипных распределителей памяти в Стандарт включен следующий текст: «…Авторам реализаций рекомендуется создавать библиотеки, которые… поддерживают неэквивалентные распределители. В таких реализациях… семантика контейнеров и алгоритмов для неэквивалентных экземпляров распределителей определяется самой реализацией».

Трогательное проявление заботы, однако пользователю STL, рассматривающему возможность создания нестандартного распределителя с состоянием, это не дает практически ничего. Этим положением можно воспользоваться только в том случае, если вы уверены в том, что используемая реализация STL поддерживает неэквивалентные распределители, готовы потратить время на углубленное изучение документации, чтобы узнать, подходит ли вам «определяемое самой реализацией» поведение неэквивалентных распределителей, и вас не беспокоят проблемы с переносом кода в реализации STL, в которых эта возможность может отсутствовать. Короче говоря, это положение (для особо любознательных — абзац 5 раздела 20.1.5) лишь выражает некие благие намерения по поводу будущего распределителей. До тех пор пока эти благие намерения не воплотятся в жизнь, программисты, желающие обеспечить переносимость своих программ, должны ограничиваться распределителями без состояния.

Выше уже говорилось о том, что распределители обладают определенным сходством с оператором new — они тоже занимаются выделением физической памяти, но имеют другой интерфейс. Чтобы убедиться в этом, достаточно рассмотреть объявления стандартных форм operator new и allocator<T>::allocate:

void* operator new(size_t bytes);
pointer allocator<T>::allocate(size_type numObjects);
// Напоминаю: pointer - определение типа.
//практически всегда эквивалентное T*

В обоих случаях передается параметр, определяющий объем выделяемой памяти, но в случае с оператором new указывается конкретный объем в байтах, а в случае с allocator<T>::allocate указывается количество объектов T, размещаемых в памяти. Например, на платформе, где sizeof (int)==4, при выделении памяти для одного числа int оператору new передается число 4, а allocator<int>::allocate — число 1. Для оператора new параметр относится к типу size_t, а для функции allocate — к типу allocator<T>::size_type, В обоих случаях это целочисленная величина без знака, причем allocator<T>::size_type обычно является простым определением типа для size_t. В этом несоответствии нет ничего страшного, однако разные правила передачи параметров оператору new и allocator<T>::allocate усложняют использование готовых пользовательских версий new в разработке нестандартных распределителей.

Оператор new отличается от allocator<T>::allocate и типом возвращаемого значения. Оператор new возвращает void*, традиционный способ представления указателя на неинициализированную память в C++. Функция allocator<T>::allocate возвращает T* (через определение типа pointer), что не только нетрадиционно, но и отдает мошенничеством. Указатель, возвращаемый allocator<T>::allocate, не может указывать на объект T, поскольку этот объект еще не был сконструирован! STL косвенно предполагает, что сторона, вызывающая allocator<T>::allocate, сконструирует в полученной памяти один или несколько объектов T (вероятно, посредством allocator<T>::construct, uninitialized_fill или raw_storage_iterator), хотя в случае vector::reseve или string::reseve этого может никогда не произойти (совет 13). Различия в типах возвращаемых значений оператора new и allocator<T>::allocate означают изменение концептуальной модели неинициализированной памяти, что также затрудняет применение опыта реализации оператора new к разработке нестандартных распределителей.

Мы подошли к последней странности распределителей памяти в STL: большинство стандартных контейнеров никогда не вызывает распределителей, с которыми они ассоциируются. Два примера:

list<int> L; // То же, что и list<int, allocator<int».
             // Контейнер никогда не вызывает
             // allocator<int> для выделения памяти!
set<Widget.SAW> s;// SAW представляет собой определение типа
                  // для SpeciаlAllосаtor<Widget>, однако
                  // ни один экземпляр SAW не будет
                  // выделять память!

Данная странность присуща list и стандартным ассоциативным контейнерам (set, multiset, map и multimap). Это объясняется тем, что перечисленные контейнеры являются узловыми, то есть основаны на структурах данных, в которых каждый новый элемент размещается в динамически выделяемом отдельном узле. В контейнере list узлы соответствуют узлам списка. В стандартных ассоциативных контейнерах узлы часто соответствуют узлам дерева, поскольку стандартные ассоциативные контейнеры обычно реализуются в виде сбалансированных бинарных деревьев.

Давайте подумаем, как может выглядеть типичная реализация list<T>. Список состоит из узлов, каждый из которых содержит объект T и два указателя (на следующий и предыдущий узлы списка).

template<typename T>,           // Возможная реализация
typename Allocator=allocator<T> // списка
class list {
private:
 Allocator alloc;// Распределитель памяти для объектов типа T
 struct ListNode{// Узлы связанного списка
  T data;
  ListNode *prev;
  ListNode *next;
 };
 …
};

При включении в список нового узла необходимо получить для него память от распределителя, однако нам нужна память не для T, а для структуры ListNode, содержащей T. Таким образом, объект Allocator становится практически бесполезным, потому что он выделяет память не для ListNode, а для T. Теперь становится понятно, почему list никогда не обращается к Allocator за памятью — последний просто не способен предоставить то, что требуется list.

Следовательно, list нужны средства для перехода от имеющегося типа распределителя к соответствующему распределителю ListNode. Задача была бы весьма непростой, но по правилам распределитель памяти должен предоставить определение типа для решения этой задачи. Определение называется other, но не все так просто — это определение вложено в структуру с именем rebind, которая сама по себе является шаблоном, вложенным в распределитель, — причем последний тоже является шаблоном!

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

template<typename T>
class allocator {
public:
 template<typename U>
 struct rebind{
  typedef allocator<U> other;
 };
 …
}

В программе, реализующей list<T>, возникает необходимость определить тип распределителя ListNode, соответствующего распределителю, существующему для T. Тип распределителя для T задается параметром allocator. Учитывая сказанное, тип распределителя для ListNode должен выглядеть так:

Allocator::rebind<ListNode>::other

А теперь будьте внимательны. Каждый шаблон распределителя A (например, std::allocator, SpecialAllocator и т. д.) должен содержать вложенный шаблон структуры с именем rebind. Предполагается, что rebind получает параметр U и не определяет ничего, кроме определения типа other, где other — просто имя для A<U>. В результате list<T> может перейти от своего распределителя объектов T(Allocator) к распределителю объектов ListNode по ссылке Allocator::rebind<ListNode>::other.

Может, вы разобрались во всем сказанном, а может, и нет (если думать достаточно долго, вы непременно разберетесь, но подумать придется — знаю по своему опыту). Но вам как пользователю STL, желающему написать собственный распределитель памяти, в действительности не нужно точно понимать суть происходящего. Достаточно знать простой факт: если вы собираетесь создать распределитель памяти и использовать его со стандартными контейнерами, ваш распределитель должен предоставлять шаблон rebind, поскольку стандартные шаблоны будут на это рассчитывать (для целей отладки также желательно понимать, почему узловые контейнеры T никогда не запрашивают память у распределителей объектов T).

Ура! Наше знакомство со странностями распределителей памяти закончено. Позвольте подвести краткий итог того, о чем необходимо помнить при программировании собственных распределителей памяти:

• распределитель памяти оформляется в виде шаблона с параметром T, представляющим тип объектов, для которых выделяется память;

• предоставьте определения типов pointer и reference, но следите за тем, чтобы pointer всегда был эквивалентен T*, а reference — T&;

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

• помните, что функциям allocate передается количество объектов, для которых необходимо выделить память, а не объем памяти в байтах. Также помните, что эти функции возвращают указатели T* (через определение типа pointer) несмотря на то, что ни один объект T еще не сконструирован;

• обязательно предоставьте вложенный шаблон rebind, от наличия которого зависит работа стандартных контейнеров.

Написание собственного распределителя памяти обычно сводится к копированию приличного объема стандартного кода и последующей модификации нескольких функций (в первую очередь allocate и deallocate). Вместо того чтобы писать базовый код с самого начала, я рекомендую воспользоваться кодом с web-страницы Джосаттиса [23] или из статьи Остерна «What Are Allocators Good For?» [24].

Материал, изложенный в этом совете, дает представление о том, чего не могут сделать распределители памяти, но вас, вероятно, больше интересует другой вопрос — что они могут? Это весьма обширная тема, которую я выделил в совет 11.

Оглавление книги