Understanding Memory Pools
At its core, a memory pool is a pre-allocated, fixed-size block of memory from which memory allocations are made. Instead of requesting memory from the system heap on demand, memory pools allocate memory in advance, typically during program initialization or when memory needs are known in advance. This pre-allocation minimizes the overhead associated with frequent memory allocation and deallocation, leading to improved performance and reduced fragmentation.
Advantages of Memory Pools
- Reduced Overhead: Memory pools reduce overhead by minimizing the need for dynamic memory allocation and deallocation. Since memory blocks are pre-allocated, there is no overhead associated with heap management or fragmentation.
- Improved Performance: By eliminating the overhead of dynamic memory allocation, memory pools offer improved performance, especially in scenarios where memory is frequently allocated and deallocated.
- Enhanced Control: Memory pools provide developers with greater control over memory usage and allocation strategies. Customization options allow developers to tailor memory pools to specific use cases, optimizing memory usage for efficiency and performance.
Creating a memory pool and memory allocator
Creating a memory pool and memory allocator in C++ involves designing a class that manages a pre-allocated block of memory and provides methods for allocating and deallocating memory from within that block. Below is a simple implementation of a memory pool and memory allocator class in C++:
#include <iostream>
class MemoryPool {
private:
char* memory;
size_t totalSize;
size_t blockSize;
bool* allocationMap;
public:
MemoryPool(size_t totalSize, size_t blockSize)
: totalSize(totalSize), blockSize(blockSize) {
memory = new char[totalSize];
allocationMap = new bool[totalSize / blockSize]();
}
~MemoryPool() {
delete[] memory;
delete[] allocationMap;
}
void* allocate() {
for (size_t i = 0; i < totalSize / blockSize; ++i) {
if (!allocationMap[i]) {
allocationMap[i] = true;
return memory + i * blockSize;
}
}
std::cerr << "Memory pool exhausted\n";
return nullptr;
}
void deallocate(void* ptr) {
if (ptr < memory || ptr >= memory + totalSize) {
std::cerr << "Invalid deallocation\n";
return;
}
size_t index = ((char*)ptr - memory) / blockSize;
if (allocationMap[index]) {
allocationMap[index] = false;
} else {
std::cerr << "Invalid deallocation\n";
}
}
};
// Example usage
int main() {
MemoryPool pool(1024, 32);
void* ptr1 = pool.allocate();
void* ptr2 = pool.allocate();
if (ptr1 && ptr2) {
std::cout << "Memory allocated at " << ptr1 << " and " << ptr2 << std::endl;
}
pool.deallocate(ptr1);
pool.deallocate(ptr2);
return 0;
}
Explanation:
- The MemoryPool class manages a pre-allocated block of memory (memory) of size totalSize.
- It divides the memory into fixed-size blocks (blockSize) and maintains an allocation map (allocationMap) to track which blocks are allocated.
- The allocate method searches for the first available block in the allocation map and marks it as allocated.
- The deallocate method marks the block corresponding to the given pointer as deallocated.
OR
Another approach to creating a memory pool and allocator in C++ is to use fixed-size array of memory blocks and implement a simple free list allocation scheme.
#include <iostream>
class MemoryPool {
private:
static const size_t MAX_BLOCKS = 100;
static const size_t BLOCK_SIZE = 32;
char memory[MAX_BLOCKS * BLOCK_SIZE];
bool allocated[MAX_BLOCKS];
size_t findFirstFreeBlock() {
for (size_t i = 0; i < MAX_BLOCKS; ++i) {
if (!allocated[i]) {
return i;
}
}
return MAX_BLOCKS;
}
public:
MemoryPool() {
for (size_t i = 0; i < MAX_BLOCKS; ++i) {
allocated[i] = false;
}
}
void* allocate(size_t size) {
if (size > BLOCK_SIZE) {
std::cerr << "Allocation size exceeds block size\n";
return nullptr;
}
size_t index = findFirstFreeBlock();
if (index < MAX_BLOCKS) {
allocated[index] = true;
return memory + (index * BLOCK_SIZE);
} else {
std::cerr << "Memory pool exhausted\n";
return nullptr;
}
}
void deallocate(void* ptr) {
if (ptr < memory || ptr >= memory + (MAX_BLOCKS * BLOCK_SIZE)) {
std::cerr << "Invalid deallocation\n";
return;
}
size_t index = ((char*)ptr - memory) / BLOCK_SIZE;
if (allocated[index]) {
allocated[index] = false;
} else {
std::cerr << "Invalid deallocation\n";
}
}
};
// Example usage
int main() {
MemoryPool pool;
void* ptr1 = pool.allocate(16);
void* ptr2 = pool.allocate(16);
if (ptr1 && ptr2) {
std::cout << "Memory allocated at " << ptr1 << " and " << ptr2 << std::endl;
}
pool.deallocate(ptr1);
pool.deallocate(ptr2);
return 0;
}
Explanation:
- The MemoryPool class maintains a fixed-size array of memory blocks (memory) with each block having a size of BLOCK_SIZE.
- It also maintains a boolean array (allocated) to track whether each block is allocated or not.
- The allocate method searches for the first available block in the allocated array and marks it as allocated.
- The deallocate method marks the block corresponding to the given pointer as deallocated.
Custom Block Size Allocation
The implementation provided above allocated fixed-size blocks, which can indeed lead to fragmentation if the application requires varying sizes of memory blocks.
To address this limitation and allow for custom-sized memory allocation while still benefiting from the performance advantages of a memory pool, we can modify the implementation to support variable-sized allocations. One common approach is to implement a buddy memory allocation scheme. In this scheme, memory blocks are recursively split and merged to accommodate allocation of different sizes.
#include <iostream>
#include <cmath>
class MemoryPool {
private:
static const size_t MAX_BLOCKS = 100;
char memory[MAX_BLOCKS * MAX_BLOCKS];
bool allocated[MAX_BLOCKS];
struct Block {
size_t size;
size_t index;
bool isFree;
Block* next;
};
Block* head;
Block* findFreeBlock(size_t size) {
Block* current = head;
while (current) {
if (current->isFree && current->size >= size) {
return current;
}
current = current->next;
}
return nullptr;
}
Block* splitBlock(Block* block, size_t size) {
if (block->size == size) {
return block;
}
size_t newSize = block->size / 2;
Block* newBlock = new Block{newSize, block->index + newSize, true, block->next};
block->size = newSize;
block->next = newBlock;
return splitBlock(block, size);
}
public:
MemoryPool() {
for (size_t i = 0; i < MAX_BLOCKS; ++i) {
allocated[i] = false;
}
head = new Block{MAX_BLOCKS, 0, true, nullptr};
}
void* allocate(size_t size) {
size_t blockSize = pow(2, ceil(log2(size)));
Block* freeBlock = findFreeBlock(blockSize);
if (!freeBlock) {
std::cerr << "Memory pool exhausted\n";
return nullptr;
}
freeBlock->isFree = false;
return memory + (freeBlock->index * blockSize);
}
void deallocate(void* ptr) {
if (ptr < memory || ptr >= memory + (MAX_BLOCKS * MAX_BLOCKS)) {
std::cerr << "Invalid deallocation\n";
return;
}
size_t index = ((char*)ptr - memory) / MAX_BLOCKS;
Block* current = head;
while (current) {
if (current->index == index) {
current->isFree = true;
break;
}
current = current->next;
}
}
};
// Example usage
int main() {
MemoryPool pool;
void* ptr1 = pool.allocate(16);
void* ptr2 = pool.allocate(32);
if (ptr1 && ptr2) {
std::cout << "Memory allocated at " << ptr1 << " and " << ptr2 << std::endl;
}
pool.deallocate(ptr1);
pool.deallocate(ptr2);
return 0;
}
Explanation:
- The MemoryPool class maintains a linked list of memory blocks (head) that are recursively split to accommodate variable-sized allocations.
- The allocate method searches for a free block that can accommodate the requested size, or recursively splits a larger block if needed.
- The deallocate method marks the block corresponding to the given pointer as free.