[Перевод] Базовые концепции аллокаторов
Находясь в поисках какой-то агрегированной информации о стандартных приёмах, используемых при проектировании кастомных аллокаторов, я обнаружил, что существует достаточное количество статей о том, как аллокаторы работают в 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Гб памяти, можно выделить блок такого размера в начале. Выделять память будем согласно некоторой стратегии, а удалять не будем ничего, чтобы не тратить на это время. При достаточном количестве памяти и недостаточном количестве времени мы можем добиться нужной эффективности.
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) {
Blk r = P::allocate(n);
if (!r.ptr) r = F::allocate(n);
return r;
}
В случае же deallocate
появляется вопрос: кто должен удалять пришедшую память, ведь нельзя отдавать в аллокатор указатель, который он не возвращал? Становится понятно, что интерфейса только с двумя методами выделения/удаления памяти недостаточно. Нужен ещё один: метод owns
, который будет подсказывать, владеет ли аллокатор указателем. При таком дополнении реализовать deallocate
становится просто:
template
Blk FallbackAllocator::deallocate(Blk b) {
if (P::owns(b)) P::deallocate(b);
else F::deallocate(b);
}
Обычно метод owns
— это простой range-тест: входит ли пришедший указатель в интервал указателей, которыми владеет аллокатор.
Как видим, этот метод точно нужно реализовать primary-аллокатору. Но нужно ли его реализовывать для fallback? Для деаллокации нет. Но правилом хорошего тона при такой реализации является реализовать метод owns и для всего FallbackAllocator:
template
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
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
class StackAllocator {...};
class Mallocator {...};
using MyAlloc = FallbackAllocator<
StackAllocator<16384>,
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: