Распределитель (C ++) - Allocator (C++)

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

Распределители были изобретены Александр Степанов как часть Стандартная библиотека шаблонов (STL). Изначально они были задуманы как средство сделать библиотеку более гибкой и независимой от лежащих в основе модель памяти, позволяя программистам использовать настраиваемые указатель и ссылка типы с библиотекой. Однако в процессе внедрения STL в Стандарт C ++ комитет по стандартизации C ++ понял, что абстракция модели памяти приведет к недопустимому спектакль штрафы. Чтобы исправить это, требования распределителей были сделаны более строгими. В результате уровень настройки, предоставляемый распределителями, более ограничен, чем первоначально предполагал Степанов.

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

Фон

Дальнейшая информация: Стандартная библиотека шаблонов

Александр Степанов и Мэн Ли представил Стандартная библиотека шаблонов к C ++ комитет по стандартам в марте 1994 г.[1] Библиотека получила предварительное одобрение, хотя были подняты несколько вопросов. В частности, Степанову было предложено сделать библиотечные контейнеры независимыми от лежащих в основе модель памяти,[2] что привело к созданию распределителей. Следовательно, все интерфейсы контейнеров STL пришлось переписать, чтобы они принимали распределители.

При адаптации STL для включения в Стандартная библиотека C ++, Степанов тесно сотрудничал с несколькими членами комитета по стандартам, включая Эндрю Кениг и Бьярне Страуструп, который заметил, что пользовательские распределители потенциально могут использоваться для реализации постоянного хранения Контейнеры STL, которые Степанов в то время считал «важной и интересной находкой».[2]

С точки зрения переносимости, все машинно-зависимые вещи, относящиеся к понятию адреса, указателя и т. Д., Заключены в крошечный, хорошо понятный механизм. [2]

—Алексей Степанов, дизайнер Стандартная библиотека шаблонов

Первоначальное предложение распределителя включало некоторые языковые особенности, которые еще не были приняты комитетом, а именно возможность использования аргументы шаблона которые сами по себе являются шаблонами. Поскольку эти функции не могут быть скомпилированы никакими существующими компилятор По словам Степанова, «Бьярну [Страуструпу] и Энди [Кенигу] требовалось время, чтобы убедиться, что мы правильно используем эти нереализованные функции».[2] Где библиотека ранее использовала указатель и ссылка типы напрямую, теперь он будет ссылаться только на типы, определенные распределителем. Позднее Степанов описал распределители следующим образом: «Хорошая особенность STL в том, что единственное место, где упоминаются машинно-зависимые типы (...), заключено примерно в 16 строк кода».[2]

Хотя Степанов изначально планировал, что распределители будут полностью инкапсулировать модель памяти, комитет по стандартам понял, что такой подход приведет к неприемлемому снижению эффективности.[3][4] Чтобы исправить это, в требования к распределителю была добавлена ​​дополнительная формулировка. В частности, реализации контейнеров могут предполагать, что распределитель определения типов для указателей и связанных интегральные типы эквивалентны тем, которые предоставляются распределителем по умолчанию, и что все экземпляры данного типа распределителя всегда сравнивать равные,[5][6] эффективно противоречит первоначальным целям разработки распределителей и ограничивает полезность распределителей, передающих состояние.[4]

Позднее Степанов прокомментировал, что, хотя распределители «не такая уж плохая [идея] в теории (...) [и], к сожалению, они не могут работать на практике». Он заметил, что, чтобы сделать распределители действительно полезными, изменение основного языка в отношении Рекомендации было необходимо.[7]

В Редакция 2011 года стандарта C ++ удалил ласковые слова требуя, чтобы распределители заданного типа всегда сравнивали равные и использовали обычные указатели. Эти изменения делают распределители с отслеживанием состояния намного более полезными и позволяют распределителям управлять общей памятью вне процесса.[8][9] Текущая цель распределителей - дать программисту контроль над распределением памяти внутри контейнеров, а не адаптировать адресную модель базового оборудования. Фактически, пересмотренный стандарт устранил способность распределителей представлять расширения модели адресов C ++, формально (и намеренно) устранив их первоначальную цель.[10]

Требования

