Click here to Skip to main content
Click here to Skip to main content

Why to use memory pool and how to implement it

, 3 Jul 2008 CPOL
Rate this:
Please Sign up or sign in to vote.
Introduce memory pool

Download MemoryPoolSourceCode.zip - 21.82 KB

Introduction

What is memory pool? I think I must answer the question firstly, because it is important to beginner. In short, memory pool is a memory block which you got from system and use some unit of it to replace the system call malloc/free and new/delete. The advantage of the technology is reuse existing memory block so that reduce the times of system call. It`s a hard work to give the definition. If you still can`t understand the concept, please google it.

Background

Why to use memory pool? I have two reason:[1]To shorten the time that program allocate memory. Now I show an example to prove the technology have good efficiency:

#include <span class="code-keyword"><windows.h></span>
#include <span class="code-keyword"><iostream.h></span>

class CTestClass
{    
    char m_chBuf[4096];
};

int main()
{
    DWORD count = GetTickCount();    
    
    for(unsigned int i=0; i<0x5fffff; i++)
    {
        CTestClass *p = new CTestClass;
        delete p;
    }
    
    cout << "Interval = " << GetTickCount()-count << " ms" << endl;
    
    return 0;
} 

In my computer (Intel 3.0G Hz CPU / 512 MB of RAM / Win XP SP2 / VC6.0), the result is:

Interval = 8735 ms

When I use a simple memory pool, the code is following:

#include <span class="code-keyword"><windows.h></span>
#include <span class="code-keyword"><iostream.h></span>

char buf[4100];  //Simple Memory Pool 

class CTestClass
{
    char m_chBuf[4096];
public:    
    void *operator new(unsigned int uiSize)
    {
        return (void *)buf;
    }
    void  operator delete(void *p)
    {
    }
};

int main()
{
    DWORD count = GetTickCount();
    
    for(unsigned int i=0; i<0x5fffff; i++)
    {
        CTestClass *p = new CTestClass; //Didn`t use system new operator!
        delete p;
    }
    
    cout << " Interval = " << GetTickCount()-count << " ms" << endl;
    
    return 0;
}
In my computer, the result is:

Interval = 391 ms

As you see, the later is about twenty times faster than the former! What is cause? Because system call new/delete spent much time of former program! Of course, this is an extreme example! Anyway, we can know the value of memory pool from previous code!

[2]To avoid memory`s fragment. It`s regretting, I haven`t simple and good example to prove the conclusion. I reached the conclusion from some book and theory!

Note that memory pool just is valuable when program use memory with system call malloc/free or new/delete frequently. Otherwise, you needn`t use it.

Implememtation

Now, we pay attention to how implement memory pool. I believe memory pool include three element at least.

[1]We need a big memory block. Where do we get it? OS can provide memory block for us from stack, heap, global data section and so on. Perhaps, we also get memory block from mapping file for memory pool; I didn`t tested the method and don`t know the result! Usually, we get the block from heap, which is good and convenient way.

[2] We need an algorithm to allocate memory unit to client code from memory block. It isn`t an easy problem! Many operating system textbook introduce it in detail. Much implementation of memory pool is that we divide memory block into same size unit usually.

[3] We need an algorithm to free memory unit from client code. The problem is associated with the second point.

Here, I`ll show an example which is an implementation of memory pool:

#ifndef __MEMPOOL_H__
#define __MEMPOOL_H__
                                          
class CMemPool
{
private:
    //The purpose of the structure`s definition is that we can operate linkedlist conveniently
    struct _Unit                     //The type of the node of linkedlist.
    {
        struct _Unit *pPrev, *pNext;
    };

    void* m_pMemBlock;                //The address of memory pool.

    //Manage all unit with two linkedlist.
    struct _Unit*    m_pAllocatedMemBlock; //Head pointer to Allocated linkedlist.
    struct _Unit*    m_pFreeMemBlock;      //Head pointer to Free linkedlist.

    unsigned long    m_ulUnitSize; //Memory unit size. There are much unit in memory pool.
    unsigned long    m_ulBlockSize;//Memory pool size. Memory pool is make of memory unit.

public:
    CMemPool(unsigned long lUnitNum = 50, unsigned long lUnitSize = 1024);
    ~CMemPool();
    
