Привет, Хабр!

Сегодня мы обратим свой взор на производительность в 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 расскажут на бесплатном вебинаре, а также покажут конкретный пример увеличения производительности программы с помощью настроенного аллокатора.

• Зарегистрироваться на бесплатный вебинар