Любой класс что выполняет требования к распределителю может использоваться как распределитель. В частности, класс А способен выделять память для объекта типа Т должен предоставить типы A :: указатель, A :: const_pointer, Ссылка, A :: const_reference, и A :: value_type для общего объявления объектов и ссылок (или указателей) на объекты типа Т. Также должен быть указан тип A :: size_type, беззнаковый тип, который может представлять наибольший размер для объекта в модели распределения, определяемой А, и аналогично подписанный интеграл A :: разница_типа которые могут представлять разницу между любыми двумя указатели в модели распределения.[11]

Хотя соответствующая реализация стандартной библиотеки может предполагать, что распределитель A :: указатель и A :: const_pointer просто typedefs за Т * и T const *, разработчикам библиотек рекомендуется поддерживать более общие распределители.[12]

Распределитель, А, для объектов типа Т должна иметь функцию-член с подписью А::указатель А::выделить(size_type п, А<пустота>::const_pointer намекать = 0). Эта функция возвращает указатель на первый элемент вновь выделенного массива, достаточно большой, чтобы содержать п объекты типа Т; выделяется только память, а объекты не создаются. Более того, необязательный аргумент указателя (который указывает на объект, уже выделенный А) может использоваться как подсказка реализации о том, где должна быть выделена новая память, чтобы улучшить местонахождение.[13] Однако реализация может игнорировать аргумент.

Соответствующие void A :: deallocate (A :: pointer p, A :: size_type n) функция-член принимает любой указатель, который был возвращен из предыдущего вызова A :: выделить функция-член и количество элементов, которые нужно освободить (но не уничтожить).

В A :: max_size () функция-член возвращает наибольшее количество объектов типа Т которые можно было бы ожидать, чтобы они были успешно выделены вызовом A :: выделить; возвращаемое значение обычно A :: size_type (-1) / размер (Т).[14] Так же A :: адрес функция-член возвращает A :: указатель обозначающий адрес объекта, учитывая Ссылка.

Построение и уничтожение объекта выполняется отдельно от выделения и освобождения.[14] Распределитель должен иметь две функции-члены, A :: конструкция и A :: уничтожить (обе функции объявлены устаревшими в C ++ 17 и удалены в C ++ 20), который обрабатывает создание и уничтожение объектов соответственно. Семантика функций должна быть эквивалентна следующему:[11]

шаблон <typename Т>пустота А::строить(А::указатель п, А::const_reference т) { новый ((пустота*) п) Т(т); }шаблон <typename Т>пустота А::уничтожить(А::указатель п){ ((Т*)п)->~Т(); }

В приведенном выше коде используется размещение новый синтаксис и вызывает деструктор прямо.

Распределители должны быть копируемый. Распределитель для объектов типа Т может быть построен из распределителя для объектов типа U. Если распределитель, А, выделяет область памяти, р, тогда р может быть освобожден только распределителем, который сравнивает равный А.[11]

Распределители необходимы для предоставления члена класса шаблона шаблон <typename U> struct A :: rebind { typedef A другое; };, что дает возможность получить связанный распределитель, параметризованный в терминах другого типа. Например, учитывая тип распределителя IntAllocator для объектов типа int, связанный тип распределителя для объектов типа длинная можно получить, используя IntAllocator :: rebind :: other.[14]

Пользовательские распределители

Одна из основных причин написания собственного распределителя - это производительность. Использование специализированного настраиваемого распределителя может существенно улучшить производительность или использование памяти, или и то, и другое вместе.[4][15] Распределитель по умолчанию использует оператор новый выделить память.[16] Часто это делается тонким слоем вокруг C куча функции распределения,[17] которые обычно оптимизированы для нечастого выделения больших блоков памяти. Этот подход может хорошо работать с контейнерами, которые в основном выделяют большие куски памяти, например вектор и дек.[15] Однако для контейнеров, требующих частого выделения небольших объектов, таких как карта и список, использование распределителя по умолчанию обычно выполняется медленно.[4][17] Другие распространенные проблемы с маллок распределитель на основе включает плохой местонахождение ссылки,[4] и чрезмерный фрагментация памяти.[4][17]

Популярный подход к повышению производительности - создание пул памяти распределитель на основе.[15] Вместо того, чтобы выделять память каждый раз, когда элемент вставляется или удаляется из контейнера, большой блок памяти (пул памяти) выделяется заранее, возможно, при запуске программы. Пользовательский распределитель будет обслуживать индивидуальные запросы выделения, просто возвращая указатель на память из пула. Фактическое освобождение памяти можно отложить до продолжительность жизни пула памяти заканчивается. Пример распределителей на основе пула памяти можно найти в Библиотеки Boost C ++.[15]

