分析高效內(nèi)存池的實現(xiàn)方式

1. 內(nèi)存池的目的

  • 提高程序效率
  • 減少運行時間
  • 避免內(nèi)存碎片

為什么會產(chǎn)生內(nèi)存碎片曾棕?
1.內(nèi)部碎片是采用固定大小的內(nèi)存分區(qū),當(dāng)一個進程不能完全使用分配給它的固定內(nèi)存分區(qū)時,就會產(chǎn)生內(nèi)存碎片淹魄。
2.外部碎片是由于可分配的連續(xù)內(nèi)存太小,不能滿足任何進程的需求堡距,從而不能被進程使用甲锡。

再扯一個概念:段頁式內(nèi)存分配方式
將進程的內(nèi)存區(qū)域分成不同的段,段由多個固定大小的頁組成羽戒。那么通過頁表機制缤沦,段內(nèi)的頁就不需要存儲在同一塊內(nèi)存區(qū)域

段頁式內(nèi)存分配方式

默認(rèn)內(nèi)存管理
當(dāng)我們調(diào)用new在堆上分配一些內(nèi)存的時候易稠,系統(tǒng)收到了分配內(nèi)存的請求缸废,就會根據(jù)一定的算法在空閑內(nèi)存塊里尋找適合該內(nèi)存大小的內(nèi)存塊。如果內(nèi)存塊過大驶社,就會將內(nèi)存塊分割成適合的內(nèi)存塊企量。釋放內(nèi)存塊后,內(nèi)存塊就會重新被放入空閑內(nèi)存塊中亡电。默認(rèn)內(nèi)存管理里還用到了多線程的應(yīng)用届巩,每次分配和釋放內(nèi)存的時候都需要加鎖,這樣就損耗了性能逊抡。

可見姆泻,如果應(yīng)用程序頻繁地在堆上分配和釋放內(nèi)存,則會導(dǎo)致性能的損失冒嫡,并且會使系統(tǒng)中出現(xiàn)大量的內(nèi)存碎片拇勃,降低內(nèi)存的利用率

2. 內(nèi)存池的定義和分類

2.1 定義

顧名思義,我們在系統(tǒng)申請一塊適合的內(nèi)存作為內(nèi)存池孝凌,應(yīng)用程序?qū)?nèi)存的分配和釋放都在這個內(nèi)存池里實現(xiàn)方咆,只有當(dāng)內(nèi)存池不夠大需要動態(tài)擴增的時候才會調(diào)用系統(tǒng)的分配內(nèi)存函數(shù),其他時間對內(nèi)存的一切操作都是用應(yīng)用程序控制的蟀架。

2.2 分類

從線程安全角度看瓣赂,有多線程內(nèi)存池單線程內(nèi)存池
從內(nèi)存池可分配大小來看片拍,有固定大小內(nèi)存池(在這里的固定指的是每一次和系統(tǒng)申請的內(nèi)存的大小都是固定的煌集,而不是這個內(nèi)存池大小只能那么大)和可變內(nèi)存池

3. 固定內(nèi)存池

3.1 固定內(nèi)存池的簡要理解

固定內(nèi)存池由一系列固定大小的內(nèi)存塊組成,每一個內(nèi)存塊里又包含了固定數(shù)量和大小的內(nèi)存單元捌省。其實在內(nèi)存池初次生成的時候苫纤,我們只是向系統(tǒng)申請了一塊內(nèi)存塊,返回一個指針作為整個內(nèi)存池的頭指針。后面隨著內(nèi)存池的不斷擴大卷拘,我們通過指針將內(nèi)存池連接在一起喊废。

因為每一次系統(tǒng)都是分配固定大小的內(nèi)存,所以系統(tǒng)的分配效率高栗弟。

固定內(nèi)存池

固定內(nèi)存池就像一個鏈表一樣污筷,將內(nèi)存塊一個一個聯(lián)系到一起。
當(dāng)我們要需要一個內(nèi)存單元的時候乍赫,就會隨著鏈表去查看每一個內(nèi)存塊的頭信息瓣蛀,如果內(nèi)存塊里有空閑的內(nèi)存單元,將該地址返回耿焊,并且將頭信息里的空閑單元改成下一個空閑單元揪惦。
當(dāng)應(yīng)用程序釋放某內(nèi)存單元,就會到對應(yīng)的內(nèi)存塊的頭信息里修改該內(nèi)存單元為空閑單元罗侯。

