Кастомные аллокаторы в C++ и оптимизация управления памятью

int* ptr = new int; // Запрашиваем 4 байта, но реально выделяется больше

// Представим, что это происходит тысячи раз в цикле
for (int i = 0; i < 1000; i++) {
    int* smallBlock = new int[10];
    double* mediumBlock = new double[50];
    delete[] smallBlock;
    char* largeBlock = new char[200];
    delete[] mediumBlock;
    delete[] largeBlock;
}
// К концу выполнения куча будет сильно фрагментирована

// C++ стиль - вызывает конструктор и деструктор
MyClass* obj = new MyClass();
delete obj;
 
// C стиль - только выделение и освобождение памяти
void* raw = malloc(sizeof(MyClass));
free(raw);

// Стандартный new не гарантирует специального выравнивания
float* data = new float[4]; // Может быть не выровнен для SIMD-операций
 
// С C++17 появился aligned new
float* aligned_data = new(std::align_val_t(16)) float[4]; // Выровнено по 16 байт

// В многопоточной среде эти операции вызывают конкуренцию
// Thread 1
auto data1 = new SomeData(); // Блокирует глобальный мьютекс
 
// Thread 2 (ждёт, пока Thread 1 освободит мьютекс)
auto data2 = new SomeData(); // Вынужден ждать, даже если запрашивает память из другого региона

// Пример неэффективного доступа к памяти
struct BadLayout {
    char a;       // 1 байт
    double b;     // 8 байт, но из-за выравнивания занимает позицию с 8 по 15 байт
    char c;       // 1 байт, но занимает позицию с 16 по 23 байта (из-за выравнивания)
}; // Размер: 24 байта вместо теоретических 10 байт
 
// Более эффективная организация
struct GoodLayout {
    double b;     // 8 байт
    char a, c;    // 2 байта (упакованы вместе)
}; // Размер: 16 байт, лучшее использование кэш-линий

template<typename T>
class PoolAllocator {
    struct Block {
        Block* next;
        char data[sizeof(T)];
    };
    
    Block* freeList = nullptr;
    
public:
    PoolAllocator(size_t initialSize) {
        // Выделяем пул блоков
        char* memory = new char[sizeof(Block) * initialSize];
        freeList = reinterpret_cast<Block*>(memory);
        
        // Связываем блоки в список
        for (size_t i = 0; i < initialSize - 1; ++i) {
            Block* current = reinterpret_cast<Block*>(memory + i * sizeof(Block));
            current->next = reinterpret_cast<Block*>(memory + (i + 1) * sizeof(Block));
        }
        // Последний блок указывает в никуда
        Block* lastBlock = reinterpret_cast<Block*>(memory + (initialSize - 1) * sizeof(Block));
        lastBlock->next = nullptr;
    }
    
    T* allocate() {
        if (freeList == nullptr) {
            throw std::bad_alloc();
        }
        Block* block = freeList;
        freeList = freeList->next;
        return reinterpret_cast<T*>(block->data);
    }
    
    void deallocate(T* ptr) {
        Block* block = reinterpret_cast<Block*>(
            reinterpret_cast<char*>(ptr) - offsetof(Block, data)
        );
        block->next = freeList;
        freeList = block;
    }
    
    // Остальные методы опущены для краткости
};

class StackAllocator {
    char* memory;
    size_t capacity;
    size_t current;
    
public:
    StackAllocator(size_t size) : capacity(size), current(0) {
        memory = new char[size];
    }
    
    ~StackAllocator() {
        delete[] memory;
    }
    
    void* allocate(size_t size, size_t alignment = 8) {
        // Выравнивание адреса
        size_t alignmentPadding = 0;
        size_t currentAddress = reinterpret_cast<size_t>(memory + current);
        size_t alignmentMask = alignment - 1;
        
        if (currentAddress & alignmentMask) {
            alignmentPadding = alignment - (currentAddress & alignmentMask);
        }
        
        // Проверка наличия места
        if (current + alignmentPadding + size > capacity) {
            return nullptr; // Или throw std::bad_alloc()
        }
        
        current += alignmentPadding;
        void* alignedAddress = memory + current;
        current += size;
        
        return alignedAddress;
    }
    