    void* Alloc(unsigned long ulSize, bool bUseMemPool = true); //Allocate memory unit
    void Free( void* p );                                   //Free memory unit
};

#endif //__MEMPOOL_H__

There is a picture which could help you understand the class. MemoryPoolSorceCode
From the picture, we can know that m_pMemBlock point to a memory block and the memory block be divided into many memory unit which have same size. All memory units be managed by double linked list. Why do we need double linked list to manage memory unit? The answer is that this way assure the effect of function Alloc(…) and Free() is O(1)! There are two double linked list; the first one which is pointed by m_pFreeMemBlock is make up of all free unit, and the second which is pointed by m_pAllocatedMemBlock is make up of all allocated unit. When generate an object of the class, the constructor CMemPool(…) will allocate a memory block from OS firstly then create a double linked list to manage all free unit. Please note that it is a static double linked list. So we needn`t free each node of linked list in ~CMemPool() and just free the memory block which is pointed by m_pMemBlock. The job of function Alloc(…) is to get a node from “Free” linked list and to insert the node to “Allocated ” Linked list, then return an address to client code. The function Free() is a reverse process of function Alloc(…).

I will explain previous description according to the source code.

/*==========================================================
CMemPool:
    Constructor of this class. It allocate memory block from system and create
    a static double linked list to manage all memory unit.

Parameters:
    [in]ulUnitNum
    The number of unit which is a part of memory block.

    [in]ulUnitSize
    The size of unit.
//=========================================================
*/
CMemPool::CMemPool(unsigned long ulUnitNum,unsigned long ulUnitSize) :
    m_pMemBlock(NULL), m_pAllocatedMemBlock(NULL), m_pFreeMemBlock(NULL), 
    m_ulBlockSize(ulUnitNum * (ulUnitSize+sizeof(struct _Unit))), 
    m_ulUnitSize(ulUnitSize)
{    
    m_pMemBlock = malloc(m_ulBlockSize);     //Allocate a memory block.
    
    if(NULL != m_pMemBlock)
    {
        for(unsigned long i=0; i<ulUnitNum; i++)  //Link all mem unit . Create linked list.
        {
            struct _Unit *pCurUnit = (struct _Unit *)( (char *)m_pMemBlock + i*(ulUnitSize+sizeof(struct _Unit)) );
            
            pCurUnit->pPrev = NULL;
            pCurUnit->pNext = m_pFreeMemBlock;    //Insert the new unit at head.
            
            if(NULL != m_pFreeMemBlock)
            {
                m_pFreeMemBlock->pPrev = pCurUnit;
            }
            m_pFreeMemBlock = pCurUnit;
        }
    }    
} 


The chief task of function CMemPool(…) is create a static double linked list. There are some skills of pointer which may be hard to beginner. I just explain a statement “struct _Unit *pCurUnit = (struct _Unit *)( (char *)m_pMemBlock + i*(ulUnitSize+sizeof(struct _Unit)) )” ; the result is pCurUnit point to start address a memory unit, and the variable “i” in this statement represent which unit. If you didn`t master pointer, please refer to textbook.

/*===============================================================
~CMemPool():
    Destructor of this class. Its task is to free memory block.
//===============================================================
*/
CMemPool::~CMemPool()
{
    free(m_pMemBlock);
}
The function ~CMemPool(…) is easy to be understood. I will explain nothing.

/*================================================================
Alloc:
    To allocate a memory unit. If memory pool can`t provide proper memory unit,
    It will call system function.

Parameters:
    [in]ulSize
    Memory unit size.

    [in]bUseMemPool
    Whether use memory pool.

Return Values:
    Return a pointer to a memory unit.
//=================================================================
*/
void* CMemPool::Alloc(unsigned long ulSize, bool bUseMemPool)
{
    if(    ulSize > m_ulUnitSize || false == bUseMemPool || 
        NULL == m_pMemBlock   || NULL == m_pFreeMemBlock)
    {
        return malloc(ulSize);
    }

    //Now FreeList isn`t empty
    struct _Unit *pCurUnit = m_pFreeMemBlock;
    m_pFreeMemBlock = pCurUnit->pNext;            //Get a unit from free linkedlist.
    if(NULL != m_pFreeMemBlock)
    {
        m_pFreeMemBlock->pPrev = NULL;
    }

    pCurUnit->pNext = m_pAllocatedMemBlock;
    
    if(NULL != m_pAllocatedMemBlock)
    {
        m_pAllocatedMemBlock->pPrev = pCurUnit; 
    }
    m_pAllocatedMemBlock = pCurUnit;

    return (void *)((char *)pCurUnit + sizeof(struct _Unit) );
}
The chief task of function Alloc(…) is to move a unit from “Free linked list” to “Allocated linked list” and will return the address of ninth byte of a unit.

/*================================================================
Free:
    To free a memory unit. If the pointer of parameter point to a memory unit,
    then insert it to "Free linked list". Otherwise, call system function "free".

Parameters:
    [in]p
    It point to a memory unit and prepare to free it.

Return Values:
    none
//================================================================
*/
void CMemPool::Free( void* p )
{
    if(m_pMemBlock<p && p<(void *)((char *)m_pMemBlock + m_ulBlockSize) )
    {
        struct _Unit *pCurUnit = (struct _Unit *)((char *)p - sizeof(struct _Unit) );

        m_pAllocatedMemBlock = pCurUnit->pNext;
        if(NULL != m_pAllocatedMemBlock)
        {
            m_pAllocatedMemBlock->pPrev = NULL;
        }

        pCurUnit->pNext = m_pFreeMemBlock;
        if(NULL != m_pFreeMemBlock)
        {
             m_pFreeMemBlock->pPrev = pCurUnit;
        }

        m_pFreeMemBlock = pCurUnit;
    }
    else
    {
        free(p);
    }
}
The chief task of function Free() is to move a unit from “Allocated linked list” to “Free linked list”.

Using the memory pool

How to use the memory pool? In the one hand, you must define an object of CMemPool for instance g_MemPool at proper place. In the other hand, you need override new/delete operator of some class which prepare to use memory pool like previous example.

Test

The following picture is the result of my demo code in my computer.
Result_Data.JPG

The following chart is made according to previous result.

zbt.JPG

It`s obvious that the memory pool can improve the effect of a program which use system call new/delete or malloc/free frequently.

That`s off.

Thank you.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Jude Deng
Software Developer
China China
^_^

Comments and Discussions

 
QuestionThey are still faster on 2014 Pinmemberrxantos13-Feb-14 19:51 
GeneralMy vote of 5 Pinmemberjcyangzh5-Mar-13 18:54 
QuestionNice Pinmemberboyhailong21-Jan-13 5:56 
QuestionConfused! PinmemberMember 857608123-Mar-12 1:21 
QuestionJust need it.Thank you!! Pinmember小熊 from Beijing,Haidian20-Mar-12 21:48 
QuestionNice Article Pinmembermfwan24-Jun-11 21:13 
QuestionDo you have a chinese version of this? Pinmemberkoalaphoenix26-Oct-10 16:56 
QuestionIs m_pAllocatedMemBlock really needed? Pinmembercoldstar24-Jun-10 0:05 
AnswerRe: Is m_pAllocatedMemBlock really needed? PinmemberJude Deng21-Oct-10 5:20 
GeneralThanks PinmemberJune Deng23-Jul-08 16:16 
Generalmemory pool Pinmembersrinivaaaaaas16-Jul-08 20:45 
GeneralDanger of destructors + advice using mem pool. PinmemberDitlef Martens14-Jul-08 6:59 
Questiondynamical pool size? PinmemberStefan638-Jul-08 4:04 
GeneralThe test is not enough Pinmemberdanscort yu8-Jul-08 2:10 
GeneralRe: The test is not enough Pinmembersuxiaojack13-Jul-08 18:13 
QuestionHow long does your pool take Pinmembercmk4-Jul-08 8:41 
JokeDWORD Pinmemberjimbobmcgee4-Jul-08 1:53 
GeneralRe: DWORD PinmemberMaximilien4-Jul-08 6:57 
QuestionRe: DWORD PinmemberStefan638-Jul-08 4:06 
AnswerRe: DWORD Pinmemberjimbobmcgee8-Jul-08 5:04 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.1411022.1 | Last Updated 4 Jul 2008
Article Copyright 2008 by Jude Deng
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid