为什么使用内存池以及如何实现它

下载 MemoryPoolSourceCode.zip - 21.82 KB

简介

什么是内存池？我认为我首先必须回答这个问题，因为它对初学者很重要。简而言之，内存池是您从系统获取的一个内存块，并使用其中的一部分单位来替换系统调用 malloc/free 和 new/delete。这项技术的好处在于重用现有的内存块，从而减少系统调用的次数。定义一个精确的定义是一项艰巨的任务。如果您仍然无法理解这个概念，请谷歌搜索。

背景

为什么使用内存池？我有两个原因：[1] 缩短程序分配内存的时间。现在我举一个例子来证明这项技术具有良好的效率。

#include <windows.h>
#include <iostream.h>

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;
} 

在我的电脑上（Intel 3.0G Hz CPU / 512 MB RAM / Win XP SP2 / VC6.0），结果是

当我使用一个简单的内存池时，代码如下

#include <windows.h>
#include <iostream.h>

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;
}

您可以看到，后者比前者快了大约二十倍！原因是什么？因为系统调用 new/delete 占用了前一个程序很多时间！当然，这是一个极端的例子！无论如何，我们可以从前面的代码中了解到内存池的价值！

[2] 避免内存碎片。遗憾的是，我还没有一个简单而好的例子来证明这个结论。我从一些书籍和理论中得出了这个结论！

请注意，只有当程序频繁使用系统调用 malloc/free 或 new/delete 时，内存池才具有价值。否则，您就不需要使用它。

实现

现在，我们来关注如何实现内存池。我相信内存池至少包含三个要素。

[1] 我们需要一个大的内存块。我们从哪里获得它？操作系统可以从栈、堆、全局数据段等地方为我们提供内存块。也许，我们也可以从映射文件中获取内存块用于内存池；我没有测试过这种方法，也不知道结果！通常，我们从堆中获取内存块，这是一种良好且方便的方法。

[2] 我们需要一种算法，从内存块中将内存单元分配给客户端代码。这不是一个简单的问题！许多操作系统教科书对此进行了详细介绍。内存池的许多实现是将内存块划分为相同大小的单元。

[3] 我们需要一种算法，将内存单元从客户端代码中释放。这个问题与第二点有关。

在这里，我将展示一个内存池的实现示例

#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__

有一张图片可以帮助您理解这个类。
从图片可以看出，m_pMemBlock 指向一个内存块，该内存块被划分为许多相同大小的内存单元。所有内存单元都由双向链表管理。为什么我们需要双向链表来管理内存单元？答案是，这种方式可以确保 Alloc(...) 和 Free() 函数的效率是 O(1)！有两个双向链表；第一个由 m_pFreeMemBlock 指向，由所有空闲单元组成，第二个由 m_pAllocatedMemBlock 指向，由所有已分配单元组成。当创建一个类的对象时，构造函数 CMemPool(...) 将首先从操作系统分配一个内存块，然后创建一个双向链表来管理所有空闲单元。请注意，这是一个静态双向链表。因此，我们不需要在 ~CMemPool() 中释放链表的每个节点，只需释放 m_pMemBlock 指向的内存块。Alloc(...) 函数的工作是从“空闲”链表中获取一个节点并将其插入到“已分配”链表中，然后将地址返回给客户端代码。Free() 函数是 Alloc(...) 函数的反向过程。

我将根据源代码解释之前的描述。

/*==========================================================
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;
        }
    }    
} 

函数 CMemPool(...) 的主要任务是创建一个静态双向链表。其中有一些指针技巧，对初学者来说可能有点难。我只解释一个语句“struct _Unit *pCurUnit = (struct _Unit *)( (char *)m_pMemBlock + i*(ulUnitSize+sizeof(struct _Unit)) )”；结果是 pCurUnit 指向一个内存单元的起始地址，“i”变量在这个语句中表示哪个单元。如果您还没有掌握指针，请参考教科书。

/*===============================================================
~CMemPool():
    Destructor of this class. Its task is to free memory block.
//===============================================================
*/
CMemPool::~CMemPool()
{
    free(m_pMemBlock);
}

/*================================================================
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) );
}

/*================================================================
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);
    }
}