Еще одно жизнеспособное использование пользовательских распределителей - это отладка ошибки, связанные с памятью.[18] Этого можно достичь, написав распределитель, который выделяет дополнительную память, в которую помещает отладочную информацию.[19] Такой распределитель может использоваться для обеспечения выделения и освобождения памяти одним и тем же типом распределителя, а также для обеспечения ограниченной защиты от перерасходы.[19]

Короче говоря, этот параграф (...) является Стандартом "У меня есть мечта "речь для распределителей. Пока эта мечта не станет общей реальностью, программисты, озабоченные переносимостью, будут ограничиваться настраиваемыми распределителями без состояния

—Скотт Мейерс, Эффективный STL

Тема пользовательских распределителей затрагивалась многими C ++ эксперты и авторы, в том числе Скотт Мейерс в Эффективный STL и Андрей Александреску в Современный дизайн на C ++. Мейерс подчеркивает, что C ++ 98 требует всех экземпляры распределителя, чтобы быть эквивалентным, и отмечает, что это фактически заставляет портативный распределители не должны иметь состояние. Хотя стандарт C ++ 98 действительно поощрял разработчиков библиотек поддерживать распределители с отслеживанием состояния,[12] Мейерс называет соответствующий абзац «прекрасным чувством», которое «почти ничего не предлагает», характеризуя ограничение как «драконовское».[4]

В Язык программирования C ++, Бьярне Страуструп, с другой стороны, утверждает, что «очевидно [d] raconian ограничение на информацию для каждого объекта в распределителях не является особенно серьезным»,[3] указание на то, что большинству распределителей не требуется состояние, и они имеют лучшую производительность без него. Он упоминает три варианта использования настраиваемых распределителей, а именно: пул памяти распределители, Общая память распределители и память со сборкой мусора распределители. Он представляет реализацию распределителя, которая использует пул внутренней памяти для быстрого выделения и освобождения небольших фрагментов памяти, но отмечает, что такая оптимизация может уже выполняться распределителем, предоставленным реализацией.[3]

Применение

При создании одного из стандартных контейнеров распределитель указывается через шаблон аргумент, который значения по умолчанию к std :: allocator :[20]

