Что такое аллокатор c

Неудаляющий аллокатор

Программы на C могут выделять память под объекты двумя способами: на стэке (stack allocation) и на куче (heap allocation).

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

Во втором подходе программа вежливо просит операционную систему выделить сколько-то байт памяти как ей удобно и вернуть на них указатель, а также гарантировать, что другие процессы не будут иметь к ней никакого доступа (хотя компьютер — вещь сложная, и это не всегда получается). В этом случае программист сам должен думать об удалении объектов, когда они становятся не нужны. Для создания объектов таким образом нужно вызвать оператор new , а при удалении вызывать оператор delete .

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

Пожертвовав «правильным» освобождением памяти, можно значительно ускорить — иногда в полтора-два раза — скорость работы работы структур данных, которые используют delete (в частности, большинство контейнеров STL).

Для этого можно глобально переопределить new и delete :

 const int max_memory = 1e8; int pos_memory = 0; char memory[max_memory]; void* operator new(size_t n)  char *res = memory + pos_memory; pos_memory += n; assert(pos_memory  max_memory); return (void*) res; > void operator delete(void *)<>

Оператор new принимает количество байт памяти, которые требуется выделить, и возвращает указатель на выделенную память — у нас он возвращает и увеличивает конец «стэка».

Оператор delete принимает указатель на начало памяти и освобождает её. В нашем случае, он просто не делает ничего.

Базовые концепции аллокаторов

Находясь в поисках какой-то агрегированной информации о стандартных приёмах, используемых при проектировании кастомных аллокаторов, я обнаружил, что существует достаточное количество статей о том, как аллокаторы работают в C++, каких-то базовых вариантах или наоборот очень специфических версиях, но ничего достаточно общего. Попался только замечательный доклад замечательного Андрея Александреску про неправильную архитектуру std::allocator и собственно базовые концепции построения своего нового самого крутого в мире аллокатора. Эта статья является довольно вольным переводом второй части его выступления с моими небольшими дополнениями. Конечно же, категорически рекомендую посмотреть оригинальный доклад, но, если вы любитель текстовых версий, прошу под кат.

Огромной проблемой аллокаторов в C++ является то, что они оперируют только указателями и следить за размерами должны сами. Невозможность подсказать компилятору размер удаляемой памяти вынуждает его позаботиться об этом самому(часто размеры сохраняются перед выделенным блоком памяти). Потому далее будем оперировать вот такими структурами:

struct Blk < void* ptr; size_t size; >;

Одной из проблем инструментов стандартной библиотеки( malloc / new / std::allocator ) является то, что они предназначены для общего использования. Они обязаны одинаково хорошо работать на размерах от 1 байта до 10Гб, в то время как зная некоторые особенности своих нужд, разработчик может применять более оптимальные стратегии поведения. Потому существует множество нестандартных аллокаторов, применимых в различных ситуациях. Однако также частым приёмом при реализации нового аллокатора является применение композиции нескольких аллокаторов. Если взглянуть на документацию популярных аллокаторов, то можно заметить, что почти всегда они построены на применении нескольких абсолютно различных стратегий управления памятью в зависимости от некоторых условий(чаще всего от размеров блоков памяти). Рассмотрим самые популярные концепции проектирования аллокаторов и способы применения композиций.

Null-аллокатор

Самым простым примером нестандартного аллокатора является null-аллокатор. На запрос выделить память он возвращает nullptr , а на запрос удаления памяти проверяет(корректнее всего сделать assert), является ли этот указатель nullptr , потому что аллокатор может принимать лишь то, что он возвращал. Можно сказать, что этот аллокатор имеет бесконечное количество памяти. Или не имеет памяти вообще. Вы свободны в своём выборе 🙂

Может появиться вопрос, зачем такое нужно. Представим, что мы спроектировали аллокатор, использующий 10 разных стратегий для разных размеров требуемой памяти. Но для очень больших размеров мы понятия не имеем, как лучше всего будет поступать. Используем null-аллокатор! Можно сказать, что он выполняет роль терминальной стратегии.

