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

#cpp #c #память

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

Ответы

Ответ 1

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


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


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

struct linear_allocator_t
{
    void* base_pointer;
    size_t size;
    size_t offset;
};

typedef struct linear_allocator_t linear_allocator_t;


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

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


Надеюсь, что мой ответ оказался вам полезным!


Ответ 2

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


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


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

// Создание объекта типа `T`
void *raw = my_malloc(sizeof(T)); // <- любой способ выделения памяти
T *pt = new(raw) T(параметры);    // <- инициализация объекта


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

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

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


Вот и все.

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