内存池(MemPool)技术详解 - 经典内存池

柔情只为你懂 2022-04-11 06:07 257阅读 0赞

转自  
\[url\]http://cplusplus.wikidot.com/cn:dive-into-memory-pool\[/url\]  
  
\[align=center\]\[b\]概述\[/b\]\[/align\]  
内存池（MemPool）技术备受推崇。我用google搜索了下，没有找到比较详细的原理性的文章，故此补充一个。另外，补充了boost::pool组件与经典MemPool的差异。同时也描述了MemPool在sgi-stl/stlport中的运用。  
  
  
\[align=center\]\[b\]经典的内存池技术\[/b\]\[/align\]  
经典的内存池（MemPool）技术，是一种用于分配大量大小相同的小对象的技术。通过该技术可以极大加快内存分配/释放过程。下面我们详细解释其中的奥妙。  
  
经典的内存池只涉及两个常量：MemBlockSize、ItemSize（小对象的大小，但不能小于指针的大小，在32位平台也就是不能小于4字节），以及两个指针变量MemBlockHeader、FreeNodeHeader。开始，这两个指针均为空。

class MemPool
    {
       
    private:
        const int m_nMemBlockSize;
        const int m_nItemSize;
    
        struct _FreeNode {
       
            _FreeNode* pPrev;
            BYTE data[m_nItemSize - sizeof(_FreeNode*)];
        };
    
        struct _MemBlock {
       
            _MemBlock* pPrev;
            _FreeNode data[m_nMemBlockSize/m_nItemSize];
        };
    
        _MemBlock* m_pMemBlockHeader;
        _FreeNode* m_pFreeNodeHeader;
    
    public:
       MemPool(int nItemSize, int nMemBlockSize = 2048)
           : m_nItemSize(nItemSize), m_nMemBlockSize(nMemBlockSize),
             m_pMemBlockHeader(NULL), m_pFreeNodeHeader(NULL)
       {
       
       }
    };

其中指针变量MemBlockHeader是把所有申请的内存块（MemBlock）串成一个链表，以便通过它可以释放所有申请的内存。FreeNodeHeader变量则是把所有自由内存结点（FreeNode）串成一个链。  
  
这段话涉及两个关键概念：\[color=red\]内存块（MemBlock）\[/color\]和\[color=red\]自由内存结点（FreeNode）\[/color\]。内存块大小一般固定为MemBlockSize字节（除去用以建立链表的指针外）。内存块在申请之初就被划分为多个内存结点（Node）1，每个Node大小为ItemSize（小对象的大小），计MemBlockSize/ItemSize个。这MemBlockSize/ItemSize个内存结点刚开始全部是自由的，他们被串成链表。我们看看申请/释放内存过程，就很容易明白这样做的目的。  
  
\[align=center\]\[b\]申请内存过程\[/b\]\[/align\]  
代码如下：

void* MemPool::malloc()    // 没有参数
    {
       
        if (m_pFreeNodeHeader == NULL)
        {
       
           const int nCount = m_nMemBlockSize/m_nItemSize;
            _MemBlock* pNewBlock = new _MemBlock;
            pNewBlock->data[0].pPrev = NULL;
            for (int i = 1; i < nCount; ++i)
                pNewBlock->data[i].pPrev = &pNewBlock->data[i-1];
            m_pFreeNodeHeader = &pNewBlock->data[nCount-1];
            pNewBlock->pPrev = m_pMemBlock;
            m_pMemBlock = pNewBlock;
        }
        void* pFreeNode = m_pFreeNodeHeader;
        m_pFreeNodeHeader = m_pFreeNodeHeader->pPrev;
        return pFreeNode;
    }

内存申请过程分为两种情况：  
  
在自由内存结点链表（FreeNodeList）非空。在此情况下，Alloc过程只是从链表中摘下一个结点的过程。  
否则，意味着需要一个新的内存块(MemBlock)。这个过程需要将新申请的MemBlock切割成多个Node，并把它们串起来，MemPool技术的开销主要在这。  
  
  
\[align=center\]\[b\]释放内存过程\[/b\]\[/align\]  
  
代码如下：

void MemPool::free(void* p)
    {
       
        _FreeNode* pNode = (_FreeNode*)p;
        pNode->pPrev = m_pFreeNodeHeader;
        m_pFreeNodeHeader = pNode;
    }

释放过程极其简单，只是把要释放的结点挂到自由内存链表（FreeNodeList）的开头即可。  
  
\[align=center\]\[b\]性能分析\[/b\]\[/align\]  
  
MemPool技术申请内存/释放内存均极其快（比AutoFreeAlloc慢）。其内存分配过程多数情况下复杂度为O(1)，主要开销在FreeNodeList为空需要生成新的MemBlock时。内存释放过程复杂度为O(1)。  
  
\[b\]boost::pool\[/b\]  
boost::pool是内存池技术的变种。主要的变化如下：  
  
MemBlock改为非固定长度(MemBlockSize)，而是：第1次申请时m\_nItemSize\*32，第2次申请时 m\_nItemSize\*64，第3次申请时m\_nItemSize\*128，以此类推。不采用固定的MemBlockSize，而采用这种做法预测模型2，是一个细节上的改良。  
增加了ordered\_free(void\* p) 函数。ordered\_free区别于free的是，free把要释放的结点挂到自由内存链表（FreeNodeList）的开头， ordered\_free则假设FreeNodeList是有序的，因此会遍历FreeNodeList把要释放的结点插入到合适的位置。我们已经看到，free的复杂度是O(1)，非常快。但请注意ordered\_free是比较费的操作，其复杂度是O(N)。这里N是FreeNodeList的大小。对于一个频繁释放/申请的系统，这个N很可能是个大数。这个boost描述得很清楚：http://www.boost.org/libs/pool/doc/interfaces/pool.html  
注意：不要认为boost提供ordered\_free是多此一举。后文我们会在讨论boost::object\_pool时解释这一点。  
  
  
\[align=center\]\[b\]基于内存池技术的通用内存分配组件\[/b\]\[/align\]  
\[size=medium\]\[color=red\]SGI STL把内存池（MemPool）技术进行发扬光大，用它来实现其最根本的allocator。  
  
其大体的思想是，建立16个MemPool，<=8字节的内存申请由0号MemPool分配，<=16字节的内存申请由1号 MemPool分配，<=24字节的内存有2号MemPool分配，以此类推。最后，>128字节的内存申请由普通的malloc分配。\[/color\]\[/size\]  
  
\[align=center\]\[b\]内存池技术的缺陷\[/b\]\[/align\]  
遗憾的是，MemPool技术可能导致内存占用只增不减。还没有非常有效的办法去避免这种情况的发生。不过我后来在ScopeAlloc的实现中发现BlockPool（是一个简化版的内存池）反倒避免了这一缺陷。  
  
\[align=center\]\[b\]注意\[/b\]\[/align\]  
以上代码属于伪代码（struct \_FreeNode、\_MemBlock编译通不过），并且去除了出错处理。  
  
\[b\]Footnotes\[/b\]  
1. boost:pool/object\_pool 中称之为块（Chunk）。  
2. 是的，这是一种用户内存需求的预测模型，其实std::vector的内存增长亦采用了该模型。