C++17 In Detail

29 June 2020

Polymorphic Allocators, 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.

Last update: 6th July 2020 (title image, storing strings section)

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:

Resources about C++17 STL:

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.

Storing pmr::string

How about inserting a string into a pmr::vector?

The nice thing about polymorphic allocators is that if objects in a container are also using polymorphic allocators, then they will ask for the parent container’s allocator to manage the memory.

If you want to use this property, you have to use std::pmr::string rather than std::string.

Have a look at the example below where we preallocate a buffer on the stack and then pass it to vector of strings:

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

int main() {
    std::cout << "sizeof(std::string): " << sizeof(std::string) << '\n';
    std::cout << "sizeof(std::pmr::string): " << sizeof(std::pmr::string) << '\n';

    char buffer[256] = {}; // a small buffer on the stack
    std::fill_n(std::begin(buffer), std::size(buffer) - 1, '_');

    const auto BufferPrinter = [](std::string_view buf, std::string_view title) { 
        std::cout << title << ":\n";
        for (auto& ch : buf) {
            std::cout << (ch >= ' ' ? ch : '#');
        }
        std::cout << '\n';
    };

    BufferPrinter(buffer, "zeroed buffer");

    std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)};
    std::pmr::vector<std::pmr::string> vec{ &pool };
    vec.reserve(5);

    vec.push_back("Hello World");
    vec.push_back("One Two Three");
    BufferPrinter(std::string_view(buffer, std::size(buffer)), "after two short strings");

    vec.emplace_back("This is a longer string");
    BufferPrinter(std::string_view(buffer, std::size(buffer)), "after longer string strings");

    vec.push_back("Four Five Six");
    BufferPrinter(std::string_view(buffer, std::size(buffer)), "after the last string");    
}

Here’s the output that I got on GCC 9.2/Coliru

pmr string in a vector

Here are the major things we can observe with this example:

  • The size of pmr::string is larger than a regular std::string. This is because the allocator is not stateless, and it has to store a pointer to a memory resource.
  • The example reserves five spots for the elements so the vector won’t grow when we insert four elements
  • The first two strings are short so they can fit into a memory block of the vector, there’s no dynamic memory allocation here
  • But for the third string we require its a separate memory chunk, and the vector only stores a pointer to it. As you can see on the output "This is a longer string" is located almost at the end of the buffer.
  • When we insert another short string then it goes into the vector memory block again.

And for comparison here’s the output when you use regular std::string:

pmr string in a vector

This time the elements in the container use less memory, as there’s no need to store the pointer to a memory resource. Short strings are stored inside the vector’s memory block, but please notice the longer string… it’s not in the buffer! To be correct, the vector stores a pointer to a memory block where the long string is allocated, but a default allocator allocated it so it won’t appear in our output.

You can play with the example @Coliru

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

Sorry for a little interruption in the flow :)
I've prepared a little bonus if you're interested in Modern C++, check it out here:

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.

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.

C++17 In Detail
© 2017, Bartlomiej Filipek, Blogger platform
Disclaimer: Any opinions expressed herein are in no way representative of those of my employers. All data and information provided on this site is for informational purposes only. I try to write complete and accurate articles, but the web-site will not be liable for any errors, omissions, or delays in this information or any losses, injuries, or damages arising from its display or use.
This site contains ads or referral links, which provide me with a commission. Thank you for your understanding.