内存池实现

发布于 2025-09-26  640 次阅读

项目地址:daoxiang0520/MemoryPool

一.前言

大一刚开学，没什么事情干，随便找点东西写写学学看

emmm原有一个伟大的愿景，想玩个大的，但是越探索越觉得水深

有预感会半途而废，学多少是多少好了

当然如果能完成那再发欸嘿嘿嘿，现在发多少有点立了flag了

稍微写个小笔记吧。

二.原理

说回来，众所周知C++分配内存用的是new与delete，C老一点是malloc和free

然而在代码实现的时候，有可能多次分配内存

于是天天买生活用品我们受够了，决定不买散装的，直接买一个月的

就是类似于如此

三.架构与思路

如图，大致的结构就是如此，其中MemoryBlock就是我们想要的内存块，即内存单位；MemoryPool负责内存单元的管理和分配。为了实现动态增删，我们使用链表结构来储存MemoryBlock。若已分配\创建的内存单位不足，可随时增添；删除虽然麻烦点，但这个结构也是最适合内存处理的，（也许）后面会涉及。

四.实现

（1）MemoryPage

现在我们一部分一部分考虑，先从MemoryPage说起

如上图，我们创建一个MemoryPage类

class MemoryPage{

    public:

        int nSize;

        int nFree;

        int nFirst;

        void* operator new(size_t,int Unitsize,int Unitnum);

        void operator delete(void* pBlock);

        MemoryPage(int Unitsize,int Unitnum);

        ~MemoryPage(){};

        MemoryPage* pNext;

        char aData[1];

};

其中

  • nSize用于记录总大小
  • nFree用于记录剩余空闲空间
  • *pNext记录链表下一位
  • aData用于记录内存单元可用初始指针，这个用了C99一个很骚的特性，不理解先看着结构即可

构造函数(与new的重载)中

  • Unitsize:内存单元大小
  • Unitnum:内存单元数量

在构造函数时要注意内存对齐问题，这个问题会在MemoryPool类得到处理(处理Unitsize大小)

ok，现在从构造函数说起

A.MemoryPage(int Unitsize,int Unitnum);

MemoryPage::MemoryPage(int Unitsize,int Unitnum):

            nSize(Unitsize*Unitnum),

            nFree(Unitnum-1),

            pNext(NULL),

            nFirst(1)

        {

            char* pData=aData;

            for(int i=1;i<Unitnum-1;i++){

                *(unsigned short*)pData=i;

                pData+=Unitsize;

            }

        };

1.初始化:内存页构造完成后将总大小(nSize)设定为Unitsize*Unitnum,即单元大小*单元数量;

nFree设定为Unitnum-1(由于第一个单元已被aData征用)

pNext自然是NULL

nFirst用于记录内存的首位，初始为1

接下来是对aData的解释:

灵活数组成员(Flexible Array Member),一个C99标准中引入的骚东西。该特性允许在结构体中存放一个零长数组(此处长度为1，所以占用一部分内存，nFree=Unitnum-1)，要求是该数组必须存放在结构体的最后一个成员，此时该数组可作为正常指针使用，可容纳任意数量的数据(只要你分配了内存)

看到好处没有？我们在编写之前一大难题就是，未分配的内存向系统申请后就这样放着吗？又该怎么访问并存储数据呢？

aData给出了答案，分配内存后，从头指针aData本身便可追溯到指定的内存地址。通过aData+Unitsize+所在的序号即可

那么赋值i又是为什么呢？此处我们用内存存储前两字节(short类型占两字节，范围0~65536)来存储序号，则我们能顺着链表找到我们想要的那块，而nFirst则是标明下一个空闲内存页的序号，方便访问和分配。于是我们完成了MemoryPage的构造。

B.new/delete的重载

void* MemoryPage::operator new(size_t,int Unitsize,int Unitnum){

    return ::operator new(sizeof(MemoryPage)+Unitnum*Unitsize);

}void MemoryPage::operator delete(void* pBlock){

    ::operator delete(pBlock);

}

delete操作直接调用原来的delete即可

而new的重载则考虑所需的内存空间大小即sizeofof(MemoryPage)+Unitnum*Unitsize，即给MemoryPage内成员开好空间，接着继续开Unitnum*Unitsize的内存空间，这些空间的存储地址以aData指针为首位，进而继续有Unitnum*Unitsize空间的池容量

到这里，MemoryPage便构建完成

（2）MemoryPool

class MemoryPool{

    public:

        MemoryPool(int Unit,int Init=256,int Grow=1024);

        ~MemoryPool();

        void* Allocate();

        void Free(void* pFree);

    private:

        int Unitsize;

        int Initsize;

        int Growsize;

        MemoryPage* pBlock;

};

接下来是MemoryPool类

MemoryPool作为一个链表头来访问管理和分配MemoryPage，以实现内存分配

其中Unitsize仍然是内存单元大小，Initsize是初始内存数，Growsize是增长的内存数，pBlock存储内存块链表头，Allocate与Free则是内存分配与释放。

A.MemoryPool(int Unit,int Init=256,int Grow=1024);