3.2 固定內(nèi)存池的優(yōu)點(性能優(yōu)化方面)
  1. 內(nèi)存池中的內(nèi)存塊大小相等器腋,所以在分配的時候不需要太復(fù)雜的算法和多線程的保護,也減少了維護系統(tǒng)空閑內(nèi)存表的開銷钩杰。
  2. 單個內(nèi)存池塊是連續(xù)的內(nèi)存空間纫塌,提升了程序性能。
  3. 申請的內(nèi)存塊大小相等讲弄,有利于控制頁邊界對齊和內(nèi)存對齊措左。
3.3 固定內(nèi)存池的實現(xiàn)
3.3.1 MemoryPool和MemoryBlock聲明
class MemoryPool
{
private:
    MemoryBlock*   pBlock;
    USHORT          nUnitSize;
    USHORT          nInitSize;
    USHORT          nGrowSize;

public:
                     MemoryPool( USHORT nUnitSize,
                                  USHORT nInitSize = 1024,
                                  USHORT nGrowSize = 256 );
                    ~MemoryPool();

    void*           Alloc();
    void            Free( void* p );
};
struct MemoryBlock
{
    USHORT          nSize;
    USHORT          nFree;
    USHORT          nFirst;
    USHORT          nDummyAlign1;
    MemoryBlock*  pNext;
    char            aData[1];

    static void* operator new(size_t, USHORT nTypes, USHORT nUnitSize)
    {
        return ::operator new(sizeof(MemoryBlock) + nTypes * nUnitSize);
    }
    static void  operator delete(void *p, size_t)
    {
        ::operator delete (p);
    }

    MemoryBlock (USHORT nTypes = 1, USHORT nUnitSize = 0);
    ~MemoryBlock() {}
};
3.3.2 該內(nèi)存池總體機制的理解
  1. 有一個MemoryPool類作為內(nèi)存池,它擁有一個指向第一個MemoryBlock的頭指針避除。當(dāng)我們有許多內(nèi)存塊的時候怎披,一個內(nèi)存塊由pNext指針指向下一個內(nèi)存塊。

  2. 內(nèi)存塊由內(nèi)存塊結(jié)構(gòu)體與內(nèi)存單元構(gòu)成瓶摆,這些內(nèi)存單元的大小固定(在這里用nSize表示)凉逛,MemoryBlock結(jié)構(gòu)體不維護那些已經(jīng)分配的內(nèi)存單元的信息,它的nFree成員記錄未分配內(nèi)存單元的數(shù)量群井,nFirst記錄第一個未分配的內(nèi)存單元的編號状飞,每個內(nèi)存單元編號的前兩個字節(jié)記錄了緊跟它的下一個內(nèi)存單元的編號,這樣內(nèi)存單元就一個個被鏈接起來书斜。

  3. 當(dāng)有新的內(nèi)存請求時诬辈,內(nèi)存池會使用pBlock去遍歷內(nèi)存塊,查找內(nèi)存塊中nFree大于0的內(nèi)存塊荐吉,找到了對應(yīng)的內(nèi)存塊后焙糟,我們再根據(jù)nFirst找到第一個空閑的內(nèi)存單元,在返回這個內(nèi)存單元的地址之前样屠,將nFirst的值改為取到的內(nèi)存單元的前兩個字節(jié)的值(也就是它的下一個內(nèi)存單元)酬荞,再將nFree減1搓劫,最后才將剛才定位到的內(nèi)存地址返回給調(diào)用者。

  4. 如果現(xiàn)有內(nèi)存塊找不到空閑內(nèi)存單元混巧,MemoryPool就會從堆上申請分配一個內(nèi)存塊,立即進行初始化(nSize為所有內(nèi)存單元的大小勤揩,nFree為n-1咧党,因為立馬要分配一個空閑單元,所以就先減1陨亡,nFirst為1傍衡,因為為0的馬上就要分配出去了),MemoryBlock的構(gòu)造函數(shù)主要的作用是將編號為0之后的內(nèi)存單元鏈接在一起负蠕。因為每個內(nèi)存單元大小固定(為MemoryPool的nUnitSize)蛙埂,所以要定位到內(nèi)存單元就通過它的頭兩位與內(nèi)存單元大小的乘積作為偏移值進行定位。那么定位要從哪個地方開始呢遮糖?思考一下我們的aData[1]的作用绣的,它是MemoryBlock結(jié)構(gòu)體的最后一個字節(jié)。所以實質(zhì)上欲账,MemoryBlock結(jié)構(gòu)體的最后一個字節(jié)也用做被分配出去的分配單元的一部分屡江。因為整個內(nèi)存塊由MemoryBlock結(jié)構(gòu)體和整數(shù)個分配單元組成,這意味著內(nèi)存塊的最后一個字節(jié)會被浪費赛不。所以我們可以從aData[1]的位置開始惩嘉,每個nUnitSize大小取其頭兩字節(jié),記錄它后面自由單元的序號踢故。因為剛開始所有分配單元都是自由的文黎,所以這個編號就是自身編號加1,即位置上緊跟其后的單元的編號殿较。

  5. 當(dāng)內(nèi)存被釋放的時候耸峭,內(nèi)存重新回到內(nèi)存池。MemoryPool根據(jù)內(nèi)存單元的地址遍歷所有內(nèi)存塊斜脂,判斷該內(nèi)存單元是否在內(nèi)存塊的范圍內(nèi)抓艳。注意重新加回去的時候,MemoryBlock的nFree+1帚戳,nFirst可能會改變玷或。如果這個內(nèi)存塊內(nèi)都是空閑的,那么就會將它返回給堆片任。因為這個內(nèi)存單元被放入內(nèi)存塊偏友,那么證明這個內(nèi)存塊一定有空閑空間,所以我們將頭指針指向該內(nèi)存塊对供,方便下一次查找位他。

