Аллокаторы памяти06.06.2020 21:32

Предполагается, что STL контейнеры обращаются к аллокатору не напрямую, а через шаблон std: allocator_traits, который предоставляет значения, такие как:

typedef T* pointer;
typedef const T* const_pointer; 
… 

Отлично, с требованиями разобрались, теперь наконец приступаем к написанию аллокатора. Для начала напишем некоторый интерфейс или адаптер, на самом деле это трудно назвать и тем, и другим, поэтому пусть это будет некая «прослойка», в которой при помощи стратегий мы сможем без проблем менять алгоритм аллоцирования памяти для определенных целей:

// Common interface for interaction with STL
// containers and algorithms. You can manually change
// allocation algorithm with different 'AllocationStrategy'
//
// In this implementation was not implented 'adress' and 'max_size'
// unnecessary functions for.

template
class Allocator
{
    static_assert(!std::is_same_v, "Type of the allocator can not be void");
public:
    using value_type = T;

    template
    friend class Allocator;
    
    template
    struct rebind
    {
        using other = Allocator;
    };
public:
    Allocator() = default;
    
    explicit Allocator(AllocationStrategy& strategy) noexcept
        : m_allocation_strategy(&strategy) {}
    
    Allocator(const Allocator& other) noexcept
        : m_allocation_strategy(other.m_allocation_strategy) {}
    
    template
    Allocator(const Allocator& other) noexcept
        : m_allocation_strategy(other.m_allocation_strategy) {}
    
    T* allocate(std::size_t count_objects)
    {
        assert(m_allocation_strategy && "Not initialized allocation strategy");
        return static_cast(m_allocation_strategy->allocate(count_objects * sizeof(T)));
    }
    
    void deallocate(void* memory_ptr, std::size_t count_objects)
    {
        assert(m_allocation_strategy && "Not initialized allocation strategy");
        m_allocation_strategy->deallocate(memory_ptr, count_objects * sizeof(T));
    }
    
    template
    void construct(U* ptr, Args&&... args)
    {
        new (reinterpret_cast(ptr)) U { std::forward(args)... };
    }
    
    template
    void destroy(U* ptr)
    {
        ptr->~U();
    }
private:
    AllocationStrategy* m_allocation_strategy = nullptr;
};

template
bool operator==(const Allocator& lhs, const Allocator& rhs)
{
    return lhs.m_allocation_strategy == rhs.m_allocation_strategy;
}

template
bool operator!=(const Allocator& lhs, const Allocator& rhs)
{
    return !(lhs == rhs);
}

Благодаря стратегии для распределения памяти, мы сможем делать примерно вот так:

template
using AllocatorForSmallObjects = Allocator;
template
using AllocatorForBigObjects = Allocator;

То есть мы можем гибко менять алгоритмы распределения для необходимых целей в той или иной ситуации. Единственное требование к AllocationStrategy — у них должны быть операции allocate и deallocate.

// Strategy for manipulation memory chunks, like
// a primitive malloc allocator.
//
// Warning: if you try to deallocate some random block
// of the memory, most of all it will be an undefined behavior,
// because current implementation doesn't check this possible situation.

template
class CustomAllocationStrategy
{
    static_assert(CHUNK_SIZE != 0u, "Chunk size must be more, than zero");
    static_assert(CHUNK_SIZE <= std::numeric_limits::max(),
        "Chunk size must be less or equal max value of the uint32_t");
public:
    void* allocate(std::size_t size)
    {
        assert(size < CHUNK_SIZE && "Incorrect chunk size for future usage");

        if (size == 0u)
        {
            return nullptr;
        }
        
        for (auto& chunk : m_chunks)
        {
            void* allocated_block = chunk.tryReserveBlock(size);
            if (allocated_block) //if the block was not reserved, then memory in the chunk has run out
            {
                return allocated_block;
            }
        }

        m_chunks.push_back(details::Chunk{});
        auto& chunk = m_chunks.back();
        std::uint8_t* allocated_block = chunk.tryReserveBlock(size);
        return allocated_block;
    }

    void deallocate(void* memory_ptr, std::size_t size)
    {
        if ( (!memory_ptr) || (size == 0u) )
        {
            return;
        }

        std::uint8_t* deallocation_ptr = static_cast(memory_ptr);
        for (auto& chunk : m_chunks)
        {
            if (chunk.isInside(deallocation_ptr))
            {
                chunk.releaseBlock(deallocation_ptr);
            }
        }
    }
private:
    std::deque> m_chunks{ 1u };
};

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

namespace details
{

    std::size_t getAlignmentPadding(std::size_t not_aligned_address, std::size_t alignment)
    {
        if ( (alignment != 0u) && (not_aligned_address % alignment != 0u) )
        {
            const std::size_t multiplier = (not_aligned_address / alignment) + 1u;
            const std::size_t aligned_address = multiplier * alignment;
            return aligned_address - not_aligned_address;
        }

        return 0u;
    }

    // Current chunk implementation works only with size
    // aligned by 4 bytes, because HEADER_SIZE now also 4 bytes.
    // You can modify it with HEADER_SIZE without problems for your purposes.

    template
    class Chunk
    {
        static constexpr std::size_t HEADER_SIZE = 4u;
        static_assert(CHUNK_SIZE % HEADER_SIZE == 0, "CHUNK_SIZE must be multiple of the four");
        static_assert(CHUNK_SIZE > HEADER_SIZE, "CHUNK_SIZE must be more than HEADER_SIZE");
    public:
        Chunk()
        {
            m_blocks.resize(CHUNK_SIZE);
            std::uint32_t* init_header = reinterpret_cast(m_blocks.data());
            *init_header = CHUNK_SIZE - HEADER_SIZE;
            m_max_block = init_header;
            m_free_blocks.insert(init_header);
        }
        
        bool isInside(const std::uint8_t* address) const noexcept
        {
            const std::uint8_t* start_chunk_address = reinterpret_cast(m_blocks.data());
            const std::uint8_t* end_chunk_address = start_chunk_address + CHUNK_SIZE;
            return (start_chunk_address <= address) && (address <= end_chunk_address);
        }
        
        std::uint8_t* tryReserveBlock(std::size_t allocation_size)
        {
            const std::size_t not_aligned_address = reinterpret_cast(m_max_block) + allocation_size;
            const std::size_t alignment_padding = getAlignmentPadding(not_aligned_address, HEADER_SIZE);
            const std::uint32_t allocation_size_with_alignment = static_cast(allocation_size + alignment_padding);
            if ( (!m_max_block) || (allocation_size_with_alignment > *m_max_block) ) // Check on enaught memory for allocation
            {
                return nullptr;
            }
            
            // Find min available by size memory block
            const auto min_it = std::min_element(m_free_blocks.cbegin(), m_free_blocks.cend(), [allocation_size_with_alignment] (const std::uint32_t* lhs, const std::uint32_t* rhs)
            {
                if (*rhs < allocation_size_with_alignment)
                {
                    return true;
                }
                
                return (*lhs < *rhs) && (*lhs >= allocation_size_with_alignment);
            });
            
            assert(min_it != m_free_blocks.cend() && "Internal logic error with reserve block, something wrong in implementation...");
            assert(**min_it >= allocation_size_with_alignment && "Internal logic error with reserve block, something wrong in implementation...");
            
            std::uint32_t* header_address = *min_it;
            std::uint32_t* new_header_address =
                reinterpret_cast(reinterpret_cast(header_address) + HEADER_SIZE + allocation_size_with_alignment);
            if (m_free_blocks.find(new_header_address) == m_free_blocks.cend()) // check if there is free memory in the current block
            {
                const std::uint32_t old_block_size = *header_address;
                const std::uint32_t difference = old_block_size - HEADER_SIZE;
                if (difference >= allocation_size_with_alignment) // check if there is enough space for another block
                {
                    const std::uint32_t new_block_size = difference - allocation_size_with_alignment;
                    *new_header_address = new_block_size;
                    m_free_blocks.insert(new_header_address);
                }
            }
            
            m_free_blocks.erase(header_address);
            *header_address = static_cast(allocation_size);
            if (header_address == m_max_block) // if the maximum block were changed, then need to find the maximum block again
            {
                // Find max block by size
                const auto max_it = std::max_element(m_free_blocks.cbegin(), m_free_blocks.cend(), [] (const std::uint32_t* lhs, const std::uint32_t* rhs)
                {
                    return (*lhs) < (*rhs);
                });
                
                // If there are no free blocks, therefore the memory in this chunk is over
                m_max_block = (max_it != m_free_blocks.cend()) ? (*max_it) : (nullptr);
            }

            return reinterpret_cast(header_address) + HEADER_SIZE;
        }
        
