Как работает аллокатор памяти

Обновлено: 07.07.2024

Вопрос звучит так: "Напишите быстрый аллокатор памяти"
Как я его понимаю: можно пожертвовать растратой памяти, всякими наворотами, возможно максимальной величиной обьекта..

Может у кого-то есть какие-то варианты? Мне что-то ничего в голову не приходит кроме как заранее поделить пул на поля с фиксированным размером N и завести битовое поле в котором храним флаги занято/свободно.. Может подкинете пару идей?

__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь

Аллокатор памяти общего назначения
Добрый день! В ВУЗе задали написать аллокатор памяти общего назначения на С++, но у меня нет ни.

Задача с собеседования
Всем привет! Недавно был на собеседование. Было много вопросов по строкам. Такое объявление строки.

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

Аллокатор в chrome
Всем привет, начал изучать исходники хрома, в аллокаторе, метод realloc должен возвращать nullptr.

Да фактически ж пул и просят по идее. Выделяете pool_size * sizeof(T) байт под пул, два массива размером в pool_size: один из bool (метки занятых ячеек; думаю, это будет быстрее битовых полей), второй из T* (кеш для указателей в пуле, рассчитывается при инициализации; тоже чуть ускоряет), определяете аллокацию-деаллокацию с помощью placement new и вызова деструктора, вместе с обновлением меток.

Отдельный квест: как ускорить выделение ещё сильнее. Особенно выделение массивов. То есть ускорить нахождение нужного количества пустых блоков. Применять всякие связные списки пустых блоков и т. п.

Решение

, Александреску можно почитать на этот счет, по идее в Loki очень быстрый аллокатор для маленьких объектов ( но Александреску в своей библиотеке выделывает с С++ такое, что пытаться сделать что-то такое же просто страшно).

Вроде бы по замерам clock() неплохо, но может быть можно лучше. И еще вопрос: как сделать чтобы allocate умел прокидывать параметры конструктора во внутрь Placement new ? Variadic templates по идее помогут (немного упрощённый пример, но суть понятна). Как без них красиво — не знаю. Разве что пачку шаблонов под allocate(один шаблонный параметр), allocate(два шаблонных параметра), . allocate(пять шаблонных параметров). Вопрос в двух строчках не осветить. Лучше статьи книги поискать, где тема раскрывается.
В частности, в александревску расписан один из возможных вариантов написания собственного распределителя памяти. У Джосатиса в справочнике по STL есть кое-что про требования к совместимым со стандартными распределителями памяти. Где-то еще видел, но всмопнить не могу. Вопрос звучит так: "Напишите быстрый аллокатор памяти"

На самом деле, вопрос не однозначен. Ведь аллокатор это абстрактное название, никак не связанное с контейнерами STL. Поэтому не очевидно, должна ли память выделяться для одного объекта или для нескольких объектов. Уже упомянутый Александреску решил все эти проблемы при помощи классов стратегий, но тебе-то нужно один простенький вариант написать. В общем, первым делом нужно пытать задающего вопросы, чтобы не было разночтений. Это тоже входит в обязанности разработчика, потому что в документации может быть любая чушь написана, которую все по своему понять могут и реализовать вовсе не то, чего изначально думалось.

Ну а по теме могу добавить ещё реализацию аллокатора из буста. Но у Александреску более очевидная реализация и лучше у него подсмотри.

Шаблон класса описывает объект, который управляет выделением и освобождением памяти для массивов объектов типа Type . Объект класса allocator является объектом распределителя по умолчанию, указанным в конструкторах для нескольких шаблонов классов контейнеров в стандартной библиотеке C++.

Синтаксис

Параметры

Тип
Тип объекта, для которого выполняется выделение и освобождение памяти.

Remarks

Все контейнеры стандартной библиотеки C++ имеют параметр шаблона, который по умолчанию имеет значение allocator . Создание контейнера с пользовательским распределителем дает возможность управлять выделением и освобождением памяти для элементов контейнера.

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

