rikki_tikki Feb 5 at 15:52

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

11 min

5.2K

OTUS corporate blogC++*

Translation

Original author: David Lafreniere

Нашла и перевела: Ксения Мосеенкова

Реализация защиты от сбоев из-за фрагментации кучи и повышение скорости выполнения с помощью 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 _Ty, class _Ax = allocator<_Ty> >
class list : public _List_val<_Ty, _Ax>
{
    // ...
}

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

std::list<int> 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 <typename T>
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 <class U> struct rebind { typedef stl_allocator<U> other; };
    template <class U> stl_allocator(const stl_allocator<U>&){}

    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<void>::const_pointer hint = 0)
    {
        return static_cast<pointer>(xmalloc(n*sizeof(T)));
    }

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

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

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

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

По сути код представляет из себя просто стандартный интерфейс std::allocator. В сети можно найти множество подобных примеров. Исходный код, приложенный к этой статье, использовался во многих различных компиляторах (GCC, Keil, VisualStudio). Нас интересует, как подключиться к интерфейсу с помощью собственного менеджера памяти. А именно, нас интересуют следующие методы:

allocate()
deallocate()

allocate() выделяет n экземпляров объекта типа T. xmalloc() используется для получения памяти из пула блоков фиксированного размера, а не из глобальной кучи.

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

Функция deallocate() высвобождает блок памяти, ранее выделенный с помощью функции allocate(). Простой вызов xfree() направляет запрос нашему менеджеру памяти.

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

На самом деле, это все, что вам нужно сделать, если у вас есть менеджер памяти, работающий с блоками фиксированного размера. xallocator предназначен для обработки запросов на память любого размера. Т.е. независимо от размера памяти, требуемого стандартной библиотекой C++ под конкретные элементы или узлы, xmalloc/xfree обработает этот запрос.

Разумеется, stl_allocator — это шаблонный класс. Обратите внимание, что обязанности по выделению фиксированных блоков делегированы нешаблонным функциям xmalloc() и xfree(). Это позволяет минимизировать количество инстанцируемого кода для каждого экземпляра.

"x"-контейнеры

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

std::list
std::map
std::multipmap
std::set
std::multiset
std::queue

Для того, чтобы сделать использование stl_allocator немного проще, для многих стандартных типов контейнеров были созданы новые специальные классы. Каждый из этих контейнеров просто наследуется от аналога из стандартной библиотеки и имеет префикс "x".

xlist
xmap
xmultimap
xset
xmultiset
xqueue

Следующий код показывает полную реализацию xlist. Обратите внимание, что xlist просто наследует от std::list, но ключевым отличием является то, что аргумент шаблона _Ax по умолчанию устанавливает stl_allocator, а не std::allocator.

#ifndef _XLIST_H
#define _XLIST_H

#include "stl_allocator.h"
#include <list>

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

#endif

Каждая из "x"-версий STL-контейнеров используется так же, как и std-версия, за исключением того, что все аллокации обрабатываются stl_allocator. Например:

#include  "xlist.h"

xlist<xstring> myList;
myList.push_back("hello world");

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

std::string
std::vector

Соответствующий xvector не был реализован из соображений безопасности, потому что векторы требуют смежной области памяти, в то время как другие типы контейнеров работают с узлами. Фиксированный аллокатор прекрасно работает с блоками одинакового размера, но не очень хорошо, если вектор постоянно расширяется в виде одного блока памяти все большего и большего размера. Хотя stl_allocator и может работать с вектором, его можно использовать неправильно и вызвать проблемы с менеджером памяти.

std::string также меняет размер запрашиваемой памяти во время выполнения, но обычно строки не используются неограниченно. То есть, в большинстве случаев вам не нужно хранить строку размером 100 Кбайт, в то время как с вектором такое вполне может быть. Поэтому мы можем использовать xstring, как объясняется далее.

"x"-строки

Были созданы новые "x"-версии стандартной и расширенной версий класса string.

xstring
xwstring

Здесь мы просто делаем typedef новой "x"-версии, используя stl_allocator в качестве аллокатора по умолчанию для типов char и wchar_t:

#ifndef _XSTRING_H
#define _XSTRING_H

#include "stl_allocator.h"
#include <string>

typedef std::basic_string<char, std::char_traits<char>, stl_allocator<char> > xstring;
typedef std::basic_string<wchar_t, std::char_traits<wchar_t>, stl_allocator<wchar_t> > xwstring;

#endif

Использование xstring выглядит так же, как и у любой другой std::string.

#include "xstring.h"

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

"x"-потоки

Стандартная библиотека C++ iostreams предлагает простой в использовании и функциональный способ форматирования строк с помощью stream-классов.

std::stringstream
std::ostringstream
std::wstringstream
std::wostringstream

Как и с контейнерными классами, iostreams можно использовать с нашим собственным аллокатором вместо глобальной кучи с помощью этих новых определений.

xstringstream
xostringstream
xwstringstream
xwostringstream

Опять же, это просто typedef новых "x"-версий с аргументами шаблона по умолчанию stl_allocator:

#ifndef _XSSTREAM_H
#define _XSSTREAM_H

#include "stl_allocator.h"
#include <sstream>

typedef std::basic_stringstream<char, std::char_traits<char>, 
stl_allocator<char> > xstringstream;
typedef std::basic_ostringstream<char, std::char_traits<char>, 
stl_allocator<char> > xostringstream;

typedef std::basic_stringstream<wchar_t, std::char_traits<wchar_t>, 
stl_allocator<wchar_t> > xwstringstream;
typedef std::basic_ostringstream<wchar_t, std::char_traits<wchar_t>, 
stl_allocator<wchar_t> > xwostringstream;

#endif

И использование xstringstream не отличается от оригинала:

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

Бенчмаркинг