        void releaseBlock(std::uint8_t* block_ptr)
        {
            std::uint8_t* header_address = block_ptr - HEADER_SIZE;
            const std::uint32_t size_relized_block = *header_address;
            if ( (!m_max_block) || (size_relized_block > *m_max_block) ) // if the relized block is greater than the maximum, then need to replace it
            {
                m_max_block = reinterpret_cast(header_address);
            }
                
            m_free_blocks.insert(reinterpret_cast(header_address));
            auto forward_it = m_free_blocks.find(reinterpret_cast(header_address));
            auto backward_it = tryDefragment(forward_it, m_free_blocks.end());
            tryDefragment(std::make_reverse_iterator(backward_it), m_free_blocks.rend());
        }
    private:
        template
        constexpr DstIterator getIterator(SrcIterator it) const
        {
            using iterator = std::set::iterator;
            using reverse_iterator = std::set::reverse_iterator;
            if constexpr ( (std::is_same_v) && (std::is_same_v) )
            {
                return std::make_reverse_iterator(it);
            }
            else if constexpr ( (std::is_same_v) && (std::is_same_v) )
            {
                return it.base();
            }
            else
            {
                return it;
            }
        }
        
        template
        Iterator tryDefragment(Iterator start_it, Iterator end_it)
        {
            // primitive defragmentation algorithm - connects two neighboring
            // free blocks into one with linear complexity
   
            auto current_it = start_it++;
            auto next_it = start_it;
            std::uint32_t* current_header_address = *current_it;
            if ( (current_it != end_it) && (next_it != end_it) )
            {
                std::uint32_t* next_header_address = *next_it;
                const std::uint32_t current_block_size = *current_header_address;
                const std::uint32_t* available_current_block_address =
                    reinterpret_cast(reinterpret_cast(current_header_address) + HEADER_SIZE + current_block_size);
                if (available_current_block_address == next_header_address)
                {
                    const std::uint32_t next_block_size = *next_header_address;
                    const std::uint32_t new_current_block_size = current_block_size + HEADER_SIZE + next_block_size;
                    *current_header_address = new_current_block_size;
                    if (new_current_block_size > *m_max_block)
                    {
                        m_max_block = reinterpret_cast(current_header_address);
                    }
                            
                    auto delete_it = getIterator::iterator>(next_it);
                    return getIterator(m_free_blocks.erase(delete_it));
                }
            }
            
            return current_it;
        }
    public:
        std::vector m_blocks;
        std::set m_free_blocks;
        std::uint32_t* m_max_block;
    };

}

Теперь немного о том, как можно украсить использование аллокаторов вместе со стандартными контейнерами:

template
using CustomAllocator = Allocator>;

template
using CustomAllocatorWithStackChunks = Allocator>;

template
using CustomAllocatorWithHeapChunks = Allocator>;

template
using custom_vector = std::vector>;

template
using custom_list = std::list>;

template
using custom_set = std::set, CustomAllocator>;

template
using custom_unordered_set = std::unordered_set, std::equal_to, CustomAllocator>;