(Только C++ 98/03) При наследовании от класса распределителя необходимо предоставить структуру повторной привязки , _Other typedef которой ссылается на вновь производный класс.

Таким образом, распределитель определяет следующие типы:

указатель ведет себя как указатель на Type .

const_pointer ведет себя как Константный указатель на Type .

ссылка ведет себя как ссылка на Type .

const_reference ведет себя как Константная ссылка на Type .

Они Type указывают форму, которую должны принимать указатели и ссылки для выделенных элементов. ( распределитель::p оинтер не обязательно такой же, как и Type* для всех объектов распределителя, хотя он имеет это очевидное определение для класса allocator .)

C++11 and later: чтобы включить операции перемещения в распределитель, используйте минимальный интерфейс распределителя и реализуйте конструктор копирования, операторы == и !=, функции allocate и deallocate. Дополнительные сведения и пример см. в статье Распределители.

Члены

Конструкторы

Имя	Описание
allocator	Конструкторы, используемые для создания объектов allocator .

Определения типов

Имя	Описание
const_pointer	Тип, предоставляющий постоянный указатель на тип объекта, управляемого распределителем.
const_reference	Тип, предоставляющий постоянную ссылку на тип объекта, управляемого распределителем.
difference_type	Тип целого числа со знаком, который может представлять разницу между значениями указателей на тип объекта, управляемого распределителем.
вид	Тип, предоставляющий указатель на тип объекта, управляемого распределителем.
reference	Тип, предоставляющий ссылку на тип объекта, управляемого распределителем.
size_type	Целочисленный тип без знака, который может представлять длину любой последовательности, которую allocator может выделить объект типа.
value_type	Тип, управляемый распределителем.

Функции

Имя	Описание
address	Находит адрес объекта, значение которого задано.
allocate	Выделяет блок памяти, достаточный для хранения по крайней мере некоторого указанного числа элементов.
создания	Создает определенный тип объекта по указанному адресу, инициализированный с использованием заданного значения.
deallocate	Освобождает указанное число объектов из памяти, начиная с заданной позиции.
завершить	Вызывает деструктор объектов без освобождения памяти, в которой хранился объект.
max_size	Возвращает число элементов типа Type , которые могут быть выделены объектом класса allocator в пределах имеющейся свободной памяти.
повторно привязать	Структура, позволяющая распределителю, предназначенному для объектов одного типа, выделять память для объектов другого типа.

Операторы

Имя	Описание
Оператор =	Назначает один объект allocator другому объекту allocator .

адрес

Находит адрес объекта, значение которого задано.

Параметры

Val
Константное или неконстантное значение объекта, адрес которого ищется.

Возвращаемое значение

Константный или неконстантный указатель на найденный объект соответственно константного или неконстантного значения.

Remarks

Функции элементов возвращают адрес Val в форме, которую указатели должны принимать для выделенных элементов.

Пример

памяти

Выделяет блок памяти, достаточный для хранения по крайней мере некоторого указанного числа элементов.

Параметры

count
Количество элементов, для которых необходимо выделить достаточный объем памяти.

_Hint
Константный указатель, который может помочь объекту allocator удовлетворить запрос хранилища, найдя адрес объекта, выделенного до запроса.

Возвращаемое значение

Указатель на выделенный объект или значение null, если память не была выделена.

Remarks

Функция-член выделяет хранилище для массива элементов count типа Type , вызывая оператор New (Count). Она возвращает указатель на выделенный объект. Аргумент hint помогает некоторым распределителям улучшить расположение ссылок; недопустимый вариант — это адрес объекта, выделенный ранее тем же объектом allocator, который еще не был освобожден. Чтобы не предоставлять подсказок, используйте аргумент пустого указателя.

Пример

выделен

Освобождает указанное число объектов из памяти, начиная с заданной позиции.

Параметры

указатель
Указатель на первый объект, который должен быть освобожден из хранилища.

count
Количество объектов для освобождения из хранилища.

Remarks

