基于C++的高效內存池的設計與實現

鄢 濤, 于 曦, 劉永紅, 趙衛東, 余 悅, 曾 誼

(1.成都大學 信息科學與工程學院, 四川 成都 610106;2.成都大學 模式識別與智能信息處理四川省高校重點實驗室, 四川 成都 610106)

基于C++的高效內存池的設計與實現

鄢 濤1,2, 于 曦1,2, 劉永紅1,2, 趙衛東1,2, 余 悅1, 曾 誼1

(1.成都大學 信息科學與工程學院, 四川 成都 610106;2.成都大學 模式識別與智能信息處理四川省高校重點實驗室, 四川 成都 610106)

為了高效、安全地利用計算機內存資源，在大型的軟件設計中，往往要進行大量的內存分配與回收操作，為此，C++專門提供了malloc等相關函數進行操作，這些函數能夠滿足一般的使用，但由于它們調用了操作系統API，所以實際使用時會在操作系統中產生大量的內存碎片，讓內存分配成為效率瓶頸，從而降低系統性能.基于此，通過對循環首次適應算法進行改進，設計并實現了基于C++的高效內存池，大幅提升了內存分配與回收的效率.同時,還為內存池編寫了相關的分配子，使其能與C++標準庫無縫對接，提供了若干具有垃圾回收功能的智能指針，提高了內存管理與程序運行的效率.

內存池；內存分配；循環首次適應算法；高效策略

0 引 言

大型的計算機軟件應用中，往往需要進行大量的內存分配與回收工作，這些工作可以通過各種內存分配函數來完成，比如C語言的malloc.但由于操作系統在分配內存時，需要進行大量的查找工作，所以使用如malloc來分配內存實際上是比較低效的.不僅如此，由于分配算法本身的問題，多次的內存分配/回收還會產生大量系統級別的內存碎片，進而降低內存的利用率.針對這些問題，內存池將會是一個很好的解決方案，內存池實際上是一種緩沖的機制，它一次性申請大量內存，以后每當有內存分配請求時，不再調用malloc這樣的函數，而是在內存池中尋找一片合適的區域來使用.

目前，基于C++的內存池設計與實現有不少方案，其中最為優秀的當屬準標準庫Boost提供的boost::pool和boost::object-pool，前者用于儲存各種基本數據，后者用來儲存各種類的實例對象.Boost是一個重量級的庫，安裝和配置非常繁瑣，雖然boost::pool在分配指定大小的內存時很高效，但是在分配任意大小的內存時，卻顯得比較笨拙.在某些應用場景下，boost中的內存池不能完美滿足開發的需求.基于此，本研究設計并實現了一款高性能且輕量級的內存池.比起已有的研究成果，本研究的最終方案不僅擁有讓使用者滿意的分配效率，而且還能提供很多方便開發者利用的內存池輔助工具.

1 數據結構設計

1.1 內存池對象設計

內存池對象的設計要解決的首要問題就是內存池類的維護和管理，具體為：首先需要提供至少2個接口：allocate和deallocate，分別負責內存分配與回收工作；然后是內存資源的維護，大多數內存池的實現都會采用鏈表，有所不同的是本研究所維護的鏈表的基本結點并不是內存，而是“內存池結點對象"，這些結點又各自維護著自己的內存塊.采用這種模式，能最大限度地減小內存池各個組件之間的耦合性.

由于內存池的創建和銷毀都需要消耗大量的資源，所以不妨在這個設計中利用單例模式來防止用戶創建過多的內存池對象.單例模式是一種最簡單的設計模式，只需要把構造/析構函數設置為私有，然后提供一個靜態函數作為接口即可.此外，還需要若干個成員變量，分別表示鏈表頭、鏈表尾、當前結點等.內存池類的簽名如下，

class memPool final

{

public:

void *allocate(size-t);

bool deallocate(void *);

static memPool& memPool();

private:

memPool();

～memPool();

memNode *currentNode;

memNode *lastNode;

memNode *firstNode;

};

這個類禁止被繼承，所以需使用final修飾，同時，為了保證最多只有1個實例，還需要禁用拷貝構造函數和賦值運算符.

這樣的設計非常簡潔，在不影響內存池功能的情況下，最大程度地簡化了對外接口，用戶能很輕松使用這個內存池.

1.2 內存池結點設計

內存池維護一個“內存池結點”的鏈表，每到分配內存時，便通過某種算法，找到1個合適的結點，然后讓結點來執行分配操作，所以結點類依然要有allocate和deallocate 2個接口.內存池結點的簽名為，

