Класс allocator
Синтаксис
Параметры
Тип
Тип объекта, для которого выполняется выделение и освобождение памяти.
Remarks
Например, объект распределителя может выделить память в закрытой куче или в общей памяти. Он также может выполнить оптимизацию для крупных или мелких объектов. Он может также указывать, посредством определения типов, которые он предоставляет, что доступ к элементам возможен только через специальные объекты метода доступа, управляющие общей памятью или выполняющие автоматическую сборку мусора. Таким образом, класс, который выделяет память с использованием объекта распределителя, должен использовать эти типы для объявления указателя и объектов ссылок, как это делают контейнеры в библиотеке стандартов C++.
Таким образом, распределитель определяет следующие типы:
Члены
Конструкторы
Определения типов
| Имя | Описание |
|---|---|
| const_pointer | Тип, предоставляющий постоянный указатель на тип объекта, управляемого распределителем. |
| const_reference | Тип, предоставляющий постоянную ссылку на тип объекта, управляемого распределителем. |
| difference_type | Тип целого числа со знаком, который может представлять разницу между значениями указателей на тип объекта, управляемого распределителем. |
| вид | Тип, предоставляющий указатель на тип объекта, управляемого распределителем. |
| reference | Тип, предоставляющий ссылку на тип объекта, управляемого распределителем. |
| size_type | Целочисленный тип без знака, который может представлять длину любой последовательности, которую allocator может выделить объект типа. |
| value_type | Тип, управляемый распределителем. |
Функции
Операторы
адрес
Находит адрес объекта, значение которого задано.
Параметры
Val
Константное или неконстантное значение объекта, адрес которого ищется.
Возвращаемое значение
Константный или неконстантный указатель на найденный объект соответственно константного или неконстантного значения.
Remarks
Функции элементов возвращают адрес Val в форме, которую указатели должны принимать для выделенных элементов.
Пример
памяти
Выделяет блок памяти, достаточный для хранения по крайней мере некоторого указанного числа элементов.
Параметры
count
Количество элементов, для которых необходимо выделить достаточный объем памяти.
_Hint
Константный указатель, который может помочь объекту allocator удовлетворить запрос хранилища, найдя адрес объекта, выделенного до запроса.
Возвращаемое значение
Указатель на выделенный объект или значение null, если память не была выделена.
Remarks
Пример
выделен
Конструкторы, используемые для создания объектов allocator.
Параметры
Правильно
Объект allocator для копирования.
Remarks
Конструктор не выполняет никаких действий. Однако в целом объект allocator, построенный из другого объекта allocator, должен оцениваться как эквивалентный ему, и должно быть разрешено перемешивание выделения и освобождения объектов между этими двумя объектами allocator.
Пример
const_pointer
Тип, предоставляющий постоянный указатель на тип объекта, управляемого распределителем.
Remarks
Пример
const_reference
Тип, предоставляющий постоянную ссылку на тип объекта, управляемого распределителем.
Remarks
Пример
создания
Создает определенный тип объекта по указанному адресу, инициализированный с использованием заданного значения.
Параметры
указатель
Указатель места, в котором должен создаваться объект.
Val
Значение, с которым создаваемый объект будет инициализирован.
Remarks
Пример
deallocate
Освобождает указанное число объектов из памяти, начиная с заданной позиции.
Параметры
указатель
Указатель на первый объект, который должен быть освобожден из хранилища.
count
Количество объектов для освобождения из хранилища.
Remarks
Пример
Пример использования этой функции-члена см. в разделе allocator::allocate.
завершить
Вызывает деструктор объектов без освобождения памяти, в которой хранился объект.
Параметры
указатель
Указатель, обозначающий адрес уничтожаемого объекта.
Remarks
Функция-член уничтожает объект, обозначенный ptr, путем вызова деструктора ptr->Type::
Пример
difference_type
Тип целого числа со знаком, который может представлять разницу между значениями указателей на тип объекта, управляемого распределителем.
Remarks
Пример
max_size
Возвращаемое значение
Количество элементов, которые могут быть выделены.
Пример
Оператор =
Назначает один объект allocator другому объекту allocator.
Параметры
Правильно
Объект allocator для назначения другому такому объекту.
Возвращаемое значение
Ссылка на объект allocator
Remarks
Оператор присваивания шаблона не выполняет никаких действий. Однако в целом объект allocator, назначенный другому объекту allocator, должен оцениваться как эквивалентный ему, и должно быть разрешено перемешивание выделения и освобождения объектов между этими двумя объектами allocator.
Пример
Указатель
Тип, предоставляющий указатель на тип объекта, управляемого распределителем.
Remarks
Пример
повторно привязать
Структура, позволяющая распределителю, предназначенному для объектов одного типа, выделять память для объектов другого типа.
Параметры
иной
Тип элемента, для которого выделяется память.
Remarks
Эту структуру удобно использовать для выделения памяти для типа, который отличается от типа элемента реализуемого контейнера.
Например, при наличии объекта распределителя al типа A можно выделить объект типа _Other с помощью выражения:
Кроме того, можно дать имя его типу указателя, написав тип:
Пример
Ссылка
Тип, предоставляющий ссылку на тип объекта, управляемого распределителем.
Remarks
Пример
size_type
Целочисленный тип без знака, который может представлять длину любой последовательности, которую allocator может выделить объект типа.
Пример
value_type
Тип, управляемый распределителем.
Remarks
Аллокаторы памяти
Предисловие
Для начала, хотелось бы сразу отметить, что если кто-то впервые слышит термины «аллокатор», «алгоритмы распределения памяти» и не понимает, для чего это все нужно, то тогда, прежде чем читать данную статью, я рекомендую ознакомиться с данным источником. В данной статье достаточно хорошо рассказывается, какие существуют проблемы в стандартных аллокаторах памяти, и для каких целей стоит использовать другие способы распределения памяти, помимо стандартных. Здесь же я буду рассказывать только о самих алгоритмах распределения, ну и, конечно же, в конце приведу реализацию одного из аллокаторов, которая может быть без проблем использована в стандартных контейнерах С++.
Основы
Концептуально выделяется пять основных операции, которые можно осуществить над аллокатором (хочется отметить, что не все аллокаторы могут явно соответствовать этому интерфейсу):
Linear Allocator
Linear Allocator, он же «линейный» — это самый простой вид аллокаторов. Идея состоит в том, чтобы сохранить указатель на начало блока памяти выделенному аллокатору, а также использовать другой указатель или числовое представление, которое необходимо будет перемещать каждый раз, когда выделение из аллокатора завершено. В этом аллокаторе внутренняя фрагментация сведена к минимуму, потому что все элементы вставляются последовательно (пространственная локальность), и единственная фрагментация между ними — выравнивание.
Дальше предлагаю рассмотреть несколько примеров, в которых будет наглядно показано в деталях, как работает данный аллокатор. Возьмем некоторый блок памяти равный 14 байтам и отдадим его в управление аллокатору. Как видно из картинки ниже, мы сохраняем указатель на начало памяти (start), а также храним два указателя, либо два числовых представления, которые содержат информацию об общем (end) и используемом (used) размерах памяти.
Представим, что в аллокатор поступил запрос на выделение 4 байт памяти. Действия аллокатора на исполнения этого запроса будут следующие:
Дальше, например, приходит запрос на выделение 8 байт и, соответственно, действия аллокатора будут точно такими же вне зависимости от размера выделяемого блока памяти.
А вот здесь уже будет немного интереснее, например, если приходит запрос на выделение только 1 байта, и если мы не хотим выравнивать блоки в памяти (например адреса кратные 2, 4, …), то действия аллокатора останутся точно такими же.
Но, если нам нужно выделять блоки памяти с определенным выравниванием (например выравнивание адресов кратных 2), то здесь действие аллокатора немного меняется. Меняется оно не в плане реализации, а в том, что помимо самих данных равных объему одного байта, мы еще забираем и один дополнительный байт из памяти аллокатора для выравнивания, который не несет никакой смысловой нагрузки. Как раз-таки это и есть та самая возможная минимальная фрагментация памяти внутри линейного аллокатора.
Отлично, теперь самое время поговорить об освобождении памяти. Как уже отмечалось ранее, данный вид аллокоторов не поддерживает выборочное освобождение определенных блоков памяти. То есть, если провести тонкую аналогию с malloc/free, имея указатель, скажем, на 0xFFAA00, мы могли бы освободить этот блок памяти, но вот линейный аллокатор нам этого позволить не может.
Все, что мы можем сделать, это освободить всю занятую память целиком внутри аллокатора и продолжить работать с ним, как с совершенно пустым.
Pool Allocator
Идея блочного аллокатора заключается в том, что он разделяет некоторый большой участок памяти на более мелкие участки одинакового размера. По своей сути он также является очень простым аллокатором, так как, когда запрашивается выделение, он просто возвращает один из свободных участков памяти фиксированного размера, а когда запрашивается освобождение то, он просто сохраняет этот участок памяти для дальнейшего использования. Таким образом, распределение работает очень быстро, а фрагментация все еще очень мала.
Дальше, также, как и с линейным аллокатором, предлагаю рассмотреть все на примере, чтобы детальнее понять, как он работает, поэтому возьмем некоторый блок памяти равный 12 байт и отдадим его в управление аллокатору. Как видно из картинки ниже, мы сохраняем указатель на начало (start) и конец (end) памяти, которой управляет аллокатор, а также список (freeblocks) из адресов свободных блоков в аллокаторе. В качестве средства для хранения данных о том, что блок занят или свободен, можно использовать много средств, например массив из булевых значений, но я именно решил остановиться на выборе односвязного списка, так как он наиболее просто и наглядно характеризует данную концепцию (кстати, сами звенья списка можно хранить в свободных блоках памяти, тем самым убрав дополнительные расходы с памятью).
Если приходит запрос на выделение одного блока памяти, то действия аллокатора очень примитивные. Сначала он проверяет, есть ли звенья в списке свободных блоков, если их там нет, то не трудно догадаться, что память в аллокаторе уже закончилась. Если же там есть хотя бы одно звено, то он просто достает корневое или хвостовое (в данной реализации отдаются хвостовые звенья) звено списка и отдает его адрес пользователю.
Если приходит запрос на выделение нескольких блоков памяти, то аллокатор точно так же по очереди проделывает те же действия, описанные на предыдущем шаге.
Что касается освобождения блока, если приходит запрос на освобождение, то тогда аллокатор просто добавляет этот адрес в один из концов односвязного списка. Стоит отметить такой момент, что в качестве адреса блока для освобождения может прийти, например адрес, несоответствующий адресу памяти аллокатора, например 0xEFAB12, и тогда будет возможна такая ситуация, что мы в дальнейшем отдадим пользователю тот участок памяти, который нам не принадлежит (конечно же, это приведет к undefined behavior или если очень сильно повезет, то просто к краху программы). Для избегания этой возможной проблемы как раз-таки и используются begin и end, которые позволяют проверить, не ошибся ли пользователь адресом во время запроса на операцию освобождения.
Помимо выхода за пределы памяти, которой не управляет аллокатор, есть еще одна возможная проблема. Пользователь может прийти с запросом освободить совершенно любой адрес, находящийся в области памяти аллокатора, но не равный адресу начала какого-либо из блоков, допустим блока с адресом 0xFFAA07. Эта операция, конечно же, приведет к undefined behavior. Если есть необходимость дополнительно проверять, все ли правильно делает пользователь, то есть возможность это отслеживать. Для отслеживания этого существует множество решений, например хранить также адреса и занятых блоков или вообще проверять адрес на кратность размеру блоков в аллокаторе (все зависит от фантазии и от конкертной ситуации, в которой используется аллокатор).
Stack Allocator
На самом деле, это умная эволюция линейного распределителя, которая позволяет управлять памятью, как стеком. Все так же, как и раньше, мы сохраняем указатель вместе с «header» блоком (в дальнейшем будет употребляться, как заголовок) на текущий адрес памяти и перемещаем его вперед для каждого выделения. В отличие от линейного аллокатора, мы также можем переместить его назад, то есть выполнить операцию deallocate, которая линейным аллокатором не поддерживается. Как и прежде, сохраняется принцип пространственной локальности, а фрагментация все еще минимальная.
Предлагаю рассмотреть несколько примеров все с тем же блоком памяти в 14 байт. Как и с линейным аллокатором, мы точно также сохраняем указатели на начало памяти (start) и конец (end), а также указатель на конец используемой памяти (used).
Когда приходит запрос на выделение памяти, помимо выделения некоего ее объема памяти, запрашиваемого пользователем, мы еще дополнительно выделяем заголовок (пользователь с ним никак не будет взаимодействовать), в котором храним сведения о том, сколько было выделено байт (в данном примере размер заголовка составляет 2 байта). Например, если пришел запрос на выделение 2 байт, то состояние аллокатора будет точно таким же, как на рисунке ниже. Важно отметить то, что пользователю будет отдан указатель не на заголовок, а на блок, следующий сразу за заголовком, то есть в данном примере это блок с адресом 0xFFAA02.
Аналогичная ситуация будет и, например с выделением 6 байт.
А вот с освобождением все немного поинтереснее (как уже обсуждалось ранее, выделять и освобождать память мы можем только с использованием алгоритма LIFO). Для начала от указателя, который пользователь просит освободить, нужно отнять размер заголовка, после чего разыменовать значение и уже только после этого сдвинуть указатель used на размер заголовка вместе с размером блока, полученного из заголовка. Здесь так же, как и с блочным аллокатором, возможна ситуация освобождения «рандомных» блоков памяти, которая также приведет к undefined behavior. Дополнять аллокаторы дополнительными проверками или нет – дело каждого. Самое главное — не забывать об этом моменте.
Теперь, разобравшись в основах, самое время освоить что-то более серьезное.
«Примитивный стандартный аллокатор»
Дальше будет представлена реализация аллокатора, который можно будет без проблем использовать с STL. Алгоритм распределения памяти в этом аллокаторе будет схож с алгоритмом, который используется стандартным аллокатором. Хочу сразу отметить, что не претендую на полноту реализации malloc, мною были взяты лишь основные концепции из него c добавлением в некоторых местах своей логики. Все его тонкости и нюансы, конечно же, не были учтены в этой реализации…
В основе алгоритма лежит взаимодействие с «chunks» (дальше будет употреблено, как участок, в данной реализации их размер статичен и должен быть кратен четырем, а также все выделения памяти из памяти аллоктора выравниваются на размер, кратный четырем), о которых дальше и пойдет речь. В качестве примера возьмем участок c размером 16 байт. Внутри себя он будет содержать указатели на начало (start) и конец (end) памяти, указатель на максимальный блок памяти (maxblock) и множество (freeblocks), в котором будут храниться заголовки свободных блоков. Размер заголовка в данной реализации занимает 4 байта, но он может без проблем варьироваться в размере для нужных вам целей. Например, если вы точно знаете, что размер выделяемых блоков памяти будет не больше, чем максимальное числовое значение, которое можно представить в одно или двухбайтной переменной, то можно будет использовать заголовок в размере 1 или 2 байт.
При операции выделения памяти из участка, прежде всего нужно проверить, достаточно ли памяти (в данной реализации, это константная операция, мы просто сравниваем с maxblock заголовком и, если размер аллоцируемой памяти меньше, чем максимальный блок, то значит у нас достаточно памяти для этого выделения). Если памяти достаточно, то мы просто отдаем адрес памяти, следующий за заголовком, как и в стековом аллокаторе, а также удаляем прошлый заголовок из множества свободных блоков и уже только после этого добавляем туда новый заголовок, только что выделенного блока памяти. Важно отметить, что если мы аллоцировали память из максимального блока, то нам нужно будет обновить значение максимального блока.
При последующих выделениях все происходит точно также, как и на предыдущем шаге.
Но вот как только память в участке закончилась, аллокатор берет и просто создает еще один участок того же или большего размера (в данной реализации все участки одинакового размера). Стоит также следить за тем, чтобы размер возможного блока для выделения не превышал размер участка с вычетом размера заголовка.
Дальше уже в новом участке можно без проблем выделять нужные блоки памяти. Выделение памяти будет происходить по точно такому же сценарию, как и в предыдущем участке.
Теперь немного о том, почему именно в данной реализации размер участка должен быть кратен четырем. Ответ очень просто – это делается для простоты реализации и восприятия алгоритма. Так как возможна такая ситуация, что в конце участка может остаться некоторая область памяти, в которой просто на просто не поместится заголовок (пример этого продемонстрирован на следующем рисунке). Чтобы решить эту проблему, можно будет заполнять эту память дополнительным выравниваем, либо делать размер заголовка меньшим или же использовать дополнительные средства для отслеживания этой возможной проблемы, иначе эта память будет потеряна и самая главное, что в дальнейшем потерянная память сможет накапливаться!
Прежде, чем освободить память, нужно определить, в каком участке находится блок (в текущей реализации эта операция с линейной сложностью относительно общего количества участков, если подразумевается, что будет большое количество участков, то ее можно будет сделать константной, добавив в заголовок индекс участка, в котором была выделена память). В последующем операция освобождения идентична со стековым аллокатором, за исключением того, что нужно будет добавить адрес заголовка освобожденного блока во множество свободных блоков, а также обновить maxblock, если размер только что освобожденного блока больше, чем maxblock.
Важно отметить, что в данной реализации, при каждом последующем освобождении памяти происходит попытка дефрагментации в том участке из которого была освобождена память. Дефрагментация нужна для того, чтобы объединять свободные блоки в большие по размеру. Например, в данной ситуации, как на рисунке ниже, мы не сможем выделить 6 байт, пусть даже размер свободной памяти нам и позволяет это сделать, но зато фрагментация говорит нам твердое и решительное «нет»!
Операция дефрагментации очень примитивная. Суть ее заключается в том, что после операции освобождения памяти идет проверка, не свободны ли два соседних блока слева и справа от освобожденного. Если два соседствующих блока свободны, то они объединяются в один единый.
Еще хотелось бы отметить, что данная реализация будет катастрофически ужасно работать с выделением маленьких блоков памяти, например равных 1 байту. В такой ситуации мы получаем +7 лишних байт на выделение всего лишь одно байта памяти из-за того, что размер заголовка равен 4 байтам и еще плюс 3 байта для вырывания адресов, которые должны быть кратны четырем. Этим я хочу сказать, что не стоит слепо использовать какой-либо алгоритм распределения памяти, так как вместо долгожданной оптимизации иногда можно получить только лишь дополнительные затраты.
Думаю, теории будет достаточно и поэтому, как сказал Линус Торвальдс: «Болтовня ничего не стоит. Покажите мне код». Ну что ж, приступаем…
Реализация
Требования к аллокаторам приведены в стадарте С++ в главе «Allocator requirements [allocator.requirements]«. Исходя из тех требований самый примитивный интерфейс аллокатора, который может использоваться в STL, должен выглядеть примерно вот так:
Предполагается, что STL контейнеры обращаются к аллокатору не напрямую, а через шаблон std::allocator_traits, который предоставляет значения, такие как:
Отлично, с требованиями разобрались, теперь наконец приступаем к написанию аллокатора. Для начала напишем некоторый интерфейс или адаптер, на самом деле это трудно назвать и тем, и другим, поэтому пусть это будет некая «прослойка», в которой при помощи стратегий мы сможем без проблем менять алгоритм аллоцирования памяти для определенных целей:
Благодаря стратегии для распределения памяти, мы сможем делать примерно вот так:
То есть мы можем гибко менять алгоритмы распределения для необходимых целей в той или иной ситуации. Единственное требование к AllocationStrategy — у них должны быть операции allocate и deallocate.
Здесь и дальше используются стандартные контейнеры. Согласен, что будет очень много выделений из кучи. Думаю, что для тех, кто будет писать свои аллокаторы, это будет неприемлемо. В качестве альтернативы, конечно же, можно писать свои контейнеры или использовать чужие, заточенные под определенные нужды, но в данной реализации я старался как можно проще преподнести материал, поэтому мой выбор лег именно на стандартные контейнеры.
Теперь немного о том, как можно украсить использование аллокаторов вместе со стандартными контейнерами:
Можно также использовать аллокаторы и с умными указателями, но для этого придется написать небольшую прослойку:
Ну и теперь, наконец, пример использования всего этого:
Хотелось бы заострить внимание на том, что данная реализация является самой примитивной, но она может быть без проблем расширена в ту сторону, которая вам необходима, поэтому все в ваших руках!
Заключение
Спасибо за внимание, очень надеюсь, что данная статья оказалась кому-то полезной. Также желаю всем успехов в тесном взаимодействии с памятью, и самое главное, не забывать очень важные слова Дональда Кнута: «Преждевременная оптимизация — корень всех зол».
Ссылка на репозиторий с полной реализацией аллокатора.