3.3.3 細(xì)節(jié)剖析
MemoryPool的構(gòu)造函數(shù)

每個分配單元在自由狀態(tài)時氛濒,其頭兩個字節(jié)用來存放"其下一個自由分配單元的編號"。即每個分配單元"最少"有"兩個字節(jié)"鹅髓,這就是⑤處賦值的原因舞竿。④處是將大于4個字節(jié)的大小_nUnitSize往上"取整到"大于nUnitSize的最小的MEMPOOL ALIGNMENT的倍數(shù)(前提是MEMPOOL_ALIGNMENT為2的倍數(shù))。如_nUnitSize為11時窿冯,MEMPOOL_ALIGNMENT為8骗奖,nUnitSize為16;MEMPOOL_ALIGNMENT為4醒串,nUnitSize為12执桌;

當(dāng)向MemoryPool提出內(nèi)存請求時

void* MemoryPool::Alloc()
{
    if ( !pBlock )           //1
    {
            ……                          
    }

    MemoryBlock* pMyBlock = pBlock;
    while (pMyBlock && !pMyBlock->nFree )//2
        pMyBlock = pMyBlock->pNext;

    if ( pMyBlock )         //3
    {
        char* pFree = pMyBlock->aData+(pMyBlock->nFirst*nUnitSize);         
        pMyBlock->nFirst = *((USHORT*)pFree);
                            
        pMyBlock->nFree--;  
        return (void*)pFree;
    }
    else                    //4
    {
        if ( !nGrowSize )
            return NULL;

        pMyBlock = new(nGrowSize, nUnitSize) FixedMemBlock(nGrowSize, nUnitSize);
        if ( !pMyBlock )
            return NULL;

        pMyBlock->pNext = pBlock;
        pBlock = pMyBlock;

        return (void*)(pMyBlock->aData);
    }

}

MemoryPool回收內(nèi)存時