Функция-член освобождает хранилище для массива объектов счетчика типа Type , начиная с ptr, путем вызова operator delete(ptr) . Указатель ptr должен быть возвращен ранее путем вызова метода allocate для объекта распределителя, который сравнивает * этот объект, выделяя объект массива такого же размера и типа. deallocate никогда не создает исключений.

Пример

Пример использования этой функции-члена см. в разделе allocator::allocate.

завершить

Вызывает деструктор объектов без освобождения памяти, в которой хранился объект.

Параметры

указатель
Указатель, обозначающий адрес уничтожаемого объекта.

Remarks

Функция-член уничтожает объект, обозначенный ptr, путем вызова деструктора ptr->Type::

Пример

difference_type

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

Remarks

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

Пример

max_size

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

Возвращаемое значение

Количество элементов, которые могут быть выделены.

Пример

Оператор =

Назначает один объект allocator другому объекту allocator.

Параметры

Правильно
Объект allocator для назначения другому такому объекту.

Возвращаемое значение

Целочисленный тип без знака, который может представлять длину любой последовательности, которую allocator может выделить объект типа.

Не так давно услышал о том, что существует способ управлять памятью самому, а не использовать, например, new и delete . Может кто-нибудь сможет осветить эту тему поподробнее, и привести какой-нибудь пример кода на С или С++, так как в интернете нашел мало информации на эту тему.

27.2k 10 10 золотых знаков 47 47 серебряных знаков 108 108 бронзовых знаков

Функциональность оператора new фактически сводится к

Вызову функции выделения "сырой" памяти требуемого размера
Инициализации объекта в этой "сырой" памяти

Никто вам не запрещает выполнять эти шаги самостоятельно: выделять "сырую" память любым удобным для вас способом, а затем инициализировать объект в этой памяти при помощи placement-new

При выделении памяти в общем случае следует позаботиться не только об ее размере, но и о соблюдении требований выравнивания.

Удаление объекта повторяет функциональность оператора delete , т.е. делается через синтаксис вызова псевдо-деструктора и вашу же функцию освобождения "сырой" памяти

А если ваша задача выходит за рамки функциональности голого new и delete , и, например, предполагает создание своих аллокаторов для стандартных контейнеров, то это уже несколько другая история.

67.4k 3 3 золотых знака 56 56 серебряных знаков 132 132 бронзовых знака @Philippe: Это синтаксис placement-new . Обратите внимание на круглые скобки с аргументом raw внутри. Это совсем не то, что "обычное" new . А с помощью __attribute __ ((cleanup (x))) (gcc,clang) можно делать собственные умные переменные, на подобии unique_ptr , в добавление к собственной реализации new. И собственный аллокатор ИМХО имеет смысл писать с учётом сборщика мусора, в этом ещё есть какой-то смысл. Не надо в C++ делать "умные переменные" через __attrbiute__((cleanup(fn))) , это костыль для C, потому что там нем деструкторов. Идиома в C++ называется RAII.

Прежде всего, почему динамическое управление памятью медленное занятие:

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

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

Создаем структуру, которая имеет несколько полей: base_pointer - указатель на выделенный участок памяти при помощи стандартной библиотечной функций, size - размер выделенной памяти, offset - смещение, относительно последнего выделения памяти, уже нашим собственным аллокатором.

Python многое делает за нас. Мы привыкли не заботиться об управлении памятью и о написании соответствующего кода. Пусть эти процессы и скрыты, но без их понимания трудно подготовить производительный код для высоконагруженных задач. В этой статье мы рассмотрим модель памяти Python и то, как интерпретатор Python взаимодействует с оперативной памятью компьютера.

Диспетчер памяти: «командовать парадом буду я»

Python — это интерпретируемый язык программирования, поэтому перед запуском программы код на языке Python компилируется в машиночитаемые инструкции — байт-код . Инструкции байт-кода интерпретируются виртуальной машиной, определяемой реализацией языка, например, стандартной — CPython .

Доклад Егора Овчаренко «Устройство CPython» поможет разобраться в стандартной реализации Python

