Аллокатор для небольших объектов

1-small-object-allocator.md

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

Дисклеймер

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

Архитектура

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

Обзор

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

2-small_object_diagram.png

3-chunk.md

Словарь:

Небольшой объект - 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
}

Схема чанка:

4-chunk.png

5-chunk-diagram-description.md

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

fixed-allocator.md

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);
    }
}

Тесты

TODO:

Привет, поправлю, пасиб)