T
Tron Thomas
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::MemoryPool
(
size_t memorySize
)
{
m_pMemoryPool = :
perator new(memorySize);
::memset(m_pMemoryPool, 0, memorySize);
size_t blockSize = memorySize - sizeof(Block);
m_pFirstBlock = new(m_pMemoryPool) Block(blockSize);
}
MemoryPool::~MemoryPool()
{
:perator delete(m_pMemoryPool);
}
void* MemoryPool::Reserve
(
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::Release
(
void* pMemory
)
{
Block* pBlock = Block::FromMemory(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(pBlock);
}
if(NULL != pPriorBlock){
pPriorBlock->FuseWith(pBlock);
}
else{
m_pFirstBlock = pBlock;
}
}
MemoryPool::Block* MemoryPool::Block::FromMemory
(
void* pMemory
)
{
Byte* pBytes = reinterpret_cast<Byte*>(pMemory);
return reinterpret_cast<Block*>(pBytes - sizeof(Block));
}
MemoryPool::Block::Block
(
size_t size,
Block* pPrior,
Block* pNext
) : m_size(size),
m_pPrior(pPrior),
m_pNext(pNext)
{
}
size_t MemoryPool::Block::GetSize() const
{
return m_size;
}
void* MemoryPool::Block::GetMemory()
{
Byte* pMemory = reinterpret_cast<Byte*>(this);
pMemory += sizeof(*this);
return pMemory;
}
MemoryPool::Block* MemoryPool::Block:rior()
{
return m_pPrior;
}
MemoryPool::Block* MemoryPool::Block::Next()
{
return m_pNext;
}
MemoryPool::Block* MemoryPool::Block::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_cast<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::Block* MemoryPool::Block::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::Block* MemoryPool::Block::End() const
{
const Byte* pEnd = reinterpret_cast<const Byte*>(this);
pEnd += (sizeof(*this) + m_size);
return reinterpret_cast<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_memoryPool(Buffer:OOL_SIZE);
void* Buffer:perator new
(
size_t size
)
{
return m_memoryPool.Reserve(size);
}
void Buffer:perator delete
(
void* pMemory
)
{
m_memoryPool.Release(pMemory);
}
Buffer::Buffer
(
size_t size
)
{
m_pData = reinterpret_cast<Byte*>(m_memoryPool.Reserve(size));
::memset(m_pData, 0xFF, size);
}
Buffer::~Buffer()
{
m_memoryPool.Release(m_pData);
}
typedef std::list<Buffer*> BufferList;
typedef BufferList::iterator BufferIterator;
void AddBuffer(BufferList* pList, size_t size = 0);
void RemoveBuffer(BufferList* 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_SIZE > size){
size = MIN_BUFFER_SIZE;
}
}
pList->push_back(new 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(itBuffer, 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(&bufferList);
}
for(int nRemove = 0; 5 > nRemove; ++nRemove){
::RemoveBuffer(&bufferList);
}
for(int nTest = 0; 10 > nTest; ++nTest){
if(0 == ::rand() % 2){
::AddBuffer(&bufferList);
}
else{
::RemoveBuffer(&bufferList);
}
}
::ClearBufferList(&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::MemoryPool
(
size_t memorySize
)
{
m_pMemoryPool = :
perator new(memorySize);::memset(m_pMemoryPool, 0, memorySize);
size_t blockSize = memorySize - sizeof(Block);
m_pFirstBlock = new(m_pMemoryPool) Block(blockSize);
}
MemoryPool::~MemoryPool()
{
:
perator delete(m_pMemoryPool);}
void* MemoryPool::Reserve
(
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::Release
(
void* pMemory
)
{
Block* pBlock = Block::FromMemory(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(pBlock);
}
if(NULL != pPriorBlock){
pPriorBlock->FuseWith(pBlock);
}
else{
m_pFirstBlock = pBlock;
}
}
MemoryPool::Block* MemoryPool::Block::FromMemory
(
void* pMemory
)
{
Byte* pBytes = reinterpret_cast<Byte*>(pMemory);
return reinterpret_cast<Block*>(pBytes - sizeof(Block));
}
MemoryPool::Block::Block
(
size_t size,
Block* pPrior,
Block* pNext
) : m_size(size),
m_pPrior(pPrior),
m_pNext(pNext)
{
}
size_t MemoryPool::Block::GetSize() const
{
return m_size;
}
void* MemoryPool::Block::GetMemory()
{
Byte* pMemory = reinterpret_cast<Byte*>(this);
pMemory += sizeof(*this);
return pMemory;
}
MemoryPool::Block* MemoryPool::Block:
rior(){
return m_pPrior;
}
MemoryPool::Block* MemoryPool::Block::Next()
{
return m_pNext;
}
MemoryPool::Block* MemoryPool::Block::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_cast<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::Block* MemoryPool::Block::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::Block* MemoryPool::Block::End() const
{
const Byte* pEnd = reinterpret_cast<const Byte*>(this);
pEnd += (sizeof(*this) + m_size);
return reinterpret_cast<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_memoryPool(Buffer:
OOL_SIZE);void* Buffer:
perator new(
size_t size
)
{
return m_memoryPool.Reserve(size);
}
void Buffer:
perator delete(
void* pMemory
)
{
m_memoryPool.Release(pMemory);
}
Buffer::Buffer
(
size_t size
)
{
m_pData = reinterpret_cast<Byte*>(m_memoryPool.Reserve(size));
::memset(m_pData, 0xFF, size);
}
Buffer::~Buffer()
{
m_memoryPool.Release(m_pData);
}
typedef std::list<Buffer*> BufferList;
typedef BufferList::iterator BufferIterator;
void AddBuffer(BufferList* pList, size_t size = 0);
void RemoveBuffer(BufferList* 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_SIZE > size){
size = MIN_BUFFER_SIZE;
}
}
pList->push_back(new 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(itBuffer, 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(&bufferList);
}
for(int nRemove = 0; 5 > nRemove; ++nRemove){
::RemoveBuffer(&bufferList);
}
for(int nTest = 0; 10 > nTest; ++nTest){
if(0 == ::rand() % 2){
::AddBuffer(&bufferList);
}
else{
::RemoveBuffer(&bufferList);
}
}
::ClearBufferList(&bufferList);
}