In this blog, we will dive into the intricacies of memory management by developing a custom memory allocator in C++. This is an advanced topic that can help you optimize your applications by having more control over how memory is allocated and deallocated.
Introduction
Memory management is a crucial aspect of system-level programming. While C++ provides standard memory management facilities, there are scenarios where a custom memory allocator can provide significant performance improvements and more predictable memory usage.
Why Use a Custom Memory Allocator?
Custom memory allocators can:
- Reduce fragmentation
- Increase allocation and deallocation speed
- Provide more predictable memory usage patterns
- Be tailored to the specific needs of your application
Basic Concepts
Before we start, let's review some basic concepts:
- Memory Pool: A large block of memory from which smaller chunks are allocated.
- Free List: A linked list of free memory blocks that can be reused.
- Alignment: Ensuring that memory addresses meet certain alignment requirements.
Designing the Allocator
We'll design a simple allocator with the following features:
- A fixed-size memory pool
- A free list for managing available blocks
- Support for basic allocation and deallocation operations
Implementation
Memory Pool
We'll start by defining a memory pool that will act as the source of memory for our allocator.
#include <iostream>
#include <cstddef>
#include <cassert>
class MemoryPool {
public:
MemoryPool(size_t size);
~MemoryPool();
void* allocate(size_t size);
void deallocate(void* ptr);
private:
struct FreeBlock {
FreeBlock* next;
};
char* pool;
size_t poolSize;
FreeBlock* freeList;
void* alignPointer(void* ptr, size_t alignment);
};
MemoryPool::MemoryPool(size_t size)
: poolSize(size), freeList(nullptr) {
pool = new char[size];
freeList = reinterpret_cast<FreeBlock*>(pool);
freeList->next = nullptr;
}
MemoryPool::~MemoryPool() {
delete[] pool;
}
void* MemoryPool::alignPointer(void* ptr, size_t alignment) {
uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
size_t offset = addr % alignment;
if (offset != 0) {
addr += (alignment - offset);
}
return reinterpret_cast<void*>(addr);
}
void* MemoryPool::allocate(size_t size) {
// Align the requested size to the alignment of FreeBlock
size = (size + sizeof(FreeBlock) - 1) & ~(sizeof(FreeBlock) - 1);
FreeBlock* prev = nullptr;
FreeBlock* curr = freeList;
while (curr != nullptr) {
if (reinterpret_cast<char*>(curr) + size <= pool + poolSize) {
if (prev != nullptr) {
prev->next = curr->next;
} else {
freeList = curr->next;
}
return reinterpret_cast<void*>(curr);
}
prev = curr;
curr = curr->next;
}
return nullptr; // No suitable block found
}
void MemoryPool::deallocate(void* ptr) {
FreeBlock* block = reinterpret_cast<FreeBlock*>(ptr);
block->next = freeList;
freeList = block;
}
int main() {
const size_t poolSize = 1024;
MemoryPool allocator(poolSize);
void* p1 = allocator.allocate(128);
std::cout << "Allocated 128 bytes at " << p1 << std::endl;
void* p2 = allocator.allocate(256);
std::cout << "Allocated 256 bytes at " << p2 << std::endl;
allocator.deallocate(p1);
std::cout << "Deallocated memory at " << p1 << std::endl;
void* p3 = allocator.allocate(64);
std::cout << "Allocated 64 bytes at " << p3 << std::endl;
return 0;
}Explanation
MemoryPool Constructor
The constructor initializes the memory pool and sets up the initial free list.
MemoryPool::MemoryPool(size_t size)
: poolSize(size), freeList(nullptr) {
pool = new char[size];
freeList = reinterpret_cast<FreeBlock*>(pool);
freeList->next = nullptr;
}Align Pointer
The alignPointer function ensures that the memory addresses meet certain alignment requirements.
void* MemoryPool::alignPointer(void* ptr, size_t alignment) {
uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
size_t offset = addr % alignment;
if (offset != 0) {
addr += (alignment - offset);
}
return reinterpret_cast<void*>(addr);
}Allocate Memory
The allocate function searches the free list for a suitable block and returns a pointer to the allocated memory.
void* MemoryPool::allocate(size_t size) {
size = (size + sizeof(FreeBlock) - 1) & ~(sizeof(FreeBlock) - 1);
FreeBlock* prev = nullptr;
FreeBlock* curr = freeList;
while (curr != nullptr) {
if (reinterpret_cast<char*>(curr) + size <= pool + poolSize) {
if (prev != nullptr) {
prev->next = curr->next;
} else {
freeList = curr->next;
}
return reinterpret_cast<void*>(curr);
}
prev = curr;
curr = curr->next;
}
return nullptr;
}Deallocate Memory
The deallocate function adds the deallocated block back to the free list.
void MemoryPool::deallocate(void* ptr) {
FreeBlock* block = reinterpret_cast<FreeBlock*>(ptr);
block->next = freeList;
freeList = block;
}Testing the Allocator
Here is a simple main function to test our allocator.
int main() {
const size_t poolSize = 1024;
MemoryPool allocator(poolSize);
void* p1 = allocator.allocate(128);
std::cout << "Allocated 128 bytes at " << p1 << std::endl;
void* p2 = allocator.allocate(256);
std::cout << "Allocated 256 bytes at " << p2 << std::endl;
allocator.deallocate(p1);
std::cout << "Deallocated memory at " << p1 << std::endl;
void* p3 = allocator.allocate(64);
std::cout << "Allocated 64 bytes at " << p3 << std::endl;
return 0;
}Performance Comparison
You can add performance comparison code to benchmark our custom allocator against the standard new and delete operators to demonstrate the benefits.
#include <chrono>
void benchmarkAllocator() {
const size_t poolSize = 1024 * 1024;
const size_t numAllocations = 10000;
const size_t blockSize = 128;
MemoryPool allocator(poolSize);
auto start = std::chrono::high_resolution_clock::now();
for (size_t i = 0; i < numAllocations; ++i) {
void* ptr = allocator.allocate(blockSize);
allocator.deallocate(ptr);
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration = end - start;
std::cout << "Custom allocator duration: " << duration.count() << " seconds" << std::endl;
start = std::chrono::high_resolution_clock::now();
for (size_t i = 0; i < numAllocations; ++i) {
void* ptr = operator new(blockSize);
operator delete(ptr);
}
end = std::chrono::high_resolution_clock::now();
duration = end - start;
std::cout << "Standard allocator duration: " << duration.count() << " seconds" << std::endl;
}
int main() {
benchmarkAllocator();
return 0;
}Conclusion
Custom memory allocators can provide significant performance benefits and more predictable memory usage. By understanding and implementing a basic allocator, you can tailor memory management to the specific needs of your application.