template
using custom_map = std::map, CustomAllocator>>;

template
using custom_unordered_map = std::unordered_map, std::equal_to, CustomAllocator>>;

using custom_string = std::basic_string, CustomAllocator>;

Можно также использовать аллокаторы и с умными указателями, но для этого придется написать небольшую прослойку:

template
using custom_unique_ptr = std::unique_ptr>;

template
custom_unique_ptr make_custom_unique(Allocator allocator, Args&&... args)
{
    const auto custom_deleter = [allocator](T* ptr) mutable
    {
        allocator.destroy(ptr);
        allocator.deallocate(ptr, 1u);
    };
        
    void* memory_block = allocator.allocate(1u);
    if (memory_block)
    {
        T* object_block = static_cast(memory_block);
        allocator.construct(object_block, std::forward(args)...);
        return custom_unique_ptr{ object_block, custom_deleter };
    }

    return nullptr;
}

Ну и теперь, наконец, пример использования всего этого:

int main(int argc, char** argv)
{
    CustomAllocationStrategy allocation_area{};

    CustomAllocator custom_int_allocator{ allocation_area };
    custom_vector vector{ custom_int_allocator };
    for (int i = 0u; i < 100; ++i)
    {
        vector.push_back(i);
        std::cout << vector.at(i) << " ";
    }
    
    vector.resize(16u);
    for (int val : vector)
    {
        std::cout << val << " ";
    }

CustomAllocator custom_int_allocator_copy = vector.get_allocator();
    custom_unique_ptr ptr1 = make_custom_unique>(custom_int_allocator_copy, 100);
    custom_unique_ptr ptr2 = make_custom_unique>(custom_int_allocator_copy, 500);
    custom_unique_ptr ptr3 = make_custom_unique>(custom_int_allocator_copy, 1000);
    custom_unique_ptr ptr4 = make_custom_unique>(custom_int_allocator_copy, 1500);
    std::cout << *ptr1 << " " << *ptr2 << " " << *ptr3 << " " << *ptr4 << " ";
    
    CustomAllocator custom_float_allocator { custom_int_allocator };
    custom_list list{ { 10.0f, 11.0f, 12.0f, 13.0f, 14.0f, 15.0f }, custom_float_allocator };
    for (float val : list)
    {
        std::cout << val << " ";
    }
    
    CustomAllocator> custom_pair_allocator{ allocation_area };
    custom_map map{ { { 1.0, 100.0 }, { 2.0, 200.0 } }, custom_pair_allocator };
    for (const auto& it : map)
    {
        std::cout << "{" << it.first << " : " << it.second << "} ";
    }
    
    CustomAllocator custom_double_allocator{ allocation_area };
    custom_set set{ { 1000.0, 2000.0, 3000.0 }, custom_double_allocator };
    for (double val : set)
    {
        std::cout << val << " ";
    }

    CustomAllocator custom_char_allocator{ allocation_area };
    custom_string string1{ "First allocated string without SBO ", custom_char_allocator };
    custom_string string2{ "Second allocated string without SBO ", custom_char_allocator };
    custom_string string3{ "Third allocated string without SBO ", custom_char_allocator };
    custom_string result_string = string1 + string2 + string3;
    std::cout << result_string;
    
    return EXIT_SUCCESS;
}

Хотелось бы заострить внимание на том, что данная реализация является самой примитивной, но она может быть без проблем расширена в ту сторону, которая вам необходима, поэтому все в ваших руках!

Заключение

Спасибо за внимание, очень надеюсь, что данная статья оказалась кому-то полезной. Также желаю всем успехов в тесном взаимодействии с памятью, и самое главное, не забывать очень важные слова Дональда Кнута:»Преждевременная оптимизация — корень всех зол».

Ссылка на репозиторий с полной реализацией аллокатора.

Используемые источники

1. habr.com/ru/post/274827
2. github.com/mtrebi/memory-allocators

© Habrahabr.ru