struct memPool::memNode

{

explicit memNode(size-t);

～memNode();

void* allocate(size-t s);

void deallocate(void *);

memNode *next;

void *block;

};

內存池結點類是內存池類的內部結構體，不能被外部所實例化.

這樣設計內存池結點的好處在于，把實際的內存分配工作下發給各個結點，而不由內存池親自完成，降低了內存池和結點之間的耦合度，同時提高了代碼的可讀性.

2 分配算法的實現

2.1 結點的分配與回收算法

2.1.1 結點的分配與回收.

內存池結點并不直接與外界打交道，只負責處理來自內存池對象的分配/回收請求，即：當1個結點被請求分配內存時，它被內存池認為是當前最合適的選擇，接著它會嘗試從自己維護的內存區段中尋找一片合適的內存分區并將其分割，然后返回結果，如果不能找到合適的，則返回NULL.

結點所維護的內存區段被分為若干個不同的塊，每個塊由塊頭、塊尾及中間區域3部分組成.塊頭和塊尾標記這塊內存是否可以被分配，以及這塊內存的大小，而中間的區域則是可以被外界所使用的.

2.1.2 結點的分配算法.

內存分配算法中，目前比較通用的是循環首次適應算法，該算法在分配內存空間時，從上次找到空閑區的下1個空閑分區開始查找，直到找到第1個能滿足要求的空閑區為止，并從中劃出一塊與請求大小相等的內存空間分配給作業.該算法能使內存中的空閑區分布得較均勻，但這樣會缺少大的空閑分區.

本研究內存分配算法是對循環首次適應算法的改進，主要改進的地方為把內存分區的連接方式從鏈表改為了線性表.比起傳統的算法，雖然改進后的算法失去了一些優點，但以下的優點卻讓它更適合內存池：回收內存時只需修改標記即可，不需要查找任何表，只消耗常量時間；回收內存后可以很容易地合并空閑分區，這在一定程度上克服了原算法缺少較大的空閑分區的問題；比起鏈表，線性表需要更少的布局成本，能讓更多的內存被用戶使用，而不是用作系統保留.

本算法的思路為：從第1個結點開始，依次檢索結點中的空閑分區，直到找到1個合適大小的分區為止；若在某個結點中，無法找到合適的結點，則嘗試下1個結點，若所有結點都已經試過，則增加1個新的結點，或者直接返回錯誤信息；若能找到合適的區域，則檢查該區域是否“足夠大”.本分配算法的代碼為，