Pool-аллокатор

Полезной концепцией является pooled-аллокаторы: выделяем некоторый участок памяти и работаем только с ним, не выделяя больше памяти через malloc / new .

Удобным может быть такой приём: зная, что за всё время использования программы она суммарно не потребует более, например, 1Гб памяти, можно выделить блок такого размера в начале. Выделять память будем согласно некоторой стратегии, а удалять не будем ничего, чтобы не тратить на это время. При достаточном количестве памяти и недостаточном количестве времени мы можем добиться нужной эффективности. Аллокаторы с подобной стратегией называют monotonic-аллокаторами.

Fallback-аллокатор

Простейшей композицией является fallback-аллокатор:

template class FallbackAllocator : private Primary , private Fallback < public: Blk allocate(size_t); void deallocate(Blk); >;

Ведёт он себя так: «обычно я буду использовать primary-стратегию, но в случае, если что-то пойдёт не так, fallback-стратегию».

Отметим, что использование наследования тут особенно полезно в случае stateless аллокаторов(не хранящих никакой метаинформации), что позволяет компилятору задействовать Empty Base Class Optimization.

Покажем реализацию методов fallback-аллокатора. В случае allocate нет ничего нетривиального:

template Blk FallbackAllocator::allocate(size_t n)

В случае же deallocate появляется вопрос: кто должен удалять пришедшую память, ведь нельзя отдавать в аллокатор указатель, который он не возвращал? Становится понятно, что интерфейса только с двумя методами выделения/удаления памяти недостаточно. Нужен ещё один: метод owns , который будет подсказывать, владеет ли аллокатор указателем. При таком дополнении реализовать deallocate становится просто:

template void FallbackAllocator::deallocate(Blk b)

Обычно метод owns — это простой range-тест: входит ли пришедший указатель в интервал указателей, которыми владеет аллокатор.

Как видим, этот метод точно нужно реализовать primary-аллокатору. Но нужно ли его реализовывать для fallback? Для деаллокации нет. Но правилом хорошего тона при такой реализации является реализовать метод owns и для всего FallbackAllocator:

template bool FallbackAllocator::owns(Blk b)

Причём C++ имеет замечательную особенность: в случае, если fallback-аллокатор не реализует метод owns и FallbackAllocator::owns никогда не будет вызван, программа успешно скомпилируется и корректно отработает(по аналогии со SFINAE можно сказать, что это Method Definition Failure Is Not An Error). Потому разработчик сам вправе решать, необходимо ли ему реализовывать требуемый метод в зависимости от своих потребностей.

Чаще всего в качестве fallback-аллокатора используется malloc : мы попробовали несколько различных стратегий, у нас ничего не вышло, тогда обратимся к стандартному способу, причём это нормально, если fallback-аллокатор ничего не знает об указателях, которыми он владеет.

Stack-аллокатор

Stack-аллокатор — аллокатор, выделяющий память на стеке(неожиданно, правда?). Как известно, работа со стеком гораздо быстрее работы с кучей, потому такой приём может значительно улучшить перфоманс вашей программы.

template class StackAllocator < char d_[s]; // буфер char* p_; // указатель на начало свободной памяти StackAllocator() : p_(d_) <>. >;

Много говорить про него не будем, так как это довольно известная концепция. Отметим только несколько интересных фактов.

Понятно как реализовать метод owns :

bool owns(Blk b)

В силу концепции стека удалять можем только последний аллоцированный блок. Но ещё получаем бесплатную фичу: удаление всех данных происходит за О(1). Достаточно просто переместить указатель на начало буфера.

Учитывая, что размер памяти в нём ограничен, можем создать удобную композицию с использованием fallback-аллокатора:

template class StackAllocator ; class Mallocator ; using MyAlloc = FallbackAllocator< StackAllocator, Mallocator >;

Freelist