MemoryPool::MemoryPool(int Unit,int Init,int Grow):

    Unitsize(Unit),

    Initsize(Init),

    Growsize(Grow),

    pBlock(NULL)

{

    if(Unit>4)Unitsize=(Unit+7)&~7;

    else if(Unit>2)Unitsize=4;

    else Unitsize=2;

}

按理来说MemoryPool构造没什么好讲的，初始化参数即可，但偏偏有一个很影响功能的问题

内存对齐

为什么要内存对齐

  1. 平台原因(移植原因)：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
  2. 性能原因：数据结构(尤其是栈)应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。
  • 假如没有内存对齐机制，数据可以任意存放，现在一个int变量存放在从地址1开始的联系四个字节地址中，该处理器去取数据时，要先从0地址开始读取第一个4字节块,剔除不想要的字节（0地址）,然后从地址4开始读取下一个4字节块,同样剔除不要的数据（5，6，7地址）,最后留下的两块数据合并放入寄存器。这需要做很多工作。
  • 现在有了内存对齐的，int类型数据只能存放在按照对齐规则的内存中，比如说0地址开始的内存。那么现在该处理器在取数据时一次性就能将数据读出来了，而且不需要做额外的操作，提高了效率。

此处同样如此

那么如何对齐呢？仔细一想，存储时内存大小由我们决定，要使内存存储在对应的的系统内存上，只需要对内存大小进行一些小处理，也就是让其存储与4/8等2次幂的倍数上。于是有这一条

  • if(Unit>4)Unitsize=(Unit+7)&~7;

即将Unitsize提升到8的倍数

但为什么小于等于4时也需处理呢？

避免浪费

譬如一个长度为3的空间需求，若按8的倍数需要分配8的内存，此时有67.5%的内存被浪费了

于是此时我们分情况对齐内存即可。

B.MemoryPool::~MemoryPool()

MemoryPool::~MemoryPool(){

    MemoryPage* tmp=pBlock;

    while(tmp!=NULL){

        MemoryPage* Del=tmp;

        tmp=tmp->pNext;

        delete(Del);

    }

}

很好理解，遍历链表，一一删除释放即可

C.void* MemoryPool::Allocate()

void* MemoryPool::Allocate(){

    if(pBlock==NULL){

        pBlock=(MemoryPage*)new(Unitsize,Initsize) MemoryPage(Unitsize,Initsize);

        return pBlock->aData;

    }MemoryPage* tmp=pBlock;

    while(!tmp->nFree)tmp=tmp->pNext;

    if(tmp==NULL){

        if(Growsize==0)return NULL;

        tmp->pNext=(MemoryPage*)new(Unitsize,Growsize) MemoryPage(Unitsize,Growsize);

        tmp=tmp->pNext;

        return (void*)tmp->aData;

    }tmp->nFree--;

    char* ptmp=tmp->aData+tmp->nFirst*Unitsize;

    tmp->nFirst=*ptmp;

    return (void*)ptmp;

}

对于分配的解释会冗长一点

首次分配时先为pBlock分配初始内存同时调用构造函数，再将首地址返回

若是再次分配，则遍历链表，找到空闲单元（nFree>0），并根据nFirst返回可用的内存指针，然后对nfirst等进行处理

若是nFree=0,那就需要新开一个单元，根据Growsize内存数新分配单元再返回首地址即可访问，最后返回的是void*指针

D.void MemoryPool::Free(void* pFree)

void MemoryPool::Free(void* pFree){

    MemoryPage* ptmp=pBlock;

    MemoryPage* pre=NULL;

    while(ptmp!=NULL&&(ptmp->aData>pFree||ptmp->aData+ptmp->nSize<pFree)){

        pre=ptmp;

        ptmp=ptmp->pNext;

    }if(ptmp==NULL){

        throw "404";

        return;

    }*(int*)pFree=ptmp->nFirst;

    ptmp->nFirst=((char*)pFree-ptmp->aData)/Unitsize;

    ptmp->nFree++;

    if(ptmp->nFree==ptmp->nSize/Unitsize){

        if(pre==NULL)pBlock=ptmp->pNext;

        else pre->pNext=ptmp->pNext;

        delete ptmp;

    }else{

        pre->pNext=ptmp->pNext;

        ptmp->pNext=pBlock->pNext;

        pBlock=ptmp;

    }

}

接着是释放内存

Free函数获取一个已分配的指针，接下来去找到指针所属的内存单元，找不到就抛出异常，接着考虑释放该内存此时要做一个判断

  • 若是该内存单元所有内存全部清空，则将该内存单元释放清空
  • 若是去除后仍有内存单元，则将nFirst改变，并将该内存单元移动至链表头部（其实没什么必要），然后继续运作

五.改进的可能

首先就是MemoryPage可能能够通过内存对齐提升性能，AI说的不大清楚，其实MemoryPool的内存对齐应该已经够了

其次便是MemoryPage，注意到了吗，该内存池实际上是个定长内存池，即每个内存单元的长度统一且固定，感兴趣的可以了解一下变长内存池，这类内存池能够根据需求变化内存单元大小

okk，完结撒花

拥抱大地，展望天空