Оговоримся, что CPython не взаимодействует напрямую с регистрами и ячейками физической памяти — только с ее виртуальным представлением. В начале выполнения программы операционная система создает новый процесс и выделяет под него ресурсы. Выделенную виртуальную память интерпретатор использует для 1) собственной корректной работы, 2) стека вызываемых функций и их аргументов и 3) хранилища данных, представленного в виде кучи .

В отличие от C/C++, мы не можем управлять состоянием кучи напрямую из Python. Функции низкоуровневой работы с памятью предоставляются Python/C API , но обычно интерпретатор просто обращается к хранилищу данных через диспетчер памяти Python (memory manager).

Диспетчер памяти — своеобразный портье, который регистрирует и расселяет гостей отеля. Каждый постоялец получает ключ с номером комнаты, так что ни один из гостей не может заселиться не в свой номер. Две программы не могут одновременно записать переменную в одно место виртуальной памяти.

Фактически за это отвечает даже не диспетчер задач, который ожидает гостей за регистрационной стойкой, а GIL — глобальная блокировка интерпретатора. GIL гарантирует: в один и тот же момент времени байт-код выполняется только одним потоком. Главное преимущество — безопасная работа с памятью, а основной недостаток в том, что многопоточное выполнение программ Python требует специфических решений.

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

Организация доступной виртуальной памяти

Непосредственно с оперативной памятью взаимодействует распределитель сырой памяти (raw memory allocator). Поверх него работают аллокаторы, реализующие стратегии управления памятью, специфичные для отдельных типов объектов. Объекты разных типов — например, числа и строки — занимают разный объем, к ним применяются разные механизмы хранения и освобождения памяти. Аллокаторы стараются не занимать лишнюю память до тех пор, пока она не станет совершенно необходимой — этот момент определен стратегией распределения памяти CPython.

Python использует динамическую стратегию, то есть распределение памяти выполняется во время выполнения программы. Виртуальная память Python представляет иерархическую структуру, оптимизированную под объекты Python размером менее 256 Кб:

Арена — фрагмент памяти, расположенный в пределах непрерывного блока оперативной памяти объемом 256 Кб. Объекты размером более 256 Кб направляются в стандартный аллокатор C.
Пул — блок памяти внутри арены, занимающий 4 Кб, что соответствует одной странице виртуальной памяти. То есть одна арена включает до 256/4 = 64 пулов.
Блок — элемент пула размером от 16 до 512 байт. В пределах пула все блоки имеют одинаковый размер. Размер блока определяется тем, сколько байт требуется для представления конкретного объекта. Размеры блоков кратны 16 байт. То есть существует всего 512/16 = 32 классов ( size class ) блоков. То есть в одном пуле, в зависимости от класса, может находиться от 8 до 256 блоков.

Блок содержит не более одного объекта Python и находится в одном из трех состояний:

untouched — блок еще не использовался для хранения данных;
free — блок использовался механизмом памяти, но больше не содержит используемых программой данных;
allocated — блок хранит данные, необходимые для выполнения программы.

В пределах пула блоки free организованы в односвязный список с указателем freeblock . Если аллокатору для выделения памяти не хватит блоков списка freeblock , он задействует блоки untouched . Освобождение памяти означает всего лишь то, что аллокатор меняет статус блока с allocated на free и начинает отслеживать блок в списке freeblock .

Пул может находиться в одном из трех состояний: used (занят), full (заполнен), empty (пуст). Пустые пулы отличаются от занятых отсутствием блоков allocated и тем, что для них пока не определен size class . Пулы full полностью заполнены блоками allocated и недоступны для записи. Стоит освободиться любому из блоков заполненного пула — и он помечается как used .

Пулы одного типа и одного размера блоков организованы в двусвязные списки. Это позволяет алгоритму легко находить доступное пространство для блока заданного размера. Алгоритм проверяет список usedpools и размещает блок в доступном пуле. Если в usedpools нет ни одного подходящего пула для запроса, алгоритм использует пул из списка freepools , который отслеживает пулы в состоянии empty .

Арена

Арены содержат пулы любых видов и организованы в двусвязный список usable_arenas . Список отсортирован по количеству доступных пустых пулов. Чем меньше в арене таких пулов, тем она ближе к началу списка. Для размещения новых данных выбирается область, наиболее заполненная данными.

