![](https://habrastorage.org/getpro/habr/upload_files/149/b8a/da7/149b8ada7730548b407f96fa3d6fced6.png)
Привет, Хабр!
Сегодня мы обратим свой взор на производительность в C++, и как ни странно, нашими главными героями станут не библиотеки или сложные алгоритмы, а казалось бы, простые аллокаторы. Но не просто аллокаторы, а кастомные, которые могут заметно ускорить работу приложений.
Создание базового кастомного аллокатора
В основном кастомные аллокаторы реализуются через определение шаблона класса с методами allocate
и deallocate
, а также с функциями construct
и destroy
.
Пример простого аллокатора:
template<typename T>
class SimpleAllocator {
public:
using value_type = T;
SimpleAllocator() noexcept = default;
template<typename U> constexpr SimpleAllocator(const SimpleAllocator<U>&) noexcept {}
T* allocate(std::size_t n) {
if (n > std::numeric_limits<std::size_t>::max() / sizeof(T))
throw std::bad_alloc();
if (auto p = static_cast<T*>(std::malloc(n * sizeof(T)))) {
return p;
}
throw std::bad_alloc();
}
void deallocate(T* p, std::size_t) noexcept {
std::free(p);
}
template<typename U, typename... Args>
void construct(U* p, Args&&... args) {
new(p) U(std::forward<Args>(args)...);
}
template<typename U>
void destroy(U* p) noexcept {
p->~U();
}
};
Здесь:
allocate: выделяет блок памяти достаточного размера для хранения
n
объектов типаT
. Примечанием: тут используетсяstd::malloc
для аллокации, что иногда не очень эффективный метод для всех сценариев.deallocate: освобождает блок памяти, указатель на который предоставлен. Метод использует
std::free
.construct: использует
placement new
для конструирования объекта в предоставленной памяти. Так можно размещать объекты типаU
(который может отличаться отT
) с произвольными параметрами конструктора.destroy: вызывает деструктор для объекта, не освобождая при этом память.
Рассмотрим аллокатор посложней:
#include <cstddef>
#include <new>
#include <iostream>
template<typename T>
class PoolAllocator {
public:
using value_type = T;
explicit PoolAllocator(std::size_t size = 1024) : poolSize(size), pool(new char[size * sizeof(T)]) {}
~PoolAllocator() { delete[] pool; }
template<typename U>
PoolAllocator(const PoolAllocator<U>& other) noexcept : poolSize(other.poolSize), pool(other.pool) {}
T* allocate(std::size_t n) {
if (n > poolSize) throw std::bad_alloc();
return reinterpret_cast<T*>(pool + (index++ * sizeof(T)));
}
void deallocate(T* p, std::size_t n) noexcept {
// deallocate не делает ничего, так как память управляется вручную
}
template<typename U, typename... Args>
void construct(U* p, Args&&... args) {
new(p) U(std::forward<Args>(args)...);
}
template<typename U>
void destroy(U* p) {
p->~U();
}
private:
std::size_t poolSize;
char* pool;
std::size_t index = 0;
};
int main() {
PoolAllocator<int> alloc(10); // пул для 10 int
int* num = alloc.allocate(1);
alloc.construct(num, 7);
std::cout << *num << std::endl;
alloc.destroy(num);
alloc.deallocate(num, 1);
}
В некоторых ситуациях возможно понадобится интеграция кастомных аллокаторов с контейнерами стандартной библиотеки, например, с std::vector
.
Интеграция
Для std::vector
кастомный аллокатор должен соответствовать концепции Allocator, что включает в себя реализацию функций allocate
и deallocate
.
Класс аллокатора должен определять типы value_type
и предоставлять методы allocate
для выделения памяти и deallocate
для её освобождения. Эти методы используются контейнером std::vector
для управления памятью при изменении размера вектора.
При создании экземпляра std::vector
можно указать кастомный аллокатор как параметр шаблона. Так вектору можно использовать аллокатор для всех операций с памятью.
Пример кастомного аллокатора и его использования с std::vector
:
#include <vector>
#include <iostream>
template<typename T>
class SimpleAllocator {
public:
using value_type = T;
T* allocate(std::size_t n) {
return static_cast<T*>(::operator new(n * sizeof(T)));
}
void deallocate(T* p, std::size_t) noexcept {
::operator delete(p);
}
};
int main() {
std::vector<int, SimpleAllocator<int>> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
for (int i : vec) {
std::cout << i << ' ';
}
std::cout << std::endl;
return 0;
}
Здесь SimpleAllocator
выделяет и освобождает память без учёта особых требований к выравниванию или других оптимизаций.
Пару заметок:
Корректное выравнивание памяти очень важно для производительности. Кастомный аллокатор должен учитывать alignof(T)
, чтобы обеспечить правильное выравнивание объектов в памяти.
При нехватке памяти аллокатор должен корректно генерировать исключения типа std::bad_alloc
.
Альтернативные подходы
Еще можно рассмотреть несколько альтернативных подходов, которые учитывают специфику работы с памятью и типами данных:
Использование Proxy-класса для аллокатора: подход позволяет добавить доп функциональные возможности к аллокатору – логирование операций выделения и освобождения памяти.
#include <iostream>
#include <memory>
template <typename T, typename Allocator = std::allocator<T>>
class LoggingAllocator : public Allocator {
public:
using value_type = T;
T* allocate(std::size_t n) {
std::cout << "Allocating " << n << " objects of type " << typeid(T).name() << std::endl;
return Allocator::allocate(n);
}
void deallocate(T* p, std::size_t n) {
std::cout << "Deallocating " << n << " objects of type " << typeid(T).name() << std::endl;
Allocator::deallocate(p, n);
}
};
int main() {
std::vector<int, LoggingAllocator<int>> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
}
Создание аллокатора с поддержкой нескольких пулов памяти: такой аллокатор управляет несколькими пулами памяти, оптимизированными для разных типов или размеров объектов:
#include <vector>
#include <map>
template <typename T>
class MultiPoolAllocator {
public:
using value_type = T;
T* allocate(std::size_t n) {
auto size = sizeof(T) * n;
// выбираем пул на основе размера объекта
if (size <= 128) {
return smallObjectPool.allocate(n);
} else {
return largeObjectPool.allocate(n);
}
}
void deallocate(T* p, std::size_t n) {
auto size = sizeof(T) * n;
if (size <= 128) {
smallObjectPool.deallocate(p, n);
} else {
largeObjectPool.deallocate(p, n);
}
}
private:
std::allocator<T> smallObjectPool;
std::allocator<T> largeObjectPool;
};
int main() {
std::vector<int, MultiPoolAllocator<int>> vec;
vec.push_back(1);
vec.push_back(2);
}
Можно создать аллокатор, который адаптируется к паттернам использования памяти, оптимизируя выделение на лету.
Например, используем простую стратегию адаптации на основе статистики использования памяти:
#include <unordered_map>
#include <iostream>
template <typename T>
class AdaptiveAllocator {
public:
using value_type = T;
T* allocate(std::size_t n) {
std::cout << "Adaptive allocation for " << n << " objects of type " << typeid(T).name() << std::endl;
adaptAllocationStrategy(n);
return std::allocator<T>().allocate(n);
}
void deallocate(T* p, std::size_t n) {
std::allocator<T>().deallocate(p, n);
}
private:
// структура для хранения статистики использования
std::unordered_map<std::size_t, std::size_t> usageStatistics;
void adaptAllocationStrategy(std::size_t n) {
// увеличиваем счетчик запросов на выделение памяти данного размера
usageStatistics[n]++;
// отображаем текущую статистику
std::cout << "Current memory allocation statistics:" << std::endl;
for (auto& stat : usageStatistics) {
std::cout << "Size: " << stat.first << ", Count: " << stat.second << std::endl;
}
// адаптивная логика: определяем, нужно ли изменить стратегию выделения
// например, если запросы на выделение маленьких объектов слишком часты
if (usageStatistics[n] > 10) {
// логика изменения аллокационной стратегии, если это нужно
std::cout << "Adapting allocation strategy for size " << n << std::endl;
}
}
};
int main() {
AdaptiveAllocator<int> allocator;
for (int i = 0; i < 20; i++) {
int* num = allocator.allocate(1);
allocator.deallocate(num, 1);
}
return 0;
}
ЗдесьAdaptiveAllocator
использует std::unordered_map
для отслеживания, сколько раз была запрошена память каждого размера. Далее эту информацию можно использовать для адаптации стратегии выделения памяти. Например, если размер часто запрашивается, можно выделить блок памяти большего размера заранее, чтобы ускорить будущие операции выделения.
C++ известен тем, что позволяет работать с памятью напрямую. Здесь вы точно знаете, где и как расположен каждый из ваших объектов, сколько памяти он занимает. Но можете ли вы принимать решение, где и как будет размещен ваш объект? Часто стандартные методы выделения памяти не удовлетворяют узким требованиям конкретной логики. О том, зачем в C++ существуют аллокаторы, коллеги из OTUS расскажут на бесплатном вебинаре, а также покажут конкретный пример увеличения производительности программы с помощью настроенного аллокатора.
Комментарии (4)
n0lavar
31.07.2024 23:59+9Извините, но статья больше похожа на "в С++ есть интерфейс для аллокаторов, выглядит вот так, можно делать разные прикольные штуки"
Вот библиотека с кастомными аллокаторами, там в ридми в разы больше информации - https://github.com/mtrebi/memory-allocators
Nemoumbra
31.07.2024 23:59+1Тема
select_on_container_copy_construction
иpropagate_on_container_copy_assignment
не раскрыта)Ну и странно, что про Allocator Traits не рассказали... Ну ладно, допустим, что это детали.
А почему у Вас
PoolAllocator
имеет копирующий конструктор, но при этом не клонируется пул, а копируется указатель? Мы так к дабл-фри придём очень быстро.
supermaxus
Пока не понятно, в чем состоит "разгон". Все приемы, что приведены с статье - интересны с архитектурной точки зрения и "правильности" построения кода. Но все эти приемы не устраняют основные причины замедления при работе с блоками памяти.
Проблемы с выделением и освобождением памяти в с++ примерно такие:
В мультипоточной среде, если используется одна куча памяти (heap), то в своих операциях она использует средства синхронизации ОС. Т.о. если потоков много, то они начинают "ждать" друг-друга, поскольку операции выделения, освобождения и перераспределения размера блока не очень быстрые (особенно в драйверах). Также, если они должны учесть выравнивание выделенного блока на определенную границу. Для избежания этого можно делать несколько куч. Главное - не запутаться в них. Система управления кучами - здесь бы помогла. Т.е. по какому принципу их разделять, когда создавать, какого размера и т.д.
Любая куча быстро замусоривается/фрагментируется, если в ней происходит работа с разного размера блоками. Попытка использования такого блока в операциях выделения и изменения размера приводит к увеличению задержек в п.1. Какая-то необычная структура кучи могла бы повысить скорость работы с ней.
Стандартные средства синхронизации ОС, используемые в куче (критическая секция, мьютекс) НЕ гарантируют доступ к ресурсу в порядке какой-то очередности. Т.е. если конкурентных потоков очень много, то один из первых запросов может ждать захвата ресурса О-О-очень долго (по меркам процессора и даже профайлера).
Сборщик "мусора" в с++ - традиционная головная боль, если начинаешь хоть как-то сам управлять этими кучами. умные указатели гарантируют лишь своевременное освобождение ресурса. Дефрагментацией приходится заниматься либо в момент освобождения блока (что существенно замедляет операцию освобождения), либо отдельным процессом, который тоже лочит всю кучу и мешает другим потокам с ней работать.
Ну, что-то такое.