C ++ 17 polymorphic allocators

Very soon, a new course stream will start at OTUS “C ++ Developer. Professional “… On the eve of the start of the course, our expert Alexander Klyuchev prepared an interesting material about polymorphic allocators. We give the floor to Alexander:

In this article, I would like to show simple examples of working with components from a namespace pmr and the basic ideas behind polymorphic allocators.

The main idea of polymorphic allocators introduced in c ++ 17 is to improve the standard allocators implemented on the basis of static polymorphism or in other words templates. They are much easier to use than standard allocators, in addition, they allow you to preserve the container type when using different allocators and , therefore, change allocators at runtime.

If you want to std::vector with a specific memory allocator, you can use the Allocator template parameter:

auto my_vector = std::vector<int, my_allocator>();

But there is a problem – this vector is not of the same type as a vector with a different allocator, including one defined by default.
Such a container cannot be passed to a function that requires a vector with a default container, nor can two vectors with different allocator types be assigned to the same variable, for example:

auto my_vector = std::vector<int, my_allocator>();
auto my_vector2 = std::vector<int, other_allocator>();
auto vec = my_vector; // ok
vec = my_vector2; // error

The polymorphic allocator contains a pointer to the interface memory_resourceso it can use dynamic dispatch.

To change the strategy of working with memory, it is enough to replace the instance memory_resourcekeeping the type of allocator. This can be done at runtime as well. Otherwise, polymorphic allocators work according to the same rules as standard ones.

The specific data types used by the new allocator are in the namespace std::pmr… There are also template specializations of standard containers that can work with a polymorphic allocator.
One of the main problems at the moment is the incompatibility of new versions of containers from std::pmr with analogues from std…

Main components `std::pmr:`

std::pmr::memory_resource – an abstract class, the implementation of which is ultimately responsible for working with memory.
Contains the following interface:
- 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 – implementation of the standard allocator, uses a pointer to memory_resource to work with memory.
new_delete_resource() and null_memory_resource() used to work with “global” memory
A set of ready-made memory pools:
- synchronized_pool_resource
- unsynchronized_pool_resource
- monotonic_buffer_resource
Specializations of standard containers with a polymorphic allocator, std::pmr::vector, std::pmr::string, std::pmr::map etc. Each specialization is defined in the same header file as the corresponding container.
Set of ready memory_resource:
- memory_resource* new_delete_resource() Free function, returns a pointer to memory_resource, which uses global operators new and delete to allocate memory.
- memory_resource* null_memory_resource()
  The free function returns a pointer to memory_resourcewhich throws an exception std::bad_alloc for each allocation attempt.

This can be useful to ensure that objects do not allocate memory on the heap or for testing purposes.

class synchronized_pool_resource : public std::pmr::memory_resource
A thread-safe, general-purpose memory_resource implementation consists of a set of pools with different sizes of memory blocks.
Each pool is a collection of chunks of memory of the same size.
class unsynchronized_pool_resource : public std::pmr::memory_resource
Single threaded version synchronized_pool_resource…
class monotonic_buffer_resource : public std::pmr::memory_resource
Single-threaded, fast, memory_resource special purpose takes memory from a pre-allocated buffer, but does not free it, that is, it can only grow.

Usage example monotonic_buffer_resource and pmr::vector:

#include <iostream>
#include <memory_resource>   // pmr core types
#include <vector>        	// pmr::vector
#include <string>        	// pmr::string
 
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';
}

Program output:


_______________________________________________________________
aababcdabcdefghabcdefghijklmnopabcdefghijklmnopqrstuvwxyz______

In the above example, we used monotonic_buffer_resourceinitialized with a buffer allocated on the stack. Using a pointer to this buffer, we can easily display the contents of memory.

The vector takes memory from the pool, which is very fast since it is on the stack, if the memory runs out, it requests it using the global operator new… An example demonstrates reallocating a vector when trying
insert more than the reserved number of elements. Wherein monotonic_buffer do not free old memory, but only grows.
You can, of course, call reserve() for a vector to minimize reallocations, but the purpose of the example is precisely to demonstrate how monotonic_buffer_resource when expanding the container.

Storage `pmr::string`

What if we want to store lines in pmr::vector?
An important feature is that if objects in a container also use a polymorphic allocator, then they request the parent container’s allocator for memory management.