    void deallocateAll() {
        // Просто сбрасываем указатель
        current = 0;
    }
    
    // Метод отката до маркера
    size_t getMarker() {
        return current;
    }
    
    void rollbackToMarker(size_t marker) {
        current = marker;
    }
};

class ArenaAllocator {
private:
    struct Chunk {
        Chunk* next;
        size_t size;
        size_t used;
        char data[1]; // Гибкий массив (нестандартный, но распространённый приём)
    };
    
    Chunk* currentChunk;
    size_t chunkSize;
    
public:
    ArenaAllocator(size_t initialSize = 4096) : chunkSize(initialSize), currentChunk(nullptr) {
        allocateChunk();
    }
    
    void* allocate(size_t size, size_t alignment = 8) {
        // Выравнивание
        size_t padding = calculatePadding(reinterpret_cast<uintptr_t>(currentChunk->data + currentChunk->used), alignment);
        
        // Если не хватает места в текущем чанке - создаём новый
        if (currentChunk->used + padding + size > currentChunk->size) {
            allocateChunk(std::max(chunkSize, size + sizeof(Chunk) - 1));
            padding = calculatePadding(reinterpret_cast<uintptr_t>(currentChunk->data), alignment);
        }
        
        void* ptr = currentChunk->data + currentChunk->used + padding;
        currentChunk->used += padding + size;
        
        return ptr;
    }
    
    void reset() {
        // Сбрасываем использование во всех чанках
        Chunk* chunk = currentChunk;
        while (chunk) {
            chunk->used = 0;
            chunk = chunk->next;
        }
    }
    
private:
    void allocateChunk(size_t minimumSize = 0) {
        size_t allocSize = std::max(chunkSize, minimumSize);
        Chunk* newChunk = reinterpret_cast<Chunk*>(malloc(sizeof(Chunk) + allocSize - 1));
        newChunk->size = allocSize;
        newChunk->used = 0;
        newChunk->next = currentChunk;
        currentChunk = newChunk;
    }
    
    size_t calculatePadding(uintptr_t address, size_t alignment) {
        return (alignment - (address & (alignment - 1))) & (alignment - 1);
    }
};

// Пример политики выделения: использование обычной кучи
struct MallocPolicy {
    static void* allocate(size_t size) {
        return malloc(size);
    }
    
    static void deallocate(void* ptr) {
        free(ptr);
    }
};
 
// Политика синхронизации: отсутствие синхронизации
struct NoLockPolicy {
    void lock() {}
    void unlock() {}
};
 
// Политика синхронизации: использование мьютекса
struct MutexPolicy {
    std::mutex mtx;
    void lock() { mtx.lock(); }
    void unlock() { mtx.unlock(); }
};
 
// Комбинирование политик в один аллокатор
template<typename AllocPolicy, typename SyncPolicy>
class PolicyAllocator : private SyncPolicy {
    AllocPolicy allocPolicy;
    
public:
    void* allocate(size_t size) {
        this->lock();
        void* ptr = allocPolicy.allocate(size);
        this->unlock();
        return ptr;
    }
    
    void deallocate(void* ptr) {
        this->lock();
        allocPolicy.deallocate(ptr);
        this->unlock();
    }
};
 
// Использование
using ThreadSafeAllocator = PolicyAllocator<MallocPolicy, MutexPolicy>;
using FastSingleThreadedAllocator = PolicyAllocator<MallocPolicy, NoLockPolicy>;

template<typename T>
class VectorPoolAllocator {
public:
    // Обязательные типы для STL
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    
    // Конвертер в другой тип
    template<typename U>
    struct rebind {
        using other = VectorPoolAllocator<U>;
    };
    
    VectorPoolAllocator() = default;
    
    // Конструктор для ребиндинга
    template<typename U>
    VectorPoolAllocator(const VectorPoolAllocator<U>&) {}
    
    // Методы выделения и освобождения памяти
    pointer allocate(size_type n) {
        // Здесь ваша логика выделения памяти
        return static_cast<pointer>(operator new(n * sizeof(T)));
    }
    
