轉(zhuǎn)載聲明：本文轉(zhuǎn)自csdn博客，許式偉著，鏈接：http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx?
小狼注：上次也寫了一個(gè)簡單的內(nèi)存池，是使用STL的deque來管理的，實(shí)現(xiàn)起來比較簡單，不過有個(gè)缺點(diǎn)就是只能固定分配大小，所以需要根據(jù)經(jīng)驗(yàn)值事先分配內(nèi)存大小，然后把內(nèi)存再次劃分為等大的小的內(nèi)存供使用。
概述
內(nèi)存池（MemPool）技術(shù)備受推崇。我用google搜索了下，沒有找到比較詳細(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ù)。通過該技術(shù)可以極大加快內(nèi)存分配/釋放過程。下面我們詳細(xì)解釋其中的奧妙。
?
經(jīng)典的內(nèi)存池只涉及兩個(gè)常量：MemBlockSize、ItemSize（小對(duì)象的大小，但不能小于指針的大小，在32位平臺(tái)也就是不能小于4字節(jié)），以及兩個(gè)指針變量MemBlockHeader、FreeNodeHeader。開始，這兩個(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是把所有申請的內(nèi)存塊（MemBlock）串成一個(gè)鏈表，以便通過它可以釋放所有申請的內(nèi)存。FreeNodeHeader變量則是把所有自由內(nèi)存結(jié)點(diǎn)（FreeNode）串成一個(gè)鏈。
?
這
段話涉及兩個(gè)關(guān)鍵概念：內(nèi)存塊（MemBlock）和自由內(nèi)存結(jié)點(diǎn)（FreeNode）。內(nèi)存塊大小一般固定為MemBlockSize字節(jié)（除去用以建
立鏈表的指針外）。內(nèi)存塊在申請之初就被劃分為多個(gè)內(nèi)存結(jié)點(diǎn)（Node），每個(gè)Node大小為?ItemSize（小對(duì)象的大小），計(jì)
MemBlockSize/ItemSize個(gè)。這MemBlockSize/ItemSize個(gè)內(nèi)存結(jié)點(diǎn)剛開始全部是自由的，他們被串成鏈表。我們看看
申請/釋放內(nèi)存過程，就很容易明白這樣做的目的。
?
申請內(nèi)存過程
代碼如下：
void*?MemPool::malloc()????//?沒有參數(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)存申請過程分為兩種情況：
????*?在自由內(nèi)存結(jié)點(diǎn)鏈表（FreeNodeList）非空。
??????在此情況下，Alloc過程只是從鏈表中摘下一個(gè)結(jié)點(diǎn)的過程。
???????
????*?否則，意味著需要一個(gè)新的內(nèi)存塊(MemBlock)。
??????這個(gè)過程需要將新申請的MemBlock切割成多個(gè)Node，并把它們串起來。
??????MemPool技術(shù)的開銷主要在這。
????????
釋放內(nèi)存過程
?代碼如下：
void?MemPool::free(void*?p)
{
????_FreeNode*?pNode?=?(_FreeNode*)p;
????pNode->pPrev?=?m_pFreeNodeHeader;
????m_pFreeNodeHeader?=?pNode;
}
?
釋放過程極其簡單，只是把要釋放的結(jié)點(diǎn)掛到自由內(nèi)存鏈表（FreeNodeList）的開頭即可。
?
性能分析
MemPool技術(shù)申請內(nèi)存/釋放內(nèi)存均極其快（比AutoFreeAlloc慢）。其內(nèi)存分配過程多數(shù)情況下復(fù)雜度為O(1)，主要開銷在FreeNodeList為空需要生成新的MemBlock時(shí)。內(nèi)存釋放過程復(fù)雜度為O(1)。
?
?
boost::pool
boost::pool是內(nèi)存池技術(shù)的變種。主要的變化如下：
?
???*?MemBlock改為非固定長度(MemBlockSize)，而是：第1次申請時(shí)
m_nItemSize*32，第2次申請時(shí)?m_nItemSize*64，第3次申請時(shí)m_nItemSize*128，以此類推。不采用
固定的MemBlockSize，而采用這種做法預(yù)測模型（是的，這是一種用戶內(nèi)存需求的預(yù)測模型，其實(shí)std::vector的內(nèi)存增長亦采用了該模
型），是一個(gè)細(xì)節(jié)上的改良。
???????
????*?增加了ordered_free(void*?p)?函數(shù)。
?
?????ordered_free區(qū)別于free的是，free把要釋放的結(jié)點(diǎn)掛到自由內(nèi)存鏈表
（FreeNodeList）的開頭，ordered_free則假設(shè)FreeNodeList是有序的，因此會(huì)遍歷FreeNodeList把要釋放的
結(jié)點(diǎn)插入到合適的位置。
??????我們已經(jīng)看到，free的復(fù)雜度是O
(1)，非常快。但請注意ordered_free是比較費(fèi)的操作，其復(fù)雜度是O(N)。這里N是FreeNodeList的大小。對(duì)于一個(gè)頻繁釋放/申
請的系統(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)光大，用它來實(shí)現(xiàn)其最根本的allocator。
?
其
大體的思想是，建立16個(gè)MemPool，<=8字節(jié)的內(nèi)存申請由0號(hào)MemPool分配，<=16字節(jié)的內(nèi)存申請由1號(hào)?
MemPool分配，<=24字節(jié)的內(nèi)存有2號(hào)MemPool分配，以此類推。最后，>128字節(jié)的內(nèi)存申請由普通的malloc分配。
注意
以上代碼屬于偽代碼（struct?_FreeNode、_MemBlock編譯通不過），并且去除了出錯(cuò)處理。