[Перевод] Создаем свою STL-совместимую реализацию std::allocator с лучшей производительностью05.02.2024 16:00

Реализация защиты от сбоев из-за фрагментации кучи и повышение скорости выполнения с помощью STL-альтернативы std::allocator, работающей с блоками памяти фиксированного размера.

В этой статье описывается реализация STL-совместимого аллокатора, ориентированного на выделение и высвобождение блоков памяти фиксированного размера. Предложенный аллокатор предотвращает сбои, вызванные фрагментированной кучей, и обеспечивает стабильное время выполнения выделения/высвобождения памяти. Моей главной целью при создании stl_allocator было устранение ошибок памяти. Вдобавок использование STL-совместимого блочного аллокатора открывает возможность использования функций стандартной библиотеки шаблонов (STL) C++ в проектах, в которых иначе это было бы невозможно.

Скачать исходный код — 20.6 KB

Введение

Это моя третья и последняя статья, посвященная аллокаторам, работающим с фиксированными блоками памяти, на Code Project. И на этот раз мы создадим полноценную альтернативу менеджеру памяти std::allocator из стандартной библиотеки C++, опираясь на основы, заложенные в первых двух статьях. 

Стандартная библиотека шаблонов (STL) — это мощная программная библиотека C++, предлагающая поддержку контейнеров и итераторов. Проблема с использованием библиотеки в критически важных или ограниченных по времени обработки проектах заключается не в самой STL — библиотека очень надежна. Проблема заключается в неограниченном использовании глобальной кучи (global heap). Стандартный аллокатор STL интенсивно использует кучу во время работы. Это представляет серьезную проблему для встраиваемых систем с ограниченными ресурсами. Встраиваемые устройства могут работать без остановки месяцами или даже годами, и в этом случае просто необходимо предотвратить сбои, вызванные фрагментацией кучи. К счастью, STL предоставляет возможность заменить std: allocator на аллокатор собственной разработки. 

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

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

std: allocator

STL-класс std::allocator реализует стратегию выделения и высвобождения памяти по умолчанию. Если вы взгляните на код класса-контейнера, такого как std::list, то увидите там аргумент шаблона по умолчанию std::allocator. В данном случае allocator<_Ty> — это шаблонный класс, разбирающийся с хлопотами аллокации для объектов _Ty.

template >
class list : public _List_val<_Ty, _Ax>
{
    // ...
}

Поскольку параметр шаблона _Ax по умолчанию принимает значение allocator<_Ty>, вы можете создать объект-список, не указывая аллокатор вручную. Объявление myList, как показано ниже, создает класс аллокатора для выделения/высвобождения значений int. 

std::list myList;

Для своих элементов и узлов контейнеры STL полагаются на динамическую память. Элемент (element) имеет размер вставленного объекта. В данном случае sizeof(int) — это память, необходимая для хранения одного элемента списка. Узел (node) отражает внутреннюю структуру, необходимую для связывания элементов вместе. Для std::list это двунаправленный связный список, хранящий, как минимум, указатели на следующий и предыдущий узлы. 

В то время, как размер элемента зависит от хранимых объектов, размер узла также зависит от используемого контейнера. Узел std::list может иметь другой размер, нежели узел std::map. В связи с этим STL-совместимый аллокатор должен уметь обрабатывать запросы на блоки памяти разного размера. 

STL-совместимый аллокатор должен придерживаться определенных требований к интерфейсу. Но эта статья не о том, как и почему работает API std::allocator — на просторах интернета есть множество ссылок, которые объяснят это куда лучше, чем я. Вместо этого я сосредоточусь на том, где разместить вызовы аллокации/деаллокации памяти в существующем интерфейсе класса stl_allocator, и предоставлю новые «x»-версии всех популярных контейнеров для упрощения использования.  

xallocator    

Большая часть работы представленного фиксированного STL-аллокатора с приходится на базовый класс xallocator, как описано в моей статье «Замена malloc/free быстрым аллокатором фиксированными блоками памяти». Как сказано в названии, этот модуль заменяет malloc/free новыми версиями xmalloc/xfree, работающими с блоками памяти фиксированного размера. 

С точки зрения пользователя эти новые функции работают так же, как и стандартные CRT-версии, за исключением работы с фиксированными блоками памяти. Вкратце, xallocator имеет два режима работы: статические пулы (static pools), когда вся память берется из заранее объявленной статической памяти, или блоки кучи (heap blocks), когда блоки берутся из глобальной кучи, но при высвобождении перерабатываются для последующего использования. Подробности реализации смотрите в вышеупомянутой статье. 

stl_allocator

Класс stl_allocator — это реализация STL-совместимого фиксированного аллокатора. Этот класс используется как альтернатива std::allocator. 

template 
class stl_allocator
{
public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;

    stl_allocator(){}
    ~stl_allocator(){}

    template  struct rebind { typedef stl_allocator other; };
    template  stl_allocator(const stl_allocator&){}

    pointer address(reference x) const {return &x;}
    const_pointer address(const_reference x) const {return &x;}
    size_type max_size() const throw() {return size_t(-1) / sizeof(value_type);}

    pointer allocate(size_type n, stl_allocator::const_pointer hint = 0)
    {
        return static_cast(xmalloc(n*sizeof(T)));
    }

    void deallocate(pointer p, size_type n)
    {
        xfree(p);
    }

    void construct(pointer p, const T& val)
    {
        new(static_cast(p)) T(val);
    }

    void construct(pointer p)
    {
        new(static_cast(p)) T();
    }

    void destroy(pointer p)
    {
        p->~T();
    }
};

pointer allocate(size_type n, stl_allocator::const_pointer hint = 0)
{
    return static_cast(xmalloc(n*sizeof(T)));
}

void deallocate(pointer p, size_type n)
{
    xfree(p);
}

#ifndef _XLIST_H
#define _XLIST_H

#include "stl_allocator.h"
#include 

template >
class xlist : public std::list<_Ty, _Ax>
{
};

#endif

#include  "xlist.h"

xlist myList;
myList.push_back("hello world");

#ifndef _XSTRING_H
#define _XSTRING_H

#include "stl_allocator.h"
#include 

typedef std::basic_string, stl_allocator > xstring;
typedef std::basic_string, stl_allocator > xwstring;

#endif

#include "xstring.h"

xwstring s = L"This is ";
s += L"my string.";

#ifndef _XSSTREAM_H
#define _XSSTREAM_H

#include "stl_allocator.h"
#include 

typedef std::basic_stringstream, 
stl_allocator > xstringstream;
typedef std::basic_ostringstream, 
stl_allocator > xostringstream;

typedef std::basic_stringstream, 
stl_allocator > xwstringstream;
typedef std::basic_ostringstream, 
stl_allocator > xwostringstream;

#endif

xstringstream myStringStream;
myStringStream << "hello world " << 2016 << ends;

list myList;
for (int i=0; i