CppExplore

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

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

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

SingleThreaded	單線程
ObjectLevelLockable	對(duì)象級(jí)別，一個(gè)對(duì)象一個(gè)鎖
ClassLevelLockable	類級(jí)別，一個(gè)類一個(gè)鎖，該類的所有對(duì)象共用該鎖

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