пространство имен стандартное {  шаблон <класс Т, класс Распределитель = распределитель<Т> > класс вектор;// ...

Как и все шаблоны классов C ++, экземпляры стандартной библиотеки контейнеры с разными аргументами распределителя разные типы. Функция, ожидающая std :: vector аргумент поэтому примет только вектор создается с помощью распределителя по умолчанию.

Улучшения распределителей в C ++ 11

В C ++ 11 Стандарт улучшил интерфейс распределителя, чтобы разрешить распределители с ограниченными областями, так что контейнеры с "вложенными" выделениями памяти, такими как вектор строк или карта списков наборов определяемых пользователем типов, могут гарантировать, что вся память будет получена из распределитель контейнера.[21]

пример

#включают <iostream>с помощью пространство имен стандартное;с помощью пространство имен __gnu_cxx;класс Обязательное размещение{общественный:	Обязательное размещение ();	~Обязательное размещение ();	стандартное::basic_string<char> s = "Привет, мир!";};Обязательное размещение::Обязательное размещение (){	cout << "RequiredAllocation :: RequiredAllocation ()" << конец;}Обязательное размещение::~Обязательное размещение (){	cout << "RequiredAllocation :: ~ RequiredAllocation ()" << конец;}пустота выделить(__gnu_cxx ::new_allocator<Обязательное размещение>* все, беззнаковый int размер, пустота* pt, Обязательное размещение* т){	пытаться		{			все->выделить (размер, pt);			cout << все->max_size () << конец;			за (авто& е : т->s)				{					cout << е;				}		}	ловить (стандартное::bad_alloc& е)		{			cout << е.Какие () << конец;		}}intосновной (){	__gnu_cxx ::new_allocator<Обязательное размещение> *все =			новый __gnu_cxx ::new_allocator<Обязательный> ();	Обязательное размещение т;	пустота* pt = &т;	/*** Что происходит, когда новые не могут найти магазин для размещения? По умолчанию распределитель генерирует станцию.* исключение dard-library bad_alloc (альтернативу см. §11.2.4.1)* @C Bjarne Stroustrup Язык программирования C ++	 */	беззнаковый int размер = 1073741824;	выделить(все, размер, &pt, &т);	размер = 1;	выделить(все, размер, &pt, &т);	вернуть 0;}

[22]

Рекомендации

  1. ^ Степанов, Александр; Мэн Ли (7 марта 1994 г.). «Стандартная библиотека шаблонов. Презентация комитету по стандартам C ++» (PDF). Библиотеки Hewlett-Packard. Получено 12 мая 2009.
  2. ^ а б c d е Стивенс, Эл (1995). "Интервью Эла Стивенса Алексу Степанову". Журнал доктора Добба. В архиве из оригинала 1 мая 2009 г.. Получено 12 мая 2009.
  3. ^ а б c Страуструп, Бьярне (1997). Язык программирования C ++, 3-е издание. Эддисон-Уэсли.
  4. ^ а б c d е ж грамм Мейерс, Скотт (2001). Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов. Эддисон-Уэсли.
  5. ^ ISO /IEC (2003). ISO / IEC 14882: 2003 (E): Языки программирования - C ++ § 20.1.5 Требования к распределителю [lib.allocator.requirements] пункт 4
  6. ^ ISO /IEC (2003). ISO / IEC 14882: 2003 (E): Языки программирования - C ++ § 20.4.1 Распределитель по умолчанию [lib.default.allocator]
  7. ^ Ло Руссо, Грациано (1997). «Интервью с А. Степановым». stlport.org. Получено 13 мая 2009.
  8. ^ Хальперн, Пабло (4 февраля 2008 г.). «Поведение свопа и перемещения для конкретного распределителя» (PDF). ISO. Получено 21 августа 2012.
  9. ^ Хальперн, Пабло (22 октября 2009 г.). «Распределители публикуют сообщение об удалении концепций C ++ (ред. 1)» (PDF). ISO. Получено 21 августа 2012.
  10. ^ Беккер, Пит. «Проблема LWG 1318: N2982 удаляет предыдущие возможности распределителя (закрыто в марте 2011 г.)». ISO. Получено 21 августа 2012.
  11. ^ а б c ISO /IEC (2003). ISO / IEC 14882: 2003 (E): Языки программирования - C ++ § 20.1.5 Требования к распределителю [lib.allocator.requirements] пункт 2
  12. ^ а б ISO /IEC (2003). ISO / IEC 14882: 2003 (E): Языки программирования - C ++ § 20.1.5 Требования к распределителю [lib.allocator.requirements] пункт 5
  13. ^ Лангер, Анжелика; Клаус Крефт (1998). «Типы распределителя». Отчет C ++. Получено 13 мая 2009.
  14. ^ а б c Остерн, Мэтью (1 декабря 2000 г.). "Стандартный библиотекарь: для чего нужны распределители?". Журнал доктора Добба. В архиве из оригинала 28 апреля 2009 г.. Получено 12 мая 2009.
  15. ^ а б c d Оуэ, Энтони (1 сентября 2005 г.). «Повышение производительности с помощью настраиваемых распределителей пула для STL». Журнал доктора Добба. Получено 13 мая 2009.
  16. ^ ISO /IEC (2003). ISO / IEC 14882: 2003 (E): Языки программирования - Члены распределителя C ++ § 20.4.1.1 [lib.allocator.members] пункт 3
  17. ^ а б c Александреску, Андрей (2001). Современный дизайн на C ++. Эддисон-Уэсли. п. 352. ISBN  0-201-70431-5.
  18. ^ Влащану, Кристиан (1 апреля 2001 г.). «Отладка ошибок памяти с помощью настраиваемых распределителей». Журнал доктора Добба. Получено 14 мая 2009.
  19. ^ а б Остерн, Мэтью (1 декабря 2001 г.). «Стандартный библиотекарь: отладчик». Журнал доктора Добба. Получено 14 мая 2009.
  20. ^ ISO /IEC (2003). ISO / IEC 14882: 2003 (E): Языки программирования - C ++ § 23.2 Последовательности [lib.sequences] пункт 1
  21. ^ Хальперн, Пабло (29 февраля 2008 г.). "Модель распределителя с ограниченным объемом (версия 2)" (PDF). ISO. Получено 21 августа 2012.
  22. ^ __gnu_cxx :: new_allocator <имя_типа> Справочник по шаблону класса

внешняя ссылка