一.XXX
1)概念說明
這里不再具體描述內(nèi)存池的概念和作用,需要了解請看http://baike.baidu.com/view/2659852.htm?fr=ala0_1_1。
2)描述
在開發(fā)一個長時間運行的服務(wù)器程序時，一般頻繁的向操作系統(tǒng)動態(tài)申請內(nèi)存，而采用堆new分配,速度較慢，而且如果一個程序頻繁的申請小內(nèi)存塊，很容易產(chǎn)生內(nèi)存碎片，每次查找相對較慢。
因為堆是向高地址擴展的數(shù)據(jù)結(jié)構(gòu),每次內(nèi)存分配其實都是進行虛擬內(nèi)存分配，都會建立虛擬內(nèi)存的到物理內(nèi)存的映射,而是分配的一種不連續(xù)的內(nèi)存區(qū)域,由于系統(tǒng)是用鏈表來存儲的空閑內(nèi)存地址的，而鏈表的遍歷方向是由低地址向高地址。
這里還有一篇關(guān)于關(guān)于頻繁的內(nèi)存分配性能分析 ，圖文并茂的講得很詳細。
3)實現(xiàn)目標.
而設(shè)計內(nèi)存池的目的是為了保證一個程序長時間高效的運行，而該程序?qū)?nèi)存申請頻繁，為了減少系統(tǒng)內(nèi)存碎片的產(chǎn)生，合理分配管理用戶內(nèi)存，從而減少系統(tǒng)中出現(xiàn)有效空間足夠，而無法分配大塊連續(xù)內(nèi)存的情況。
關(guān)于實現(xiàn)一個高效與穩(wěn)定內(nèi)存池模塊有如下目標:
A.如何實現(xiàn)內(nèi)存的快速分配
B.如何實現(xiàn)內(nèi)存的快速釋放
C.如何管理內(nèi)存池的穩(wěn)定與效率.
注：本文介紹的內(nèi)存池管理效率相對較高，且可以針對任意大小內(nèi)存分配....
二.設(shè)計
設(shè)計前我們假設(shè)內(nèi)存申請很頻繁，而且申請小于在5120byte的遠遠大于5120byte字節(jié)。
為了讓設(shè)計的內(nèi)存池的使用更具有通用型和高效性，這里大致介紹通過需求不同指定一種基于內(nèi)存需求策略的方式設(shè)計出一種內(nèi)存池。
及小于5120字節(jié)的采用小塊內(nèi)存分配，大于5120的通過操作系統(tǒng)分配，內(nèi)存池管理.
此內(nèi)存池包括2中分配方式，介紹分配如下:
1) 個數(shù)固定的不定長的靜態(tài)內(nèi)存分配(BlockPool)。
A.設(shè)計思路
這種主要是根據(jù)程序中不同對象的大小而指定的一種策略，對于每一種大小又是通過一個鏈表鏈表管理，每個鏈表的節(jié)點的內(nèi)存大小不同，而為了方便內(nèi)存的管理，一般在程序初始化的時候針對不同的策略大小分配一塊內(nèi)存塊，然后把此內(nèi)存塊劃分為多個節(jié)點保存到鏈表中,每一個鏈表中保存的將是空閑的節(jié)點。
B.基本數(shù)據(jù)結(jié)構(gòu)
基本數(shù)據(jù)結(jié)構(gòu)：
/**//// 指定的策略 enum eBuff_Type
{
eBT_32 =0,
eBT_64,
eBT_128,
eBT_256,
eBT_512,
eBT_1024,
eBT_2048,
eBT_5120,
eBT_END,
}; /// 定一個雙向鏈表的節(jié)點2個指針
/**////
/// file BaseNode.h
/// brief 一個雙向鏈表需要的前后指針節(jié)點
///
#pragma once
template < typename T >
class CNode
{
typedef T Node;
public:
Node* next;
Node* prev;
CNode()
{
next = prev = NULL;
}
};
/**//// 節(jié)點struct Buffer: CNode<Buffer>
{
eBuff_Type type;
};
/// 不同大小的數(shù)據(jù)節(jié)點.
struct Buffer32 : Buffer { char buf[32]; };
struct Buffer64 : Buffer { char buf[64]; };
struct Buffer128 : Buffer { char buf[128]; };
struct Buffer256 : Buffer { char buf[256]; };
struct Buffer512 : Buffer { char buf[512]; };
struct Buffer1024: Buffer { char buf[1024]; };
struct Buffer2048: Buffer { char buf[2048]; };
struct Buffer5120: Buffer { char buf[5120]; };
/**////TlinkedList為一個鏈表
///這里包括eBT_END數(shù)組TlinkedList<Buffer> m_MemPool[eBT_END];
m_MemPool主要結(jié)構(gòu)圖如下:
C.性能分析
分配
這里策略只是針對小于eBT_5120Byte的內(nèi)存進行分配,根據(jù)傳入的大小直接Hash利用m_MemPool[idx]返回鏈表頭,返回Buffer節(jié)點的buf數(shù)據(jù)塊。
釋放：根據(jù)傳入要釋放的Mem內(nèi)存地址
/**//// 獲得偏移地址Buffer* buf = (Buffer_Face*)( (char*)Mem - offsetof(Buffer_Face,buf) );
通過偏移地址即可獲得buf的地址，buf里面包括type獲得m_MemPool的索引，然后把釋放的節(jié)點重新Push到m_MemPool[type]中。
性能: 插入,分配都是0(1)
2) 完全動態(tài)分配內(nèi)存(HeapPool)。
介紹了上面的靜態(tài)內(nèi)存分配，其實是在利用已經(jīng)分配好了的內(nèi)存塊里面在進行查找，釋放也是直接根據(jù)傳入的直接直接保存到緩存表中。
A.介紹下需要的基本數(shù)據(jù)結(jié)構(gòu)
struct listNode : CNode<listNode>
{
long size;
/**//// 指向的內(nèi)存
char* ptr;
};
struct HeapNode
{
/**//// memory request rate
__int64 m_Count;
/**//// all free memory list
TlinkedList<listNode> m_FreeList;
/**//// using memory list
TlinkedList<listNode> m_Used;
HeapNode( )
{
m_Count = 0 ;
m_FreeList.ReleaseList();
m_Used.ReleaseList();
}
};
typedef std::map<unsigned long,HeapNode* > MHEAPLIST; /// 其中map的key是分配的大小。
HeapNode的結(jié)構(gòu)圖如下:
B.設(shè)計思路
根據(jù)策略程序一般大于5120Byte字節(jié)的相對比較少，而程序請求大小也是相對比較規(guī)則，散列不是太大。
HeapNode有2個鏈表m_FreeList和m_Used，其中鏈表的節(jié)點如圖ListNode所示
listNode有一個ptr表示需要配的內(nèi)存，ptr指向的前8個地址為listnode的地址值（根據(jù)Cpu的最大尋址為64位），ptr+8則是分配的內(nèi)存地址,為什么這么設(shè)計呢？
我是這樣想的外界使用內(nèi)存空間為data區(qū)域，那么我們釋放的時候的只是需要傳入data的地址，即可通過求出listnode的地址，
/**//// 根據(jù)MemAddr的地址求listnode地址__int64 pAddr = *(__int64*)((char*)MemAddr-8);
listNode* pNode = (listNode*)pAddr;
得到listNode地址后即可進行找到對應(yīng)的HeapNode，然后進行釋放或者放入緩存列表的操作。
關(guān)于HeapNode的管理，為了節(jié)約內(nèi)存我們不可能一直申請內(nèi)存而不釋放，所以我們約定m_FreeList只是保存m_Used中一半大小的結(jié)點。當m_FreeList過多的節(jié)點時需要釋放一定空間。(這個約定可以根據(jù)不同的需求而制定).
上面介紹了為什么如此的設(shè)計這個數(shù)據(jù)結(jié)構(gòu)，下面介紹分配策略。分配的時候先查找是否有緩存數(shù)據(jù)，沒有則分配一個，否則直接返回m_FreeList的一個listNode(結(jié)點)的ptr+8;
C.性能分析
通過上面描述可以確定基于完全動態(tài)分配的效率
分配的時候 lg(n);
釋放的時候 lg(n);
而map的查找基于AVL樹，所以查找基本是常量型的。
三.實現(xiàn)
上面只是介紹了分配方式，下面介紹實現(xiàn)。
通過上面描述可知，對于大于5120byte的內(nèi)存分配采用HeapPool分配，否則采用BlockPool分配。
為了方便外界使用我們使用一個CMemFactory內(nèi)存分配工廠，通過使用者申請Size和釋放pAddr即可快速進行分配和釋放。
代碼如下：
http://code.google.com/p/tpgame/source/browse/#svn/trunk/MemPool/MemPool
具體代碼打包如下:
/Files/expter/Pool.rar
注：如需了解跟多的內(nèi)存池是實現(xiàn)可以閱讀STL SGI, Loki, Boost內(nèi)存池的實現(xiàn)...
附帶最新內(nèi)存池，實現(xiàn)和介紹...
http://www.shnenglu.com/expter/archive/2011/01/18/138787.html