CODEWITHSUNDEEP
c++containersc++20allocator
Steven
Steven

Reputation: 700

Given that allocators are copied by value how is allocator state shared?

I have implemented a custom allocator that takes a block of memory from the stack and allocates linearly out of it, ignoring calls to deallocate.
This is used with a std::map to improve performance in a tight loop.

template <typename T>
struct region_allocator
{
    using value_type = T;

    region_allocator() = delete;

    region_allocator( void* baseAddress, size_t sizeInBytes )
    {
        m_memBegin = (char*)baseAddress;
        m_memCurr = m_memBegin;
        m_memEnd = m_memCurr + sizeInBytes;
    }

    template <class U>
    constexpr region_allocator( const region_allocator<U>& other ) noexcept
    {
        m_memBegin = other.m_memBegin;
        m_memCurr = other.m_memCurr;
        m_memEnd = other.m_memEnd;
    }

    template <class U>
    struct rebind
    {
        using other = region_allocator<U>;
    };

    T* allocate( std::size_t n )
    {
        char* address = m_memCurr;

        size_t sizeRequired = sizeof( T ) * n;

        m_memCurr += sizeRequired;

        if( m_memCurr > m_memEnd ) [[unlikely]] 
        {
            m_memCurr -= sizeRequired;
            assert( "Out of memory" );
        }

        return (T*)address;
    }

    void deallocate( T* p, std::size_t n ) noexcept
    {
        // don't free; caller will release full block
    }

protected:
    template <class U>
    friend struct region_allocator;

    char* m_memCurr = nullptr;
    char* m_memEnd = nullptr;
    char* m_memBegin = nullptr;
};

template <class T, class U>
bool operator==( const region_allocator<T>& lhs, const region_allocator<U>& rhs ) noexcept
{
    if( lhs.m_memBegin != rhs.m_memBegin )
        return false;
    if( lhs.m_memEnd != rhs.m_memEnd )
        return false;
    return true;
}

Regardless of whether this is the best algorithmic solution, the problem I am encountering is that the allocator is copied by value during the rebind operation, and state is copied, and the original allocator instance passed in does not see the changes in state as allocations are made.

I understand that allocators are copied by value. I see that what I want to do is hold onto a shared instance of the allocator state (current offset into the block of memory), but I am not clear on the best pattern to do that.

What pattern do others use for this problem?

Upvotes: 4

Views: 138

Answers (2)

wohlstad
wohlstad

Reputation: 28049

the allocator is copied by value during the rebind operation, and state is copied, and the original allocator instance passed in does not see the changes in state as allocations are made.

In order to overcome this, you can utilize the shared ownership that std::shared_ptr offers:

Extract the state of the allocator into a new inner class like region_allocator_state, and instead of holding the state members directly in your allocator, use a member of type std::shared_ptr<region_allocator_state> in it.

Below is a skeleton for the solution using this approach:

#include <memory>  // for std::shared_ptr

template <typename T>
struct region_allocator {
    using value_type = T;

    region_allocator() = delete;

    region_allocator( void* baseAddress, size_t sizeInBytes ) {
        // initialize m_state ...
    }

    template <class U>
    constexpr region_allocator( const region_allocator<U>& other ) noexcept {
        // copy m_state ...
    }

    T* allocate( std::size_t n ) {
        // update the data in m_state and return pointer to block ...
    }


    // ...
 
protected:
    class region_allocator_state {
        region_allocator_base( void* baseAddress, size_t sizeInBytes ) { 
            // initialize state members ...  
        }

        char* m_memCurr = nullptr;
        char* m_memEnd = nullptr;
        char* m_memBegin = nullptr;
    };

    std::shared_ptr<region_allocator_state> m_state;
};

Upvotes: 3

Eugene
Eugene

Reputation: 7160

A stateful allocator is supposed to be a handle for a separate memory resource.

Standard C++ library, starting from C++17, has polymorphic allocators following this pattern. Its std::pmr::polymorphic_allocator points to base class std::pmr::memory_resource. The classes derived from it include std::pmr::monotonic_buffer_resource, similar to your idea of region_allocator. You can also use std::pmr::map alias for std::map that uses std::pmr::polymorphic_allocator.

If, after profiling, you find that you cannot afford polymorphism in allocators, you can use this design as an example of how to make your own non-polymorphic one.

There are a few pitfalls with std::pmr::monotonic_buffer_resource (which you will also likely have if you create a similar allocator on your own). The problem is who owns the memory resource object and what happens if the container using it is copied or moved.

For more details, please study "Allocators" chapter in this excellent book: Mastering the C++17 STL

Upvotes: 2

Related Questions