Freelist всегда имеет основной аллокатор, который выделяет/удаляет память в большинстве случаев. Сам он вступает в дело, когда происходят деаллокации некоторого конкретного размера, который нас интересует. В самом начале указатель на начало списка пуст, но в случае, когда удаляется интересный блок, он просто добавляется в лист блоков. В следующий раз когда требуется выделить блок какого-то специфического размера и лист не пуст, берём блок оттуда. Теперь мы не тратим время не выделение памяти!

Однако есть и недостатки: память, попавшая в лист свободных блоков, никогда не освободится(по крайней мере до завершения программы). Мы могли выделить 10000 блоков по 64 байта, и все они находятся в аллокаторе. Получили очень фрагментированную память.

Также из-за некоторых проблем с выполнением во многопоточной среде, часто реализуют lock free list как первый уровень защиты. Часто каждому потоку создают свой freelist и делают глобальный на всякий случай.

Однако несмотря на все недостатки, freelist — довольно мощный паттерн, который очень хорош для объектов небольшого размера. Пусть он и очень сложный.

Не будем разбирать полную реализацию т.к. идейно она ничего интересного не представляет, но отметим один момент в deallocate :

template class Freelist < Alloc parent_; struct Node < Node* next; >root_; void deallocate(Blk b) < if (b.length != Size) return parent_.deallocate(b); auto p = (Node*)b.ptr; p.next = root_; root_ = p; >>;

Учитывая, что это свободная память, и данные в ней уже не нужны, мы абсолютно не тратимся на память для хранения информации о следующем блоке, ведь можно хранить её прямо в этой памяти. Потому вся дополнительная память — это всего одно поле root_ .

Рассмотрим некоторые улучшения такого аллокатора:

• Предоставлять память в некотором диапазоне. Если мой freelist хорош в управлении блоками размером 1Кб, должен ли он отдавать блок при запросе 900 байт? Возможно мы сможем получить некоторый прирост эффективности. Потому иногда устанавливают некоторые границы(например в нашем случае можно отдавать блок при запросе в диапазоне от 513 байт до 1Кб).
• Аллокация сразу нескольких объектов. Вместо аллоцирования одного объекта, можно выделять память сразу для нескольких, что позволяет хранить больше объектов рядом друг с другом. Однако сложно понимать, в какой момент уже можно удалять этот блок.
• Установка верхней границы размера листа со свободными блоками. Это поможет бороться с фрагментацией памяти из-за невозможности бесконечного роста.

Учитывая улучшения, можно представить, как часто выглядит freelist:

Freelist alloc;

Удобно, что использование freelist возможно с любым другим аллокатором(возможно, при некоторых доработках). Например при использовании со stack-аллокатором мы получаем возможность работать с блоками внутри последнего.

Affix-аллокатор

Иногда бывает полезным добавить некоторую метаинформацию до и после выделенного блока. Например мы можем байтами подписать блок и использовать их в качестве цифровой подписи: если при деаллокации подписи не совпадают, значит что-то пошло не так. Или до и после блока оставить память размером 1Кб и при деаллокации следить, что состояние этих участков не изменилось, иначе был выход за границы памяти. Похожий принцип используется в санитайзерах памяти.

template class AffixAllocator;

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

Довольно частым приёмом является хранение информации о названии файла и номера строки, в которой был запрос на выделение памяти.

Stats-аллокатор

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

template class StatsAllocator;

BitmappedBlock

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

template class BitmappedBlock;

Недостатками такого подхода является фиксированность размера блока, что может привести к фрагментации, и некоторые проблемы при работе в многопоточной среде. Нет ничего с одними только достоинствами 🙂

Cascading-аллокатор

Чаще всего BitmappedBlock управляет участками памяти внутри большого блока(например множество участков по 64 байта внутри блока размером 1Мб). Но что делать, если в какой-то момент 1Мб перестало хватать? Нужно выделить новый большой блок и создать новый BitmappedBlock для него. Этим и занимается Cascading-аллокатор. Он лениво будет создавать новые участки памяти, пока вам это нужно, и будет удалять неиспользуемые участки.

Однако его реализация является не самой тривиальной из-за сложной логики поведения.

template class CascadingAllocator; . auto ca = CascadingAllocator(< return BitmappedBlock(); >);

