C++ custom allocators are a topic I don’t get around too much. They scream performance and memory usage and that’s a place I want to be. I felt a few times I might need a custom allocator to solve particular problems around dynamic memory, but it’s not something I would just jump on.
In embedded systems, dynamic memory is often replaced by static memory to get better performance and deterministic behavior. But writing custom allocators for this is not the first approach I would have. A vector can be replaced by an array and a map by a static map, and in general, memory can be allocated on the stack.
Everything has a price
This comes with costs. Not once I would’ve used dynamic polymorphism to design a feature. Even if in C++ dynamic polymorphism is not the greatest and templates can be used to achieve compile-time polymorphism, there are moments when I would choose the dynamic version for its design simplicity.
I ask myself from time to time how I could use virtual inheritance… without allocating on the heap. Some data structures from the standard library accept a custom allocator to allow me to better control how memory is managed. And this idea of controlling how an object is being allocated is bugging me more often. So I’m making a first, small, shy step.
Getting back to the basics
Speaking of dynamic polymorphism, you know where this is going. It has to be a Car or a Person or a Shape. I’m picking a Shape this time. I design a few shapes, a factory to create them, then I use them:
#include <iostream>
#include <memory>
class Shape {
public:
virtual void draw() const = 0;
virtual ~Shape() = default;
};
class Circle : public Shape {
public:
void draw() const override { std::cout << "circle\n"; }
};
class Square : public Shape {
public:
void draw() const override { std::cout << "square\n"; }
};
class ShapeFactory {
public:
static std::unique_ptr<Shape> create(int type)
{
switch (type) {
case 1:
return std::make_unique<Circle>();
case 2:
return std::make_unique<Square>();
default:
throw std::invalid_argument{"unknown shape"};
}
}
};
int main()
{
const auto circle = ShapeFactory::create(1);
circle->draw();
const auto square = ShapeFactory::create(2);
square->draw();
}
From smart pointers back to raw pointers
What I’m aiming for is to have the same design, but to replace dynamic memory with static memory. I’m not going to do it like IT SHOULD BE DONE. I don’t even know what’s THE WAY or if there is one. I’m just going to start to play around the subject. I’m taking a step back from smart pointers and I’m going back to raw pointers. The shape design remains the same, but I’m going to choose to construct the objects with raw pointers.
class ShapeFactory {
public:
static Shape* create(int type)
{
switch (type) {
case 1:
return new Circle();
case 2:
return new Square();
default:
throw std::invalid_argument{"unknown shape"};
}
}
};
The objects are still being allocated on the heap. But they are not being deallocated anymore. I’m losing (my) memory and it’s OK, it’s part of the process.
Now I “just” have to take control over the memory allocation and, when new is called, I should not let the object get to the heap, but instead, construct it into a preallocated memory area. Overloading the new operator could be a way to do it, but this time I’m not choosing it because I don’t want to change the classes. I want to alter the construction of the objects without them knowing.
I want to place the new object into static memory
Another possibility is placement new. When I construct the object, I’m specifying the exact location in memory where I want to place it.
Instead of just creating a new object
new Circle()
I’m creating it by passing to new a memory buffer (address to a location in memory) where I know I have enough space for the new object
static char buffer[128]; new (buffer) Circle()
Now, the memory is not allocated each time I create a new object, it’s not dynamic memory, and I don’t have to worry about freeing it. Every byte of memory that I use is in the preallocated buffer. The classes are not changed, the usage is not changed, but the factory class must handle the object creation differently.
Custom memory allocator – Part 0
The factory needs to manage the buffer so that it places each newly created object at a specific offset. If I would use the same memory location for each new object, I would always overwrite the previously created one.
template <std::size_t Size>
class StaticMemoryAllocator {
static char buffer_[Size];
static std::size_t offset_;
public:
template <typename T>
static auto allocate()
{
const auto new_offset = offset_ + sizeof(T);
const auto place = buffer_ + new_offset - sizeof(T);
offset_ = new_offset;
return new (place) T{};
}
};
template <std::size_t Size>
char StaticMemoryAllocator<Size>::buffer_[] = {};
template <std::size_t Size>
std::size_t StaticMemoryAllocator<Size>::offset_ = 0;
The allocator is a class that stores a buffer of a given size. And it has an allocate function that constructs an object of a type given as a template parameter. For each allocation, it determines the next free place in the buffer where it can store the created object. It also stores an offset to know where it allocated last time. When allocating, the new offset is determined based on the last one and the size of the constructed object.
// The new memory offset new_offset = previous_offset + size_of_object; // The place in memory is determined by incrementing the buffer address by the new offset, then subtracting the object size. Eg: for a first object of size 8, I start from the buffer + previous_offset (0) + size_of_object, which is buffer + 8; then I subtract 8 to start from 0. place = buffer_ + new_offset - sizeof(T); // Finally, I store the offset for the next allocation offset_ = new_offset;
And the factory class is using the custom allocator:
class StaticShapeFactory {
using allocator = StaticMemoryAllocator<8>;
public:
static Shape* create(int type)
{
switch (type) {
case 1:
return allocator::allocate<Circle>();
case 2:
return allocator::allocate<Square>();
default:
throw std::invalid_argument{"unknown shape"};
}
}
};
Problems
If things were only that simple… What you saw is only a starting point. I can’t put that in production code. There are a few aspects that need to be improved.
What happens when the buffer is full?
At one point, the offset reaches the end of the buffer. So there is no more space to allocate. When working with static memory, ideally I know the sizes I’m working with and I’m in control of everything. I need to control how many allocations happen.
For uncontrolled situations, there are some (bad?) ideas I could approach when I cannot allocate anymore:
-
- throw an error (std::bad_alloc)
- return a null pointer (std::optional)
- start from the beginning of the buffer and overwrite previous objects
Destructors
With dynamic memory, allocated memory must be freed, manually for raw pointers, or automatically for smart pointers. But this custom allocator is not using dynamic memory, thus the memory does not need to be deallocated. If I want to rely on destructors (eg: classes managing resources that I want to free when the object is gone), I can only call the destructors manually (circle->~Shape();).
Trying to delete the object (delete circle;) is undefined behavior because it does not respect some of the requirements for an object to be deleted. I’m allocating types like Circle and Square into a char buffer and the types do not match.
Memory alignment
The memory used for allocation must be properly aligned to the data type of the allocated object; otherwise, I have undefined behavior.
To be continued…