void MemoryPool::Free( void* pFree )
{
    ……

    MemoryBlock* pMyBlock = pBlock;

    while ( ((ULONG)pMyBlock->aData > (ULONG)pFree) ||
         ((ULONG)pFree >= ((ULONG)pMyBlock->aData + pMyBlock->nSize)) )//1
    {
         ……
    }

    pMyBlock->nFree++;                    //2
    *((USHORT*)pFree) = pMyBlock->nFirst;  //3
    pMyBlock->nFirst = (USHORT)(((ULONG)pFree-(ULONG)(pBlock->aData)) / nUnitSize);//4

    if (pMyBlock->nFree*nUnitSize == pMyBlock->nSize )//5
    {
        ……
    }
    else
    {
        ……
    }
}

一個分配單元的內(nèi)存地址無論是在分配后,還是處于自由狀態(tài)時芜赌,一直都不會變化仰挣。變化的只是其狀態(tài)(已分配/自由),以及當(dāng)其處于自由狀態(tài)時在自由分配單元鏈表中的位置缠沈。

參考:
內(nèi)存池技術(shù)介紹(圖文并茂膘壶,非常清楚)
C++ 實現(xiàn)高性能內(nèi)存池
極高效內(nèi)存池實現(xiàn) (cpu-cache)
固定大小塊的內(nèi)存池設(shè)計

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市博烂,隨后出現(xiàn)的幾起案子香椎,更是在濱河造成了極大的恐慌,老刑警劉巖禽篱,帶你破解...
    沈念sama閱讀 218,122評論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件畜伐,死亡現(xiàn)場離奇詭異,居然都是意外死亡躺率,警方通過查閱死者的電腦和手機玛界,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,070評論 3 395
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來悼吱,“玉大人慎框,你說我怎么就攤上這事『筇恚” “怎么了笨枯?”我有些...
    開封第一講書人閱讀 164,491評論 0 354
  • 文/不壞的土叔 我叫張陵,是天一觀的道長遇西。 經(jīng)常有香客問我馅精,道長,這世上最難降的妖魔是什么粱檀? 我笑而不...
    開封第一講書人閱讀 58,636評論 1 293
  • 正文 為了忘掉前任洲敢,我火速辦了婚禮,結(jié)果婚禮上茄蚯,老公的妹妹穿的比我還像新娘压彭。我一直安慰自己睦优,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 67,676評論 6 392
  • 文/花漫 我一把揭開白布壮不。 她就那樣靜靜地躺著汗盘,像睡著了一般。 火紅的嫁衣襯著肌膚如雪忆畅。 梳的紋絲不亂的頭發(fā)上衡未,一...
    開封第一講書人閱讀 51,541評論 1 305
  • 那天,我揣著相機與錄音家凯,去河邊找鬼。 笑死如失,一個胖子當(dāng)著我的面吹牛绊诲,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播褪贵,決...
    沈念sama閱讀 40,292評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼掂之,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了脆丁?” 一聲冷哼從身側(cè)響起世舰,我...
    開封第一講書人閱讀 39,211評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎槽卫,沒想到半個月后跟压,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,655評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡歼培,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,846評論 3 336
  • 正文 我和宋清朗相戀三年震蒋,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片躲庄。...
    茶點故事閱讀 39,965評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡查剖,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出噪窘,到底是詐尸還是另有隱情笋庄,我是刑警寧澤,帶...
    沈念sama閱讀 35,684評論 5 347
  • 正文 年R本政府宣布倔监,位于F島的核電站直砂,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏丐枉。R本人自食惡果不足惜哆键,卻給世界環(huán)境...
    茶點故事閱讀 41,295評論 3 329
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望瘦锹。 院中可真熱鬧籍嘹,春花似錦闪盔、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,894評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至颂碘,卻和暖如春异赫,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背头岔。 一陣腳步聲響...
    開封第一講書人閱讀 33,012評論 1 269
  • 我被黑心中介騙來泰國打工塔拳, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人峡竣。 一個月前我還...
    沈念sama閱讀 48,126評論 3 370
  • 正文 我出身青樓靠抑,卻偏偏與公主長得像,于是被迫代替她去往敵國和親适掰。 傳聞我的和親對象是個殘疾皇子颂碧,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,914評論 2 355

推薦閱讀更多精彩內(nèi)容