概述
內存池（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）1，每個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，而采用這種做法預測模型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時解釋這一點。
基于內存池技術的通用內存分配組件
SGI STL把內存池（MemPool）技術進行發揚光大，用它來實現其最根本的allocator。
其大體的思想是，建立16個MemPool，<=8字節的內存申請由0號MemPool分配，<=16字節的內存申請由1號 MemPool分配，<=24字節的內存有2號MemPool分配，以此類推。最后，>128字節的內存申請由普通的malloc分配。
內存池技術的缺陷
遺憾的是，MemPool技術可能導致內存占用只增不減。還沒有非常有效的辦法去避免這種情況的發生。不過我后來在ScopeAlloc的實現中發現BlockPool（是一個簡化版的內存池）反倒避免了這一缺陷。
注意
以上代碼屬于偽代碼（struct _FreeNode、_MemBlock編譯通不過），并且去除了出錯處理。
Footnotes
1. boost:pool/object_pool 中稱之為塊（Chunk）。
2. 是的，這是一種用戶內存需求的預測模型，其實std::vector的內存增長亦采用了該模型。