Thanks for the memory (allocator)

One of the design goals of Modern C++ is to find new ways – better, more effective – of doing things we could already do in C++.  Some might argue this is one of the more frustrating aspects of Modern C++ – if it works, don’t fix it (alternatively: why use lightbulbs when we have perfectly good candles?!)

This time we’ll look at a new aspect of Modern C++:  the Allocator model for dynamic containers.  This is currently experimental, but has been accepted into C++20.

The Allocator model allows programmers to provide their own memory management strategy in place of their library’s default implementation.  Although it is not specified by the C++ standard, many implementations use malloc/free.

Understanding this feature is important if you work on a high-integrity, or safety-critical, project where your project standards say ‘no’ to malloc.

The Standard Template Library model

The Standard Template Library (STL) has a model of separation-of-concerns.  The basic separation is:

• Containers hold, and manage the lifetime of, data
• Algorithms process data from containers
• Iterators provide an interface to allow algorithms to access / manipulate elements in containers

There are three additional concepts that need to be included:

• Functors allow clients to provide callbacks / predicates to algorithms
• Adapters provide consistent interfaces to heterogeneous classes
• Allocators manage ‘raw’ memory for containers.

It is this final element – Allocators – that we will be looking at in this article.  In particular the changes to the Allocator model brought in with C++17.

Containers and allocators

All standard library components that need to allocate storage (with the exception of std::array, std::shared_ptr and std::function) do so via an allocator.  That includes (not surprisingly) the STL dynamic containers; and also components like std::string.

The allocator is responsible for managing raw memory storage; and also for constructing / destroying allocated objects.  C++ uses Allocator to define a set of requirements, rather than an actual type.  Any type that fulfils the requirements of Allocator can be used for memory allocation/deallocation by containers (etc).

Any component requiring memory allocation has its Allocator provided as a template parameter.  Let’s use the declaration for std::vector

template<typename T, typename Allocator = std::allocator<T>>
class vector;

Notice the Allocator template parameter is defaulted to std::allocator.  This Allocator implementation uses the free store as its memory resource.

A quick aside:

What’s the difference between the free store and the heap?

In C++, the free store is the region of memory used for dynamic object allocations.  It is the region used by new and delete.

The heap is the other region of dynamic memory allocation; this being used by malloc/free.

That said, this difference is largely conceptual.  In many implementations the free store and the heap are mapped to the same memory section; and many implementations of new/delete use malloc/free underneath.

Most programmers (myself included) tend to use the terms interchangeably.  You could argue keeping the concepts separate is a useful way to reinforce the fact you should NEVER intermix new/delete and malloc/free.

Building an Allocator

Since Allocator defines a set of requirements, we can implement our own allocator type.  This is useful since many embedded projects, particularly high-integrity ones, preclude the use of heap (or more specifically, the malloc algorithm) as a memory resource.

To explore this, let’s build a very simple fixed-block allocator for use with containers.

Building an allocator in C++03 was reasonably straightforward, but required a fair amount of what might be considered ‘boilerplate’ code.  It was decided, for C++11, to simplify the Allocator minimum requirements; making many of the Allocator’s definitions optional.  This makes creating allocators considerably less onerous in Modern C++.

The allocator is a template class; with the template parameter being the type of object being allocated.

template <typename T>
class Pool_allocator {
public:
  using value_type = T;

  T* allocate(size_t num);
  T* allocate(size_t num, const void* hint);
  void deallocate(T* ptr, size_t num);

  Pool_allocator(const Pool_allocator&)            = default;
  Pool_allocator(Pool_allocator&&)                 = default;
  Pool_allocator& operator=(const Pool_allocator&) = default;
  Pool_allocator& operator=(Pool_allocator&&)      = default;
};


template <typename T1, typename T2>
bool operator==(
    const Pool_allocator<T1>& lhs, 
    const Pool_allocator<T2>& rhs
);


template <typename T1, typename T2>
bool operator!=(
    const Pool_allocator<T1>& lhs, 
    const Pool_allocator<T2>& rhs
)

I’ve ignored constructors and destructors for this example, since our allocator has no internal state.

Note, however, an Allocator must support copy (and move) construction.  In our case the default implementations are fine.

Next, the critical functions – allocation and deallocation

An Allocator allocates a number of objects, rather than raw bytes of memory; and the interface reflects that.  Let’s assume for this article we have some fixed-block memory resource already created.