Информацию о текущем распределении памяти в аренах, пулах и блоках можно посмотреть, запустив функцию sys._debugmallocstats() :

Чтобы не произошло утечки памяти, диспетчер памяти должен отследить, что вся выделенная память освободится после завершения работы программы. То есть при завершении программы CPython дает задание очистить все арены.

Именно количество используемых арен определяет объем оперативной памяти, занимаемой программой на Python — если в арене все пулы в состоянии empty , СPython делает запрос на освобождение этого участка виртуальной памяти. Но уже понятно: чтобы пулы стали empty , все их блоки должны быть free или untouched . Получается, нужно понять, как CPython освобождает память.

Освобождение памяти: счетчик ссылок, сборщик мусора

Для освобождения памяти используются два механизма: счетчик ссылок и сборщик мусора.

Всё в Python является объектами, а прародителем всех типов объектов в реализации CPython является PyObject . От него наследуются все остальные типы. В PyObject определены счетчик ссылок и указатель на фактический тип объекта. Счетчик ссылок увеличивается на единицу, когда мы создаем что-то, что обращается к объекту, например, сохраняем объект в новой переменной. И наоборот, счетчик уменьшается на единицу, когда мы перестаем ссылаться на объект.

Счетчик ссылок любого объекта можно проверить с помощью sys.getrefcount() . Учтите, что передача объекта в getrefcount() увеличивает счетчик ссылок на 1, так как сам вызов метода создает еще одну ссылку. Когда счетчик уменьшается до нуля, происходит вызов аллокатора для освобождения соответствующих блоков памяти.

Однако счетчик ссылок неспособен отследить ситуации с циклическими ссылками. К примеру, возможна ситуация, когда два объекта ссылаются друг на друга, но оба уже не используются программой. Для борьбы с такими зависимостями используется сборщик мусора ( garbage collector ).

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

Заключение

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

Обращайте внимание на работу с неизменяемыми объектами . К примеру, вместо использования оператора + для соединения строк используйте методы .join() , .format() или f-строки.
Избегайте вложенных циклов. Создание сложных вложенных циклов приводит к генерации чрезмерно большого количества объектов, занимающих значительную часть виртуальной памяти. Большинство задач, решаемых с помощью вложенных циклов, разрешимы методами модуля itertools.
Используйте кэширование . Если вы знаете, что функция или класс используют или генерируют набор однотипных объектов, применяйте кэширование . Часто для этого достаточно добавить всего лишь один декоратор из библиотеки functools .
Профилируйте код. Если программа начинает «тормозить», то профилирование — самый быстрый способ найти корень всех зол.

На ранних этапах работы с кодом Python можно вполне обойтись стандартными средствами Python. Но по мере разрастания кодовой базы и приближения к коммерческому использованию кода производительность становится одним из ключевых факторов. Многие задачи, связанные с производительностью Python, лежат в области понимания устройства инструмента и конкретной реализации языка. Не пожалейте времени на изучение исходного кода CPython, находящегося в свободном доступе в репозитории на GitHub .

На Python создают прикладные приложения, пишут тесты и бэкенд веб-приложений, автоматизируют задачи в системном администрировании, его используют в нейронных сетях и анализе больших данных. Язык можно изучить самостоятельно, но на это придется потратить немало времени. Если вы хотите быстро понять основы программирования на Python, обратите внимание на онлайн-курс «Библиотеки программиста». За 30 уроков (15 теоретических и 15 практических занятий) под руководством практикующих экспертов вы не только изучите основы синтаксиса, но и освоите две интегрированные среды разработки (PyCharm и Jupyter Notebook), работу со словарями, парсинг веб-страниц, создание ботов для Telegram и Instagram, тестирование кода и даже анализ данных. Чтобы процесс обучения стал более интересным и комфортным, студенты получат от нас обратную связь. Кураторы и преподаватели курса ответят на все вопросы по теме лекций и практических занятий.

Читайте также: