woaidongmao

內(nèi)存池（MemPool）技術(shù)備受推崇。我用google搜索了下，沒(méi)有找到比較詳細(xì)的原理性的文章，故此補(bǔ)充一個(gè)。另外，補(bǔ)充了boost::pool組件與經(jīng)典MemPool的差異。同時(shí)也描述了MemPool在sgi-stl/stlport中的運(yùn)用。

經(jīng)典的內(nèi)存池技術(shù)

經(jīng)典的內(nèi)存池（MemPool）技術(shù)，是一種用于分配大量大小相同的小對(duì)象的技術(shù)。通過(guò)該技術(shù)可以極大加快內(nèi)存分配/釋放過(guò)程。下面我們?cè)敿?xì)解釋其中的奧妙。

經(jīng)典的內(nèi)存池只涉及兩個(gè)常量：MemBlockSize、ItemSize（小對(duì)象的大小，但不能小于指針的大小，在32位平臺(tái)也就是不能小于4字節(jié)），以及兩個(gè)指針變量MemBlockHeader、FreeNodeHeader。開(kāi)始，這兩個(gè)指針均為空。

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是把所有申請(qǐng)的內(nèi)存塊（MemBlock）串成一個(gè)鏈表，以便通過(guò)它可以釋放所有申請(qǐng)的內(nèi)存。FreeNodeHeader變量則是把所有自由內(nèi)存結(jié)點(diǎn)（FreeNode）串成一個(gè)鏈。

這段話(huà)涉及兩個(gè)關(guān)鍵概念：內(nèi)存塊（MemBlock）和自由內(nèi)存結(jié)點(diǎn)（FreeNode）。內(nèi)存塊大小一般固定為MemBlockSize字節(jié)（除去用以建立鏈表的指針外）。內(nèi)存塊在申請(qǐng)之初就被劃分為多個(gè)內(nèi)存結(jié)點(diǎn)（Node）¹，每個(gè)Node大小為ItemSize（小對(duì)象的大?。?jì)MemBlockSize/ItemSize個(gè)。這MemBlockSize/ItemSize個(gè)內(nèi)存結(jié)點(diǎn)剛開(kāi)始全部是自由的，他們被串成鏈表。我們看看申請(qǐng)/釋放內(nèi)存過(guò)程，就很容易明白這樣做的目的。

申請(qǐng)內(nèi)存過(guò)程

代碼如下：

void* MemPool::malloc()    // 沒(méi)有參數(shù)
{
    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;
}

內(nèi)存申請(qǐng)過(guò)程分為兩種情況：

1. 在自由內(nèi)存結(jié)點(diǎn)鏈表（FreeNodeList）非空。在此情況下，Alloc過(guò)程只是從鏈表中摘下一個(gè)結(jié)點(diǎn)的過(guò)程。
2. 否則，意味著需要一個(gè)新的內(nèi)存塊(MemBlock)。這個(gè)過(guò)程需要將新申請(qǐng)的MemBlock切割成多個(gè)Node，并把它們串起來(lái)，MemPool技術(shù)的開(kāi)銷(xiāo)主要在這。

釋放內(nèi)存過(guò)程

代碼如下：

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

釋放過(guò)程極其簡(jiǎn)單，只是把要釋放的結(jié)點(diǎn)掛到自由內(nèi)存鏈表（FreeNodeList）的開(kāi)頭即可。

性能分析

MemPool技術(shù)申請(qǐng)內(nèi)存/釋放內(nèi)存均極其快（比AutoFreeAlloc慢）。其內(nèi)存分配過(guò)程多數(shù)情況下復(fù)雜度為O(1)，主要開(kāi)銷(xiāo)在FreeNodeList為空需要生成新的MemBlock時(shí)。內(nèi)存釋放過(guò)程復(fù)雜度為O(1)。

boost::pool

boost::pool是內(nèi)存池技術(shù)的變種。主要的變化如下：

1. MemBlock改為非固定長(zhǎng)度(MemBlockSize)，而是：第1次申請(qǐng)時(shí)m_nItemSize*32，第2次申請(qǐng)時(shí) m_nItemSize*64，第3次申請(qǐng)時(shí)m_nItemSize*128，以此類(lèi)推。不采用固定的MemBlockSize，而采用這種做法預(yù)測(cè)模型²，是一個(gè)細(xì)節(jié)上的改良。
2. 增加了ordered_free(void* p) 函數(shù)。ordered_free區(qū)別于free的是，free把要釋放的結(jié)點(diǎn)掛到自由內(nèi)存鏈表（FreeNodeList）的開(kāi)頭， ordered_free則假設(shè)FreeNodeList是有序的，因此會(huì)遍歷FreeNodeList把要釋放的結(jié)點(diǎn)插入到合適的位置。我們已經(jīng)看到，free的復(fù)雜度是O(1)，非?？?。但請(qǐng)注意ordered_free是比較費(fèi)的操作，其復(fù)雜度是O(N)。這里N是FreeNodeList的大小。對(duì)于一個(gè)頻繁釋放/申請(qǐng)的系統(tǒng)，這個(gè)N很可能是個(gè)大數(shù)。這個(gè)boost描述得很清楚：http://www.boost.org/libs/pool/doc/interfaces/pool.html

注意：不要認(rèn)為boost提供ordered_free是多此一舉。后文我們會(huì)在討論boost::object_pool時(shí)解釋這一點(diǎn)。

基于內(nèi)存池技術(shù)的通用內(nèi)存分配組件

SGI STL把內(nèi)存池（MemPool）技術(shù)進(jìn)行發(fā)揚(yáng)光大，用它來(lái)實(shí)現(xiàn)其最根本的allocator。

其大體的思想是，建立16個(gè)MemPool，<=8字節(jié)的內(nèi)存申請(qǐng)由0號(hào)MemPool分配，<=16字節(jié)的內(nèi)存申請(qǐng)由1號(hào) MemPool分配，<=24字節(jié)的內(nèi)存有2號(hào)MemPool分配，以此類(lèi)推。最后，>128字節(jié)的內(nèi)存申請(qǐng)由普通的malloc分配。

內(nèi)存池技術(shù)的缺陷

遺憾的是，MemPool技術(shù)可能導(dǎo)致內(nèi)存占用只增不減。還沒(méi)有非常有效的辦法去避免這種情況的發(fā)生。不過(guò)我后來(lái)在ScopeAlloc的實(shí)現(xiàn)中發(fā)現(xiàn)BlockPool（是一個(gè)簡(jiǎn)化版的內(nèi)存池）反倒避免了這一缺陷。

注意

以上代碼屬于偽代碼（struct _FreeNode、_MemBlock編譯通不過(guò)），并且去除了出錯(cuò)處理。

Footnotes

1. boost:pool/object_pool 中稱(chēng)之為塊（Chunk）。

2. 是的，這是一種用戶(hù)內(nèi)存需求的預(yù)測(cè)模型，其實(shí)std::vector的內(nèi)存增長(zhǎng)亦采用了該模型。