Polymorphic Allocators from C++17, std:vector Growth and Hacking

The concept of a polymorphic allocator from C++17 is an enhancement to standard allocators from the Standard Library.

It’s much easier to use than a regular allocator and allows containers to have the same type while having a different allocator, or even a possibility to change allocators at runtime.

Let’s see how we can use it and hack to see the growth of std::vector containers.

• Core elements of pmr:
  • new_delete_resource()
  • null_memory_resource()
  • synchronized_pool_resource
  • unsynchronized_pool_resource
  • monotonic_buffer_resource
• • A Much Better Solution

In short, a polymorphic allocator conforms to the rules of an allocator from the Standard Library. Still, at its core, it uses a memory resource object to perform memory management.

Polymorphic Allocator contains a pointer to a memory resource class, and that’s why it can use a virtual method dispatch. You can change the memory resource at runtime while keeping the type of the allocator. This is the opposite to regular allocators which make two containers using a different allocator also a different type.

All the types for polymorphic allocators live in a separate namespace std::pmr (PMR stands for Polymorphic Memory Resource), in the <memory_resource> header.

The Series

This article is part of my series about C++17 Library Utilities. Here’s the list of the articles:

• Refactoring with std::optional
• Using std::optional
• Error handling and std::optional
• Everything You Need to Know About std::variant from C++17
• Everything You Need to Know About std::any from C++17
• std::string_view Performance andfollowup
• C++17 string searchers andfollowup
• Conversion utilities -about from_chars.
• How to get File Size in C++? and std:filesystem::file_size Advantages and Differences
• How To Iterate Through Directories

Resources about C++17 STL:

• C++17 In Detail by Bartek!
• C++17 - The Complete Guide by Nicolai Josuttis
• C++ Fundamentals Including C++ 17 by Kate Gregory
• Practical C++14 and C++17 Features - by Giovanni Dicanio
• C++17 STL Cookbook by Jacek Galowicz

OK, let’s go back to our main topic: PMR.

Core elements of pmr :

Here’s a little summary of the main parts of pmr :

• std::pmr::memory_resource - is an abstract base class for all other implementations. It defines the following pure virtual methods:
  

  virtual void* do_allocate(std::size_t bytes, std::size_t alignment)
  virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment)
  virtual bool do_is_equal(const std::pmr::memory_resource& other) const noexcept
  

• std::pmr::polymorphic_allocator - is an implementation of a standard allocator that uses memory_resource object to perform memory allocations and deallocations.
• global memory resources accessed by new_delete_resource() and null_memory_resource()
• a set of predefined memory pool resource classes:
  

  synchronized_pool_resource
  unsynchronized_pool_resource
  monotonic_buffer_resource
  

• template specialisations of the standard containers with polymorphic allocator, for example std::pmr::vector , std::pmr::string , std::pmr::map and others. Each specialisation is defined in the same header file as the corresponding container.
• It’s also worth mentioning that pool resources (including monotonic_buffer_resource ) can be chained. If there’s no available memory in a pool, the allocator will allocate from the “upstream” resource.

And we have the following predefined memory resources:

new_delete_resource()

It’s a free function that returns a pointer to a global “default” memory resource. It manages memory with the global new and delete .

null_memory_resource()

It’s a free function that returns a pointer to a global “null” memory resource which throws std::bad_alloc on every allocation. While it sounds not useful, it might be handy when you want to guarantee that your objects don’t allocate any memory on the heap. Or for testing.

synchronized_pool_resource

This is a thread-safe allocator that manages pools of different sizes. Each pool is a set of chunks that are divided into blocks of uniform size.

unsynchronized_pool_resource

A non-thread-safe pool_resource .

monotonic_buffer_resource

This is a non-thread-safe, fast, special-purpose resource that gets memory from a preallocated buffer, but doesn’t release it with deallocation. It can only grow.

An Example

Below you can find a simple example of monotonic_buffer_resource and pmr::vector :

#include <iostream>
#include <memory_resource>   // pmr core types
#include <vector>            // pmr::vector

int main() {
    char buffer[64] = {}; // a small buffer on the stack
    std::fill_n(std::begin(buffer), std::size(buffer) - 1, '_');
    std::cout << buffer << '\n';

    std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)};

    std::pmr::vector<char> vec{ &pool };
    for (char ch = 'a'; ch <= 'z'; ++ch)
        vec.push_back(ch);

    std::cout << buffer << '\n';
}

Possible output:

_______________________________________________________________
aababcdabcdefghabcdefghijklmnopabcdefghijklmnopqrstuvwxyz______

