Speeding Up C++ with Custom Allocators
Example of a simple allocator:
template<typename T>
class SimpleAllocator {
public:
using value_type = T;
SimpleAllocator() noexcept = default;
template<typename U> constexpr SimpleAllocator(const SimpleAllocator<U>&) noexcept {}
T* allocate(std::size_t n) {
if (n > std::numeric_limits<std::size_t>::max() / sizeof(T))
throw std::bad_alloc();
if (auto p = static_cast<T*>(std::malloc(n * sizeof(T)))) {
return p;
}
throw std::bad_alloc();
}
void deallocate(T* p, std::size_t) noexcept {
std::free(p);
}
template<typename U, typename... Args>
void construct(U* p, Args&&... args) {
new(p) U(std::forward<Args>(args)...);
}
template<typename U>
void destroy(U* p) noexcept {
p->~U();
}
};Here:
allocate: allocates a block of memory large enough to store
nobjects of the typeT. Note: used herestd::mallocfor allocation, which is sometimes not a very efficient method for all scenarios.deallocate: frees the memory block to which the pointer is provided. The method uses
std::free.construct: uses
placement newto construct an object in the provided memory. This allows you to place objects of the typeU(which may differ fromT) with arbitrary constructor parameters.destroy: calls the destructor for the object without freeing the memory.
Let's look at a more complex allocator:
#include <cstddef>
#include <new>
#include <iostream>
template<typename T>
class PoolAllocator {
public:
using value_type = T;
explicit PoolAllocator(std::size_t size = 1024) : poolSize(size), pool(new char[size * sizeof(T)]) {}
~PoolAllocator() { delete[] pool; }
template<typename U>
PoolAllocator(const PoolAllocator<U>& other) noexcept : poolSize(other.poolSize), pool(other.pool) {}
T* allocate(std::size_t n) {
if (n > poolSize) throw std::bad_alloc();
return reinterpret_cast<T*>(pool + (index++ * sizeof(T)));
}
void deallocate(T* p, std::size_t n) noexcept {
// deallocate не делает ничего, так как память управляется вручную
}
template<typename U, typename... Args>
void construct(U* p, Args&&... args) {
new(p) U(std::forward<Args>(args)...);
}
template<typename U>
void destroy(U* p) {
p->~U();
}
private:
std::size_t poolSize;
char* pool;
std::size_t index = 0;
};
int main() {
PoolAllocator<int> alloc(10); // пул для 10 int
int* num = alloc.allocate(1);
alloc.construct(num, 7);
std::cout << *num << std::endl;
alloc.destroy(num);
alloc.deallocate(num, 1);
}In some situations, you may need to integrate custom allocators with standard library containers, such as std::vector.
Integration
For std::vector a custom allocator must comply with the Allocator concept, which includes the implementation of functions allocate And deallocate.
The allocator class must define types value_type and provide methods allocate to allocate memory and deallocate to release it. These methods are used by the container std::vector to manage memory when changing the vector size.
When creating an instance std::vector You can specify a custom allocator as a template parameter. This allows the vector to use the allocator for all memory operations.
An example of a custom allocator and its use with std::vector:
#include <vector>
#include <iostream>
template<typename T>
class SimpleAllocator {
public:
using value_type = T;
T* allocate(std::size_t n) {
return static_cast<T*>(::operator new(n * sizeof(T)));
}
void deallocate(T* p, std::size_t) noexcept {
::operator delete(p);
}
};
int main() {
std::vector<int, SimpleAllocator<int>> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
for (int i : vec) {
std::cout << i << ' ';
}
std::cout << std::endl;
return 0;
}Here SimpleAllocator allocates and frees memory without taking into account special alignment requirements or other optimizations.
A couple of notes:
Correct memory alignment is very important for performance. A custom allocator should take this into account. alignof(T)to ensure proper alignment of objects in memory.
When there is insufficient memory, the allocator must correctly throw exceptions of the type std::bad_alloc.
Alternative approaches
There are also several alternative approaches that can be considered that take into account the specifics of working with memory and data types:
Using Proxy class for allocator: the approach allows adding additional functionality to the allocator – logging of memory allocation and deallocation operations.
#include <iostream>
#include <memory>
template <typename T, typename Allocator = std::allocator<T>>
class LoggingAllocator : public Allocator {
public:
using value_type = T;
T* allocate(std::size_t n) {
std::cout << "Allocating " << n << " objects of type " << typeid(T).name() << std::endl;
return Allocator::allocate(n);
}
void deallocate(T* p, std::size_t n) {
std::cout << "Deallocating " << n << " objects of type " << typeid(T).name() << std::endl;
Allocator::deallocate(p, n);
}
};
int main() {
std::vector<int, LoggingAllocator<int>> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
}Creating an allocator with support for multiple memory pools: such an allocator manages multiple memory pools optimized for different types or sizes of objects:
#include <vector>
#include <map>
template <typename T>
class MultiPoolAllocator {
public:
using value_type = T;
T* allocate(std::size_t n) {
auto size = sizeof(T) * n;
// выбираем пул на основе размера объекта
if (size <= 128) {
return smallObjectPool.allocate(n);
} else {
return largeObjectPool.allocate(n);
}
}
void deallocate(T* p, std::size_t n) {
auto size = sizeof(T) * n;
if (size <= 128) {
smallObjectPool.deallocate(p, n);
} else {
largeObjectPool.deallocate(p, n);
}
}
private:
std::allocator<T> smallObjectPool;
std::allocator<T> largeObjectPool;
};
int main() {
std::vector<int, MultiPoolAllocator<int>> vec;
vec.push_back(1);
vec.push_back(2);
}It is possible to create an allocator that adapts to memory usage patterns, optimizing allocation on the fly.
For example, we use a simple adaptation strategy based on memory usage statistics:
#include <unordered_map>
#include <iostream>
template <typename T>
class AdaptiveAllocator {
public:
using value_type = T;
T* allocate(std::size_t n) {
std::cout << "Adaptive allocation for " << n << " objects of type " << typeid(T).name() << std::endl;
adaptAllocationStrategy(n);
return std::allocator<T>().allocate(n);
}
void deallocate(T* p, std::size_t n) {
std::allocator<T>().deallocate(p, n);
}
private:
// структура для хранения статистики использования
std::unordered_map<std::size_t, std::size_t> usageStatistics;
void adaptAllocationStrategy(std::size_t n) {
// увеличиваем счетчик запросов на выделение памяти данного размера
usageStatistics[n]++;
// отображаем текущую статистику
std::cout << "Current memory allocation statistics:" << std::endl;
for (auto& stat : usageStatistics) {
std::cout << "Size: " << stat.first << ", Count: " << stat.second << std::endl;
}
// адаптивная логика: определяем, нужно ли изменить стратегию выделения
// например, если запросы на выделение маленьких объектов слишком часты
if (usageStatistics[n] > 10) {
// логика изменения аллокационной стратегии, если это нужно
std::cout << "Adapting allocation strategy for size " << n << std::endl;
}
}
};
int main() {
AdaptiveAllocator<int> allocator;
for (int i = 0; i < 20; i++) {
int* num = allocator.allocate(1);
allocator.deallocate(num, 1);
}
return 0;
}HereAdaptiveAllocator uses std::unordered_map to track how many times each size of memory has been requested. This information can then be used to adapt the memory allocation strategy. For example, if a size is frequently requested, a larger block of memory can be allocated in advance to speed up future allocations.
C++ is known for allowing you to work with memory directly. Here you know exactly where and how each of your objects is located, how much memory it takes up. But can you decide where and how your object will be allocated? Often, standard memory allocation methods do not satisfy the narrow requirements of a specific logic. Our colleagues from OTUS will tell you why allocators exist in C++ at free webinarand will also show a specific example of increasing program performance using a customized allocator.
