CppExplore

作者：CppExplore 地址：http://www.shnenglu.com/CppExplore/
2、定長內(nèi)存池。典型的實現(xiàn)有LOKI、BOOST。特點是為不同類型的數(shù)據(jù)結(jié)構(gòu)分別創(chuàng)建內(nèi)存池，需要內(nèi)存的時候從相應(yīng)的內(nèi)存池中申請內(nèi)存，優(yōu)點是可以在使用完畢立即把內(nèi)存歸還池中，可以更為細粒度的控制內(nèi)存塊。
    與變長的相比，這種類型的內(nèi)存池更加通用，另一方面對于大量不同的數(shù)據(jù)類型環(huán)境中，會浪費不少內(nèi)存。但一般系統(tǒng)主要的數(shù)據(jù)結(jié)構(gòu)都不會很多，并且都是重復(fù)申請釋放使用，這種情況下，定長內(nèi)存池的這點小缺點可以忽略了。
(1)Loki::SmallObject。Andrei Alexandrescu的《Modern C++ Design》第四章節(jié)已經(jīng)進行了詳細的描述，盡管和當(dāng)前的loki版本實現(xiàn)有出入，還是了解Loki::SmallObject的最佳文字講解，結(jié)合最新的loki源碼，足夠了。這里我再羅唆一下。先舉例看下使用：

#include "loki/SmallObj.h"
class Small:public  Loki::SmallObject<>//繼承SmallObject即可，所有都使用默認策略
{
public:
 Small(int data):data_(data){}
private:
 int data_;
};
int main()
{
 Small *obj=new Small(8);
 delete obj;
}

使用valgrind執(zhí)行可以證實new一個obj和多new幾次，申請的內(nèi)存都是4192。可以看出loki在使用層面非常簡單。
    loki的內(nèi)存池分4層,從低向上依次是chunk、FixedAllocator、SmallObjAllocator、SmallObject。
1）chunk：每個chunk管理一定數(shù)量（最大255，char型保存）的block，每個chunk中block的申請和釋放，時間復(fù)雜度都是o(1)，非常快，實現(xiàn)算法非常精巧，boost::pool中也是采用的相同算法。
    這里簡單說下這個算法：首次申請一塊連續(xù)內(nèi)存，pdata_指向該內(nèi)存基址，依據(jù)block大小，劃分成多個連續(xù)的block，每個block開頭的第一個字節(jié)保存該block的順序號，第一個是1，第二個是2，依次類推。另有一字節(jié)變量firstAvailableBlock_存儲上次分配出的block序號，開始是0。
    分配block：返回pdata_ +firstAvailableBlock_*blocksize，同時firstAvailableBlock_賦值為該塊的序列號。
    回收block：block指針假設(shè)為pblock，該塊序列號賦值為firstAvailableBlock_，firstAvailableBlock_賦值為（pblock-pdata_ ）/blocksize即可。
2）FixedAllocator：chunk中的block上限是255，不具有通用性，因此封裝了一層，稱為FixedAllocator，它保存了一個vector<chunk>，消除了單個chunk中block數(shù)目的上限限制。
   FixedAllocator中的block申請：FixedAllocator中保存活動的chunk（上次有空閑空間的chunk），申請block的時候如果活動chunk有空閑快，直接申請，否則掃描vector，時間復(fù)雜度o(N),同時更新活動chunk。
   FixedAllocator中的回收block：簡單想，給定block回收到FixedAllocator，自然要掃描vector，以確認block屬于哪個chunk，以便chunk回收。實際實現(xiàn)的時候，Loki針對應(yīng)用場景進行了優(yōu)化，一般使用都是批量使用，回收一般和申請順序相同或者相反，因此FixedAllocator保存上次回收block的chunk指針，每次回收優(yōu)先匹配這個chunk，匹配不上則以該chunk為中心，向兩側(cè)chunk順序檢測。
   FixedAllocator帶來的優(yōu)點：上文提到的消除了block的上限限制。另一方面，可以以chunk為單位，把內(nèi)存歸還給操作系統(tǒng)。實際實現(xiàn)中防止剛釋放的內(nèi)存立即又被申請，是存在兩個空閑chunk的時候才回收一個。這個特點，這里暫時歸結(jié)為優(yōu)點吧。實際使用中，回收多余內(nèi)存?zhèn)€人認為是個缺點，意義并不是很大。
   FixedAllocator帶來的缺點：很明顯，就是申請回收block的時間復(fù)雜度。
3）SmallObjAllocator：截至到FixedAllocator層面blocksize都是定長。因此封裝一層適用于任意長度的內(nèi)存申請。SmallObjAllocator保存了一個FixedAllocator的數(shù)組pool_，存儲擁有不同block長度的FixedAllocator。《Modern C++ Design》中描述該數(shù)組下標(biāo)和存儲的FixedAllocator的block長度無直接關(guān)系，從SmallObjAllocator申請以及回收block的時候二分查找找到對應(yīng)的FixedAllocator再調(diào)用相應(yīng)FixedAllocator的申請或者回收。當(dāng)前最新版本的loki，已經(jīng)拋棄了這種做法。當(dāng)前SmallObjAllocator的構(gòu)造函數(shù)有3個參數(shù)：chunksize，maxblocksize，alignsize。數(shù)組元素個數(shù)取maxblocksize除以alignsize的向上取整。每個FixedAllocator中實際的blocksize是（下標(biāo)＋1）*alignsize。
     SmallObjAllocator中block申請：依據(jù)block和alignsize的商直接取到數(shù)組pool_下標(biāo)，使用相應(yīng)的FixedAllocator申請。
     SmallObjAllocator中回收block：根據(jù)block和alignsize的商直接找到相應(yīng)的FixedAllocator回收。
     優(yōu)點：差異化各種長度的對象申請，增強了易用性。
     缺點：《Modern C++ Design》中描述增加掃描的時間復(fù)雜度，當(dāng)前版本的loki浪費內(nèi)存。這也是進一步封裝，屏蔽定長申請的細節(jié)，帶來的負面效應(yīng)。
4）SmallObject。暴露給外部使用的一層。該層面秉承了《Modern C++ Design》開始引入的以設(shè)計策略類為最終目的，讓用戶在編譯期選擇設(shè)計策略，而不是提供框架限制用戶的設(shè)計。這也是引入模版的一個層面。當(dāng)前版本SmallObject有6個模版參數(shù)，第一個是線程策略，緊接著的三個正好是SmallObjAllocator層面的三個構(gòu)造參數(shù)，下面的一個生存期策略，最后的是鎖方式。
    這里說下SmallObjAllocator層面的三個默認參數(shù)值，分別是4096，256，4。意味著SmallObjAllocator層面有數(shù)組（256+4-1)/4=64個，數(shù)組存儲的FixedAllocator中的chunksize一般都是4096（當(dāng)4096<=blocksize*255時候）字節(jié)（第一個chunk的申請推遲到首次使用的時候），各FixedAllocator中的chunk的blocksize依次是4、8......256，大于256字節(jié)的內(nèi)存申請交給系統(tǒng)的malooc/new管理，數(shù)組中FixedAllocator中單個chunk中的blocknum依次是4096/4=824>255取255、255......4096/256=16。如果這不能滿足需求，請調(diào)用的時候顯式賦值。
    當(dāng)前l(fā)oki提供了三種線程策略：

SingleThreaded	單線程
ObjectLevelLockable	對象級別，一個對象一個鎖
ClassLevelLockable	類級別，一個類一個鎖，該類的所有對象共用該鎖

目前只提供了一種鎖機制：Mutex
它的基類SmallObjectBase復(fù)寫了new/delete操作子，因此直接繼承SmallObject就可以象普通的類一樣new/delete，并且從內(nèi)存池分配內(nèi)存。
    SmalObject中block申請和釋放都從一個全局的SmallObjAllocator單例進行。
評價：chunk層面限制了上限個數(shù)，導(dǎo)致了FixedAllocator層面出現(xiàn)，造成申請回收時間復(fù)雜度的提高，而以chunk為單位回收內(nèi)存，在內(nèi)存池的使用場景下意義并不是很大。SmallObjAllocator為了差異化變長內(nèi)存的申請，對FixedAllocator進一步封裝，引入了內(nèi)存的浪費，不如去掉這個層面，直接提供給用戶層面定長的接口。另一方面，loki已經(jīng)進行了不少優(yōu)化，盡可能讓block申請釋放的時間復(fù)雜度在絕大多數(shù)情況下都是O(1),而SmallObjAllocator中內(nèi)存的浪費可以根據(jù)alignsize調(diào)整，即便是極端情況下，loki將chunk歸還給系統(tǒng)又被申請出來，根據(jù)chunk中block的最大值看，也比不使用內(nèi)存池的情況動態(tài)申請釋放內(nèi)存的次數(shù)減少了1/255。因此，loki是一個非常不錯的小巧的內(nèi)存池。