In the above example, we use a monotonic buffer resource initialised with a memory chunk from the stack. By using a simple char buffer[] array, we can easily print the contents of the “memory”. The vector gets memory from the pool (and it’s super fast since it’s on the stack), and if there’s no more space available, it will ask for memory from the “upstream” resource. The example shows vector reallocations when there’s a need to insert more elements. Each time the vector gets more space, so it eventually fits all of the letters. The monotonic buffer resource doesn’t delete any memory as you can see, it only grows.

We could also use reserve() on the vector, and that would limit the number of memory allocations, but the point of this example was to illustrate the "expansion" of the container.

I mentioned that if the memory ends then the allocator will get memory from the upstream resource. How can we observe it?

Some Hacks

At start let’s try and do some hacking :)

In our case, the upstream memory resource is a default one as we didn’t change it. That means new() and delete() . However, we have to keep in mind that do_allocate() and do_deallocate() member functions also take an alignment parameter.

That’s why if we want to hack and see if the memory is allocated by new() we have to use C++17’s new() with the alignment support:

void* lastAllocatedPtr = nullptr;
size_t lastSize = 0;

void* operator new(std::size_t size, std::align_val_t align) {
#if defined(_WIN32) || defined(__CYGWIN__)
    auto ptr = _aligned_malloc(size, static_cast<std::size_t>(align));
#else
    auto ptr = aligned_alloc(static_cast<std::size_t>(align), size);
#endif

    if (!ptr)
        throw std::bad_alloc{};

    std::cout << "new: " << size << ", align: " 
              << static_cast<std::size_t>(align) 
              << ", ptr: " << ptr << '\n';

    lastAllocatedPtr = ptr;
    lastSize = size;

    return ptr;
}

In the above code part I implemented aligned new() (you can read more about this whole new feature in my separate article: New new() - The C++17’s Alignment Parameter for Operator new() ).

And you can also spot two ugly global variables :) However, thanks to them we can see when our memory goes:

Let’s reconsider our example:

constexpr auto buf_size = 32;
uint16_t buffer[buf_size] = {}; // a small buffer on the stack
std::fill_n(std::begin(buffer), std::size(buffer) - 1, 0);

std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)*sizeof(uint16_t)};

std::pmr::vector<uint16_t> vec{ &pool };

for (int i = 1; i <= 20; ++i)
    vec.push_back(i);

for (int i = 0; i < buf_size; ++i)
    std::cout <<  buffer[i] << " ";

std::cout << std::endl;

auto* bufTemp = (uint16_t *)lastAllocatedPtr;

for (unsigned i = 0; i < lastAllocatedSize; ++i)
    std::cout << bufTemp[i] << " ";

This time we store uint16_t rather than char .

The program tries to store 20 numbers in a vector, but since the vector grows, then we need more than the predefined buffer (only 32 entries). That’s why at some point the allocator turns to global new and delete.

Here’s a possible output that you might get:

new: 128, align: 16, ptr: 0x21b3c20
1 1 2 1 2 3 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 0 0 0 0 .....
delete: 128, align: 16, ptr : 0x21b3c20

It looks like the predefined buffer could store only up to 16th elements, but when we inserted number 17, then the vector had to grow, and that’s why we see the new allocation - 128 bytes.

The second line shows the contents of the custom buffer, while the third line shows the memory allocated through new() .

Here’s a live version @Coliru

A Much Better Solution

The previous example worked and shows us something, but hacking with new() and delete() is not what you should do in production code. In fact, memory resources are extensible, and if you want the best solution, you can roll your resource!

All you have to do is to implement the following:

• Derive from std::pmr::memory_resource
• Implement:
  

  do_allocate()
  do_deallocate()
  do_is_equal()
  

• Set your custom memory resource as active for your objects and containers.

And here are the resources that you can see to learn how to implement it.

• CppCon 2017: Pablo Halpern “Allocators: The Good Parts” - YouTube
• Taming dynamic memory - An introduction to custom allocators in C++ - Andreas Weis - code::dive 2018 - YouTube
• A whole extensive chapter in Nicolai's book on C++17:
• C++ Weekly - Ep 222 - 3.5x Faster Standard Containers With PMR! - YouTube .

Summary

Through this article, I wanted to shows you some basic examples with pmr and the concept of a polymorphic allocator. As you can see, setting up an allocator for a vector is much simpler than it was with regular allocators. There is a set of predefined allocators at your disposal, and it’s relatively easy to implement your custom version. The code in the article showed just a simple hacking to illustrate where the memory is pulled from.

Back to you:

Do you use custom memory allocators?

Have you played with pmr and polymorphic allocators from C++?

Let us know in comments.