    void deallocate(pointer p, size_type) {
        // Здесь ваша логика освобождения памяти
        operator delete(p);
    }
    
    // Оператор сравнения (обычно для определения возможности переноса элементов)
    friend bool operator==(const VectorPoolAllocator&, const VectorPoolAllocator&) { return true; }
    friend bool operator!=(const VectorPoolAllocator&, const VectorPoolAllocator&) { return false; }
};
 
// Использование с std::vector
std::vector<int, VectorPoolAllocator<int>> myVector;

template<typename T>
class SimpleAllocator {
public:
    // Обязательные типы для STL
    using value_type = T;
    
    // Конструкторы
    SimpleAllocator() noexcept = default;
    
    template<typename U>
    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<class T, class U>
bool operator==(const SimpleAllocator<T>&, const SimpleAllocator<U>&) { return true; }
 
template<class T, class U>
bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&) { return false; }

template<size_t BlockSize>
class LinearAllocator {
private:
    char* memoryBlock;
    char* currentPosition;
    size_t remainingBytes;
 
public:
    LinearAllocator() : memoryBlock(nullptr), currentPosition(nullptr), remainingBytes(0) {
        memoryBlock = static_cast<char*>(std::malloc(BlockSize));
        if (!memoryBlock)
            throw std::bad_alloc();
            
        currentPosition = memoryBlock;
        remainingBytes = BlockSize;
    }
    
    ~LinearAllocator() {
        std::free(memoryBlock);
    }
    
    // Запрещаем копирование
    LinearAllocator(const LinearAllocator&) = delete;
    LinearAllocator& operator=(const LinearAllocator&) = delete;
    
    // Разрешаем перемещение
    LinearAllocator(LinearAllocator&& other) noexcept 
        : memoryBlock(other.memoryBlock), 
          currentPosition(other.currentPosition),
          remainingBytes(other.remainingBytes) {
        other.memoryBlock = nullptr;
        other.currentPosition = nullptr;
        other.remainingBytes = 0;
    }
    
    template<typename T>
    T* allocate(size_t count = 1) {
        // Вычисляем размер с учетом выравнивания
        size_t size = count * sizeof(T);
        size_t alignment = alignof(T);
        
        // Выравниваем адрес
        size_t mask = alignment - 1;
        uintptr_t addr = reinterpret_cast<uintptr_t>(currentPosition);
        size_t adjustment = (alignment - (addr & mask)) & mask;
        
        // Проверяем, хватает ли памяти
        if (remainingBytes < size + adjustment)
            throw std::bad_alloc();
            
        // Выделяем память
        char* alignedPosition = currentPosition + adjustment;
        currentPosition = alignedPosition + size;
        remainingBytes -= (size + adjustment);
        
        return reinterpret_cast<T*>(alignedPosition);
    }
    
    // Этот аллокатор не поддерживает освобождение отдельных блоков
    template<typename T>
    void deallocate(T*, size_t) noexcept {
        // Ничего не делаем - память будет освобождена только при уничтожении аллокатора
    }
    
    // Сбрасываем аллокатор в начальное состояние
    void reset() noexcept {
        currentPosition = memoryBlock;
        remainingBytes = BlockSize;
    }
};

template<typename T>
class ThreadSafeAllocator {
private:
    std::mutex allocationMutex;
    // Базовый аллокатор
    SimpleAllocator<T> baseAllocator;
 
public:
    using value_type = T;
    
    ThreadSafeAllocator() noexcept = default;
    
    template<typename U>
    ThreadSafeAllocator(const ThreadSafeAllocator<U>&) noexcept {}
    
    T* allocate(std::size_t n) {
        std::lock_guard<std::mutex> lock(allocationMutex);
        return baseAllocator.allocate(n);
    }
    
    void deallocate(T* p, std::size_t n) noexcept {
        std::lock_guard<std::mutex> lock(allocationMutex);
        baseAllocator.deallocate(p, n);
    }
};

