28 December, 2021

C++17 introduced polymorphic allocators, but what problem do they solve?

Polymorphic Allocators in C++

Standard Library Containers use Allocators

Containers in C++ are typically defined in terms of their type, supplied as a template parameter. For example, here’s a vector of int.

std::vector<int> vectorOfInt = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23};

However, if you look at the definition for std::vector then you’ll see that there are actually two template parameters. The first template parameter is the type of the object stored in the container, and the second is an Allocator for it. This second template parameter defaults to std::allocator<T>.

Standard library containers use allocators to allocate and deallocate memory. In fact, nearly all standard library components that need to allocate or deallocate memory use an allocator to do so.

Here’s a vector of int that uses std::allocator<int> explicitly.

std::vector<int, std::allocator<int>> vectorOfIntStdAllocator;

You can assign between these vectors because they’re the same type. In other words, std::vector<int> is the same type as std::vector<int, std::allocator<int>>.

// Same type, so assignment is possible.
vectorOfIntStdAllocator = vectorOfInt;
vectorOfInt = vectorOfIntStdAllocator;

Implementing an Allocator

By its nature, std::allocator is general purpose and therefore has to cater for many scenarios. It has no idea if your application needs a large number of similarly sized objects, or objects of a wide variety of sizes. It has no idea if they’ll be short-lived or long-lived, or if they’ll be large or small.

It won’t be as efficient as a custom allocator because it has no way of knowing about the memory usage of your application.

Fortunately, the containers in the C++ standard library allow you to provide your own custom allocators that are more suited to your needs. For example, if you’re handling something short-lived, such as a web request in which none of the objects will be needed once the response has been sent, then you could use a bump allocator that never deallocates, then frees memory in one operation at the end, once the request has been handled.

To be an allocator, a class has to meet certain named requirements. The named requirements for Allocator are defined on this page in cppreference.com.

A minimal C++11 allocator

Here’s a minimal C++11 allocator, based on the example from that page. It is written in terms of malloc() and free(), and logs allocations and deallocations to stdout.

template<class T>
struct ChattyAllocator
{
    using value_type = T;

    ChattyAllocator() = default;

    template<class U>
    constexpr ChattyAllocator(const ChattyAllocator<U>&) noexcept
    {
    }

    [[nodiscard]] T* allocate(std::size_t n)
    {
        if (n > std::numeric_limits<std::size_t>::max() / sizeof(T))
        {
            throw std::bad_array_new_length();
        }

        if (auto p = static_cast<T*>(std::malloc(n * sizeof(T))))
        {
            std::cout << "Allocated " << n * sizeof(T) << " bytes at 0x" << std::hex
                      << reinterpret_cast<void*>(p) << std::dec << '\n';
            return p;
        }

        throw std::bad_alloc();
    }

    void deallocate(T* p, std::size_t n) noexcept
    {
        std::cout << "Deallocated " << n * sizeof(T) << " bytes at 0x" << std::hex
                  << reinterpret_cast<void*>(p) << std::dec << '\n';
        std::free(p);
    }
};

template<class T, class U>
bool operator==(const ChattyAllocator<T>&, const ChattyAllocator<U>&)
{
    return true;
}

template<class T, class U>
bool operator!=(const ChattyAllocator<T>&, const ChattyAllocator<U>&)
{
    return false;
}

Here’s a vector of int that uses the ChattyAllocator.

std::vector<int, ChattyAllocator<int>> vectorWithCustomAllocator;

Unfortunately, using a different allocator changes the type of the vector. The vectors up to this point have been std::vector<int, std::allocator<int>>, but the new one is std::vector<int, ChattyAllocator<int>>.

Assignment between these vectors is not allowed, because they’re different types.

// Assigning from std::vector<int, ChattyAllocator<int>> to std::vector<int> is not allowed.
vectorOfInt = vectorWithCustomAllocator;

// Assigning from std::vector<int> to std::vector<int, ChattyAllocator<int>> is not allowed.
vectorWithCustomAllocator = vectorOfInt;

Polymorphic Allocators and Memory Resources

To solve this problem, C++17 introduced polymorphic allocators, in which allocators use memory resources to perform allocation and deallocations on their behalf. Polymorphic allocators and memory resources come from the <memory_resource> header.

Here’s a vector of int that uses a polymorphic allocator.

std::pmr::vector<int> vectorOfIntPmr = {29, 31, 37, 41, 43, 47, 53, 59, 61, 67};

Note that std::pmr::vector<int> is an alias for std::vector<int, std::pmr::polymorphic_allocator<int>>.

std::vector<int, std::pmr::polymorphic_allocator<int>> vectorOfIntPmrAllocator;

You can assign between these vectors because they’re the same type. In other words, std::pmr::vector<int> is the same type as std::vector<int, std::pmr::polymorphic_allocator<int>>.

vectorOfIntPmrAllocator = vectorOfIntPmr;
vectorOfIntPmr = vectorOfIntPmrAllocator;

You might think that there’s nothing new here as this was also possible with std::vector<int> and std::vector<int, std::allocator<int>>. However, polymorphic allocators, in combination with memory resources, allow for assignment between allocators that use different allocation strategies.

Memory resources derive from std::pmr::memory_resource, and look very much like allocators, in that they have allocate() and deallocate() methods. They are implemented by overriding the pure virtual methods do_allocate(), do_deallocate(), and do_is_equal().

A minimal memory resource

Here’s a minimal example of a memory resource. It uses std::pmr::new_delete_resource() to allocate and deallocate memory. As with ChattyAllocator, it also logs allocations and deallocations to stdout.

class ChattyMemoryResource : public std::pmr::memory_resource
{
    void* do_allocate(std::size_t n, std::size_t alignment) override
    {
        void* p = std::pmr::new_delete_resource()->allocate(n, alignment);
        std::cout << "Allocated " << n << " bytes at 0x" << std::hex << reinterpret_cast<void*>(p)
                  << std::dec << '\n';
        return p;
    }

    void do_deallocate(void* p, std::size_t n, std::size_t alignment) override
    {
        std::cout << "Deallocated " << n << " bytes at 0x" << std::hex << reinterpret_cast<void*>(p)
                  << std::dec << '\n';
        return std::pmr::new_delete_resource()->deallocate(p, n, alignment);
    }

    bool do_is_equal(const std::pmr::memory_resource& other) const noexcept override
    {
        return std::pmr::new_delete_resource()->is_equal(other);
    }
};

Here’s a polymorphic allocator that uses it.

ChattyMemoryResource chattyMemoryResource;
std::pmr::polymorphic_allocator<int> chattyPolymorphicAllocator(&chattyMemoryResource);

Here’s a vector of int that uses the new polymorphic allocator.

std::pmr::vector<int> vectorOfIntChattyPolymorphicAllocator{chattyPolymorphicAllocator};

You can assign between vectors that use polymorphic allocators, even when those allocators use different memory resources.

vectorOfIntChattyPolymorphicAllocator = vectorOfIntPmr;
vectorOfIntPmr = vectorOfIntChattyPolymorphicAllocator;

And that’s the problem solved by polymorphic allocators.

Gotchas

There are, of course, caveats. The notes section for polymorphic allocators on cppreference.com gives a warning that polymorphic allocator does not propagate on container copy assignment, move assignment or swap, and goes on to explain the implications.