Segregator

Segregator позволяет применять различные стратегии управления памятью в зависимости от некоторой точки отсчёта:

template struct Segregator;

Удобно, что для segregator дочерним аллокаторам не нужно реализовывать метод owns , потому что размер удаляемой памяти можно сравнить с точкой отсчёта.

Эта композиция очень легко реализуется, что является замечательным дополнением к её мощности.

Segregator можно использовать в композиции с самим собой:

using MyAlloc = Segregator, MediumAllocator>, Mallocator>;

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

Bucketizer

Такая структура позволяет для каждого блока размером step в диапазоне размеров от min до max создавать отдельный аллокатор.

template struct Bucketizer;

Часто используются конструкции, позволяющие оперировать блоками, размеры которых растут логарифмически(1, 2, 4, 8, . ).

Заключение

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

Как бонус пример реального аллокатора из продакшн-кода:

using FList = Freelist; using A = Segregator< 8, FList, 128, Bucketizer, 256, Bucketizer, 512, Bucketizer, 1024, Bucketizer, 2048, Bucketizer, 3584, Bucketizer, 4072 * 1024, CascadingAllocator, Mallocator >;

• аллокаторы
• управление памятью

Распределитель памяти для небольших объектов

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

Архитектура

Если это слово можно применить к такой небольшой системе — замечательно, если нет — мне все равно.

Обзор

Реализация очень проста в понимании, но использует не очевидные фишки языка c++ (всего одну, о ней в последнем пункте параграфа). Примечательно то что, даже в такой маленькой системе ужился CQRS. В отличие от системного этот аллокатор является stateful, но из-за особенности его использования, никаких дополнительных телодвижений пользователю делать не приходится, все работает из коробки. Нацелен он, как следует из названия, на небольшие объекты, которые аллоцируются непосредственно через new на протяжении работы программы, или порядок этих аллокаций не определен. Если необходимо единовременное выделение большого количества объектов, арена будет уместнее.

Словарь:

Небольшой объект — controversial topic. А. Александреску считает объекты меньше 64 байт небольшими, я буду считать так же. Аллоцировать объект, аллоцировать блок — каким-либо образом выделить память под объект и явно либо неявно вызвать placement new по этой памяти. Деаллоцировать объект, деаллоцировать блок — вызвать деструктор объекта через delete, который в свою очередь вызовет нужный deleter для выделенной памяти, либо системный — delete(free), либо переопределенный пользователем operator delete; Аллоцировать память, аллоцировать чанк — выделить непрерывный участок сырой памяти непосредственно через new (malloc). Деаллоцировать память, деаллоцировать чанк — освободить непрерывный участок памяти через системный delete (free).

Chunk. К успеху с самого дна

На нижнем уровне иерархии находится chunk — объект, владеющей одним непрерывным участком памяти, чанки запрашивают память у системного аллокатора и условно разделят на блоки одного размера. Блок — участок памяти, который чанк отдает в пользование. Размер блока и их количество определяется в момент конструирования чанка и не меняется никогда. Освобождение памяти через оператор delete происходит только в момент удаления чанка. Блоки объединены в хитрый связный список, в первом байте каждого свободного блока хранится индекс следующего свободного блока. Индексом первого блока владеет чанк. Таким образом, аллокация объекта происходит за O(1); Операция аналогична операции удаления головы в односвязном списке. Деаллокация объекта так же занимает фиксированное время, так как по указателю на блок памяти легко вычислить его индекс и вернуть блок в список, в целом процедура аналогична вставлению нового элемента в голову связного списка:

inline void chunk::deallocate(void* ptr, std::size_t block_size) noexcept < std::size_t byte_index = (char*)ptr - data; // find first byte of the memory block to be deleted unsigned char block_index = byte_index / block_size; // find the index of the block to be deleted data[byte_index] = first_free_block; // write in the first byte of this block the index of the next free first_free_block = block_index; // update head of the linked list free_blocks_count++; // increment free blocks count >