template<typename T>
class FineGrainedAllocator {
private:
    static constexpr size_t NUM_POOLS = 16;
    std::array<std::mutex, NUM_POOLS> poolMutexes;
    std::array<char*, NUM_POOLS> pools;
    
    // Выбор пула на основе размера блока
    size_t poolIndex(size_t size) const {
        return std::min(size / 64, NUM_POOLS - 1);
    }
 
public:
    // ... Код сокращен для ясности
    
    T* allocate(std::size_t n) {
        size_t size = n * sizeof(T);
        size_t index = poolIndex(size);
        
        std::lock_guard<std::mutex> lock(poolMutexes[index]);
        // Аллокация из соответствующего пула
        // ...
    }
};

T* allocate(std::size_t n) {
    try {
        // Пытаемся выделить память
        if (n > MAX_ALLOCATION_SIZE)
            throw std::bad_alloc();
            
        void* memory = getRawMemory(n * sizeof(T));
        if (!memory)
            throw std::bad_alloc();
            
        return static_cast<T*>(memory);
    }
    catch (...) {
        // Записываем ошибку в лог, пытаемся восстановиться
        handleAllocationFailure(n);
        throw; // Перебрасываем исключение дальше
    }
}

template<typename T>
class NoExceptAllocator {
public:
    T* allocate(std::size_t n) noexcept {
        // Пытаемся выделить память
        void* memory = fallbackAllocate(n * sizeof(T));
        return static_cast<T*>(memory);
    }
    
private:
    void* fallbackAllocate(size_t size) noexcept {
        // Пробуем несколько стратегий аллокации
        void* ptr = primaryAlloc(size);
        if (ptr) return ptr;
        
        // Освобождаем кэш и другие ресурсы
        releaseUnusedMemory();
        
        ptr = primaryAlloc(size);
        if (ptr) return ptr;
        
        // Экстренное освобождение резервов
        ptr = emergencyAlloc(size);
        return ptr; // Может вернуть nullptr
    }
};

template<typename Derived>
class AllocatorBase {
public:
    template<typename T>
    T* allocate(std::size_t n) {
        // Вызываем метод дочернего класса без виртуального диспетчера
        return static_cast<Derived*>(this)->doAllocate(n * sizeof(T));
    }
    
    template<typename T>
    void deallocate(T* p, std::size_t n) {
        static_cast<Derived*>(this)->doDeallocate(p, n * sizeof(T));
    }
};
 
class PoolAllocator : public AllocatorBase<PoolAllocator> {
public:
    // Доступен для базового класса через CRTP
    void* doAllocate(std::size_t size) {
        // Реализация пулового выделения
        return nullptr; // Для примера
    }
    
    void doDeallocate(void* p, std::size_t size) {
        // Реализация возврата в пул
    }
};

template<typename Allocator>
void benchmark_allocation(size_t iterations, size_t blockSize) {
std::vector<void*> blocks;
blocks.reserve(iterations);
 
Allocator alloc;
auto start = std::chrono::high_resolution_clock::now();
 
// Измеряем скорость аллокации
for (size_t i = 0; i < iterations; ++i) {
    void* block = alloc.allocate(blockSize);
    blocks.push_back(block);
}
 
auto mid = std::chrono::high_resolution_clock::now();
 
// Измеряем скорость деаллокации
for (void* block : blocks) {
    alloc.deallocate(block, blockSize);
}
 
auto end = std::chrono::high_resolution_clock::now();
 
std::chrono::duration<double, std::milli> alloc_time = mid - start;
std::chrono::duration<double, std::milli> dealloc_time = end - mid;
 
std::cout << "Allocation time: " << alloc_time.count() << " ms\n";
std::cout << "Deallocation time: " << dealloc_time.count() << " ms\n";
}

#include <benchmark/benchmark.h>
 
template<typename Allocator>
void BM_Allocation(benchmark::State& state) {
Allocator alloc;
const size_t blockSize = state.range(0);
 
for (auto _ : state) {
    void* ptr = alloc.allocate(blockSize);
    benchmark::DoNotOptimize(ptr);
    alloc.deallocate(ptr, blockSize);
}
 
state.SetItemsProcessed(state.iterations());
state.SetBytesProcessed(state.iterations() * blockSize);
}
 
