天天看點

記憶體池(MemPool)技術詳解概述經典的記憶體池技術boost::pool基于記憶體池技術的通用記憶體配置設定元件 注意

概述

記憶體池(MemPool)技術備受推崇。我用google搜尋了下,沒有找到比較詳細的原理性的文章,故此補充一個。另外,補充了boost::pool元件與經典MemPool的差異。同時也描述了MemPool在sgi-stl/stlport中的運用。

經典的記憶體池技術

經典的記憶體池(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)串成一個鍊。

這段話涉及兩個關鍵概念:記憶體塊(MemBlock)和自由記憶體結點(FreeNode)。記憶體塊大小一般固定為MemBlockSize位元組(除去用以建立連結清單的指針外)。記憶體塊在申請之初就被劃分為多個記憶體結點(Node),每個Node大小為ItemSize(小對象的大小),計MemBlockSize/ItemSize個。這MemBlockSize/ItemSize個記憶體結點剛開始全部是自由的,他們被串成連結清單。我們看看申請/釋放記憶體過程,就很容易明白這樣做的目的。

申請記憶體過程

代碼如下:

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技術的開銷主要在這。

釋放記憶體過程

代碼如下:

void MemPool::free(void* p)

{

       _FreeNode* pNode = (_FreeNode*)p;

       pNode->pPrev = m_pFreeNodeHeader;

       m_pFreeNodeHeader = pNode;

}

釋放過程極其簡單,隻是把要釋放的結點挂到自由記憶體連結清單(FreeNodeList)的開頭即可。

性能分析

MemPool技術申請記憶體/釋放記憶體均極其快(比AutoFreeAlloc慢)。其記憶體配置設定過程多數情況下複雜度為O(1),主要開銷在FreeNodeList為空需要生成新的MemBlock時。記憶體釋放過程複雜度為O(1)。

boost::pool

boost::pool是記憶體池技術的變種。主要的變化如下:

  • MemBlock改為非固定長度(MemBlockSize),而是:第1次申請時m_nItemSize*32,第2次申請時m_nItemSize*64,第3次申請時m_nItemSize*128,以此類推。不采用固定的MemBlockSize,而采用這種做法預測模型(是的,這是一種使用者記憶體需求的預測模型,其實std::vector的記憶體增長亦采用了該模型),是一個細節上的改良。
  • 增加了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時解釋這一點。

基于記憶體池技術的通用記憶體配置設定元件

sgi-stl把記憶體池(MemPool)技術進行發揚光大,用它來實作其最根本的allocator。

其大體的思想是,建立16個MemPool,<=8位元組的記憶體申請由0号MemPool配置設定,<=16位元組的記憶體申請由1号MemPool配置設定,<=24位元組的記憶體有2号MemPool配置設定,以此類推。最後,>128位元組的記憶體申請由普通的malloc配置設定。

注意

以上代碼屬于僞代碼(struct _FreeNode、_MemBlock編譯通不過),并且去除了出錯處理