Так как для индекса используется 1 байтовое беззнаковое целое, то максимальное количество блоков 256. Минимальный размер блока так же равняется одному байту, если бы мы использовали классические списки с индексом, то энтропия памяти могла достигать 50%. У данного подхода почти нет минусов, время выделения-удаления не ухудшается но дополнительная память почти не требуется.

Fixed allocator. Выше сильнее.

Fixed Allocator — FA

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

Если свободных чанков нет — FA создает новый и вставляет в конец вектора, обновляя индекс свободного чанка.

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

SM Allocator. Снова синглтон, или по заветам моего любимого(нет) программиста

Small Object Allocator — SMA.

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

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

Ленивый — SMA инициализируется с пустым вектором, который будет заполняться по мере поступления запросов на выделение объекта соответствующего размера. Такой подход хорош, когда приложение использует мало размеров объектов или память сильно ограничена. Аллокаторы хранятся в отсортированном виде, поиск нужного FA занимает O(logN), что в общем то хорошо, даже когда вектор заполнен полностью, так как вариантов размеров не может быть слишком много.

Не ленивый — SMA инициализруется с уже заполненным вектором, таким образом поиск нужного аллокатора занимает O(1), но может использоваться дополнительная память. Такой подход идеален для систем в которых используются небольшие объекты всех размеров, я выбрал эту реализацию.

Анализ: если заглянуть вперед на SMO станет понятно для каких объектов это спроектировано. Мы всегда аллоцируем полиморфные объекты и выравнивание объектов на куче у нас не отключено. Значит на x32 минимальный размер полиморфного объекта равен размеру указателя на vmt и равен его минимальному выравниванию(на самом деле и максимальному) — 4 байта, с учетом выравнивания получается 64 / 4 = 16 объектов разного размера. Совсем немного, незачем экономить на спичках, делаем не ленивый SMA.

Small Object. Мал, удал и хитёр.

Small Object — SM

Самый маленький и самый важный элемент. Все что нужно для использования SMA — наследовать SM!

class small_object < public: virtual ~small_object() = default; static void* operator new(std::size_t size); static void operator delete(void* ptr, std::size_t size); >; struct user_object : small_object < unsigned char b; >;

Здесь сокрыта главная хитрость, оператор new такой же как и всегда, не обсуждаем. Оператор delete намного интереснее: он принимает не только указатель на память которую надо освободить но и размер памяти, то есть размер объекта. Откуда он его узнает? Представим что мы пишем компилятор, и нужно решить проблему: как передать в operator delete размер объекта? Объект small_object имеет виртуальный деструктор и это важно, когда мы запускаем следующий код:

small_object* ptr = new user_struct; delete ptr;

Последовательность вызовов следующая:

• Вызов деструктора user_object — здесь он тривиален
• Вызов деструктора базового класса — small_object(), с передачей в него размера исходного класса. Если базовых классов несколько — вызовы идут вверх по иерархии. Если наследование множественное — в порядке наследования (с++11 этого не гарантирует но нам и не важно).
• Вызов operator delete(this, size) в деструкторе small_object.

user_object::~user_object(user_object* this) < // * some activity // * // * end of activity ~small_object(sizeof(this, user_object)); > small_object::~small_object(small_object* this, std::size_t size) < // activity operator delete(this, size); >

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

Анализ

Анализ производительности аллокатора. В идеальном случае, когда в системе присутствуют объекты всех допустимых размеров, и их количество меньше 256, аллокация и деаллокация объектов происходит за O(1), и намного быстрее чем new/delete; В случае, когда в системе много объектов одного размера и спектр размеров узок, есть незначительный — около 64 байт на каждый свободный FA, в нашем случае FA всего 16, значит в худшем случае будет жить паразитный 1K памяти — пренебрежимо мало. Выделение и удаления будут происходить за: τ = O(Max(Count(Object size))) Не так уж и плохо, выделять миллион одинаковых элементов таким образом совсем глупо, для этого есть арена.

Многопоточность

Добавить поддержку многопоточности просто, защищаем аллокацию блока критической секцией, и готово. Однако, есть несколько проблем: операторы new/delete должы быть статические, поэтому получается не слишком красиво:

