I chose a fixed size pool in order to use it for creating same size objects. The goal is to prevent memory fragmentation after creating/deleting a huge number of the same size objects.
Implemtation Details
It is implemented in C++11 using templates. A Memory Pool is a linked list of structs called “MemoryBlock”. A pool has one active MemoryBlock and is always trying to first allocate the element from the active structure. Failing to do that, the pool tries the next MemoryBlock.
Each MemoryBlock has a fixed number of elements. An element holds one instance of the object being managed. Number of elements in a MemoryBlock is set during the creation of the pool.
MemoryBlock uses simple auxiliary container (stack) which is keeping the indices of available elements rather than object pointers. It has a “stack-like” behavior and uses 16-bit values of indices to reduce memory consumption. Thus the number of elements per MemoryBlock is limited to 65655.
Allocating an Element
A new element is removed from the the stack of free elements of MemoryBlock. If the pool has no free elements, a new MemoryBlock is created with the same size as the head MemoryBlock. The new MemoryBlock becomes the active MemoryBlock for the pool. The pool is always searching for a free element in the active MemoryBlock.
Freeing an Element
When an element is returned to the pool, it’s pushed into the stack of free elements in the MemoryBlock which now becomes the active MemoryBlock. If all elements of the active block are available for allocating, the pool checks the freeing policy settings. The pool removes the active MemoryBlock if allowed by settings. Therefore, the pool is also able to deallocate dynamically allocated memory when it’s no longer needed.
How to use
class TestClass
{
public:
TestClass(int n = 0, double d = 0, unsigned long l = 0) : intVar(n), doubleVar(d), ulongVar(l) { }
void print() { std::cout << "intVar = " << intVar << std::endl; }
private:
int intVar;
double doubleVar;
unsigned long ulongVar;
};
/* memory pool instantiation */
MemPool<TestClass> classMemPool;
/* creating a test class using memory pool */
TestClass* pClass = classMemPool.getObject(123, 3.14);
pClass->print();
classMemPool.destructObject(pClass);
/* OR using smart pointer */
auto deleter = [&classMemPool] (TestClass* p) { classMemPool.destructObject(p); };
unique_ptr<TestClass, decltype(deleter)> pSmart(classMemPool.getObject(123, 3.14), deleter);
pSmart->print();
I used GCC-4.8 for testing the application on Linux and Windows platforms.
#ifndef MEMPOOL_H
#define MEMPOOL_H
#include <algorithm>
#include <iostream>
#include <memory>
#include <mutex>
#include <thread>
#include <vector>
using namespace std;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned short int ushort;
/**
* A simple container which is used for keeping
* the indices rather than free object pointers.
* It has a "stack-like" behaviour and uses 16-bit values
* as indices to reduce memory consumption.
*/
struct FreeElementIndices
{
uint m_availibleIndices;
vector<ushort> m_indices;
inline bool isEmpty() { return (0 == m_availibleIndices); }
inline bool isFull() { return (m_indices.size() == m_availibleIndices); }
inline uint size() { return m_indices.size(); }
inline uint availibleIndices() { return m_availibleIndices; }
/*
* initialize a vector
*/
void init(uint size)
{
m_indices.resize(size);
m_availibleIndices = size;
ushort N = (ushort ) (size - 1);
for (ushort i = 0; i < size; i++, N--)
{
m_indices[i] = N;
}
}
/*
* append an index of free element from the pre-allocated memory pool
*/
void push(uint index)
{
if (m_availibleIndices < m_indices.size())
{
m_indices[m_availibleIndices] = (ushort ) index;
m_availibleIndices++;
}
}
/*
* returns an index of free element
*/
uint pop()
{
uint result = (int) -1; // indicates error
if (m_availibleIndices > 0)
{
m_availibleIndices--;
result = m_indices[m_availibleIndices];
}
return result;
}
/*
* transform free indices to busy one's
*/
void transformToBusy()
{
size_t size = m_indices.size();
if (0 == m_availibleIndices)
{
// all busy
m_availibleIndices = size;
for (ushort i = 0; i < size; i++)
{
m_indices[i] = i;
}
}
else
{
std::sort(m_indices.begin(), m_indices.begin() + m_availibleIndices);
ushort j = m_availibleIndices;
for (ushort i = 0; i < m_availibleIndices; i++)
{
if (i != m_indices[i])
{
ushort k = (i == 0)? 0 : m_indices[i-1] + 1;
for (; k < m_indices[i]; k++)
{
m_indices[j] = k;
j++;
}
}
}
// erase the free elements
m_indices.erase(m_indices.begin(), m_indices.begin() + m_availibleIndices);
// set new size
m_availibleIndices = size - m_availibleIndices;
}
}
};
/**
* Simple memory pool template class
*/
template <typename T, unsigned int numOfElements = 1000> class MemPool
{
private:
struct MemoryBlock
{
bool m_useDtor;
T* m_pMemPool;
MemoryBlock* m_next;
FreeElementIndices m_items;
MemoryBlock(size_t numElements, bool useDtor = true) : m_useDtor(useDtor), m_pMemPool(nullptr), m_next(nullptr)
{
// allocate, but not construct
m_pMemPool = static_cast<T*> (::operator new (sizeof(T[numElements])));
if (m_pMemPool != nullptr)
{
m_items.init(numElements);
}
}
T* alloc()
{
T* ptr = nullptr;
if (!m_items.isEmpty())
{
ptr = &m_pMemPool[m_items.pop()];
}
return ptr;
}
bool markAsFree(T* ptr)
{
bool res = false;
if (ptr >= m_pMemPool)
{
ushort index = (ptr - m_pMemPool);
if (index < m_items.size())
{
// destroy an object but does not free memory
if (m_useDtor)
{
ptr->~T();
}
m_items.push(index);
res = true;
}
}
return res;
}
~MemoryBlock()
{
if (m_pMemPool != nullptr)
{
if (m_useDtor && m_items.isFull() == false)
{
m_items.transformToBusy();
while (m_items.availibleIndices() > 0)
{
uint index = m_items.pop();
T* ptr = &m_pMemPool[index];
ptr->~T();
}
}
// deallocate
::operator delete(m_pMemPool);
}
}
};
uint m_ElementsPerChunk;
size_t m_numChunks;
size_t m_availableTotal;
MemoryBlock* m_pHead;
MemoryBlock* m_pCurrent;
// memory freeing policy
bool m_isReleaseMemoryBlocks;
uint m_minNumChunks;
// using destructor for deleting elements.
// in some cases we do not need it
bool m_useDestructor;
#ifdef THREAD_SAVE
std::mutex m_Mutex;
#endif
public:
MemPool()
{
m_ElementsPerChunk = numOfElements;
m_numChunks = 1;
m_availableTotal = 0;
m_isReleaseMemoryBlocks = false;
m_minNumChunks = 2;
m_useDestructor = true;
// allocate a fixed-size memory pool
m_pHead = new(std::nothrow) MemoryBlock(numOfElements);
if (m_pHead != nullptr)
{
m_pCurrent = m_pHead;
m_numChunks = 1;
m_availableTotal = numOfElements;
}
}
~MemPool()
{
#ifdef THREAD_SAVE
std::lock_guard<std::mutex> lock(m_Mutex);
#endif
// release resources
MemoryBlock* pChunk = m_pHead;
while(pChunk != nullptr)
{
MemoryBlock* p = pChunk;
pChunk = pChunk->m_next;
delete p;
}
}
/**
* set a memory freeing policy
* isRelease - enable/disable to remove a memory block(s)
* minNunChunks - set the minimal number of memory blocks
*/
void setReleasePolicy(bool isRelease, uint minNumChunks)
{
m_isReleaseMemoryBlocks = isRelease;
m_minNumChunks = minNumChunks;
}
/**
* creates a new object
*/
template<typename... Args>
inline T* getObject(Args&&...args)
{
T* object = new (alloc()) T(args...);
return object;
}
/**
* getting a memory ptr from the pool
*
*/
T* alloc()
{
T* ptr = nullptr;
#ifdef THREAD_SAVE
std::lock_guard<std::mutex> lock(m_Mutex);
#endif
if (0 == m_availableTotal)
{
MemoryBlock* pChunk = new(std::nothrow) MemoryBlock(m_ElementsPerChunk);
if (pChunk != nullptr)
{
// append to the end of the list
MemoryBlock* p = m_pCurrent;
while (p->m_next != nullptr)
{
p = p->m_next;
}
p->m_next = pChunk;
m_pCurrent = pChunk;
m_availableTotal += m_ElementsPerChunk;
m_numChunks += 1;
ptr = m_pCurrent->alloc();
}
else
{
throw std::bad_alloc();
}
}
else
{
if (m_pCurrent->m_items.isEmpty())
{
MemoryBlock* p = m_pHead;
for (; p != nullptr; p = p->m_next)
{
if (p->m_items.isEmpty() == false)
{
m_pCurrent = p;
break;
}
}
}
ptr = m_pCurrent->alloc();
}
if (nullptr == ptr)
{
throw std::bad_alloc();
}
else
{
m_availableTotal--;
}
return ptr;
}
/**
* "deallocate" element
*
*/
void destructObject(T* ptr)
{
bool done = false;
#ifdef THREAD_SAVE
std::lock_guard<std::mutex> lock(m_Mutex);
#endif
done = m_pCurrent->markAsFree(ptr);
if (done == false)
{
MemoryBlock* p = m_pHead;
for (; p != nullptr; p = p->m_next)
{
// check a pointer range
if (ptr >= p->m_pMemPool && ptr <= &p->m_pMemPool[p->m_items.size() - 1])
{
if (p->markAsFree(ptr))
{
m_pCurrent = p;
done = true;
break;
}
}
}
}
if (done)
{
m_availableTotal++;
// free the empty chunk under the policy conditions
if (m_pCurrent->m_items.isFull() &&
m_isReleaseMemoryBlocks &&
m_numChunks > m_minNumChunks)
{
MemoryBlock* pChunk = m_pCurrent;
m_numChunks--;
m_availableTotal -= m_pCurrent->m_items.size();
if (m_pHead != m_pCurrent)
{
m_pCurrent = m_pHead;
while(m_pCurrent->m_next != pChunk)
{
m_pCurrent = m_pCurrent->m_next;
}
m_pCurrent->m_next = pChunk->m_next;
}
else
{
m_pHead = m_pCurrent->m_next;
m_pCurrent = m_pHead;
}
delete pChunk;
}
}
}
};
#endif // MEMPOOL_H
[whohit]pool[/whohit]