if (*blockSize- need - 2 * infoSize

{

*i = false;/*i指向“塊頭"*/

*(i + * blockSize - infoSize) = false;/*塊尾*/

this->available -= * blockSize - 2 * infoSize;/*可

用部分減少*/

return i+infoSize;/*infoSize是“塊頭”相對可用區域的偏

移*/

}

else

{

size-t oldSize = *temp;

*i = false;

*(i + 1) = need + 2 * infoSize;/*由于有分割，所以

要重設大小*/

j += need + infoSize;

*j= false;

*(j + 1) = need + 2 * infoSize;/*設置塊尾*/

j += infoSize;

*j = true;/*分割出的新塊的塊頭*/

*(j + 1) = oldSize - (need + 2 * infoSize);

*(i + oldSize - infoSize) = true;/*分割出的新塊的塊

尾*/

*(i + oldSize - infoSize + 1) = oldSize - (need + 2 *

infoSize);

available -= need + 2 * infoSize;

return i+infoSize;

}

2.1.3 結點的回收算法.

比起分配算法，結點的回收算法則要簡單得多，只需要把塊頭塊尾的標記從false改為true即可.

需要注意的是，在分配算法中，可能會導致一個內存區段中有越來越多的內存塊，太多內存塊顯然是不利于分配的，所以在內存回收時應該嘗試合并這些內存塊.在回收的時候，首先檢查塊頭的標記是否為false，如果不是，說明這塊內存已經遭到破壞，屬于嚴重錯誤，此時應該調用abort函數立即終止程序.

合并內存塊分為2步：向前檢索和向后檢索，即分別檢查前面與后面緊鄰的內存塊是否空閑，如果是則將它們合并，其代碼為，

size-t prevSize=0,nextSize=0;

if (flag != start&&*(flag - infoSize)) /*如果前方有內存塊

并且可用*/

prevSize = *(flag - sizeof(size-t));

if ((flag + tempSize)!= end&&*(flag + tempSize))

nextSize = *(flag + tempSize + sizeof(bool));

*(flag - prevSize)=true;

*(flag - prevSize + sizeof(bool)) = blockSize+ prevSize +

nextSize;/*合并后的大小*/

*(flag + tempSize + nextSize - infoSize) = true;

*(flag + nextSize + tempSize - sizeof(size-t)) = tempSize +

prevSize + nextSize;

2.2 內存池的分配與回收算法

2.2.1 內存池的分配算法.

內存池需要完成的工作是尋找一個合適的結點，并調用結點的分配算法.如果找不到合適的結點還需要額外申請空間以滿足需求；如果請求的分配大小大于單個結點所能提供的最大值，則直接返回NULL以表示分配失敗.

和結點類似，內存池對象也采用循環首次適應算法，它保存著下一次分配內存的最佳起始位置，然后依次搜索，直到分配成功或者決定新增一片內存為止，代碼為，

memNode *temp = currentNode;

for (;;)

{

temp = getNext(temp);

if (temp->available >=need+ 2 * (currentNode->

infoSize))

{

currentNode = getNext(currentNode);

result = temp->allocate(need);

if (result != nullptr)

break;

}

if (temp == currentNode)

{

lastNode->next = new memNode(nodeSize);

lastNode = lastNode->next;

result = lastNode->allocate(need);

currentNode = lastNode;

currentNodeNum++;

break;

}

}

其中，getNext函數的作用是尋找下一個結點.

2.2.2 內存池的回收算法.

而內存池的回收算法更加簡單，只需要遍歷鏈表，判斷需要回收的指針屬于哪個結點即可，由于鏈表通常不會有太多結點，因此回收算法甚至可以認為是一個O(1)的操作，代碼為，

memNode *temp=firstNode;

if (ptr == NULL)/*處理NULL的情況*/

return;

for (;temp!=NULL;temp=temp->next)

if(ptr>=temp->block&&ptrblock+temp->

size)

temp->deallocate(ptr);

3 分配子的實現

C++標準庫中，最重要的一部分是STL，STL提供了大量的高性能的容器.這些容器通常擁有自動管理內存的功能.默認情況下，它們使用new和delete來分配內存.然而，STL是一款設計精良的產品，組件之間耦合度極低，甚至低到可以由用戶單獨定制內存分配的方式，而用戶指定內存分配規則的關鍵，就在于分配子.

實際上，C++標準明確規定了一個合格的分配子應該有哪些成員，編寫一個分配子也并不復雜，而需要關心的只有負責內存分配/釋放的allocate和deallocate.allocate的全部代碼為，

pointer allocate(size-type n, const-pointer = 0)

{

void* p = pool.allocate(n*sizeof(value-type));/*從內

存池獲取內存*/

if (!p)

throw std::bad-alloc();

return (pointer)p;

}

其中，pool是一個memPool的引用，在分配子的構造函數中被初始化.

deallocate的編寫十分簡單，調用pool的相關函數即可，

void deallocate(pointer p, size-type)

{

pool.deallocate(p);

}

當然，一個分配子不止這么簡單，只是剩余部分都可以參考默認的分配子的實現，直接拷貝，而不需要額外編寫.

4 智能指針的實現

事實上，從內存池中獲取內存都需要遵循“有借有還”的原則，即分配內存后必須顯式釋放它，這需要用戶手動編寫釋放內存的代碼，這顯然是很麻煩的.

C++標準庫中有一種名叫智能指針的類，它擁有和普通指針類似的行為，但是卻能在離開作用域時自動釋放內存.受此啟發，本研究專門為內存池打造了相關的智能指針.

首先是指向緩沖區的智能指針，這類智能指針可以當成動態數組來使用，其類的簽名如下，

class poolPtr

{

public:

explicit poolPtr(size-t);

virtual ～poolPtr();

void reset(size-t);

void *get();

protected:

void *ptr;

AMemPool &pool;

};

通過get函數可以獲得原始指針，通過reset可以重設緩沖區的大小.相關函數的實現比較容易，所以這里不再贅述.

為了能讓智能指針指向各種類的對象，還需要設計一款objectPtr，它派生自poolPtr：

template

class objectPtr :protected poolPtr

{

public:

objectPtr()

virtual ～objectPtr();

T *get();

T *operator->();

T &operator*();

};

該實現是在poolPtr的基礎上增加了一些操作符而已，這些操作符底層調用父類的相關操作.需要注意的是，繼承方式是protected而不是public，這么做是為了禁用reset函數.

5 性能測試與改進

為了測試本內存池算法的性能，本研究編寫了相關代碼用于測試，其代碼為，

const int loopCount = 10000000;

const int blockSize = 10;

memPool::iniPool(1, 1000 * 1024 * 1024);/*結點數量應盡

量少*/

memPool &pool = memPool::getMemPool();

std::vector> s(loopCount);

/*使用內存池的分配子*/

for (int i = 0; i < loopCount; i++)

s[i] = pool.allocate(blockSize);

for (int i = 0; i < loopCount; i++)

pool.deallocate(s[i]);

for (int i = 0; i < loopCount; i++)

s[i] = malloc(blockSize);

for (int i = 0; i < loopCount; i++)

free(s[i]);

上述程序用于對自定義函數庫和系統函數庫進行1 000萬次內存分配和回收運算進行比較測試.利用Visual Studio提供的性能分析工具，可以看出效率差距，測試結果如圖1所示.

圖1 1 000萬次內存分配與回收性能報告

在整個程序的運行時間中，內存池的所有相關操作僅僅占了10.97%，剩下的時間用于malloc/free以及其他的一些占用時間不長的函數.

事實上，Visual Studio所提供的性能分析工具非常專業和精準，根據這個測試結果可見，本研究設計的內存池擁有相當好的性能表現.

6 結 論

本研究對循環首次適應算法進行了改進，設計并實現了基于C++的高效內存池及一系列的輔助工具,封裝成了可分發重用的類庫，能夠進行分發和復用.實際測試表明，通過該內存池使用策略來做內存分配/回收的工作，其效率遠高于直接調用內存分配/回收的函數.該內存池最大的優點在于它可以和標準庫相配合，保證了它的實用性.不僅如此，與內存池配套的智能指針也大大減少了手動管理內存的工作量，大幅度提升了使用者的工作效率和程序的運行效率.

[1]劉磊.Linux內核內存池實現研究[J].科學技術與工程,2007,7(12):2849-2851.

[2]吳捷,陶志榮.一種自適應變長塊內存池SVBSMP[J].計算機應用,2008,28(S1):280-283.

[3]余俊良,楊正益.基于虛擬單元可智能增長的內存池研究[J].計算機工程與應用,2014,50(16):127-130.

[4]許健,于鴻洋.一種Linux多線程應用下內存池的設計與實現[J].電子技術應用,2012,38(11):146-149.

[5]馬紅斌,張峰,付華楷,等.嵌入式系統高效內存池的實現方法:CN 101968772 B[P].2011-02-09.

[6]Wang N,Liu X,He J,et al.Collaborativememorypoolinclustersystem[C]//InternationalConferenceonParallelProcessing，2007.Xi'an,China:IEEE Press,2007.

[7]Wang X M, Wang Z.DesignandimplementationofmemorypoolsforembeddedDSP[C]//InternationalConferenceonComputerScienceandSoftwareEngineering,CSSE2008.Wuhan,China：IEEE Press,2008:160-164.

[8]侯捷.STL源碼剖析[M].武漢:華中科技大學出版社,2002.

[9]Bryant R E.深入理解計算機系統[M].龔奕利,賀蓮,譯.北京:機械工業出版社,2016.

Abstract:In the development of large scale software,memory allocation and reclaiming usually occur for efficiency and safety.Therefore,C++ provides special functions for this,such as malloc,etc.These functions can meet the demands of common users.However,these functions call API,so the actual use of these functions produce massive memory fragments in OS and result in the efficiency bottleneck of memory allocation which lowers the system performance.This paper has improved next-fit algorithm and designed a memory pool with efficient strategies based on C++.The strategies could extremely upgrade the efficiency of memory allocation and reclaiming.Meanwhile,for the perfect connection of memory pool with C++ standard library,the strategies provide relevant allocators for memory pool.In addition,there are a number of smart pointers which have the function of garbage collection.They can free users from complex and fallible memory management,and improve the efficiency of the program.

Keywords:memory pool;memory allocation;next-fit algorithm;efficient strategy

DesignandImplementationofEfficientMemoryPoolBasedonC++

YANTao1,2,YUXi1,2,LIUYonghong1,2,ZHAOWeidong1,2,YUYue1,ZENGYi1

(1.School of Information Science and Engineering, Chengdu University, Chengdu 610106, China;2.Key Laboratory of Pattern Recognition and Intelligent Information Processing, Chengdu University, Chengdu 610106, China)

TP311.11

A

1004-5422(2017)03-0257-05

2017-08-12.

四川省科技廳軟件科學研究計劃(2017ZR0198)、 四川省科技廳應用基礎計劃(2016JY0255)資助項目.

鄢 濤(1973 — )， 男， 碩士， 副教授， 從事計算機軟件工程研究.