std::mutex Mutex; void* small_object::operator new(std::size_t size) < std::lock_guard lock(Mutex); return small_object_allocator::instance().allocate(size); >

Вот и всё! С удалением поступаем точно так же. Однако я сделал иначе: во первых, не использовал policy-based-design как это делает А.Александреску, не хочу делать объект тяжеловесным, во вторых добавил диспатч по параметрам конфигурации: поддерживать многопоточность или нет. Вот почему: SMA плохо подходит для большого количества потоков, пытающихся выделять и удалять ресурсы единовременно. В таком случае лучше использовать несколько локальных SMA. SMA хорошо справляется с двумя-тремя потоками, которые редко встречаются в критической секции, поэтому я предлагаю использовать классические спинлоки на std::atomic_flag (CAS). Хотя современные мьютексы и являются гибридами — занимают очередь после нескольких проверок ресурса, но тесты говорят они значительно хуже.

Добавляем паттерн-матчинг по параметрам конфигурации, define-oriented programming и готово:

#ifdef MULTITHREADING # if THREADING_POLICY == SPINLOCK # define LOCK const std::lock_guard lock(SpinLock); # else # define LOCK const std::lock_guard lock(Mutex); # endif #else # define LOCK #endif namespace hope::memory < void* small_object::operator new(std::size_t size) < LOCK return small_object_allocator::instance().allocate(size); > >

Аллокаторы памяти

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

Отслеживать
28.5k 12 12 золотых знаков 58 58 серебряных знаков 118 118 бронзовых знаков
задан 26 дек 2018 в 17:45
713 7 7 серебряных знаков 29 29 бронзовых знаков
26 дек 2018 в 17:46

А что Вас конкретно интересует? Есть много способов управления памятью помимо new и delete. Выше, вот, дали ссылку на написание своего аллокатора. Рекомендую почитать так же про идиому RAII : ru.wikipedia.org/wiki/…

27 дек 2018 в 8:22
Из внешних аллокаторов заслуживает внимания llalloc locklessinc.com/articles/allocator_tricks
2 янв 2019 в 9:53

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

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

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

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

// Создание объекта типа `T` void *raw = my_malloc(sizeof(T)); //  

pt->~T(); my_free(pt); 

struct linear_allocator_t < void* base_pointer; size_t size; size_t offset; >; typedef struct linear_allocator_t linear_allocator_t; 

int la_init(linear_allocator_t* allocator, size_t memory_size) < if (memory_size == 0) return 0; allocator->offset = 0; allocator->size = memory_size; allocator->base_pointer = malloc(memory_size); return allocator->base_pointer != NULL; > void la_allocate(linear_allocator_t* allocator, size_t allocated_size) < // Проверяем на достаточное количество памяти для выделения if (allocator->offset + allocated_size > allocator->size) return NULL; // Проверяем на не нулевой размер и на выравнивание if ( (allocated_size == 0) || (allocator->size % allocated_size != 0) ) return NULL; size_t allocated_pointer = (size_t) allocator->base_pointer + allocator->offset; allocator->offset += allocated_size; return (void*) allocated_pointer; > // Данный аллокатор не поддерживает данную операцию(функция добавлена в качестве пояснения о существовании текущей операции) void la_free(linear_allocator_t* allocator, void* pointer) < assert(false && "Current allocator does not support current method. Use la_reset()"); >void la_reset(linear_allocator_t* allocator) < free(allocator->base_pointer); > 

// Тестовая структура, только для проверки struct vector_4d_t < double x, y, z, w; >; typedef struct vector_4d_t vector_4d_t; int main() < // В данном примере фрагментация отсутствует linear_allocator_t allocator; la_init(&allocator, sizeof(vector_4d_t) * 100); for (int32_t i = 0; i < 100; i++) < vector_4d_t* vector = (vector_4d_t*) la_allocate(&allocator, sizeof(vector_4d_t)); vector->x = vector->y = vector->z = vector->w = i; > la_reset(&allocator); return EXIT_SUCCESS; >