template <typename T>
T* Pool_allocator<T>::allocate(size_t num)
{
  T* ptr = reinterpret_cast<T*>(fixed_block_alloc(num * sizeof(T)));
  return ptr;
}


template <typename T>
void Pool_allocator<T>::deallocate(T* p, size_t num [[maybe_unused]])
{
  fixed_block_dealloc(p);
}

Notice the allocate() method allocates num * sizeof(T) bytes of raw memory and returns a pointer.  Elements are not constructed/initialised – no constructors must be called.

There is a second overload of allocate() which takes a void* hint.  This ‘hint’ has an implementation-specific meaning.  It may be used by the allocator to help improve performance.  For example, std::allocator uses this hint to allow a container to provide an address.  The allocator uses this to provide locality of reference: the allocator (if the implementation supports it) will attempt to allocate the new memory block as close as possible to hint.

Similarly, deallocation simply returns the memory of the object.  The destructors of any objects are not called; the elements have to have been destroyed already.

Additionally, the storage being deallocated must have been allocated by allocate() (obviously!).  Finally, the pointer must not be nullptr/0.

Finally, you must provide the equality / not-equals operator overloads

template <typename T1, typename T2>
bool operator==(
    const Pool_allocator<T1>& lhs [[maybe_unused]], 
    const Pool_allocator<T2>& rhs [[maybe_unused]]
)
{
  return true;
}


template <typename T1, typename T2>
bool operator!=(
    const Pool_allocator<T1>& lhs, 
    const Pool_allocator<T2>& rhs
)
{
  return !(lhs == rhs);
}

The equality operator can only return true if an object allocated in one allocator instance can be deallocated in another.  That is, the allocators are interchangeable.  If this cannot be guaranteed – for example, if an allocator maintains its own memory pool – then the equality operator must return false.

Using the new Allocator becomes simple.  We can supply the Allocator type as a second template parameter to the container; or use a using-alias to hard-code the container.

#include <vector>
#include “Pool_allocator.h”

using namespace std;

// Something to put in a container.
//
class Part {
public:
    Part() = default;
    Part(unsigned int);
    void show() const;

private:
    unsigned int part_num;
};


// Using-alias to simplify code
//
template<typename T>
using Pool_vector = vector<T, Pool_allocator<T>>


int main()
{
    // Explicitly specifying the allocator
    //
    vector<Part, Pool_allocator<Part>> part_list1 { };

    // Using the alias
    //
    Pool_vector<Part> part_list2 { };                 

    for (int i { 0 }; i < 20; ++i) {
        part_list1.emplace_back(i);
    }

    for (auto& part : part_list1) {
        part.show();
    }
}

A problem with Allocators and containers

When we start using replacement allocators we can end up with a semantic problem in our code.

#include <vector>
#include "Pool_allocator.h"
#include "Other_allocator.h"

using namespace std;


int main()
{
  vector<int, Pool_allocator<int>>  pool_vec  { 1, 2, 3, 4 };
  vector<int, Other_allocator<int>> other_vec { };

  other_vec = pool_vec;    // ERROR!
}

The STL separates containers from their memory management using the allocator model.  Semantically, then, a vector of int should be the same as any other vector of int; and therefore assignable.  However, since the allocator-type is part of the vector’s template signature the two vectors above are deemed to be different types.

The Polymorphic Allocator model

A polymorphic allocator provides an abstract interface to separate containers from memory-allocation semantics.  All polymorphic allocator components exist in the namespace pmr (presumably short for Polymorphic Memory Resource?)

A pmr::polymorphic_allocator must provide the methods and attributes of an allocator (see previously).

A pmr::memory_resource provides a polymorphic interface for allocating / deallocating memory.

This means different instances of a polymorphic_allocator may have completely different memory-allocation facilities (as defined by their associated memory_resource).  But to a container, they appear as identical types.

Memory resources

We’ll start at the bottom.  The pmr::memory_resource acts as an abstract interface for memory allocation and deallocation.  Derived classes must implement the pure virtual allocation / deallocation functions.

Note, a memory resource allocates ‘raw’ bytes of memory.

// <experimental/memory_resource>
//
namespace pmr {

    class memory_resource {
    public:
        memory_resource()          = default;
        virtual ~memory_resource() = default;

        void* allocate(
            std::size_t bytes,
            std::size_t alignment = alignof(std::max_align_t)
        );