If you want to take advantage of this opportunity, you need to use std::pmr::string instead std::string…

Consider an example with a buffer pre-allocated on the stack, which we will pass as memory_resource for std::pmr::vector std::pmr::string:

#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 : "https://habr.com/ru/company/otus/blog/520502/#");
    	}
    	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");   
}

Program output:

sizeof(std::string): 32
sizeof(std::pmr::string): 40
zeroed buffer:
_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
after two short strings:
#m######n#############Hello World######m#####@n#############One Two Three###_______________________________________________________________________________________________________________________________________________________________________________#
after longer string strings:
#m######n#############Hello World######m#####@n#############One Two Three####m######n#####################________________________________________________________________________________________This is a longer string#_______________________________#
after the last string:
#m######n#############Hello World######m#####@n#############One Two Three####m######n#####################________#m######n#############Four Five Six###________________________________________This is a longer string#_______________________________#

The main points to pay attention to in this example:

The size pmr::string more than std::string… This is due to the fact that a pointer to memory_resource;
We reserve the vector for 5 elements, so no reallocations occur when adding 4.
The first 2 lines are short enough for the vector memory block, so no additional memory allocation occurs.
The third line is longer and required a separate chunk of memory inside our buffer, and only the pointer to this block is stored in the vector.
As you can see from the output, “This is a longer string” is located almost at the very end of the buffer.
When we insert another short string, it falls back into the memory block of the vector

For comparison, let’s do the same experiment with std::string instead std::pmr::string

sizeof(std::string): 32
sizeof(std::pmr::string): 40
zeroed buffer:
_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
after two short strings:
###w###########Hello World########w###########One Two Three###_______________________________________________________________________________________________________________________________________________________________________________________________#
new 24
after longer string strings:
###w###########Hello World########w###########One Two Three###0#######################_______________________________________________________________________________________________________________________________________________________________________#
after the last string:
###w###########Hello World########w###########One Two Three###0#######################________@##w###########Four Five Six###_______________________________________________________________________________________________________________________________#

This time, the items in the container take up less space because there is no need to store a pointer to the memory_resource.
The short strings are still stored inside the vector memory block, but now the long string does not make it into our buffer. The long string is allocated this time using the default allocator a into the vector memory block
a pointer to it is placed. Therefore, we do not see this line in the output.

Once again about vector expansion:

It was mentioned that when the memory in the pool runs out, the allocator requests it using the operator new()…

In fact, this is not entirely true – memory is requested from memory_resourcereturned by a free function
std::pmr::memory_resource* get_default_resource()

By default, this function returns
std::pmr::new_delete_resource(), which in turn allocates memory using the operator new(), but can be replaced with the function
std::pmr::memory_resource* set_default_resource(std::pmr::memory_resource* r)

So let’s look at an example where get_default_resource returns the default.

It must be borne in mind that the methods do_allocate() and do_deallocate() use the “align” argument, so we need the C ++ 17 version new() with 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;
}

Now let’s get back to the main 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 < lastSize; ++i)
	std::cout << bufTemp[i] << " ";

The program tries to put 20 numbers into a vector, but given that the vector is only growing, we need more space than in the reserved buffer with 32 entries.

Therefore, at some point, the allocator will request memory through get_default_resource, which in turn will lead to a call to the global new()…

Program output:

new: 128, align: 16, ptr: 0xc73b20
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 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 132 0 0 0 0 0 0 0 144 0 0 0 65 0 0 0 16080 199 0 0 16176 199 0 0 16176 199 0 0 15344 199 0 0 15472 199 0 0 15472 199 0 0 0 0 0 0 145 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Judging by the output to the console, the allocated buffer is enough for only 16 elements, and when we insert the number 17, a new allocation of 128 bytes occurs using the operator new()…
On the 3rd line, we see a block of memory allocated using the operator new()…

The above example with operator override new() hardly suitable for a product solution.
Fortunately, no one bothers us to make our own implementation of the interface. memory_resource…

All we need is

inherit from std::pmr::memory_resource
Implement methods:
- do_allocate()
- do_deallocate()
- do_is_equal()
Pass our implementation memory_resource containers.

That’s all. By the link below you can watch the record of the open house day, where we tell in detail about the course program, the learning process and answer questions from potential students: