C++17: Polymorphic Allocators, Debug Resources and Custom Types

In my previous article on polymorphic allocators, we discussed some basic ideas. For example, you've seen a pmr::vector that holds pmr::string using a monotonic resource. How about using a custom type in such a container? How to enable it? Let's see.

The Goal

In the previous article there was similar code:

char buffer[256] = {}; // a small buffer on the stack

std::fill_n(std::begin(buffer), std::size(buffer) - 1, '_');

std::pmr::monotonic_buffer_resource pool{std::data(buffer),

                                         std::size(buffer)};

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

// ...

See the full example @Coliru

In this case, when you insert a new string into the vector, the new object will also use the memory resource that is specified on the vector.

And by "use" I mean the situation where the string object has to allocate some memory, which means long strings that don't fit into the Short String Optimisation buffer. If the object doesn't require any extra memory block to fetch, then it's just part of the contiguous memory blog of the parent vector.

Since the pmr::string can use the vector's memory resource, it means that it is somehow "aware" of the allocator.

How about writing a custom type:

xxxxxxxxxx

struct Product {

    std::string name;

    char cost { 0 }; // for simplicity

};

If I plug in this into the vector:

xxxxxxxxxx

std::pmr::vector<Product> prods { &pool };

Then, the vector will use the provided memory resource but won't propagate it into Product. That way if Product has to allocate memory for name it will use a default allocator.

We have to "enable" our type and make it aware of the allocators so that it can leverage the allocators from the parent container.

References

Before we start, I'd like to mention some good references if you'd like to try allocators on your own. This topic is not super popular, so finding tutorials or good descriptions is not that easy as I found.

• CppCon 2017: Pablo Halpern “Allocators: The Good Parts” - YouTube - in-depth explanations of allocators and the new PMR stuff. Even with a test implementation of some node-based container.
• CppCon 2015: Andrei Alexandrescu “std::allocator…” - YouTube - from the introduction you can learn than std::allocator was meant to fix far/near issues and make it consistent, but right now we want much more from this system.
• c++ - What is the purpose of allocator_traits in C++0x? - Stack Overflow
• Jean Guegant’s Blog – Making a STL-compatible hash map from scratch - Part 3 - The wonderful world of iterators and allocators - this is a super detailed blog post on how to make more use of allocators, not to mention good anecdotes and jokes :)
• Thanks for the memory (allocator) - Sticky Bits - a valuable introduction to allocators, their story and how the new model of PMR fit in. You can also see how to write your tracking pmr allocator and how *_pool_resource works.
• CppCon 2018: Arthur O’Dwyer “An Allocator is a Handle to a Heap” - a great talk from Arthur where he shares all the knowledge needed to understand allocators.
• C++17 - The Complete Guide by Nicolai Josuttis - inside the book, there’s a long chapter about PMR allocators.

Debug Memory Resource

To work efficiently with allocators, it would be handy to have a tool that allows us to track memory allocations from our containers.

See the resources that I listed on how to do it, but in a basic form, we have to do the following:

• Derive from std::pmr::memory_resource
• Implement:
  • do_allocate() - the function that is used to allocate N bytes with a given alignment.
  • do_deallocate() - the function called when an object wants to deallocate memory.
  • do_is_equal() - it's used to compare if two objects have the same allocator, in most cases, you can compare addresses, but if you use some allocator adapters then you might want to check some advanced tutorials on that.
• Set your custom memory resource as active for your objects and containers.

Here's a code based on Sticky Bits and Pablo Halpern's talk.

xxxxxxxxxx

class debug_resource : public std::pmr::memory_resource {

public:

    explicit debug_resource(std::string name, 

       std::pmr::memory_resource* up = std::pmr::get_default_resource())

        : _name{ std::move(name) }, _upstream{ up } 

    { }

    void* do_allocate(size_t bytes, size_t alignment) override {

        std::cout << _name << " do_allocate(): " << bytes << '\n';

        void* ret = _upstream->allocate(bytes, alignment);

        return ret;

    }

    void do_deallocate(void* ptr, size_t bytes, size_t alignment) override {

        std::cout << _name << " do_deallocate(): " << bytes << '\n';

        _upstream->deallocate(ptr, bytes, alignment);

    }

    bool do_is_equal(const std::pmr::memory_resource& other) const noexcept override {

        return this == &other;

    }

private:

    std::string _name;

    std::pmr::memory_resource* _upstream;

};

The debug resource is just a wrapper for the real memory resource. As you can see in the allocation/deallocation functions, we only log the numbers and then defer the real job to the upstream resource.

Example use case:

xxxxxxxxxx

constexpr size_t BUF_SIZE = 128;

char buffer[BUF_SIZE] = {}; // a small buffer on the stack

std::fill_n(std::begin(buffer), std::size(buffer) - 1, '_');

debug_resource default_dbg { "default" };

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

debug_resource dbg { "pool", &pool };

std::pmr::vector<std::string> strings{ &dbg };

strings.emplace_back("Hello Short String");

strings.emplace_back("Hello Short String 2");

The output:

xxxxxxxxxx

pool do_allocate(): 32

pool do_allocate(): 64

pool do_deallocate(): 32

pool do_deallocate(): 64

Above we used debug resources twice, the first one "pool" is used for logging every allocation that is requested to the monotonic_buffer_resource. In the output, you can see that we had two allocations and two deallocations.

There's also another debug resource "default". This is configured as a parent of the monotonic buffer. This means that if pool needs to allocate., then it has to ask for the memory through our "default" object.:

If you add three strings like here:

xxxxxxxxxx

strings.emplace_back("Hello Short String");

strings.emplace_back("Hello Short String 2");

strings.emplace_back("Hello A bit longer String");

Then the output is different:

xxxxxxxxxx

pool do_allocate(): 32

pool do_allocate(): 64

pool do_deallocate(): 32

pool do_allocate(): 128

default do_allocate(): 256

pool do_deallocate(): 64

pool do_deallocate(): 128

default do_deallocate(): 256

This time you can notice that for the third string there was no room inside our predefined small buffer and that's why the monotonic resource had to ask for "default" for another 256 bytes.

See the full code here @Coliru.

A Custom Type

Equipped with a debug resource and also some "buffer printing techniques" we can now check if our custom type work with allocators. Let's see:

xxxxxxxxxx

struct SimpleProduct {

    std::string _name;

    char _price { 0 };

};

int main() {

    constexpr size_t BUF_SIZE = 256;

    char buffer[BUF_SIZE] = {}; // 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 (size_t i = 0; i < buf.size(); ++i) {

            std::cout << (buf[i] >= ' ' ? buf[i] : '#');

            if ((i+1)%64 == 0) std::cout << '\n';

        }

        std::cout << '\n';

    };

    BufferPrinter(buffer, "initial buffer");

    debug_resource default_dbg { "default" };

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

    debug_resource dbg { "buffer", &pool };

    std::pmr::vector<SimpleProduct> products{ &dbg };

    products.reserve(4);

    products.emplace_back(SimpleProduct { "car", '7' }); 

    products.emplace_back(SimpleProduct { "TV", '9' }); 

    products.emplace_back(SimpleProduct { "a bit longer product name", '4' }); 

    BufferPrinter(std::string_view {buffer, BUF_SIZE}, "after insertion");

}

Possible output:

xxxxxxxxxx

________________________________________________________________

________________________________________________________________

________________________________________________________________

_______________________________________________________________

buffer do_allocate(): 160

after insertion:

p"---•..-.......car.er..-~---•..7_______-"---•..-.......TV..er..

-~---•..9_______0-j-....-.......-.......________4_______________

________________________________________________________________

_______________________________________________________________.

buffer do_deallocate(): 160

Legend: in the output the dot . means that the element of the buffer is 0. The values that are not zeros, but smaller than a space 32 are displayed as -.

Let's decipher the code and the output:

The vector contains SimpleProduct objects which is just a string and a number. We reserve four elements, and you can notice that our debug resource logged allocation of 160 bytes. After inserting three elements, we can spot car and the number 7 (this is why I used char as a price type). And then TV with 9. We can also notice 4 as a price for the third element, but there's no name there. It means that it was allocated somewhere else.

Live code @Coliru

Allocator Aware Type

Making a custom type allocator aware is not super hard, but we have to remember about the following things:

• Use pmr::* types when possible so that you can pass them an allocator.
• Declare allocator_type so that allocator trait can "recognise" that your type uses allocators. You can also declare other properties for allocator traits, but in most cases, defaults will be fine.
• Declare constructor that takes an allocator and pass it further to your members.
• Declare copy and move constructors that also takes care of allocators.
• Same with assignment and move operations.

This means that our relatively simple declaration of custom type has to grow:

xxxxxxxxxx

struct Product {

    using allocator_type = std::pmr::polymorphic_allocator<char>;

    explicit Product(allocator_type alloc = {}) 

    : _name { alloc } { }

    Product(std::pmr::string name, char price, 

            const allocator_type& alloc = {}) 

    : _name { std::move(name), alloc }, _price { price } { }

    Product(const Product& other, const allocator_type& alloc) 

    : _name { other._name, alloc }, _price { other._price } { }

    Product(Product&& other, const allocator_type& alloc) 

    : _name{ std::move(other._name), alloc }, _price { other._price } { }

    Product& operator=(const Product& other) = default;

    Product& operator=(Product&& other) = default;

    std::pmr::string _name;

    char _price { '0' };

};

And here's a sample test code:

xxxxxxxxxx

debug_resource default_dbg { "default" };

std::pmr::monotonic_buffer_resource pool{std::data(buffer), 

                       std::size(buffer), &default_dbg};

debug_resource dbg { "buffer", &pool };

std::pmr::vector<Product> products{ &dbg };

products.reserve(3);

products.emplace_back(Product { "car", '7', &dbg }); 

products.emplace_back(Product { "TV", '9', &dbg }); 

products.emplace_back(Product { "a bit longer product name", '4', &dbg }); 

The output:

xxxxxxxxxx

buffer do_allocate(): 144

buffer do_allocate(): 26

after insertion:

-----•..-----•..-.......car.#•..-.......7_______-----•..-----•..

-.......TV..#•..-.......9_______-----•..@----•..-.......-.......

________4_______a bit longer product name.______________________

_______________________________________________________________.

buffer do_deallocate(): 26

buffer do_deallocate(): 144

Sample code @Coliru

In the output, the first memory allocation - 144 - is for the vector.reserve(3) and then we have another one for a longer string (3rd element). The full buffer is also printed (code available in the Coliru link) that shows the place where the string is located.

"Full" Custom Containers

Our custom object was composed of other pmr:: containers, so it was much more straightforward! And I guess in most cases you can leverage existing types. However, if you need to access allocator and perform custom memory allocations, then you should see Pablo's talk where he guides through an example of a custom list container.

Summary

In this blog post, we've made another journey inside deep levels of the Standard Library. While allocators are something terrifying, it seems that with polymorphic allocator things get much more comfortable. This happens especially if you stick with lots of standard containers that are exposed in the pmr:: namespace.

Let me know what's your experience with allocators and pmr:: stuff. Maybe you implement your types differently? (I tried to write correct code, but still, some nuances are tricky. Let's learn something together :)