// Регистрация бенчмарка с разными размерами блоков
BENCHMARK_TEMPLATE(BM_Allocation, StdAllocator)->Range(8, 8<<10);
BENCHMARK_TEMPLATE(BM_Allocation, PoolAllocator)->Range(8, 8<<10);
BENCHMARK_TEMPLATE(BM_Allocation, LinearAllocator)->Range(8, 8<<10);

// Тест однородных аллокаций (один размер)
void uniform_allocation_test(Allocator& alloc, size_t block_size, size_t count) {
    std::vector<void*> blocks(count);
    
    // Измеряем pure allocation
    auto start = high_precision_clock();
    for (size_t i = 0; i < count; ++i) {
        blocks[i] = alloc.allocate(block_size);
    }
    auto mid = high_precision_clock();
    
    // Измеряем pure deallocation
    for (size_t i = 0; i < count; ++i) {
        alloc.deallocate(blocks[i], block_size);
    }
    auto end = high_precision_clock();
    
    // Анализ результатов...
}
 
// Тест смешанных аллокаций разных размеров
void mixed_allocation_test(Allocator& alloc, 
                          const std::vector<size_t>& sizes, 
                          size_t operations) {
    std::vector<std::pair<void*, size_t>> blocks;
    blocks.reserve(operations);
    
    auto start = high_precision_clock();
    for (size_t i = 0; i < operations; ++i) {
        // Случайно выбираем: аллокация или освобождение
        if (blocks.empty() || (rand() % 100 < 70)) {  // 70% шанс аллокации
            size_t size = sizes[rand() % sizes.size()];
            void* ptr = alloc.allocate(size);
            blocks.emplace_back(ptr, size);
        } else {
            // Освобождаем случайный блок
            size_t index = rand() % blocks.size();
            alloc.deallocate(blocks[index].first, blocks[index].second);
            blocks[index] = blocks.back();
            blocks.pop_back();
        }
    }
    auto end = high_precision_clock();
    
    // Освобождаем оставшиеся блоки
    for (auto& [ptr, size] : blocks) {
        alloc.deallocate(ptr, size);
    }
    
    // Анализ результатов...
}

// Пример использования кастомных аллокаторов в Unreal Engine
TArray<FVector, TInlineAllocator<16>> TemporaryPoints;  // Использует встроенный буфер для первых 16 элементов
TArray<FVector, TFixedSizeAllocator<256>> LimitedPoints;  // Ограничивает размер массива

// Упрощённый пример преаллокации для торговой системы
class TradingEngine {
private:
    PoolAllocator<Order, 10000> orderPool;  // Пул на 10000 заказов
    PoolAllocator<Trade, 5000> tradePool;   // Пул на 5000 сделок
    
public:
    Order* createOrder() {
        return orderPool.allocate();
    }
    
    void executeOrder(Order* order) {
        Trade* trade = tradePool.allocate();
        // Логика исполнения заказа
    }
};

// Пример использования пулового аллокатора в RTOS
StaticMemoryPool_t memoryPool;
uint8_t poolStorage[1024];
 
// Инициализация пула фиксированных блоков
MemoryPool_Init(&memoryPool, 32, 32, poolStorage);
 
// Аллокация из пула
void* data = MemoryPool_Alloc(&memoryPool);
if (data) {
    // Работа с данными
    MemoryPool_Free(&memoryPool, data);
}

// Выбор аллокатора в зависимости от контекста
template<typename T>
using FastAllocation = 
    std::conditional_t<sizeof(T) <= 64,
                      PoolAllocator<T>,
                      std::conditional_t<std::is_trivially_destructible_v<T>,
                                        LinearAllocator<T>,
                                        ThreadSafeAllocator<T>>>;

// Потенциальная катастрофа
PoolAllocator<int> allocA;
LinearAllocator<int> allocB;
 
int* valueA = allocA.allocate();
// ...
allocB.deallocate(valueA); // BOOM! Неправильный аллокатор