В моих предыдущих статьях об аллокаторах простые тесты показали, что фиксированный аллокатор работает быстрее, чем глобальная куча. Теперь давайте проверим контейнеры с поддержкой stl_allocator и посмотрим, насколько они превосходят std::allocator на ПК с Windows.

Все тесты были собраны в Visual Studio 2008 с включенной максимальной оптимизацией компилятора. xallocator работает в режиме блоков кучи (heap blocks), в котором блоки изначально берутся из кучи, но перерабатываются при деаллокации. Отладочная куча также отключена путем установки параметра Debugging > Environment _NO_DEBUG_HEAP=1. Отладочная куча работает значительно медленнее из-за дополнительных проверок безопасности.

Бенчмарки довольно простые и представляют собой вставку/удаление 10000 элементов. Каждый тест выполняется три раза. При вставке/удалении библиотека STL полагается на динамическое хранение данных, и именно на этом сосредоточены тесты, а не на производительности алгоритмов.

Приведенный ниже фрагмент кода — это тест std::list. Остальные тесты контейнеров аналогичны.

list<int> myList;
for (int i=0; i<MAX_BENCHMARK; i++)
    myList.push_back(123);
myList.clear();

Разница в производительности между std::allocator и stl_allocator, работающими в режиме выбора блоков из кучи, показана ниже:

Контейнер	Режим	Запуск	Контрольное время (мс)
std::list	Глобальная куча	1	60
std::list	Глобальная куча	2	32
std::list	Глобальная куча	3	23
xlist	Блоки из кучи	1	19
xlist	Блоки из кучи	2	11
xlist	Блоки из кучи	3	11
std::map	Глобальная куча	1	37
std::map	Глобальная куча	2	34
std::map	Глобальная куча	3	41
xmap	Блоки из кучи	1	38
xmap	Блоки из кучи	2	25
xmap	Блоки из кучи	3	25
std::string	Глобальная куча	1	171
std::string	Глобальная куча	2	146
std::string	Глобальная куча	3	95
xstring	Блоки из кучи	1	57
xstring	Блоки из кучи	2	36
xstring	Блоки из кучи	3	40

Результаты теста показывают, что для этого бенчмарка версии с поддержкой stl_allocator примерно в 2-3 раза быстрее, чем std::allocator. Но это не означает, что STL стал волшебным образом в два-три раза быстрее. Опять же, этот бенчмарк концентрируется только на производительности вставки и удаления. Базовая алгоритмическая производительность контейнера не изменилась. Поэтому общий прирост производительности будет зависеть от того, как часто ваше приложение вставляет/удаляет контейнеры.

Если xallocator используется в режиме статического пула (static pool), stl_allocator работает за постоянное время. Если xallocator работает в режиме выбора блоков из кучи, время выполнения становится постоянным после заполнения списка свободных блоков, полученными из кучи. Обратите внимание, что в приведенном выше бенчмарке xlist начальное время выполнения составляет 19 мс, а последующие выполняются по 11 мс. В первом запуске xallocator должен был получить свежие блоки из глобальной кучи с помощью оператора new. Во втором и третьем запусках блоки уже существовали в списке свободных блоков xallocator, поэтому куча не используется, что значительно ускоряет последующие запуски.

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

Разработчики игр прилагают огромные усилия для решения проблемы фрагментации кучи и множества связанных с ней проблем. В техническом документе Electronic Arts Standard Template Library (EASTL) подробно рассматриваются проблемы STL и, в частности, std::allocator. Пол утверждает следующее в документе EASTL -- Electronic Arts Standard Template Library:

Среди разработчиков игр наиболее фундаментальным недостатком считается архитектура std-аллокатора, и именно этот недостаток был самым большим фактором, способствовавшим созданию EASTL.

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

Справочные статьи

Замена malloc/free на быстрый аллокатор с фиксированными блоками памяти Дэвида Лафреньера (David Lafreniere)
Эффективный аллокатор с фиксированными блоками памяти на C++ Дэвида Лафреньера
EASTL -- Библиотека стандартных шаблонов Electronic Arts, автор Пол Педриана (Paul Pedriana)

Преимущества

STL — чрезвычайно полезная библиотека C++, но слишком часто я не могу использовать для медицинских устройств ее из-за возможности сбоя, из-за фрагментации памяти кучи. Это приводит к тому, что приходится создавать собственные классы контейнеров для каждого проекта вместо того, чтобы использовать существующую, хорошо проверенную библиотеку.

Моей целью при создании stl_allocator было устранение ошибок памяти; однако аллокатор с блоками фиксированного обеспечивает более быстрое и стабильное время выполнения в сравнении с глобальной кучей. Реализация кучи и уровень фрагментации приводят к непредсказуемому времени выполнения. В зависимости от вашего приложения это может быть проблемой.

Как показано в этой статье, простое использование STL-совместимого аллокатора блоков памяти фиксированного размера открывает возможность использовать в проекте функционал стандартной библиотеки шаблонов C++, которые в противном случае могли бы оказаться невозможными.

Ревизии

3.04.2016
- Первоначальная редакция
11.04.2016
- Исправлены ошибки в коде. К статье прикреплен новый исходный код
14.04.2017
- Исправлена незначительная ошибка включения компилятора в системах Linux
- Прикреплен обновленный исходный код
21.01.2024
- xallocator упрощен для использования std::mutex

Лицензия

Эта статья, а также весь, связанный с ней исходный код и файлы, лицензированы под Code Project Open License (CPOL)

15 февраля в OTUS в раках курса C++ Developer. Professional пройдет открытый урок, на котором разебрём, как работает динамическое выделение памяти на этапе компиляции в C++20, а также зачем это нужно и где можно использовать. Участие бесплатное, записаться можно по ссылке.

Tags:

Hubs: