Управление памятью в контейнерах STL. Ускоряем код с помощью кастомных аллокаторов

В предыдущей статье мы подробно разобрали, как устроена архитектура работы с памятью в STL. Мы увидели, как стандартная библиотека разделяет выделение памяти и конструирование объектов. Однако, стандартный std::allocator универсален, а за универсальность приходится платить скоростью. При добавлении элемента узловой контейнер обращается к аллокатору для выделения памяти под новый узел. В распространённых реализациях std::allocator это приводит к вызову глобального operator new, который, в свою очередь, может использовать malloc или другие механизмы управления памятью. В высоконагруженных системах или игровых движках это может стать узким местом. В этой статье мы рассмотрим проектирование кастомных аллокаторов, которые могут дать серьезный прирост производительности для таких контейнеров. Обсудим проблемы, возникающие при использовании пользовательских аллокаторов в STL и замерим прирост скорости с помощью бенчмарков.

Продолжаем работать в рамках С++11. Используемый для контейнеров по умолчанию std::allocator относится к аллокаторам без состояния (stateless). У таких аллокаторов нет внутренних нестатических полей данных. Любые два экземпляра такого распределителя памяти равны, так как память, выделенная одним экземпляром, может быть освобождена другим экземпляром. Экземпляры stateless аллокаторов всегда считаются равными при сравнении.

Перед погружением в глубины оптимизации, нужно понять, как узловые контейнеры запрашивают память. При объявлении переменной типа std::list<int, MyAllocator>, вы передаете аллокатор, умеющий выделять память под тип int. Но список должен хранить не только int. Он состоит из внутренних узлов, которые помимо самого значения содержат указатели на следующий и предыдущий элементы, например так:

template struct ListNode { ListNode* next; T value;};

Как списку выделить память под ListNode, если ему передали MyAllocator? Напрямую вызвать MyAllocator::allocate() нельзя — не совпадает размер. Здесь на сцену выходит механизм rebind. Для того, чтобы разобраться как он работает, напишем простейший аллокатор:

template class CustomAllocator {public: using value_type = T; //Позволяет allocator_traits связать аллокатор с другим типом данных template  struct rebind { using other = CustomAllocator; }; CustomAllocator() noexcept = default; explicit CustomAllocator(Pool* pool) noexcept : pool_(pool) {} //Конвертирующий конструктор, используемый для rebind и позволяющий //создать аллокатор для другого типа с сохранением состояния исходного аллокатора. template  CustomAllocator(const CustomAllocator& other) noexcept : pool_(other.get_pool()) {} //выделение памяти переадресуем пулу T* allocate(std::size_t n) { if (!pool_ || (n > std::numeric_limits::max() / sizeof(T))) throw std::bad_alloc(); void* p = pool_->allocate(n * sizeof(T), alignof(T)); return static_cast(p); } //за освобождение памяти также отвечает пул void deallocate(T* p, std::size_t n) noexcept { if (!pool_) return; pool_->deallocate(p, n * sizeof(T)); }...private: Pool* pool_ = nullptr;}

Внутри CustomAllocator создаем структуру rebind с помощью которой можно перенастроить аллокатор на другой тип данных. Из CustomAllocator получается другой тип CustomAllocator у которого меняется тип хранимого значения с T на U, но пул, из которого выделяется память, остается неизменным.

Allocator_traits использует rebind при помощи rebind_alloc, как будет показано позже. Для поддержки rebind также нужен конструктор template CustomAllocator(const CustomAllocator& other). Так как пользователь классов контейнеров STL задает тип значения T, а контейнеру нужно выделять память под свои внутренние структуры данных, например, Node.

Тип Pool представляет пул памяти, хранящий данные контейнера. Аллокатор является частью контейнера, поэтому он должен занимать как можно меньше места. В то же время пул может строиться на основе различных стратегий распределения памяти, например, на основе массива, размещаемого на стеке. Чтобы ограничить размер аллокатора при использовании такого пула, распределитель должен хранить его не по значению, а по указателю или ссылке. При использовании такого подхода ответственность за время жизни пула лежит на вызывающем коде. Пул должен существовать до уничтожения всех контейнеров и других объектов, использующих выделенную из него память.

Для упрощения логики аллокатора выделение и освобождение памяти инкапсулируются в пуле.

Теперь посмотрим простейший STL-подобный узловой контейнер:

template <typename T, typename Allocator = std::allocator>class SimpleList { struct Node { Node* next; T value; Node(const T& v, Node* n) : next(n), value(v) {} }; //получаем тип аллокатора, настроенного не на тип значения Т, передаваемый //пользователем SimpleList, а на внутренний тип данных Node using NodeAlloc = typename std::allocator_traits ::template rebind_alloc; //специализируем allocator_traits полученным типом для работы с памятью //работаем с аллокатором не напрямую, а с помощью этого типа using NodeAllocTraits = std::allocator_traits; Node* head_ = nullptr; NodeAlloc alloc_;public: SimpleList() = default; explicit SimpleList(const Allocator& a) : alloc_(a) {} SimpleList(const SimpleList&) = delete; SimpleList& operator=(const SimpleList&) = delete; ~SimpleList() { while (head_) { Node* next = head_->next; //вначале вызываем деструктор Node NodeAllocTraits::destroy(alloc_, head_); //затем освобождаем выделенную память NodeAllocTraits::deallocate(alloc_, head_, 1); head_ = next; } } void push_front(const T& value) { //выделяем память под Node Node* n = NodeAllocTraits::allocate(alloc_, 1); try { //конструируем объект NodeAllocTraits::construct(alloc_, n, value, head_); } catch (...) { //освобождаем память в случае возникновения исключения NodeAllocTraits::deallocate(alloc_, n, 1); throw; } head_ = n; } void pop_front() { Node* n = head_; head_ = n->next; //уничтожаем Node NodeAllocTraits::destroy(alloc_, n); NodeAllocTraits::deallocate(alloc_, n, 1); } T& front() { return head_->value; } const T& front() const { return head_->value; } bool empty() const noexcept { return head_ == nullptr; }};

С помощью rebind_alloc, использующего rebind аллокатора получаем распределитель NodeAlloc для работы с узлами (Node) списка. Работа с памятью в контейнерах STL происходит не напрямую, а при помощи std::allocator_traits. Используем std::allocator_traits с полученным типом NodeAlloc. Таким образом, все операции выделения, конструирования, уничтожения и освобождения памяти выполняются с учётом типа внутреннего узла контейнера. Далее работа с памятью происходит при помощи вызова статических методов allocate, construct, destroy и deallocate структуры NodeAllocTraits.

Наш STL-подобный контейнер SimpleList принимает объект распределителя в качестве параметра конструктора. Этим достигается гибкость работы с памятью. Можно, при необходимости, как выделить собственный распределитель каждому контейнеру, так и разделить один аллокатор между несколькими. Как всегда, для избежания неопределенного поведения, нужно следить чтобы время жизни аллокатора было не короче чем у соответствующего контейнера.

Теперь посмотрим как можно ускорить работу контейнера за счет создания пользовательских аллокаторов.

Как мы выяснили в прошлой статье, std::allocator является универсальным, но за это приходится платить скоростью выделения памяти. Одним из источников накладных расходов при использовании стандартного механизма выделения памяти может быть синхронизация при конкурентном доступе из нескольких потоков. Собственные пулы позволяют выбрать другую стратегию синхронизации, например использовать отдельный пул для каждого потока. Однако это не единственный способ ускорения. Существенный эффект может дать предварительное выделение памяти и повторное использование освобождённых блоков, что особенно важно для узловых контейнеров (std::list, std::map и т.д.), которые обращаются к аллокатору при создании каждого узла. Представленные в статье пулы памяти не являются потокобезопасными.

Рассмотрим два вида пулов. Первый использует память в виде массива, выделенного на стеке.

template  //размер пула в байтахclass StackPool {public: StackPool() = default; StackPool(const StackPool&) = delete; StackPool& operator=(const StackPool&) = delete; void* allocate(std::size_t bytes, std::size_t alignment) { void* ptr = current_; std::size_t space = (buffer_ + CapacityBytes) - current_; if (!std::align(alignment, bytes, ptr, space)) throw std::bad_alloc(); current_ = static_cast(ptr) + bytes; return ptr; } void deallocate(void*, std::size_t bytes) noexcept { //память освобождается вызовом reset() и при выходе из области видимости //пул должен жить дольше всех объектов, использующих выделенную из него память } //можно вызывать только после уничтожения всех объектов, размещённых в пуле void reset() noexcept { current_ = buffer_; }private: alignas(std::max_align_t) unsigned char buffer_[CapacityBytes]; unsigned char* current_ = buffer_;};

Alignas(std::max_align_t) заставляет начало буфера buffer_ быть выровненным по границе alignof(std::max_align_t) — обычно 16 байт на x86-64. Без alignas выравнивание buffer_ определялось бы только типом unsigned char (1 байт) и соседними членами класса, и гарантии max_align_t не было бы.

Стековый пул подходит в ситуациях, когда не требуется длительное хранение данных, например:

  1. Парсинг результатов HTTP запросов. Пул живёт один запрос или переиспользуется через reset() между запросами. Не нужно выделять динамическую память.

  2. Построение игрового кадра. Всё, что нужно на один кадр, выделяется из пула и отбрасывается в конце.

  3. Разработка для встраиваемых систем, где динамическое выделение памяти запрещено.

  4. Объекты, живущие в пределах одной функции или итерации алгоритма.

Главной проблемой StackPool является невозможность освобождения памяти, особенно в случае, когда в ней хранятся объекты разного размера. Поэтому если требуется длительное хранение данных, нужно использовать пул на основе динамического выделения с кешированием.

Посмотрим как построить такой пул, ориентированный на использование в узловых контейнерах STL. Сначала сформулируем требования.

  1. В пуле хранятся объекты одинакового размера. Размер узла не известен заранее и может варьироваться в зависимости от реализации контейнера. Объем памяти, выделяемой под узел, становится известным только при первом вызове allocate.

  2. Чтобы свести к минимуму количество вызовов операторов new/delete нужно кэшировать память в списке свободных блоков. При вызове allocate берем блок из головы списка. Если список пуст, то вызываем operator new. При вызове deallocate возвращаем блок памяти в список.

Следуя устоявшейся терминологии, будем называть слэбом (slab) непрерывный участок памяти, разбитый на одинаковые блоки для хранения узлов. Простейшая реализация пула выглядит следующим образом:

template class FreelistPool { struct Node { Node* next; }; Node* head_ = nullptr;// указатель на голову списка свободных блоков unsigned char* slab_ = nullptr;// указатель на непрерывный блок памяти unsigned char* slab_next_ = nullptr;// указатель на следующий свободный блок из слэба unsigned char* slab_end_ = nullptr;// slab_ + CapacityBytes std::size_t request_size_= 0; // размер запрашиваемого блока при аллокации std::size_t block_size_ = 0; // размер выровненного блока //проверка на принадлежность адреса слэбу. Нужна для оптимизации возврата //выделенной памяти. Если память не в слэбе, то для её освобождения нужно //вызывать operator delete. bool in_slab(const void* p) const noexcept { const auto* b = static_cast(p); return slab_ && b >= slab_ && b < slab_end_; }//ленивое создание слэба и определение его границ void init_layout() { slab_ = static_cast(::operator new(CapacityBytes)); slab_next_ = slab_; slab_end_ = slab_ + CapacityBytes; }public: FreelistPool() = default; FreelistPool(const FreelistPool&) = delete; FreelistPool& operator=(const FreelistPool&) = delete; ~FreelistPool() { //вначале нужно пройти по списку свободных блоков //и найти не принадлежащие слэбу. Node* node = head_; while (node) { Node* next = node->next; //каждый такой блок освобождаем отдельно if (!in_slab(node)) ::operator delete(node); node = next; } //в конце освобождаем слэб ::operator delete(slab_); } void calc_block_size(std::size_t bytes, std::size_t alignment) { if (alignment < alignof(Node)) alignment = alignof(Node); //определяем выравнивание данных в памяти и размер блока //на основании размера узла request_size_ = bytes; std::size_t sz = bytes  CapacityBytes) throw std::bad_alloc(); } void* allocate(std::size_t bytes, std::size_t alignment) { if (request_size_ == 0) { if (alignment next; return n; } // если освобожденных блоков нет, то пытаемся взять из слэба if (slab_next_ + block_size_ <= slab_end_) { void* p = slab_next_; slab_next_ += block_size_; return p; } // если слэб исчерпан, то выделяем память, обращаясь к системе return ::operator new(block_size_); } void deallocate(void* p, std::size_t bytes) noexcept { //защита от случая, когда в список пытаются вернуть блок другого размера assert(bytes == request_size_ && "FreelistPool deallocate or wrong block size"); if (bytes != request_size_) return; Node* node = static_cast(p); node->next = head_; head_ = node; }};

Данная реализация служит только для демонстрации принципов построения пулов памяти и не учитывает многих аспектов, связанных с выравниванием данных.

Так как объем памяти, выделяемой под узел, заранее не известен, то мы можем его определить и выполнить ленивую инициализацию памяти пула только при первом вызове «allocate». При возврате памяти в пул (deallocate) нужно предусмотреть защиту от случая, когда нам пытаются передать память другого размера. Почему это важно? Казалось бы, память выделяемая одним экземпляром FreelistPool может быть освобождена другим его экземпляром. Всё, в конечном счете, сводится к вызовам операторов new/delete. Однако ситуация не так проста, как может показаться на первый взгляд. Если возвращается участок памяти, размер которого меньше, чем block_size_, то при вызове конструктора в этой области памяти будет запись в смежную область, что повлечёт порчу данных и, как следствие, неопределенное поведение. Поэтому будем считать что два экземпляра FreelistPool не равны друг другу.

FreelistPool можно использовать в следующих ситуациях:

  1. Использование в STL контейнерах, где узлы часто создаются и удаляются.

  2. В играх для хранения частиц, летящих снарядов, противников, которые существуют на протяжении нескольких кадров, затем уничтожаются и возрождаются вновь.

  3. Часть узлов имеет длительное время жизни, а часть — короткое. StackPool тут использовать нельзя, так как нельзя вызывать reset().

Проблемы при использовании FreelistPool:

  1. Нельзя держать в одном пуле узлы list и map, нужен отдельный пул на каждый размер.

  2. Если все объекты нужно удалить одновременно, то FreelistPool делает лишнюю работу, возвращая память в список свободных блоков при deallocate, а StackPool не делает ничего.

  3. Если необходимо выделить больше чем CapacityBytes, происходит исчерпание слэба, вызывается ::operator new для каждого нового узла.

Теперь проведем тесты производительности описанных аллокаторов и сравним их с std::allocator.

Для замеров использовалась библиотека Google Benchmark. Все тесты запускались на следующем стенде:

  • Процессор: AMD Phenom II X6.

  • ОС Ubuntu 20.04.

  • Компилятор: clang++ версии 19.1.7 (сборка в режиме Release с оптимизациями -O3).

  • Объем пула: 1 МБ (1024 * 1024 байт), чего с запасом хватает для размещения 10 000 узлов.

Результаты относятся к конкретной реализации стандартной библиотеки, компилятору и аппаратной платформе. Они показывают потенциальный эффект от использования пулов памяти, но не являются универсальным сравнением производительности всех реализаций std::allocator.

Чтобы не загромождать статью листингами всех 15 бенчмарков, приведем один, а также разберем методику и логику пяти тестовых сценариев.

constexpr std::size_t POOL_SIZE_BYTES = 1024 * 1024;using MapValue = std::pair;using FreeListMapAllocator = CustomAllocator<MapValue, FreelistPool>;using FreeListMap = std::map<int, int, std::less, FreeListMapAllocator>;template static void RunMapDegradationScenario(Map& m) { // 1. Первичное заполнение for (int i = 0; i < 4000; ++i) m[i] = i; // 2. Удаляем элементы for (int i = 0; i < 4000; i += 2) m.erase(i); // 3. Добавляем новые элементы for (int i = 10000; i < 12000; ++i) m[i] = i; // 4. Поиск по всему диапазону int found = 0; for (int i = 0; i < 12000; ++i) { if (m.find(i) != m.end()) ++found; } benchmark::DoNotOptimize(found);}static void Benchmark_MapDegradation_FreeList(benchmark::State& state) { for (auto _ : state) { FreelistPool fp; FreeListMap m{ std::less{}, FreeListMapAllocator(&fp) }; RunMapDegradationScenario(m); }}

Полный исходный код тестов доступен в репозитории на GitHub.

Сценарии тестирования:

  1. Последовательная вставка в список (List_PushBack). В std::list добавляется 10 000 элементов через push_back. Здесь мы замеряем время, затраченное на выделение памяти и конструирование узлов, а также накладные расходы на удаление пулов и контейнера при выходе из области видимости.

  2. Последовательный обход списка (List_Iter). Список из 10 000 элементов суммируется в цикле. Время создания и заполнения контейнера исключено из замера с помощью state.PauseTiming() и state.ResumeTiming(). Этот тест показывает, как выбор аллокатора влияет на локальность данных.

  3. Вставка в дерево (Map_Insert). В std::map вставляется 10 000 пар ключ-значение. В отличие от списка, здесь значительную долю времени занимает балансировка дерева и сравнение ключей.

  4. Поиск по случайным ключам (MapFind). Контейнер std::map предварительно заполняется 10 000 элементами (время заполнения отсекается через PauseTiming()), после чего выполняется поиск ключей. Чтобы избежать идеального последовательного доступа к памяти, ключи предварительно перемешиваются с помощью std::shuffle.

  5. Деградация при активном удалении и вставке (MapDegradation). Имитация реальной нагрузки. В std::map добавляются 4 000 элементов, затем удаляется каждый второй (erase), после чего дописываются еще 2 000 новых элементов, и выполняется серия поисков.

Для наглядности каждый тест проходит в трех вариантах: с std::allocator (вариант по умолчанию), CustomAllocator, использующий StackPool, CustomAllocator, использующий FreelistPool.

Для наглядности переведем наносекунды в микросекунды (мкс) и посчитаем кратность ускорения относительно стандартного std::allocator:

Тестовый сценарий

std::allocator

StackPool

FreelistPool

Максимальное ускорение

Вставка в список (List_PushBack)

313.1 мкс

44.7 мкс

72.6 мкс

×7.0 (StackPool)

Обход списка (List_Iter)

150.9 мкс

11.0 мкс

34.3 мкс

×13.8 (StackPool)

Вставка в дерево (Map_Insert)

1173.4 мкс

899.5 мкс

889.7 мкс

×1.32 (FreelistPool)

Поиск по дереву (MapFind)

930.8 мкс

652.8 мкс

682.7 мкс

×1.43 (StackPool)

Смешанная нагрузка (MapDegradation)

1118.9 мкс

940.5 мкс

956.1 мкс

×1.19

(StackPool)

Анализ результатов:

  1. Значительный рост скорости на std::list при вставке (List_PushBack). StackPool оказался в 7 раз быстрее стандартного аллокатора. Вместо 10 000 вызовов operator new и последующих operator delete при уничтожении списка, стековый пул просто сдвигает указатель. При этом сам StackPool не выполняет индивидуального освобождения памяти: вызовы deallocate ничего не делают, а сброс всего пула через reset() занимает O(1). Однако уничтожение контейнера по-прежнему требует обхода всех узлов и вызова их деструкторов. FreelistPool уступает StackPool, так как при уничтожении узла его память возвращается в односвязный список свободных блоков.

  2. При обходе (List_Iter) срабатывает эффект локальности кэша. При последовательной вставке StackPool размещает узлы последовательно в памяти. Благодаря этому повышается пространственная локальность: при загрузке одной кэш-линии процессор получает данные сразу нескольких соседних узлов. Это уменьшает количество промахов кэша и сокращает время обхода почти в 14 раз (11.0 мкс против 150.9 мкс). У std::allocator узлы разбросаны по куче, что вызывает промахи кэша.

  3. Умеренный прирост производительности дает кастомный аллокатор при использовании в std::map (×1.3–1.4). Здесь при вставке и поиске процессорное время тратится не только на работу с памятью, но и на сравнение ключей и ребалансировку дерева. Поэтому даже при ускоренном выделении памяти общий выигрыш составляет около 25–30%. В тесте MapFind поиск по дереву с StackPool ускорился примерно на 40%. Вероятно, это связано с более компактным размещением узлов в памяти, улучшающим пространственную локальность. Однако, такой эффект зависит от структуры дерева и характера запросов и не является гарантированным свойством пользовательских аллокаторов.

  4. Нюанс теста MapDegradation. При работе с 4000 элементов StackPool и FreelistPool показывают почти одинаковое время (940–956 мкс). Однако здесь важно смотреть не только на время, но и на расход памяти. StackPool при удалении 2 000 элементов не возвращает память, а при добавлении новых 2 000 узлов продолжает расти вверх. В длительном цикле работы программы он неизбежно упрется в лимит CapacityBytes и выбросит исключение. FreelistPool в этом же сценарии переиспользует освобожденные ячейки, сохраняя объем потребляемой памяти постоянным без дополнительного обращения к ОС.

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

Дело в том, что CustomAllocator хранит состояние — указатель на конкретный пул (Pool*). Когда два контейнера с неравными экземплярами FreelistPool, стандартной библиотеке нужно знать: что делать с самим аллокатором, когда один контейнер присваивается другому или когда они меняются содержимым? За это поведение в std::allocator_traits отвечают три флага:

  1. propagate_on_container_copy_assignment (POCCA) — определяет, должен ли аллокатор копироваться при присваивании (container1 = container2). Если POCCA равен false_type, при копирующем присваивании контейнер сохраняет свой исходный аллокатор. При необходимости создания дополнительных элементов память будет выделяться с использованием этого аллокатора.

  2. propagate_on_container_move_assignment (POCMA). Если POCMA равен false_type, а аллокаторы не равны, один контейнер не может просто забрать узлы другого. Ему приходится создавать собственные и перемещать в них элементы исходного контейнера. Это существенно дороже перемещения указателей на узлы, поскольку требует выделения памяти и обработки каждого элемента.

  3. propagate_on_container_swap (POCS) — управляет поведением при вызове std::swap(container1, container2). Если флаг равен false_type и аллокаторы не равны, то обмен таких контейнеров приводит к неопределенному поведению.

О том, как контейнеры STL проверяют эти флаги, какие грабли возникают при неверном выборе их комбинаций и какой подход к решению этих проблем предлагает std::pmr из C++17 разберем в следующей статье.

Источник: habr.com

0 0 голоса
Рейтинг новости
1
0
Подписаться
Уведомить о
0 комментариев