        void deallocate(
            void* p,
            std::size_t bytes,
            std::size_t alignment = alignof(std::max_align_t)
        );

        bool is_equal(
            const memory_resource& other
        ) const noexcept;

    private:
        virtual void* do_allocate(
            std::size_t bytes,
            std::size_t alignment
        ) = 0;

        virtual void  do_deallocate(
            void* p, 
            std::size_t bytes, 
            std::size_t alignment
        ) = 0;

        virtual bool do_is_equal(
            const std::pmr::memory_resource& other
        ) const noexcept = 0;
    };
}

Notice that memory resources allow the programmer to control the memory alignment of allocated blocks.  The default is std::max_align_t.  std::max_align_t is usually synonymous with the largest scalar type, which is long double on most platforms; and its alignment requirement is either 8 or 16 (bytes).  For more on object alignment, look here

To create a new memory resource you must inherit from pmr::memory_resource and implement its pure virtual functions.  We’ll do that presently, but first the standard library comes with a set of pre-defined classes derived from pmr::memory_resource; accessed through the below functions.

Note:
At the time of writing these features are experimental, and may not yet be implemented.  In GCC 8.1 only new_delete_resource and null_resource are implemented.

Using polymorphic allocators

The pmr::polymorphic_allocator class fulfils the requirements of Allocator, so can be used by any STL container.

A polymorphic_allocator object takes a pointer to a memory_resource object on construction.

#include <experimental/memory_resource>
#include <vector>

using namespace std;
using namespace std::experimental::pmr;


int main()
{
  polymorphic_allocator<int> alloc { new_delete_resource() };
  polymorphic_allocator<int> other { unsynchronized_pool_resource() };

  vector<int, polymorphic_allocator<int>> v1 { alloc };
  vector<int, polymorphic_allocator<int>> v2 { other };

  // Insert some data into v1...

  v2 = v1;   // OK
}

The STL containers have been updated to be initialized with a polymorphic allocator.

Note, now our vectors have the same type – polymorphic_allocator<int> – so both vectors are seen as the same type; and hence the subsequent assignment succeeds.

The default memory resource can be overridden for all polymorphic allocators, if required.

#include <experimental/memory_resource>
#include <vector>

using namespace std;
using namespace std::experimental::pmr;


int main()
{
  // Set the default memory resource
  //
  set_default_resource(unsynchronized_pool_resource());


  // If no memory resource is provided, use the default.
  //
  polymorphic_allocator<int> alloc     { new_delete_resource() }; 
  polymorphic_allocator<int> def_alloc { };

  vector<int, polymorphic_allocator<int>> v1 { alloc };
  vector<int, polymorphic_allocator<int>> v2 { def_alloc };

  // ...
}

Synchronized / unsynchronized pool resources

A synchronized_pool_resource consists of a collection of pools that serve requests for different block sizes. Each pool manages a collection of chunks that are then divided into blocks of uniform size.

Calls to do_allocate() are dispatched to the pool serving the smallest blocks accommodating the requested size.

Exhausting memory in the pool causes the next allocation request for that pool to allocate an additional chunk of memory from the upstream allocator to replenish the pool. The chunk size obtained increases geometrically.

Allocations requests that exceed the largest block size are served from an upstream allocator directly.

The largest block size and maximum chunk size may be tuned by passing a pmr::pool_options struct to its constructor.

namespace pmr {

  struct pool_options {
    // The maximum number of blocks that will be
    // allocated at once from the upstream memory
    // resource to replenish the pool.
    //
    size_t max_blocks_per_chunk;

    // The largest allocation size that could be
    // allocated from a pool. Attempts to allocate
    // a single block larger than this will be
    // allocated directly from the upstream memory
    // resource.
    //
    size_t largest_required_pool_block;
  };
}

A synchronized_pool_resource may be accessed from multiple threads without external synchronization; and may have thread-specific pools to reduce synchronization costs. If the memory resource is only accessed from one thread, unsynchronized_pool_resource is more efficient.

Synchronized / Unsynchronized pool resources will request extra chunks (if required) from an ‘upstream’ memory resource.  If required, the upstream resource can be passed in the constructor.

If the default upstream allocator is not set, the default memory resource is used (as specified with set_default_resource())

#include <experimental/memory_resource>
#include <vector>

