Given the following information about memory management in C++:
-----
The c-runtime dynamic memory manager (and most other commercial memory
managers) has issues with fragmentation similar to a hard drive file
system.
Over time, the more often use call new/delete or alloc/free, there
will be
gaps and fragments in the heap. This can lead to inefficient use of
available memory, as well as cache-hit inefficiencies.
The goal of performance-critical applications is to minimize the
number of
calls to new/delete. Many use buffer managers that allocate blocks of
contiguous memory, and chain them together with list pointers when the
block
is consumed. Another approach is to use a Spare List, in which each
block of
memory is not actually freed but returned to a pool manager.
-----
I have implemented a memory pool that will coalesce blocks of memory
that are returned to the pool when they are freed up. I am interested
in the effectiveness of this implementation over the default memory
manager, and what I might want to change or consider when using the
pool in a specific application. I would appreciate any constructive
feedback this group has to offer.
The code to implement and test the pool is as follows:
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <new>
#include <list>
class MemoryPool
{
public:
explicit MemoryPool(size _t memorySize);
~MemoryPool();
void* Reserve(size_t size);
void Release(void* pMemory);
private:
typedef unsigned char Byte;
class Block
{
public:
static Block* FromMemory(void * pMemory);
explicit Block(size_t size, Block* pPrior = NULL, Block*
pNext = NULL);
size_t GetSize() const;
void* GetMemory();
Block* Prior();
Block* Next();
Block* SplitOff(size_t size);
Block* FuseWith( Block* pBlock);
private:
const Block* End() const;
size_t m_size;
Block* m_pPrior;
Block* m_pNext;
};
Block* m_pFirstBlock;
void* m_pMemoryPool;
};
MemoryPool::Mem oryPool
(
size_t memorySize
)
{
m_pMemoryPool = ::operator new(memorySize) ;
::memset(m_pMem oryPool, 0, memorySize);
size_t blockSize = memorySize - sizeof(Block);
m_pFirstBlock = new(m_pMemoryPo ol) Block(blockSize );
}
MemoryPool::~Me moryPool()
{
::operator delete(m_pMemor yPool);
}
void* MemoryPool::Res erve
(
size_t size
)
{
Block* pBlock = m_pFirstBlock;
while(pBlock->GetSize() < size){
pBlock = pBlock->Next();
if(NULL == pBlock){
throw std::bad_alloc( );
}
}
Block* pFreeBlock = pBlock->SplitOff(size) ;
if(NULL == pFreeBlock->Prior()){
m_pFirstBlock = pFreeBlock;
}
return pBlock->GetMemory();
}
void MemoryPool::Rel ease
(
void* pMemory
)
{
Block* pBlock = Block::FromMemo ry(pMemory);
Block* pNextBlock = m_pFirstBlock;
Block* pPriorBlock = NULL;
while(pBlock > pNextBlock){
pPriorBlock = pNextBlock;
pNextBlock = pNextBlock->Next();
if(NULL == pNextBlock){
break;
}
}
if(NULL != pNextBlock){
pBlock = pNextBlock->FuseWith(pBloc k);
}
if(NULL != pPriorBlock){
pPriorBlock->FuseWith(pBloc k);
}
else{
m_pFirstBlock = pBlock;
}
}
MemoryPool::Blo ck* MemoryPool::Blo ck::FromMemory
(
void* pMemory
)
{
Byte* pBytes = reinterpret_cas t<Byte*>(pMemor y);
return reinterpret_cas t<Block*>(pByte s - sizeof(Block));
}
MemoryPool::Blo ck::Block
(
size_t size,
Block* pPrior,
Block* pNext
) : m_size(size),
m_pPrior(pPrior ),
m_pNext(pNext)
{
}
size_t MemoryPool::Blo ck::GetSize() const
{
return m_size;
}
void* MemoryPool::Blo ck::GetMemory()
{
Byte* pMemory = reinterpret_cas t<Byte*>(this) ;
pMemory += sizeof(*this);
return pMemory;
}
MemoryPool::Blo ck* MemoryPool::Blo ck::Prior()
{
return m_pPrior;
}
MemoryPool::Blo ck* MemoryPool::Blo ck::Next()
{
return m_pNext;
}
MemoryPool::Blo ck* MemoryPool::Blo ck::SplitOff
(
size_t size
)
{
Block* pFreeBlock = NULL;
size_t totalSize = sizeof(*this) + size;
if((totalSize >= m_size)){
pFreeBlock = m_pNext;
pFreeBlock->m_pPrior = m_pPrior;
}
else{
Byte* pNextBlock = reinterpret_cas t<Byte*>(this) ;
pNextBlock += totalSize;
pFreeBlock = new(pNextBlock) Block(m_size - totalSize,
m_pPrior,
m_pNext);
if(NULL != m_pNext){
m_pNext->m_pPrior = pFreeBlock;
}
}
if(NULL != m_pPrior){
m_pPrior->m_pNext = pFreeBlock;
}
m_size = size;
m_pPrior = NULL;
m_pNext = NULL;
return pFreeBlock;
}
MemoryPool::Blo ck* MemoryPool::Blo ck::FuseWith
(
Block* pBlock
)
{
if(pBlock < this){
if(pBlock->End() == this){
pBlock->m_size += (sizeof(*this) + m_size);
pBlock->m_pNext = m_pNext;
if(NULL != m_pNext){
m_pNext->m_pPrior = pBlock;
}
}
else{
pBlock->m_pNext = this;
}
}
else{
if(this->End() == pBlock){
m_size += (sizeof(*this) + pBlock->GetSize());
m_pNext = pBlock->m_pNext;
return this;
}
else{
pBlock->m_pPrior = this;
m_pNext = pBlock;
}
}
return pBlock;
}
const MemoryPool::Blo ck* MemoryPool::Blo ck::End() const
{
const Byte* pEnd = reinterpret_cas t<const Byte*>(this);
pEnd += (sizeof(*this) + m_size);
return reinterpret_cas t<const Block*>(pEnd);
}
class Buffer
{
private:
typedef unsigned char Byte;
static const size_t POOL_SIZE = 4096;
static MemoryPool m_memoryPool;
Byte* m_pData;
public:
static void* operator new(size_t size);
static void operator delete(void* pMemory);
explicit Buffer(size_t size);
~Buffer();
};
MemoryPool Buffer::m_memor yPool(Buffer::P OOL_SIZE);
void* Buffer::operato r new
(
size_t size
)
{
return m_memoryPool.Re serve(size);
}
void Buffer::operato r delete
(
void* pMemory
)
{
m_memoryPool.Re lease(pMemory);
}
Buffer::Buffer
(
size_t size
)
{
m_pData = reinterpret_cas t<Byte*>(m_memo ryPool.Reserve( size));
::memset(m_pDat a, 0xFF, size);
}
Buffer::~Buffer ()
{
m_memoryPool.Re lease(m_pData);
}
typedef std::list<Buffe r*> BufferList;
typedef BufferList::ite rator BufferIterator;
void AddBuffer(Buffe rList* pList, size_t size = 0);
void RemoveBuffer(Bu fferList* pList, size_t buffer = 0);
void ClearBufferList (BufferList* pList);
void AddBuffer
(
BufferList* pList,
size_t size
)
{
const size_t MAX_BUFFER_SIZE = 128;
const size_t MIN_BUFFER_SIZE = 16;
if(0 == size){
size = ::rand() % MAX_BUFFER_SIZE + 1;
if(MIN_BUFFER_S IZE > size){
size = MIN_BUFFER_SIZE ;
}
}
pList->push_back(ne w Buffer(size));
}
void RemoveBuffer
(
BufferList* pList,
size_t buffer
)
{
size_t size = pList->size();
if(0 == buffer || (buffer >= size)){
buffer = ::rand() % size;
}
BufferIterator itBuffer = pList->begin();
std::advance(it Buffer, buffer);
Buffer* pBuffer = *itBuffer;
pList->erase(itBuffer );
delete pBuffer;
}
void ClearBufferList
(
BufferList* pList
)
{
BufferIterator itBuffer = pList->begin();
const BufferIterator itEND = pList->end();
while(itEND != itBuffer){
delete *itBuffer;
++itBuffer;
}
}
int main()
{
::srand(::time( NULL));
BufferList bufferList;
const int nBUFFER_COUNT = 20;
for(int nBuffer; nBUFFER_COUNT > nBuffer; ++nBuffer){
::AddBuffer(&bu fferList);
}
for(int nRemove = 0; 5 > nRemove; ++nRemove){
::RemoveBuffer( &bufferList) ;
}
for(int nTest = 0; 10 > nTest; ++nTest){
if(0 == ::rand() % 2){
::AddBuffer(&bu fferList);
}
else{
::RemoveBuffer( &bufferList) ;
}
}
::ClearBufferLi st(&bufferList) ;
}
-----
The c-runtime dynamic memory manager (and most other commercial memory
managers) has issues with fragmentation similar to a hard drive file
system.
Over time, the more often use call new/delete or alloc/free, there
will be
gaps and fragments in the heap. This can lead to inefficient use of
available memory, as well as cache-hit inefficiencies.
The goal of performance-critical applications is to minimize the
number of
calls to new/delete. Many use buffer managers that allocate blocks of
contiguous memory, and chain them together with list pointers when the
block
is consumed. Another approach is to use a Spare List, in which each
block of
memory is not actually freed but returned to a pool manager.
-----
I have implemented a memory pool that will coalesce blocks of memory
that are returned to the pool when they are freed up. I am interested
in the effectiveness of this implementation over the default memory
manager, and what I might want to change or consider when using the
pool in a specific application. I would appreciate any constructive
feedback this group has to offer.
The code to implement and test the pool is as follows:
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <new>
#include <list>
class MemoryPool
{
public:
explicit MemoryPool(size _t memorySize);
~MemoryPool();
void* Reserve(size_t size);
void Release(void* pMemory);
private:
typedef unsigned char Byte;
class Block
{
public:
static Block* FromMemory(void * pMemory);
explicit Block(size_t size, Block* pPrior = NULL, Block*
pNext = NULL);
size_t GetSize() const;
void* GetMemory();
Block* Prior();
Block* Next();
Block* SplitOff(size_t size);
Block* FuseWith( Block* pBlock);
private:
const Block* End() const;
size_t m_size;
Block* m_pPrior;
Block* m_pNext;
};
Block* m_pFirstBlock;
void* m_pMemoryPool;
};
MemoryPool::Mem oryPool
(
size_t memorySize
)
{
m_pMemoryPool = ::operator new(memorySize) ;
::memset(m_pMem oryPool, 0, memorySize);
size_t blockSize = memorySize - sizeof(Block);
m_pFirstBlock = new(m_pMemoryPo ol) Block(blockSize );
}
MemoryPool::~Me moryPool()
{
::operator delete(m_pMemor yPool);
}
void* MemoryPool::Res erve
(
size_t size
)
{
Block* pBlock = m_pFirstBlock;
while(pBlock->GetSize() < size){
pBlock = pBlock->Next();
if(NULL == pBlock){
throw std::bad_alloc( );
}
}
Block* pFreeBlock = pBlock->SplitOff(size) ;
if(NULL == pFreeBlock->Prior()){
m_pFirstBlock = pFreeBlock;
}
return pBlock->GetMemory();
}
void MemoryPool::Rel ease
(
void* pMemory
)
{
Block* pBlock = Block::FromMemo ry(pMemory);
Block* pNextBlock = m_pFirstBlock;
Block* pPriorBlock = NULL;
while(pBlock > pNextBlock){
pPriorBlock = pNextBlock;
pNextBlock = pNextBlock->Next();
if(NULL == pNextBlock){
break;
}
}
if(NULL != pNextBlock){
pBlock = pNextBlock->FuseWith(pBloc k);
}
if(NULL != pPriorBlock){
pPriorBlock->FuseWith(pBloc k);
}
else{
m_pFirstBlock = pBlock;
}
}
MemoryPool::Blo ck* MemoryPool::Blo ck::FromMemory
(
void* pMemory
)
{
Byte* pBytes = reinterpret_cas t<Byte*>(pMemor y);
return reinterpret_cas t<Block*>(pByte s - sizeof(Block));
}
MemoryPool::Blo ck::Block
(
size_t size,
Block* pPrior,
Block* pNext
) : m_size(size),
m_pPrior(pPrior ),
m_pNext(pNext)
{
}
size_t MemoryPool::Blo ck::GetSize() const
{
return m_size;
}
void* MemoryPool::Blo ck::GetMemory()
{
Byte* pMemory = reinterpret_cas t<Byte*>(this) ;
pMemory += sizeof(*this);
return pMemory;
}
MemoryPool::Blo ck* MemoryPool::Blo ck::Prior()
{
return m_pPrior;
}
MemoryPool::Blo ck* MemoryPool::Blo ck::Next()
{
return m_pNext;
}
MemoryPool::Blo ck* MemoryPool::Blo ck::SplitOff
(
size_t size
)
{
Block* pFreeBlock = NULL;
size_t totalSize = sizeof(*this) + size;
if((totalSize >= m_size)){
pFreeBlock = m_pNext;
pFreeBlock->m_pPrior = m_pPrior;
}
else{
Byte* pNextBlock = reinterpret_cas t<Byte*>(this) ;
pNextBlock += totalSize;
pFreeBlock = new(pNextBlock) Block(m_size - totalSize,
m_pPrior,
m_pNext);
if(NULL != m_pNext){
m_pNext->m_pPrior = pFreeBlock;
}
}
if(NULL != m_pPrior){
m_pPrior->m_pNext = pFreeBlock;
}
m_size = size;
m_pPrior = NULL;
m_pNext = NULL;
return pFreeBlock;
}
MemoryPool::Blo ck* MemoryPool::Blo ck::FuseWith
(
Block* pBlock
)
{
if(pBlock < this){
if(pBlock->End() == this){
pBlock->m_size += (sizeof(*this) + m_size);
pBlock->m_pNext = m_pNext;
if(NULL != m_pNext){
m_pNext->m_pPrior = pBlock;
}
}
else{
pBlock->m_pNext = this;
}
}
else{
if(this->End() == pBlock){
m_size += (sizeof(*this) + pBlock->GetSize());
m_pNext = pBlock->m_pNext;
return this;
}
else{
pBlock->m_pPrior = this;
m_pNext = pBlock;
}
}
return pBlock;
}
const MemoryPool::Blo ck* MemoryPool::Blo ck::End() const
{
const Byte* pEnd = reinterpret_cas t<const Byte*>(this);
pEnd += (sizeof(*this) + m_size);
return reinterpret_cas t<const Block*>(pEnd);
}
class Buffer
{
private:
typedef unsigned char Byte;
static const size_t POOL_SIZE = 4096;
static MemoryPool m_memoryPool;
Byte* m_pData;
public:
static void* operator new(size_t size);
static void operator delete(void* pMemory);
explicit Buffer(size_t size);
~Buffer();
};
MemoryPool Buffer::m_memor yPool(Buffer::P OOL_SIZE);
void* Buffer::operato r new
(
size_t size
)
{
return m_memoryPool.Re serve(size);
}
void Buffer::operato r delete
(
void* pMemory
)
{
m_memoryPool.Re lease(pMemory);
}
Buffer::Buffer
(
size_t size
)
{
m_pData = reinterpret_cas t<Byte*>(m_memo ryPool.Reserve( size));
::memset(m_pDat a, 0xFF, size);
}
Buffer::~Buffer ()
{
m_memoryPool.Re lease(m_pData);
}
typedef std::list<Buffe r*> BufferList;
typedef BufferList::ite rator BufferIterator;
void AddBuffer(Buffe rList* pList, size_t size = 0);
void RemoveBuffer(Bu fferList* pList, size_t buffer = 0);
void ClearBufferList (BufferList* pList);
void AddBuffer
(
BufferList* pList,
size_t size
)
{
const size_t MAX_BUFFER_SIZE = 128;
const size_t MIN_BUFFER_SIZE = 16;
if(0 == size){
size = ::rand() % MAX_BUFFER_SIZE + 1;
if(MIN_BUFFER_S IZE > size){
size = MIN_BUFFER_SIZE ;
}
}
pList->push_back(ne w Buffer(size));
}
void RemoveBuffer
(
BufferList* pList,
size_t buffer
)
{
size_t size = pList->size();
if(0 == buffer || (buffer >= size)){
buffer = ::rand() % size;
}
BufferIterator itBuffer = pList->begin();
std::advance(it Buffer, buffer);
Buffer* pBuffer = *itBuffer;
pList->erase(itBuffer );
delete pBuffer;
}
void ClearBufferList
(
BufferList* pList
)
{
BufferIterator itBuffer = pList->begin();
const BufferIterator itEND = pList->end();
while(itEND != itBuffer){
delete *itBuffer;
++itBuffer;
}
}
int main()
{
::srand(::time( NULL));
BufferList bufferList;
const int nBUFFER_COUNT = 20;
for(int nBuffer; nBUFFER_COUNT > nBuffer; ++nBuffer){
::AddBuffer(&bu fferList);
}
for(int nRemove = 0; 5 > nRemove; ++nRemove){
::RemoveBuffer( &bufferList) ;
}
for(int nTest = 0; 10 > nTest; ++nTest){
if(0 == ::rand() % 2){
::AddBuffer(&bu fferList);
}
else{
::RemoveBuffer( &bufferList) ;
}
}
::ClearBufferLi st(&bufferList) ;
}
Comment