Находясь в поисках какой-то агрегированной информации о стандартных приёмах, используемых при проектировании кастомных аллокаторов, я обнаружил, что существует достаточное количество статей о том, как аллокаторы работают в 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 Primary, class Fallback>
class FallbackAllocator : private Primary , private Fallback { 
public: 
    Blk allocate(size_t); 
    void deallocate(Blk); 
};

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

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

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

template <class P, class F>
Blk FallbackAllocator::allocate(size_t n) { 
    Blk r = P::allocate(n); 
    if (!r.ptr) r = F::allocate(n); 
    return r; 
}

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

template <class P, class F>
void FallbackAllocator::deallocate(Blk b) { 
    if (P::owns(b)) P::deallocate(b); 
    else F::deallocate(b); 
} 

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

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

template  <class P, class F>
bool FallbackAllocator::owns(Blk b) { 
    return P::owns(b) || F::owns(b); 
}

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

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

Stack-аллокатор

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

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

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

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

bool owns(Blk b) {
    return d_ <= b.ptr && b.ptr < d_ + s;
}

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

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

template <size_t s>
class StackAllocator {...};

class Mallocator {...};

using MyAlloc = FallbackAllocator<
    StackAllocator<16384>,
    Mallocator
>;

Freelist

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

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

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

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

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

template  <class Alloс, size_t Size>
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 <A, // родительский аллокатор
    17, // используем для объектов размером от 17...
    32, // … до 32 байт
    8, // аллоцируем для 8 объектов за раз
    1024 // храним не более 1024 элементов
>alloc;

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

Affix-аллокатор 

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

template <class Alloc, class Prefix, class Suffix = void>
class AffixAllocator;

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

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

Stats-аллокатор

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

template <class Alloc, ulong flags>
class StatsAllocator;

BitmappedBlock

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

template <class Alloc, size_t blockSize>
class BitmappedBlock;

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

Cascading-аллокатор

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

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

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

Segregator

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

template <size_t threshold,
    class SmallAllocator,
    class LargeAllocator>
struct Segregator;

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

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

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

using MyAlloc = Segregator<4096,
    Segregator<128,
        Freelist<Mallocator, 0, 128>,
        MediumAllocator>,
    Mallocator>;

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

Bucketizer

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

template <class Alloc,
    size_t min, size_t max, size_t step>
struct Bucketizer;

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

Заключение

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

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

using FList = Freelist<Mallocator, 0, -1>;
using A = Segregator<
  8, FList<Mallocator, 0, 8>,
  128, Bucketizer<FList, 1, 128, 16>,
  256, Bucketizer<FList, 129, 256, 32>,
  512, Bucketizer<FList, 257, 512, 64>,
  1024, Bucketizer<FList, 513, 1024, 128>,
  2048, Bucketizer<FList, 1025, 2048, 256>,
  3584, Bucketizer<FList, 2049, 3584,512>,
  4072 * 1024, CascadingAllocator<decltype(newHeapBlock)>,
  Mallocator
>;