using namespace std;
using namespace std::experimental::pmr;


int main()
{
    // Define an ‘upstream’ memory resource
    // for our pool allocator to use.
    //
    auto upstream = monotonic_buffer_resource();
    unsynchronised_pool_resource unsync_pool { upstream };

    // Use the default memory resource -
    // new_delete_resource, in this case.
    //
    polymorphic_allocator<int> def_alloc { };

    // Use the custom memory resource.
    //
    polymorphic_allocator<int> pool_alloc { unsync_pool };


    vector<int, polymorphic_allocator<int>> v1 { def_alloc };
    vector<int, polymorphic_allocator<int>> v2 { pool_alloc };

    // ...
}

Creating your own memory resource

To create your own memory resource you must inherit from pmr::memory_resource and implement its pure virtual functions.

#include <experimental/memory_resource>

using namespace std::experimental::pmr;

class Tracking_resource : public memory_resource {
public:
    void* do_allocate(
        std::size_t bytes, 
        std::size_t alignment
    )                             override;
    void do_deallocate(
        void*  p, 
        size_t bytes, 
        size_t alignment
    )                             override;
    bool do_is_equal(
        const memory_resource& other
    ) const noexcept              override;

private:
  // Implementation details, as required...
};

My implementation is trivial; as befits a toy example for explanatory purposes.

void* Tracking_resource::do_allocate(
    std::size_t bytes,
    std::size_t alignment [[maybe_unused]]
)
{
    void* ptr = malloc(bytes);
    clog << "Allocating " << bytes << " bytes ";
    clog << "at address " << ptr << endl;
    return ptr;
}


void Tracking_resource::do_deallocate(
    void* p,
    std::size_t bytes     [[maybe_unused]],
    std::size_t alignment [[maybe_unused]]
)
{
    clog << "Freeing " << bytes << " bytes ";
    clog << "at address " << p << endl;
    free(p);
}


bool Tracking_resource::do_is_equal(
    const memory_resource& other [[maybe_unused]]
) const noexcept
{
    return true;
}

The new, custom, memory resource can be used in the same way as the standard library memory resources; including being used as the default system memory resource.

#include "Tracking_resource.h"
#include "Non_tracking_resource.h"


int main()
{
    Tracking_resource     tracker     { };
    Non_tracking_resource not_tracker { };

    polymorphic_allocator<int> tracking_alloc     { &tracker };
    polymorphic_allocator<int> non_tracking_alloc { &not_tracker };

    vector<int, polymorphic_allocator<int>> v1 { tracking_alloc };
    vector<int, polymorphic_allocator<int>> v2 { non_tracking_alloc };

    // Insert elements...

    v2 = v1;

  // etc...
}

Summary

Sometimes the default allocation model is insufficient or unacceptable for your project’s requirements.  Many embedded development organisations have gone down the route of designing their own container libraries, when modifying the memory allocation model would have been sufficient.

Being able to create your own memory-allocation strategy is immensely powerful; although in earlier versions of C++ is was (unnecessarily?) over-wrought.  The new Allocator model makes this much less onerous.

In cases where one allocation strategy isn’t enough polymorphic allocators provide type-erased allocation, with multiple, different memory management strategies, whilst still retaining ‘obvious’ semantics for containers.

At the time of writing this, the new Allocator model is still experimental, and not fully complete.  As this feature has now been included into C++20 I expect fill implementations to appear very soon.

• About
• Latest Posts

Glennan Carnie

Technical Consultant at Feabhas Ltd

Glennan is an embedded systems and software engineer with over 20 years experience, mostly in high-integrity systems for the defence and aerospace industry.

He specialises in C++, UML, software modelling, Systems Engineering and process development.

Latest posts by Glennan Carnie (see all)

• Practice makes perfect, part 3 – Idiomatic kata - February 27, 2020
• Practice makes perfect, part 2– foundation kata - February 13, 2020
• Practice makes perfect, part 1 – Code kata - January 30, 2020

Glennan Carnie

Website | + posts

Glennan is an embedded systems and software engineer with over 20 years experience, mostly in high-integrity systems for the defence and aerospace industry.

He specialises in C++, UML, software modelling, Systems Engineering and process development.

• Practice makes perfect, part 3 - Idiomatic kata
• Practice makes perfect, part 2 - foundation kata
• Practice makes perfect, part 1 - Code kata
• Function function return return values values*